source: branches/2931_OR-Tools_LP_MIP/HeuristicLab.MathematicalOptimization/3.3/LinearProgramming/Algorithms/Solvers/Base/LinearSolver.cs @ 16582

Last change on this file since 16582 was 16582, checked in by ddorfmei, 7 months ago

#2931: solved the issues found during the review

File size: 10.3 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Collections.Generic;
24using System.IO;
25using System.Linq;
26using System.Reflection;
27using System.Threading;
28using Google.OrTools.LinearSolver;
29using HeuristicLab.Common;
30using HeuristicLab.Core;
31using HeuristicLab.Data;
32using HeuristicLab.Optimization;
33using HeuristicLab.Parameters;
34using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
35
36namespace HeuristicLab.ExactOptimization.LinearProgramming {
37
38  [StorableClass]
39  public class LinearSolver : ParameterizedNamedItem, ILinearSolver, IDisposable {
40
41    [Storable]
42    protected IValueParameter<EnumValue<ProblemType>> problemTypeParam;
43
44    protected Solver solver;
45
46    [Storable]
47    protected IFixedValueParameter<TextValue> solverSpecificParametersParam;
48
49    public LinearSolver() {
50      Parameters.Add(problemTypeParam =
51        new ValueParameter<EnumValue<ProblemType>>(nameof(ProblemType),
52          new EnumValue<ProblemType>(ProblemType.MixedIntegerProgramming)));
53      Parameters.Add(solverSpecificParametersParam =
54        new FixedValueParameter<TextValue>(nameof(SolverSpecificParameters), new TextValue()));
55    }
56
57    [StorableConstructor]
58    protected LinearSolver(bool deserializing)
59      : base(deserializing) {
60    }
61
62    protected LinearSolver(LinearSolver original, Cloner cloner)
63      : base(original, cloner) {
64      problemTypeParam = cloner.Clone(original.problemTypeParam);
65      solverSpecificParametersParam = cloner.Clone(original.solverSpecificParametersParam);
66    }
67
68    public double DualTolerance { get; set; } = SolverParameters.DefaultDualTolerance;
69
70    public bool Incrementality { get; set; } =
71      SolverParameters.DefaultIncrementality == SolverParameters.IncrementalityValues.IncrementalityOn;
72
73    public SolverParameters.LpAlgorithmValues LpAlgorithm { get; set; }
74    protected virtual Solver.OptimizationProblemType OptimizationProblemType { get; }
75    public bool Presolve { get; set; } = SolverParameters.DefaultPresolve == SolverParameters.PresolveValues.PresolveOn;
76    public double PrimalTolerance { get; set; } = SolverParameters.DefaultPrimalTolerance;
77
78    public ProblemType ProblemType {
79      get => problemTypeParam.Value.Value;
80      set => problemTypeParam.Value.Value = value;
81    }
82
83    public IValueParameter<EnumValue<ProblemType>> ProblemTypeParameter => problemTypeParam;
84    public double RelativeGapTolerance { get; set; } = SolverParameters.DefaultRelativeMipGap;
85    public bool Scaling { get; set; }
86
87    public string SolverSpecificParameters {
88      get => solverSpecificParametersParam.Value.Value;
89      set => solverSpecificParametersParam.Value.Value = value;
90    }
91
92    public IFixedValueParameter<TextValue> SolverSpecificParametersParameter => solverSpecificParametersParam;
93    public virtual bool SupportsPause => true;
94    public virtual bool SupportsStop => true;
95    public virtual TimeSpan TimeLimit { get; set; } = TimeSpan.Zero;
96
97    public override IDeepCloneable Clone(Cloner cloner) => new LinearSolver(this, cloner);
98
99    public void Dispose() => solver?.Dispose();
100
101    public bool ExportAsLp(string fileName, bool obfuscated = false) {
102      var lpFormat = solver?.ExportModelAsLpFormat(obfuscated);
103      if (string.IsNullOrEmpty(lpFormat))
104        return false;
105      File.WriteAllText(fileName, lpFormat);
106      return true;
107    }
108
109    public bool ExportAsMps(string fileName, bool fixedFormat = false, bool obfuscated = false) {
110      var mpsFormat = solver?.ExportModelAsMpsFormat(fixedFormat, obfuscated);
111      if (string.IsNullOrEmpty(mpsFormat))
112        return false;
113      File.WriteAllText(fileName, mpsFormat);
114      return true;
115    }
116
117    public bool ExportAsProto(string fileName, ProtoWriteFormat writeFormat = ProtoWriteFormat.ProtoBinary) =>
118      solver != null && solver.ExportModelAsProtoFormat(fileName, (Google.OrTools.LinearSolver.ProtoWriteFormat)writeFormat);
119
120    public MPSolverResponseStatus ImportFromMps(string fileName, bool? fixedFormat) =>
121      solver?.ImportModelFromMpsFormat(fileName, fixedFormat.HasValue, fixedFormat ?? false) ??
122      (MPSolverResponseStatus)SolverResponseStatus.Abnormal;
123
124    public MPSolverResponseStatus ImportFromProto(string fileName) =>
125      solver?.ImportModelFromProtoFormat(fileName) ?? (MPSolverResponseStatus)SolverResponseStatus.Abnormal;
126
127    public bool InterruptSolve() => solver?.InterruptSolve() ?? false;
128
129    public virtual void Reset() {
130      solver?.Dispose();
131      solver = null;
132    }
133
134    public virtual void Solve(ILinearProblemDefinition problemDefintion,
135      ResultCollection results, CancellationToken cancellationToken) =>
136      Solve(problemDefintion, results);
137
138    public virtual void Solve(ILinearProblemDefinition problemDefinition,
139      ResultCollection results) =>
140      Solve(problemDefinition, results, TimeLimit);
141
142    public virtual void Solve(ILinearProblemDefinition problemDefinition, ResultCollection results,
143      TimeSpan timeLimit) {
144      if (solver == null) {
145        solver = CreateSolver(OptimizationProblemType);
146        problemDefinition.BuildModel(solver);
147      }
148
149      if (timeLimit > TimeSpan.Zero) {
150        solver.SetTimeLimit((long)timeLimit.TotalMilliseconds);
151      } else {
152        solver.SetTimeLimit(0);
153      }
154
155      ResultStatus resultStatus;
156
157      using (var parameters = new SolverParameters()) {
158        parameters.SetDoubleParam(SolverParameters.DoubleParam.RelativeMipGap, RelativeGapTolerance);
159        parameters.SetDoubleParam(SolverParameters.DoubleParam.PrimalTolerance, PrimalTolerance);
160        parameters.SetDoubleParam(SolverParameters.DoubleParam.DualTolerance, DualTolerance);
161        parameters.SetIntegerParam(SolverParameters.IntegerParam.Presolve,
162          (int)(Presolve ? SolverParameters.PresolveValues.PresolveOn : SolverParameters.PresolveValues.PresolveOff));
163        parameters.SetIntegerParam(SolverParameters.IntegerParam.Incrementality,
164          (int)(Incrementality ? SolverParameters.IncrementalityValues.IncrementalityOn : SolverParameters.IncrementalityValues.IncrementalityOff));
165        parameters.SetIntegerParam(SolverParameters.IntegerParam.Scaling,
166          (int)(Scaling ? SolverParameters.ScalingValues.ScalingOn : SolverParameters.ScalingValues.ScalingOff));
167
168        if (!solver.SetSolverSpecificParametersAsString(SolverSpecificParameters))
169          throw new ArgumentException("Solver specific parameters could not be set.");
170
171        resultStatus = (ResultStatus)solver.Solve(parameters);
172      }
173
174      var objectiveValue = solver.Objective()?.Value();
175
176      problemDefinition.Analyze(solver, results);
177
178      if (solver.IsMip()) {
179        var objectiveBound = solver.Objective()?.BestBound();
180        var absoluteGap = objectiveValue.HasValue && objectiveBound.HasValue
181          ? Math.Abs(objectiveBound.Value - objectiveValue.Value)
182          : (double?)null;
183        // https://www.ibm.com/support/knowledgecenter/SSSA5P_12.7.1/ilog.odms.cplex.help/CPLEX/Parameters/topics/EpGap.html
184        var relativeGap = absoluteGap.HasValue && objectiveValue.HasValue
185          ? absoluteGap.Value / (1e-10 + Math.Abs(objectiveValue.Value))
186          : (double?)null;
187
188        if (resultStatus == ResultStatus.Optimal && absoluteGap.HasValue && !absoluteGap.Value.IsAlmost(0)) {
189          resultStatus = ResultStatus.OptimalWithinTolerance;
190        }
191
192        results.AddOrUpdateResult("BestObjectiveBound", new DoubleValue(objectiveBound ?? double.NaN));
193        results.AddOrUpdateResult("AbsoluteGap", new DoubleValue(absoluteGap ?? double.NaN));
194        results.AddOrUpdateResult("RelativeGap", new PercentValue(relativeGap ?? double.NaN));
195      }
196
197      results.AddOrUpdateResult("ResultStatus", new EnumValue<ResultStatus>(resultStatus));
198      results.AddOrUpdateResult("BestObjectiveValue", new DoubleValue(objectiveValue ?? double.NaN));
199
200      results.AddOrUpdateResult("NumberOfConstraints", new IntValue(solver.NumConstraints()));
201      results.AddOrUpdateResult("NumberOfVariables", new IntValue(solver.NumVariables()));
202
203      if (solver.IsMip() && solver.Nodes() >= 0) {
204        results.AddOrUpdateResult(nameof(solver.Nodes), new DoubleValue(solver.Nodes()));
205      }
206
207      if (solver.Iterations() >= 0) {
208        results.AddOrUpdateResult(nameof(solver.Iterations), new DoubleValue(solver.Iterations()));
209      }
210
211      results.AddOrUpdateResult(nameof(solver.SolverVersion), new StringValue(solver.SolverVersion()));
212    }
213
214    protected virtual Solver CreateSolver(Solver.OptimizationProblemType optimizationProblemType, string libraryName = null) {
215      if (!string.IsNullOrEmpty(libraryName) && !File.Exists(libraryName)) {
216        var paths = new List<string> {
217          Path.GetDirectoryName(new Uri(Assembly.GetExecutingAssembly().CodeBase).LocalPath)
218        };
219        var path = Environment.GetEnvironmentVariable("PATH");
220        if (path != null)
221          paths.AddRange(path.Split(';'));
222        if (!paths.Any(p => File.Exists(Path.Combine(p, libraryName))))
223          throw new FileNotFoundException($"Could not find library {libraryName} in PATH.", libraryName);
224      }
225
226      try {
227        solver = new Solver(Name, optimizationProblemType, libraryName ?? string.Empty);
228      } catch {
229        throw new InvalidOperationException($"Could not create {optimizationProblemType}.");
230      }
231
232      if (solver == null)
233        throw new InvalidOperationException($"Could not create {optimizationProblemType}.");
234
235      solver.SuppressOutput();
236      return solver;
237    }
238  }
239}
Note: See TracBrowser for help on using the repository browser.