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

Last change on this file since 16405 was 16405, checked in by ddorfmei, 5 months ago

#2931:

  • moved views to separate plugin HeuristicLab.MathematicalOptimization.Views
  • added button in LinearProgrammingProblemView to select the problem definition type
  • added views for problem definitions
  • added ExportFile parameter to LinearProgrammingAlgorithm
  • extended FileValue and FileValueView by the option to save a file
  • code cleanup
File size: 11.0 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.MathematicalOptimization.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), new EnumValue<ProblemType>()));
52      Parameters.Add(solverSpecificParametersParam =
53        new FixedValueParameter<TextValue>(nameof(SolverSpecificParameters), new TextValue()));
54    }
55
56    [StorableConstructor]
57    protected LinearSolver(bool deserializing)
58      : base(deserializing) {
59    }
60
61    protected LinearSolver(LinearSolver original, Cloner cloner)
62      : base(original, cloner) {
63      problemTypeParam = cloner.Clone(original.problemTypeParam);
64      solverSpecificParametersParam = cloner.Clone(original.solverSpecificParametersParam);
65    }
66
67    public double DualTolerance { get; set; } = MPSolverParameters.kDefaultDualTolerance;
68
69    public string ExportModel { get; set; }
70
71    public bool Incrementality { get; set; } =
72          MPSolverParameters.kDefaultIncrementality == MPSolverParameters.INCREMENTALITY_ON;
73
74    public LpAlgorithmValues LpAlgorithm { get; set; }
75
76    public bool Presolve { get; set; } = MPSolverParameters.kDefaultPresolve == MPSolverParameters.PRESOLVE_ON;
77
78    public double PrimalTolerance { get; set; } = MPSolverParameters.kDefaultPrimalTolerance;
79
80    public ProblemType ProblemType {
81      get => problemTypeParam.Value.Value;
82      set => problemTypeParam.Value.Value = value;
83    }
84
85    public double RelativeGapTolerance { get; set; } = MPSolverParameters.kDefaultRelativeMipGap;
86
87    public bool Scaling { get; set; }
88
89    public string SolverSpecificParameters {
90      get => solverSpecificParametersParam.Value.Value;
91      set => solverSpecificParametersParam.Value.Value = value;
92    }
93
94    public virtual bool SupportsPause => true;
95    public virtual bool SupportsStop => true;
96    public virtual TimeSpan TimeLimit { get; set; } = TimeSpan.Zero;
97    protected virtual OptimizationProblemType OptimizationProblemType { get; }
98
99    public override IDeepCloneable Clone(Cloner cloner) => new LinearSolver(this, cloner);
100
101    public void Dispose() => solver?.Dispose();
102
103    public bool ExportAsLp(string fileName, bool obfuscated = false) {
104      var lpFormat = solver?.ExportModelAsLpFormat(obfuscated);
105      if (string.IsNullOrEmpty(lpFormat))
106        return false;
107      File.WriteAllText(fileName, lpFormat);
108      return true;
109    }
110
111    public bool ExportAsMps(string fileName, bool fixedFormat = false, bool obfuscated = false) {
112      var mpsFormat = solver?.ExportModelAsMpsFormat(fixedFormat, obfuscated);
113      if (string.IsNullOrEmpty(mpsFormat))
114        return false;
115      File.WriteAllText(fileName, mpsFormat);
116      return true;
117    }
118
119    public bool ExportAsProto(string fileName, ProtoWriteFormat writeFormat = ProtoWriteFormat.ProtoBinary) =>
120      solver != null && solver.ExportModelAsProtoFormat(fileName, (int)writeFormat);
121
122    public SolverResponseStatus ImportFromMps(string fileName, bool? fixedFormat) => solver == null
123      ? SolverResponseStatus.Abnormal
124      : (SolverResponseStatus)solver.ImportModelFromMpsFormat(fileName, fixedFormat.HasValue, fixedFormat ?? false);
125
126    public SolverResponseStatus ImportFromProto(string fileName) => solver == null
127      ? SolverResponseStatus.Abnormal
128      : (SolverResponseStatus)solver.ImportModelFromProtoFormat(fileName);
129
130    public bool InterruptSolve() => solver?.InterruptSolve() ?? false;
131
132    public virtual void Reset() {
133      solver?.Dispose();
134      solver = null;
135    }
136
137    public virtual void Solve(ILinearProgrammingProblemDefinition problemDefintion, ref TimeSpan executionTime,
138      ResultCollection results, CancellationToken cancellationToken) =>
139      Solve(problemDefintion, ref executionTime, results);
140
141    public virtual void Solve(ILinearProgrammingProblemDefinition problemDefinition, ref TimeSpan executionTime,
142      ResultCollection results) =>
143      Solve(problemDefinition, results, TimeLimit);
144
145    public virtual void Solve(ILinearProgrammingProblemDefinition problemDefinition, ResultCollection results,
146      TimeSpan timeLimit) {
147      if (solver == null) {
148        solver = CreateSolver(OptimizationProblemType);
149        problemDefinition.BuildModel(solver);
150      }
151
152      if (timeLimit > TimeSpan.Zero) {
153        solver.SetTimeLimit((long)timeLimit.TotalMilliseconds);
154      } else {
155        solver.SetTimeLimit(0);
156      }
157
158      ResultStatus resultStatus;
159
160      using (var parameters = new MPSolverParameters()) {
161        parameters.SetDoubleParam(MPSolverParameters.RELATIVE_MIP_GAP, RelativeGapTolerance);
162        parameters.SetDoubleParam(MPSolverParameters.PRIMAL_TOLERANCE, PrimalTolerance);
163        parameters.SetDoubleParam(MPSolverParameters.DUAL_TOLERANCE, DualTolerance);
164        parameters.SetIntegerParam(MPSolverParameters.PRESOLVE,
165          Presolve ? MPSolverParameters.PRESOLVE_ON : MPSolverParameters.PRESOLVE_OFF);
166        parameters.SetIntegerParam(MPSolverParameters.LP_ALGORITHM, (int)LpAlgorithm);
167        parameters.SetIntegerParam(MPSolverParameters.INCREMENTALITY,
168          Incrementality ? MPSolverParameters.INCREMENTALITY_ON : MPSolverParameters.INCREMENTALITY_OFF);
169        parameters.SetIntegerParam(MPSolverParameters.SCALING,
170          Scaling ? MPSolverParameters.SCALING_ON : MPSolverParameters.SCALING_OFF);
171
172        if (!solver.SetSolverSpecificParametersAsString(SolverSpecificParameters))
173          throw new ArgumentException("Solver specific parameters could not be set.");
174
175        if (!string.IsNullOrWhiteSpace(ExportModel)) {
176          var fileInfo = new FileInfo(ExportModel);
177
178          if (!fileInfo.Directory?.Exists ?? false) {
179            Directory.CreateDirectory(fileInfo.Directory.FullName);
180          }
181
182          bool exportSuccessful;
183          switch (fileInfo.Extension) {
184            case ".lp":
185              exportSuccessful = ExportAsLp(ExportModel);
186              break;
187
188            case ".mps":
189              exportSuccessful = ExportAsMps(ExportModel);
190              break;
191
192            case ".prototxt":
193              exportSuccessful = ExportAsProto(ExportModel, ProtoWriteFormat.ProtoText);
194              break;
195
196            case ".bin": // remove file extension as it is added by OR-Tools
197              exportSuccessful = ExportAsProto(Path.ChangeExtension(ExportModel, null));
198              break;
199
200            default:
201              throw new NotSupportedException("File format selected to export model is not supported.");
202          }
203        }
204
205        // TODO: show warning if file export didn't work (if exportSuccessful is false)
206
207        resultStatus = (ResultStatus)solver.Solve(parameters);
208      }
209
210      var objectiveValue = solver.Objective()?.Value();
211
212      problemDefinition.Analyze(solver, results);
213      results.AddOrUpdateResult("ResultStatus", new EnumValue<ResultStatus>(resultStatus));
214      results.AddOrUpdateResult("BestObjectiveValue", new DoubleValue(objectiveValue ?? double.NaN));
215
216      if (solver.IsMIP()) {
217        var objectiveBound = solver.Objective()?.BestBound();
218        var absoluteGap = objectiveValue.HasValue && objectiveBound.HasValue
219          ? Math.Abs(objectiveBound.Value - objectiveValue.Value)
220          : (double?)null;
221        // https://www.ibm.com/support/knowledgecenter/SSSA5P_12.7.1/ilog.odms.cplex.help/CPLEX/Parameters/topics/EpGap.html
222        var relativeGap = absoluteGap.HasValue && objectiveValue.HasValue
223          ? absoluteGap.Value / (1e-10 + Math.Abs(objectiveValue.Value))
224          : (double?)null;
225
226        results.AddOrUpdateResult("BestObjectiveBound", new DoubleValue(objectiveBound ?? double.NaN));
227        results.AddOrUpdateResult("AbsoluteGap", new DoubleValue(absoluteGap ?? double.NaN));
228        results.AddOrUpdateResult("RelativeGap", new PercentValue(relativeGap ?? double.NaN));
229      }
230
231      results.AddOrUpdateResult("NumberOfConstraints", new IntValue(solver.NumConstraints()));
232      results.AddOrUpdateResult("NumberOfVariables", new IntValue(solver.NumVariables()));
233
234      if (solver.IsMIP() && solver.Nodes() >= 0) {
235        results.AddOrUpdateResult(nameof(solver.Nodes), new DoubleValue(solver.Nodes()));
236      }
237
238      if (solver.Iterations() >= 0) {
239        results.AddOrUpdateResult(nameof(solver.Iterations), new DoubleValue(solver.Iterations()));
240      }
241
242      results.AddOrUpdateResult(nameof(solver.SolverVersion), new StringValue(solver.SolverVersion()));
243    }
244
245    protected virtual Solver CreateSolver(OptimizationProblemType optimizationProblemType, string libraryName = null) {
246      if (!string.IsNullOrEmpty(libraryName) && !File.Exists(libraryName)) {
247        var paths = new List<string> {
248          Path.GetDirectoryName(new Uri(Assembly.GetExecutingAssembly().CodeBase).LocalPath)
249        };
250        var path = Environment.GetEnvironmentVariable("PATH");
251        if (path != null)
252          paths.AddRange(path.Split(';'));
253        if (!paths.Any(p => File.Exists(Path.Combine(p, libraryName))))
254          throw new FileNotFoundException($"Could not find library {libraryName} in PATH.", libraryName);
255      }
256
257      try {
258        solver = new Solver(Name, (int)optimizationProblemType, libraryName ?? string.Empty);
259      } catch {
260        throw new InvalidOperationException($"Could not create {optimizationProblemType}.");
261      }
262
263      if (solver == null)
264        throw new InvalidOperationException($"Could not create {optimizationProblemType}.");
265
266      solver.SuppressOutput();
267      return solver;
268    }
269  }
270}
Note: See TracBrowser for help on using the repository browser.