Changeset 16233 for branches/2931_OR-Tools_LP_MIP/HeuristicLab.MathematicalOptimization/3.3/LinearProgramming/Algorithms/LinearProgrammingAlgorithm.cs

Timestamp:

10/17/18 17:51:26 (6 years ago)

Author:

ddorfmei

Message:

#2931:

• added all available parameters OR-Tools's linear_solver to LinearProgrammingAlgorithm
  • added necessary parameter enums
• moved solving logic to Solver
  • created IncrementalSolver, ExternalSolver, ExternalIncrementalSolver
  • added logic for solvers that can be stopped and resumed
• added SupportsStop property to BasicAlgorithm
• added quality per time chart for incremental solvers

File:

• branches/2931_OR-Tools_LP_MIP/HeuristicLab.MathematicalOptimization/3.3/LinearProgramming/Algorithms/LinearProgrammingAlgorithm.cs (modified) (8 diffs)

branches/2931_OR-Tools_LP_MIP/HeuristicLab.MathematicalOptimization/3.3/LinearProgramming/Algorithms/LinearProgrammingAlgorithm.cs

@@ -1 +1 @@
 using System;
 using System.Threading;
+using Google.OrTools.LinearSolver;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
 using HeuristicLab.Data;
+using HeuristicLab.MathematicalOptimization.LinearProgramming.Algorithms.Solvers;
+using HeuristicLab.MathematicalOptimization.LinearProgramming.Algorithms.Solvers.Base;
 using HeuristicLab.MathematicalOptimization.LinearProgramming.Problems;
 using HeuristicLab.Optimization;
@@ -10 +13 @@
 
 namespace HeuristicLab.MathematicalOptimization.LinearProgramming.Algorithms {
-  [Item("Linear Programming Algorithm", "")]
-  [Creatable(CreatableAttribute.Categories.Algorithms, Priority = 162)]
+
+  [Item("Linear/Mixed Integer Programming (LP/MIP)", "")]
+  [Creatable(CreatableAttribute.Categories.SingleSolutionAlgorithms)]
   [StorableClass]
   public class LinearProgrammingAlgorithm : BasicAlgorithm {
+
+    [Storable]
+    private readonly IFixedValueParameter<DoubleValue> dualToleranceParam;
+
+    [Storable]
+    private readonly IFixedValueParameter<EnumValue<LpAlgorithmValues>> lpAlgorithmParam;
+
+    [Storable]
+    private readonly IFixedValueParameter<BoolValue> presolveParam;
+
+    [Storable]
+    private readonly IFixedValueParameter<DoubleValue> primalToleranceParam;
+
+    [Storable]
+    private readonly IFixedValueParameter<DoubleValue> relativeGapToleranceParam;
+
+    [Storable]
+    private readonly IFixedValueParameter<BoolValue> scalingParam;
 
     [Storable]
@@ -19 +41 @@
 
     [Storable]
-    private readonly IFixedValueParameter<DoubleValue> relativeGapToleranceParam;
-
-    [Storable]
     private readonly IFixedValueParameter<TimeSpanValue> timeLimitParam;
 
     public LinearProgrammingAlgorithm() {
-      Parameters.Add(solverParam = new ConstrainedValueParameter<ISolver>(nameof(Solver)));
-      Parameters.Add(relativeGapToleranceParam = new FixedValueParameter<DoubleValue>(nameof(RelativeGapTolerance), new DoubleValue()));
-      Parameters.Add(timeLimitParam = new FixedValueParameter<TimeSpanValue>(nameof(TimeLimit), new TimeSpanValue()));
+      Parameters.Add(solverParam =
+        new ConstrainedValueParameter<ISolver>(nameof(Solver), "The solver used to solve the model."));
+      Parameters.Add(relativeGapToleranceParam = new FixedValueParameter<DoubleValue>(nameof(RelativeGapTolerance),
+        "Limit for relative MIP gap.", new DoubleValue(MPSolverParameters.kDefaultRelativeMipGap)));
+      Parameters.Add(timeLimitParam = new FixedValueParameter<TimeSpanValue>(nameof(TimeLimit),
+        "Limit for runtime. Set to zero for unlimited runtime.", new TimeSpanValue()));
+      Parameters.Add(presolveParam =
+        new FixedValueParameter<BoolValue>(nameof(Presolve), "Advanced usage: presolve mode.", new BoolValue()));
+      Parameters.Add(lpAlgorithmParam = new FixedValueParameter<EnumValue<LpAlgorithmValues>>(nameof(LpAlgorithm),
+        "Algorithm to solve linear programs.", new EnumValue<LpAlgorithmValues>(LpAlgorithmValues.DualSimplex)));
+      Parameters.Add(dualToleranceParam = new FixedValueParameter<DoubleValue>(nameof(DualTolerance),
+        "Advanced usage: tolerance for dual feasibility of basic solutions.",
+        new DoubleValue(MPSolverParameters.kDefaultDualTolerance)));
+      Parameters.Add(primalToleranceParam = new FixedValueParameter<DoubleValue>(nameof(PrimalTolerance),
+        "Advanced usage: tolerance for primal feasibility of basic solutions. " +
+        "This does not control the integer feasibility tolerance of integer " +
+        "solutions for MIP or the tolerance used during presolve.",
+        new DoubleValue(MPSolverParameters.kDefaultPrimalTolerance)));
+      Parameters.Add(scalingParam = new FixedValueParameter<BoolValue>(nameof(Scaling),
+        "Advanced usage: enable or disable matrix scaling.", new BoolValue()));
 
       Problem = new LinearProgrammingProblem();
@@ -42 +78 @@
     [StorableConstructor]
     private LinearProgrammingAlgorithm(bool deserializing)
-      : base(deserializing) { }
+      : base(deserializing) {
+    }
 
     private LinearProgrammingAlgorithm(LinearProgrammingAlgorithm original, Cloner cloner)
@@ -49 +86 @@
       relativeGapToleranceParam = cloner.Clone(original.relativeGapToleranceParam);
       timeLimitParam = cloner.Clone(original.timeLimitParam);
+      presolveParam = cloner.Clone(original.presolveParam);
+      lpAlgorithmParam = cloner.Clone(original.lpAlgorithmParam);
+      dualToleranceParam = cloner.Clone(original.dualToleranceParam);
+      primalToleranceParam = cloner.Clone(original.primalToleranceParam);
+      scalingParam = cloner.Clone(original.scalingParam);
     }
 
-    public ISolver Solver {
-      get => solverParam.Value;
-      set => solverParam.Value = value;
+    public double DualTolerance {
+      get => dualToleranceParam.Value.Value;
+      set => dualToleranceParam.Value.Value = value;
+    }
+
+    public LpAlgorithmValues LpAlgorithm {
+      get => lpAlgorithmParam.Value.Value;
+      set => lpAlgorithmParam.Value.Value = value;
+    }
+
+    public bool Presolve {
+      get => presolveParam.Value.Value;
+      set => presolveParam.Value.Value = value;
+    }
+
+    public double PrimalTolerance {
+      get => primalToleranceParam.Value.Value;
+      set => primalToleranceParam.Value.Value = value;
     }
 
@@ -62 +119 @@
 
     public override Type ProblemType { get; } = typeof(LinearProgrammingProblem);
+
     public double RelativeGapTolerance {
       get => relativeGapToleranceParam.Value.Value;
@@ -69 +127 @@
     public override ResultCollection Results { get; } = new ResultCollection();
 
-    public override bool SupportsPause { get; } = false;
+    public bool Scaling {
+      get => scalingParam.Value.Value;
+      set => scalingParam.Value.Value = value;
+    }
+
+    public ISolver Solver {
+      get => solverParam.Value;
+      set => solverParam.Value = value;
+    }
+
+    public override bool SupportsPause => Solver.SupportsPause;
+
+    public override bool SupportsStop => Solver.SupportsStop;
 
     public TimeSpan TimeLimit {
@@ -77 +147 @@
 
     public override IDeepCloneable Clone(Cloner cloner) => new LinearProgrammingAlgorithm(this, cloner);
-    protected override void Run(CancellationToken cancellationToken) {
-      using (var solver = LinearSolver.CreateSolver(Solver.OptimizationProblemType, Name,
-        Solver.LibraryName ?? string.Empty, s => Problem.ProblemDefinition.BuildModel(s))) {
-        solver.RelativeGapTolerance = RelativeGapTolerance;
-        solver.TimeLimit = TimeLimit;
 
-        solver.Solve();
+    public override void Pause() {
+      base.Pause();
+      Solver.Interrupt();
+    }
 
-        Problem.ProblemDefinition.Analyze(solver.Solver, Results);
-        Results.AddOrUpdateResult("Result Status", new EnumValue<ResultStatus>(solver.ResultStatus));
-        Results.AddOrUpdateResult("Best Objective Value", new DoubleValue(solver.ObjectiveValue ?? double.NaN));
-        Results.AddOrUpdateResult("Absolute Gap", new DoubleValue(solver.AbsoluteGap ?? double.NaN));
-        Results.AddOrUpdateResult("Relative Gap", new DoubleValue(solver.RelativeGap ?? double.NaN));
-        Results.AddOrUpdateResult("Number of Constraints", new IntValue(solver.NumberOfConstraints));
-        Results.AddOrUpdateResult("Number of Variables", new IntValue(solver.NumberOfVariables));
-        Results.AddOrUpdateResult("Number of Nodes", new DoubleValue(solver.NumberOfNodes));
-        Results.AddOrUpdateResult("Iterations", new DoubleValue(solver.Iterations));
+    public override void Prepare() {
+      base.Prepare();
+      Results.Clear();
+
+      foreach (var solver in solverParam.ValidValues) {
+        solver.Reset();
       }
     }
+
+    public override void Stop() {
+      base.Stop();
+      Solver.Interrupt();
+    }
+    protected override void Initialize(CancellationToken cancellationToken) {
+      base.Initialize(cancellationToken);
+    }
+    protected override void Run(CancellationToken cancellationToken) => Solver.Solve(this, cancellationToken);
   }
 }