#region License Information
/* HeuristicLab
* Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
*
* This file is part of HeuristicLab.
*
* HeuristicLab is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* HeuristicLab is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with HeuristicLab. If not, see .
*/
#endregion
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Threading;
using Google.OrTools.LinearSolver;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Optimization;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
namespace HeuristicLab.ExactOptimization.LinearProgramming {
[StorableClass]
public class LinearSolver : ParameterizedNamedItem, ILinearSolver, IDisposable {
[Storable]
protected IValueParameter> problemTypeParam;
protected Solver solver;
[Storable]
protected IFixedValueParameter solverSpecificParametersParam;
public LinearSolver() {
Parameters.Add(problemTypeParam =
new ValueParameter>(nameof(ProblemType),
new EnumValue(ProblemType.MixedIntegerProgramming)));
Parameters.Add(solverSpecificParametersParam =
new FixedValueParameter(nameof(SolverSpecificParameters), new TextValue()));
}
[StorableConstructor]
protected LinearSolver(bool deserializing)
: base(deserializing) {
}
protected LinearSolver(LinearSolver original, Cloner cloner)
: base(original, cloner) {
problemTypeParam = cloner.Clone(original.problemTypeParam);
solverSpecificParametersParam = cloner.Clone(original.solverSpecificParametersParam);
}
public double DualTolerance { get; set; } = SolverParameters.DefaultDualTolerance;
public bool Incrementality { get; set; } =
SolverParameters.DefaultIncrementality == SolverParameters.IncrementalityValues.IncrementalityOn;
public SolverParameters.LpAlgorithmValues LpAlgorithm { get; set; }
protected virtual Solver.OptimizationProblemType OptimizationProblemType { get; }
public bool Presolve { get; set; } = SolverParameters.DefaultPresolve == SolverParameters.PresolveValues.PresolveOn;
public double PrimalTolerance { get; set; } = SolverParameters.DefaultPrimalTolerance;
public ProblemType ProblemType {
get => problemTypeParam.Value.Value;
set => problemTypeParam.Value.Value = value;
}
public IValueParameter> ProblemTypeParameter => problemTypeParam;
public double RelativeGapTolerance { get; set; } = SolverParameters.DefaultRelativeMipGap;
public bool Scaling { get; set; }
public string SolverSpecificParameters {
get => solverSpecificParametersParam.Value.Value;
set => solverSpecificParametersParam.Value.Value = value;
}
public IFixedValueParameter SolverSpecificParametersParameter => solverSpecificParametersParam;
public virtual bool SupportsPause => true;
public virtual bool SupportsStop => true;
public virtual TimeSpan TimeLimit { get; set; } = TimeSpan.Zero;
public override IDeepCloneable Clone(Cloner cloner) => new LinearSolver(this, cloner);
public void Dispose() => solver?.Dispose();
public bool ExportAsLp(string fileName, bool obfuscated = false) {
var lpFormat = solver?.ExportModelAsLpFormat(obfuscated);
if (string.IsNullOrEmpty(lpFormat))
return false;
File.WriteAllText(fileName, lpFormat);
return true;
}
public bool ExportAsMps(string fileName, bool fixedFormat = false, bool obfuscated = false) {
var mpsFormat = solver?.ExportModelAsMpsFormat(fixedFormat, obfuscated);
if (string.IsNullOrEmpty(mpsFormat))
return false;
File.WriteAllText(fileName, mpsFormat);
return true;
}
public bool ExportAsProto(string fileName, ProtoWriteFormat writeFormat = ProtoWriteFormat.ProtoBinary) =>
solver != null && solver.ExportModelAsProtoFormat(fileName, (Google.OrTools.LinearSolver.ProtoWriteFormat)writeFormat);
public MPSolverResponseStatus ImportFromMps(string fileName, bool? fixedFormat) =>
solver?.ImportModelFromMpsFormat(fileName, fixedFormat.HasValue, fixedFormat ?? false) ??
(MPSolverResponseStatus)SolverResponseStatus.Abnormal;
public MPSolverResponseStatus ImportFromProto(string fileName) =>
solver?.ImportModelFromProtoFormat(fileName) ?? (MPSolverResponseStatus)SolverResponseStatus.Abnormal;
public bool InterruptSolve() => solver?.InterruptSolve() ?? false;
public virtual void Reset() {
solver?.Dispose();
solver = null;
}
public virtual void Solve(ILinearProblemDefinition problemDefintion,
ResultCollection results, CancellationToken cancellationToken) =>
Solve(problemDefintion, results);
public virtual void Solve(ILinearProblemDefinition problemDefinition,
ResultCollection results) =>
Solve(problemDefinition, results, TimeLimit);
public virtual void Solve(ILinearProblemDefinition problemDefinition, ResultCollection results,
TimeSpan timeLimit) {
if (solver == null) {
solver = CreateSolver(OptimizationProblemType);
problemDefinition.BuildModel(solver);
}
if (timeLimit > TimeSpan.Zero) {
solver.SetTimeLimit((long)timeLimit.TotalMilliseconds);
} else {
solver.SetTimeLimit(0);
}
ResultStatus resultStatus;
using (var parameters = new SolverParameters()) {
parameters.SetDoubleParam(SolverParameters.DoubleParam.RelativeMipGap, RelativeGapTolerance);
parameters.SetDoubleParam(SolverParameters.DoubleParam.PrimalTolerance, PrimalTolerance);
parameters.SetDoubleParam(SolverParameters.DoubleParam.DualTolerance, DualTolerance);
parameters.SetIntegerParam(SolverParameters.IntegerParam.Presolve,
(int)(Presolve ? SolverParameters.PresolveValues.PresolveOn : SolverParameters.PresolveValues.PresolveOff));
parameters.SetIntegerParam(SolverParameters.IntegerParam.Incrementality,
(int)(Incrementality ? SolverParameters.IncrementalityValues.IncrementalityOn : SolverParameters.IncrementalityValues.IncrementalityOff));
parameters.SetIntegerParam(SolverParameters.IntegerParam.Scaling,
(int)(Scaling ? SolverParameters.ScalingValues.ScalingOn : SolverParameters.ScalingValues.ScalingOff));
if (!solver.SetSolverSpecificParametersAsString(SolverSpecificParameters))
throw new ArgumentException("Solver specific parameters could not be set.");
resultStatus = (ResultStatus)solver.Solve(parameters);
}
var objectiveValue = solver.Objective()?.Value();
problemDefinition.Analyze(solver, results);
if (solver.IsMip()) {
var objectiveBound = solver.Objective()?.BestBound();
var absoluteGap = objectiveValue.HasValue && objectiveBound.HasValue
? Math.Abs(objectiveBound.Value - objectiveValue.Value)
: (double?)null;
// https://www.ibm.com/support/knowledgecenter/SSSA5P_12.7.1/ilog.odms.cplex.help/CPLEX/Parameters/topics/EpGap.html
var relativeGap = absoluteGap.HasValue && objectiveValue.HasValue
? absoluteGap.Value / (1e-10 + Math.Abs(objectiveValue.Value))
: (double?)null;
if (resultStatus == ResultStatus.Optimal && absoluteGap.HasValue && !absoluteGap.Value.IsAlmost(0)) {
resultStatus = ResultStatus.OptimalWithinTolerance;
}
results.AddOrUpdateResult("BestObjectiveBound", new DoubleValue(objectiveBound ?? double.NaN));
results.AddOrUpdateResult("AbsoluteGap", new DoubleValue(absoluteGap ?? double.NaN));
results.AddOrUpdateResult("RelativeGap", new PercentValue(relativeGap ?? double.NaN));
}
results.AddOrUpdateResult("ResultStatus", new EnumValue(resultStatus));
results.AddOrUpdateResult("BestObjectiveValue", new DoubleValue(objectiveValue ?? double.NaN));
results.AddOrUpdateResult("NumberOfConstraints", new IntValue(solver.NumConstraints()));
results.AddOrUpdateResult("NumberOfVariables", new IntValue(solver.NumVariables()));
if (solver.IsMip() && solver.Nodes() >= 0) {
results.AddOrUpdateResult(nameof(solver.Nodes), new DoubleValue(solver.Nodes()));
}
if (solver.Iterations() >= 0) {
results.AddOrUpdateResult(nameof(solver.Iterations), new DoubleValue(solver.Iterations()));
}
results.AddOrUpdateResult(nameof(solver.SolverVersion), new StringValue(solver.SolverVersion()));
}
protected virtual Solver CreateSolver(Solver.OptimizationProblemType optimizationProblemType, string libraryName = null) {
if (!string.IsNullOrEmpty(libraryName) && !File.Exists(libraryName)) {
var paths = new List {
Path.GetDirectoryName(new Uri(Assembly.GetExecutingAssembly().CodeBase).LocalPath)
};
var path = Environment.GetEnvironmentVariable("PATH");
if (path != null)
paths.AddRange(path.Split(';'));
if (!paths.Any(p => File.Exists(Path.Combine(p, libraryName))))
throw new FileNotFoundException($"Could not find library {libraryName} in PATH.", libraryName);
}
try {
solver = new Solver(Name, optimizationProblemType, libraryName ?? string.Empty);
} catch {
throw new InvalidOperationException($"Could not create {optimizationProblemType}.");
}
if (solver == null)
throw new InvalidOperationException($"Could not create {optimizationProblemType}.");
solver.SuppressOutput();
return solver;
}
}
}