Changeset 16405 for branches/2931_OR-Tools_LP_MIP/HeuristicLab.MathematicalOptimization/3.3/LinearProgramming/Algorithms/Solvers/Base/LinearSolver.cs

Timestamp:

12/19/18 14:15:49 (5 years ago)

Author:

ddorfmei

Message:

#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:

• branches/2931_OR-Tools_LP_MIP/HeuristicLab.MathematicalOptimization/3.3/LinearProgramming/Algorithms/Solvers/Base/LinearSolver.cs (moved) (moved from branches/2931_OR-Tools_LP_MIP/HeuristicLab.MathematicalOptimization/3.3/LinearProgramming/Algorithms/Solvers/Base/Solver.cs) (5 diffs)

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

@@ -21 +21 @@
 
 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.MathematicalOptimization.LinearProgramming.Algorithms.Solvers.Base {
+namespace HeuristicLab.MathematicalOptimization.LinearProgramming {
 
   [StorableClass]
-  public class Solver : ParameterizedNamedItem, ISolver, IDisposable {
+  public class LinearSolver : ParameterizedNamedItem, ILinearSolver, IDisposable {
 
     [Storable]
     protected IValueParameter<EnumValue<ProblemType>> problemTypeParam;
 
-    protected LinearSolver solver;
+    protected Solver solver;
 
     [Storable]
     protected IFixedValueParameter<TextValue> solverSpecificParametersParam;
 
-    public Solver() {
+    public LinearSolver() {
       Parameters.Add(problemTypeParam =
         new ValueParameter<EnumValue<ProblemType>>(nameof(ProblemType), new EnumValue<ProblemType>()));
@@ -49 +55 @@
 
     [StorableConstructor]
-    protected Solver(bool deserializing)
+    protected LinearSolver(bool deserializing)
       : base(deserializing) {
     }
 
-    protected Solver(Solver original, Cloner cloner)
+    protected LinearSolver(LinearSolver original, Cloner cloner)
       : base(original, cloner) {
       problemTypeParam = cloner.Clone(original.problemTypeParam);
@@ -59 +65 @@
     }
 
+    public double DualTolerance { get; set; } = MPSolverParameters.kDefaultDualTolerance;
+
+    public string ExportModel { get; set; }
+
+    public bool Incrementality { get; set; } =
+          MPSolverParameters.kDefaultIncrementality == MPSolverParameters.INCREMENTALITY_ON;
+
+    public LpAlgorithmValues LpAlgorithm { get; set; }
+
+    public bool Presolve { get; set; } = MPSolverParameters.kDefaultPresolve == MPSolverParameters.PRESOLVE_ON;
+
+    public double PrimalTolerance { get; set; } = MPSolverParameters.kDefaultPrimalTolerance;
+
     public ProblemType ProblemType {
       get => problemTypeParam.Value.Value;
@@ -64 +83 @@
     }
 
-    public TextValue SolverSpecificParameters => solverSpecificParametersParam.Value;
+    public double RelativeGapTolerance { get; set; } = MPSolverParameters.kDefaultRelativeMipGap;
+
+    public bool Scaling { get; set; }
+
+    public string SolverSpecificParameters {
+      get => solverSpecificParametersParam.Value.Value;
+      set => solverSpecificParametersParam.Value.Value = value;
+    }
 
     public virtual bool SupportsPause => true;
     public virtual bool SupportsStop => true;
+    public virtual TimeSpan TimeLimit { get; set; } = TimeSpan.Zero;
     protected virtual OptimizationProblemType OptimizationProblemType { get; }
 
-    public override IDeepCloneable Clone(Cloner cloner) => new Solver(this, cloner);
+    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, (int)writeFormat);
+
+    public SolverResponseStatus ImportFromMps(string fileName, bool? fixedFormat) => solver == null
+      ? SolverResponseStatus.Abnormal
+      : (SolverResponseStatus)solver.ImportModelFromMpsFormat(fileName, fixedFormat.HasValue, fixedFormat ?? false);
+
+    public SolverResponseStatus ImportFromProto(string fileName) => solver == null
+      ? SolverResponseStatus.Abnormal
+      : (SolverResponseStatus)solver.ImportModelFromProtoFormat(fileName);
 
     public bool InterruptSolve() => solver?.InterruptSolve() ?? false;
@@ -81 +135 @@
     }
 
-    public virtual void Solve(LinearProgrammingAlgorithm algorithm, CancellationToken cancellationToken) =>
-      Solve(algorithm);
-
-    public virtual void Solve(LinearProgrammingAlgorithm algorithm) =>
-      Solve(algorithm, algorithm.TimeLimit);
-
-    public virtual void Solve(LinearProgrammingAlgorithm algorithm, TimeSpan timeLimit) {
-      string libraryName = null;
-      if (this is IExternalSolver externalSolver)
-        libraryName = externalSolver.LibraryName;
-
+    public virtual void Solve(ILinearProgrammingProblemDefinition problemDefintion, ref TimeSpan executionTime,
+      ResultCollection results, CancellationToken cancellationToken) =>
+      Solve(problemDefintion, ref executionTime, results);
+
+    public virtual void Solve(ILinearProgrammingProblemDefinition problemDefinition, ref TimeSpan executionTime,
+      ResultCollection results) =>
+      Solve(problemDefinition, results, TimeLimit);
+
+    public virtual void Solve(ILinearProgrammingProblemDefinition problemDefinition, ResultCollection results,
+      TimeSpan timeLimit) {
       if (solver == null) {
-        solver = new LinearSolver(OptimizationProblemType, s => algorithm.Problem.ProblemDefinition.BuildModel(s), Name,
-          libraryName);
-      }
-
-      solver.TimeLimit = timeLimit;
-      solver.RelativeGapTolerance = algorithm.RelativeGapTolerance;
-      solver.PrimalTolerance = algorithm.PrimalTolerance;
-      solver.DualTolerance = algorithm.DualTolerance;
-      solver.Presolve = algorithm.Presolve;
-      solver.Scaling = algorithm.Scaling;
-      solver.LpAlgorithm = algorithm.LpAlgorithm;
-      solver.Incrementality = true;
-
-      if (!solver.SetSolverSpecificParameters(SolverSpecificParameters.Value))
-        throw new ArgumentException("Solver specific parameters could not be set.");
-
-      solver.Solve();
-
-      algorithm.Problem.ProblemDefinition.Analyze(solver.Solver, algorithm.Results);
-      algorithm.Results.AddOrUpdateResult(nameof(solver.ResultStatus),
-        new EnumValue<ResultStatus>(solver.ResultStatus));
-      algorithm.Results.AddOrUpdateResult($"Best{nameof(solver.ObjectiveValue)}",
-        new DoubleValue(solver.ObjectiveValue ?? double.NaN));
-
-      if (solver.IsMip) {
-        algorithm.Results.AddOrUpdateResult($"Best{nameof(solver.ObjectiveBound)}",
-          new DoubleValue(solver.ObjectiveBound ?? double.NaN));
-        algorithm.Results.AddOrUpdateResult(nameof(solver.AbsoluteGap),
-          new DoubleValue(solver.AbsoluteGap ?? double.NaN));
-        algorithm.Results.AddOrUpdateResult(nameof(solver.RelativeGap),
-          new PercentValue(solver.RelativeGap ?? double.NaN));
-      }
-
-      algorithm.Results.AddOrUpdateResult(nameof(solver.NumberOfConstraints), new IntValue(solver.NumberOfConstraints));
-      algorithm.Results.AddOrUpdateResult(nameof(solver.NumberOfVariables), new IntValue(solver.NumberOfVariables));
-
-      if (solver.IsMip) {
-        algorithm.Results.AddOrUpdateResult(nameof(solver.NumberOfNodes), new DoubleValue(solver.NumberOfNodes));
-      }
-
-      algorithm.Results.AddOrUpdateResult(nameof(solver.Iterations), new DoubleValue(solver.Iterations));
-      algorithm.Results.AddOrUpdateResult(nameof(solver.SolverVersion), new StringValue(solver.SolverVersion));
+        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 MPSolverParameters()) {
+        parameters.SetDoubleParam(MPSolverParameters.RELATIVE_MIP_GAP, RelativeGapTolerance);
+        parameters.SetDoubleParam(MPSolverParameters.PRIMAL_TOLERANCE, PrimalTolerance);
+        parameters.SetDoubleParam(MPSolverParameters.DUAL_TOLERANCE, DualTolerance);
+        parameters.SetIntegerParam(MPSolverParameters.PRESOLVE,
+          Presolve ? MPSolverParameters.PRESOLVE_ON : MPSolverParameters.PRESOLVE_OFF);
+        parameters.SetIntegerParam(MPSolverParameters.LP_ALGORITHM, (int)LpAlgorithm);
+        parameters.SetIntegerParam(MPSolverParameters.INCREMENTALITY,
+          Incrementality ? MPSolverParameters.INCREMENTALITY_ON : MPSolverParameters.INCREMENTALITY_OFF);
+        parameters.SetIntegerParam(MPSolverParameters.SCALING,
+          Scaling ? MPSolverParameters.SCALING_ON : MPSolverParameters.SCALING_OFF);
+
+        if (!solver.SetSolverSpecificParametersAsString(SolverSpecificParameters))
+          throw new ArgumentException("Solver specific parameters could not be set.");
+
+        if (!string.IsNullOrWhiteSpace(ExportModel)) {
+          var fileInfo = new FileInfo(ExportModel);
+
+          if (!fileInfo.Directory?.Exists ?? false) {
+            Directory.CreateDirectory(fileInfo.Directory.FullName);
+          }
+
+          bool exportSuccessful;
+          switch (fileInfo.Extension) {
+            case ".lp":
+              exportSuccessful = ExportAsLp(ExportModel);
+              break;
+
+            case ".mps":
+              exportSuccessful = ExportAsMps(ExportModel);
+              break;
+
+            case ".prototxt":
+              exportSuccessful = ExportAsProto(ExportModel, ProtoWriteFormat.ProtoText);
+              break;
+
+            case ".bin": // remove file extension as it is added by OR-Tools
+              exportSuccessful = ExportAsProto(Path.ChangeExtension(ExportModel, null));
+              break;
+
+            default:
+              throw new NotSupportedException("File format selected to export model is not supported.");
+          }
+        }
+
+        // TODO: show warning if file export didn't work (if exportSuccessful is false)
+
+        resultStatus = (ResultStatus)solver.Solve(parameters);
+      }
+
+      var objectiveValue = solver.Objective()?.Value();
+
+      problemDefinition.Analyze(solver, results);
+      results.AddOrUpdateResult("ResultStatus", new EnumValue<ResultStatus>(resultStatus));
+      results.AddOrUpdateResult("BestObjectiveValue", new DoubleValue(objectiveValue ?? double.NaN));
+
+      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;
+
+        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("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(OptimizationProblemType optimizationProblemType, string libraryName = null) {
+      if (!string.IsNullOrEmpty(libraryName) && !File.Exists(libraryName)) {
+        var paths = new List<string> {
+          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, (int)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;
     }
   }