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

Last change on this file since 16736 was 16736, checked in by ddorfmei, 8 months ago

#2931: Upgraded persistence to HEAL.Attic

File size: 10.3 KB
RevLine 
[16288]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;
[16405]23using System.Collections.Generic;
24using System.IO;
25using System.Linq;
26using System.Reflection;
[16233]27using System.Threading;
[16405]28using Google.OrTools.LinearSolver;
[16233]29using HeuristicLab.Common;
[16172]30using HeuristicLab.Core;
31using HeuristicLab.Data;
[16405]32using HeuristicLab.Optimization;
[16172]33using HeuristicLab.Parameters;
[16736]34using HEAL.Attic;
[16172]35
[16582]36namespace HeuristicLab.ExactOptimization.LinearProgramming {
[16172]37
[16736]38  [StorableType("D0657902-BE8B-4826-B832-FDA84E9B24C3")]
[16405]39  public class LinearSolver : ParameterizedNamedItem, ILinearSolver, IDisposable {
[16172]40
41    [Storable]
[16373]42    protected IValueParameter<EnumValue<ProblemType>> problemTypeParam;
[16172]43
[16405]44    protected Solver solver;
[16172]45
[16373]46    [Storable]
47    protected IFixedValueParameter<TextValue> solverSpecificParametersParam;
48
[16405]49    public LinearSolver() {
[16373]50      Parameters.Add(problemTypeParam =
[16582]51        new ValueParameter<EnumValue<ProblemType>>(nameof(ProblemType),
52          new EnumValue<ProblemType>(ProblemType.MixedIntegerProgramming)));
[16373]53      Parameters.Add(solverSpecificParametersParam =
54        new FixedValueParameter<TextValue>(nameof(SolverSpecificParameters), new TextValue()));
[16172]55    }
56
57    [StorableConstructor]
[16736]58    protected LinearSolver(StorableConstructorFlag _) : base(_) { }
[16172]59
[16405]60    protected LinearSolver(LinearSolver original, Cloner cloner)
[16172]61      : base(original, cloner) {
[16373]62      problemTypeParam = cloner.Clone(original.problemTypeParam);
63      solverSpecificParametersParam = cloner.Clone(original.solverSpecificParametersParam);
[16172]64    }
65
[16582]66    public double DualTolerance { get; set; } = SolverParameters.DefaultDualTolerance;
[16405]67
68    public bool Incrementality { get; set; } =
[16582]69      SolverParameters.DefaultIncrementality == SolverParameters.IncrementalityValues.IncrementalityOn;
[16405]70
[16582]71    public SolverParameters.LpAlgorithmValues LpAlgorithm { get; set; }
72    protected virtual Solver.OptimizationProblemType OptimizationProblemType { get; }
73    public bool Presolve { get; set; } = SolverParameters.DefaultPresolve == SolverParameters.PresolveValues.PresolveOn;
74    public double PrimalTolerance { get; set; } = SolverParameters.DefaultPrimalTolerance;
[16405]75
[16373]76    public ProblemType ProblemType {
77      get => problemTypeParam.Value.Value;
78      set => problemTypeParam.Value.Value = value;
[16172]79    }
80
[16582]81    public IValueParameter<EnumValue<ProblemType>> ProblemTypeParameter => problemTypeParam;
82    public double RelativeGapTolerance { get; set; } = SolverParameters.DefaultRelativeMipGap;
[16405]83    public bool Scaling { get; set; }
84
85    public string SolverSpecificParameters {
86      get => solverSpecificParametersParam.Value.Value;
87      set => solverSpecificParametersParam.Value.Value = value;
88    }
89
[16582]90    public IFixedValueParameter<TextValue> SolverSpecificParametersParameter => solverSpecificParametersParam;
[16373]91    public virtual bool SupportsPause => true;
92    public virtual bool SupportsStop => true;
[16405]93    public virtual TimeSpan TimeLimit { get; set; } = TimeSpan.Zero;
[16172]94
[16405]95    public override IDeepCloneable Clone(Cloner cloner) => new LinearSolver(this, cloner);
[16233]96
97    public void Dispose() => solver?.Dispose();
98
[16405]99    public bool ExportAsLp(string fileName, bool obfuscated = false) {
100      var lpFormat = solver?.ExportModelAsLpFormat(obfuscated);
101      if (string.IsNullOrEmpty(lpFormat))
102        return false;
103      File.WriteAllText(fileName, lpFormat);
104      return true;
105    }
106
107    public bool ExportAsMps(string fileName, bool fixedFormat = false, bool obfuscated = false) {
108      var mpsFormat = solver?.ExportModelAsMpsFormat(fixedFormat, obfuscated);
109      if (string.IsNullOrEmpty(mpsFormat))
110        return false;
111      File.WriteAllText(fileName, mpsFormat);
112      return true;
113    }
114
115    public bool ExportAsProto(string fileName, ProtoWriteFormat writeFormat = ProtoWriteFormat.ProtoBinary) =>
[16582]116      solver != null && solver.ExportModelAsProtoFormat(fileName, (Google.OrTools.LinearSolver.ProtoWriteFormat)writeFormat);
[16405]117
[16582]118    public MPSolverResponseStatus ImportFromMps(string fileName, bool? fixedFormat) =>
119      solver?.ImportModelFromMpsFormat(fileName, fixedFormat.HasValue, fixedFormat ?? false) ??
120      (MPSolverResponseStatus)SolverResponseStatus.Abnormal;
[16405]121
[16582]122    public MPSolverResponseStatus ImportFromProto(string fileName) =>
123      solver?.ImportModelFromProtoFormat(fileName) ?? (MPSolverResponseStatus)SolverResponseStatus.Abnormal;
[16405]124
[16373]125    public bool InterruptSolve() => solver?.InterruptSolve() ?? false;
[16233]126
127    public virtual void Reset() {
[16288]128      solver?.Dispose();
[16233]129      solver = null;
[16172]130    }
131
[16582]132    public virtual void Solve(ILinearProblemDefinition problemDefintion,
[16405]133      ResultCollection results, CancellationToken cancellationToken) =>
[16582]134      Solve(problemDefintion, results);
[16233]135
[16582]136    public virtual void Solve(ILinearProblemDefinition problemDefinition,
[16405]137      ResultCollection results) =>
138      Solve(problemDefinition, results, TimeLimit);
[16233]139
[16582]140    public virtual void Solve(ILinearProblemDefinition problemDefinition, ResultCollection results,
[16405]141      TimeSpan timeLimit) {
[16233]142      if (solver == null) {
[16405]143        solver = CreateSolver(OptimizationProblemType);
144        problemDefinition.BuildModel(solver);
[16233]145      }
146
[16405]147      if (timeLimit > TimeSpan.Zero) {
148        solver.SetTimeLimit((long)timeLimit.TotalMilliseconds);
149      } else {
150        solver.SetTimeLimit(0);
151      }
[16233]152
[16405]153      ResultStatus resultStatus;
[16373]154
[16582]155      using (var parameters = new SolverParameters()) {
156        parameters.SetDoubleParam(SolverParameters.DoubleParam.RelativeMipGap, RelativeGapTolerance);
157        parameters.SetDoubleParam(SolverParameters.DoubleParam.PrimalTolerance, PrimalTolerance);
158        parameters.SetDoubleParam(SolverParameters.DoubleParam.DualTolerance, DualTolerance);
159        parameters.SetIntegerParam(SolverParameters.IntegerParam.Presolve,
160          (int)(Presolve ? SolverParameters.PresolveValues.PresolveOn : SolverParameters.PresolveValues.PresolveOff));
161        parameters.SetIntegerParam(SolverParameters.IntegerParam.Incrementality,
162          (int)(Incrementality ? SolverParameters.IncrementalityValues.IncrementalityOn : SolverParameters.IncrementalityValues.IncrementalityOff));
163        parameters.SetIntegerParam(SolverParameters.IntegerParam.Scaling,
164          (int)(Scaling ? SolverParameters.ScalingValues.ScalingOn : SolverParameters.ScalingValues.ScalingOff));
[16233]165
[16405]166        if (!solver.SetSolverSpecificParametersAsString(SolverSpecificParameters))
167          throw new ArgumentException("Solver specific parameters could not be set.");
[16373]168
[16405]169        resultStatus = (ResultStatus)solver.Solve(parameters);
[16373]170      }
171
[16405]172      var objectiveValue = solver.Objective()?.Value();
[16373]173
[16405]174      problemDefinition.Analyze(solver, results);
175
[16582]176      if (solver.IsMip()) {
[16405]177        var objectiveBound = solver.Objective()?.BestBound();
178        var absoluteGap = objectiveValue.HasValue && objectiveBound.HasValue
179          ? Math.Abs(objectiveBound.Value - objectiveValue.Value)
180          : (double?)null;
181        // https://www.ibm.com/support/knowledgecenter/SSSA5P_12.7.1/ilog.odms.cplex.help/CPLEX/Parameters/topics/EpGap.html
182        var relativeGap = absoluteGap.HasValue && objectiveValue.HasValue
183          ? absoluteGap.Value / (1e-10 + Math.Abs(objectiveValue.Value))
184          : (double?)null;
185
[16582]186        if (resultStatus == ResultStatus.Optimal && absoluteGap.HasValue && !absoluteGap.Value.IsAlmost(0)) {
187          resultStatus = ResultStatus.OptimalWithinTolerance;
188        }
189
[16405]190        results.AddOrUpdateResult("BestObjectiveBound", new DoubleValue(objectiveBound ?? double.NaN));
191        results.AddOrUpdateResult("AbsoluteGap", new DoubleValue(absoluteGap ?? double.NaN));
192        results.AddOrUpdateResult("RelativeGap", new PercentValue(relativeGap ?? double.NaN));
[16373]193      }
194
[16582]195      results.AddOrUpdateResult("ResultStatus", new EnumValue<ResultStatus>(resultStatus));
196      results.AddOrUpdateResult("BestObjectiveValue", new DoubleValue(objectiveValue ?? double.NaN));
197
[16405]198      results.AddOrUpdateResult("NumberOfConstraints", new IntValue(solver.NumConstraints()));
199      results.AddOrUpdateResult("NumberOfVariables", new IntValue(solver.NumVariables()));
200
[16582]201      if (solver.IsMip() && solver.Nodes() >= 0) {
[16405]202        results.AddOrUpdateResult(nameof(solver.Nodes), new DoubleValue(solver.Nodes()));
203      }
204
205      if (solver.Iterations() >= 0) {
206        results.AddOrUpdateResult(nameof(solver.Iterations), new DoubleValue(solver.Iterations()));
207      }
208
209      results.AddOrUpdateResult(nameof(solver.SolverVersion), new StringValue(solver.SolverVersion()));
[16233]210    }
[16405]211
[16582]212    protected virtual Solver CreateSolver(Solver.OptimizationProblemType optimizationProblemType, string libraryName = null) {
[16405]213      if (!string.IsNullOrEmpty(libraryName) && !File.Exists(libraryName)) {
214        var paths = new List<string> {
215          Path.GetDirectoryName(new Uri(Assembly.GetExecutingAssembly().CodeBase).LocalPath)
216        };
217        var path = Environment.GetEnvironmentVariable("PATH");
218        if (path != null)
219          paths.AddRange(path.Split(';'));
220        if (!paths.Any(p => File.Exists(Path.Combine(p, libraryName))))
221          throw new FileNotFoundException($"Could not find library {libraryName} in PATH.", libraryName);
222      }
223
224      try {
[16582]225        solver = new Solver(Name, optimizationProblemType, libraryName ?? string.Empty);
[16405]226      } catch {
227        throw new InvalidOperationException($"Could not create {optimizationProblemType}.");
228      }
229
230      if (solver == null)
231        throw new InvalidOperationException($"Could not create {optimizationProblemType}.");
232
233      solver.SuppressOutput();
234      return solver;
235    }
[16172]236  }
[16288]237}
Note: See TracBrowser for help on using the repository browser.