Changes between Version 2 and Version 3 of Documentation/Reference/ExactOptimization

Timestamp:

01/31/19 13:50:06 (5 years ago)

Author:

ddorfmei

Comment:

--

Documentation/Reference/ExactOptimization

@@ -23 +23 @@
  * [https://scip.zib.de/index.php#download SCIP].
 
-Make sure that the solver you install is added to the environment variable `Path` and the `LibraryName` property of the solver in he Algorithm view is set to the correct name of the solver DLL (e.g. `cplex1280.dll` for version 12.8.0 of CPLEX). The default values for the solver DLLs can be set in the configuration file of HeuristicLab. Note that most solvers offer to change the `ProblemType` property to `LinearProgramming`, the solver then solves the linear programming relaxation of your model (all integer constraints are removed).
+Make sure that the solver you install is added to the environment variable `Path` and the `LibraryName` property of the solver in the Algorithm view is set to the correct name of the solver DLL (e.g. `cplex1280.dll` for version 12.8.0 of CPLEX). The default values for the solver DLLs can be set in the configuration file of HeuristicLab. Note that most solvers offer to change the `ProblemType` property to `LinearProgramming`, the solver then solves the linear programming relaxation of your model (all integer constraints are removed).
+
+[[Image(MixedIntegerLinearProgramming.png)]]
 
 For a general introduction to MIP and a simple model implemented using the linear solver wrapper, see https://developers.google.com/optimization/mip/integer_opt. For further examples demonstrating more advanced usage of the linear solver wrapper using the C# API, see https://github.com/google/or-tools/tree/master/examples/dotnet.
@@ -106 +108 @@
 using HeuristicLab.Problems.TravelingSalesman;
 
+using HeuristicLab.Problems.Instances;
+
 public class TravelingSalesmanLinearModel : CompiledProblemDefinition, ILinearProblemDefinition {
   private Variable[,] x;
@@ -118 +122 @@
     // Miller-Tucker-Zemlin formulation
     TravelingSalesmanProblem problem = vars.Problem;
-    DistanceMatrixHelper.CalculateDistanceMatrix(problem);
+    CalculateDistanceMatrix(problem);   
     var c = problem.DistanceMatrix;
     var n = c.Rows;
@@ -178 +182 @@
   }
 
-  public static class DistanceMatrixHelper {
-    private static double CalculateDistanceEuclideanPath(double x1, double y1, double x2, double y2) {
-      return Math.Sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
-    }
-
-    private static double CalculateDistanceRoundedEuclideanPath(double x1, double y1, double x2, double y2) {
-      return Math.Round(Math.Sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
-    }
-
-    private static double CalculateDistanceUpperEuclideanPath(double x1, double y1, double x2, double y2) {
-      return Math.Ceiling(Math.Sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
-    }
-
-    private const double PI = 3.141592;
-    private const double RADIUS = 6378.388;
-
-    private static double CalculateDistanceGeoPath(double x1, double y1, double x2, double y2) {
-      double latitude1, longitude1, latitude2, longitude2;
-      double q1, q2, q3;
-      double length;
-
-      latitude1 = ConvertToRadian(x1);
-      longitude1 = ConvertToRadian(y1);
-      latitude2 = ConvertToRadian(x2);
-      longitude2 = ConvertToRadian(y2);
-
-      q1 = Math.Cos(longitude1 - longitude2);
-      q2 = Math.Cos(latitude1 - latitude2);
-      q3 = Math.Cos(latitude1 + latitude2);
-
-      length = (int)(RADIUS * Math.Acos(0.5 * ((1.0 + q1) * q2 - (1.0 - q1) * q3)) + 1.0);
-      return (length);
-    }
-
-    private static double ConvertToRadian(double x) {
-      return PI * (Math.Truncate(x) + 5.0 * (x - Math.Truncate(x)) / 3.0) / 180.0;
-    }
-
-    private static double CalculateDistance(ITSPEvaluator evaluator, double x1, double y1, double x2, double y2) {
-      if (evaluator is TSPEuclideanPathEvaluator)
-        return CalculateDistanceEuclideanPath(x1, y1, x2, y2);
-      if (evaluator is TSPRoundedEuclideanPathEvaluator)
-        return CalculateDistanceRoundedEuclideanPath(x1, y1, x2, y2);
-      if (evaluator is TSPUpperEuclideanPathEvaluator)
-        return CalculateDistanceUpperEuclideanPath(x1, y1, x2, y2);
-      if (evaluator is TSPGeoPathEvaluator)
-        return CalculateDistanceGeoPath(x1, y1, x2, y2);
-      throw new InvalidOperationException("Unkown distance measure.");
-    }
-
-    public static void CalculateDistanceMatrix(TravelingSalesmanProblem problem) {
-      var dm = problem.DistanceMatrix;
-      if (dm != null)
-        return;
-      
-      // calculate distance matrix
-      var c = problem.Coordinates;
-      if (c == null) throw new InvalidOperationException("Neither a distance matrix nor coordinates were given.");
-      dm = new DistanceMatrix(c.Rows, c.Rows);
-      for (var i = 0; i < dm.Rows; i++) {
-        for (var j = 0; j < dm.Columns; j++)      
-          dm[i, j] = CalculateDistance(problem.Evaluator, c[i, 0], c[i, 1], c[j, 0], c[j, 1]);
-      }
-      problem.DistanceMatrix = (DistanceMatrix)dm.AsReadOnly();
-    }
+  private static void CalculateDistanceMatrix(TravelingSalesmanProblem problem) {
+    if (problem.DistanceMatrix != null)
+      return;
+    
+    // calculate distance matrix
+    var distanceMeasure = GetDistanceMeasure(problem.Evaluator);
+    var coordinates = problem.Coordinates.CloneAsMatrix();
+    
+    if (coordinates == null)
+      throw new InvalidOperationException("Neither a distance matrix nor coordinates were given.");
+    
+    var dimension = coordinates.GetLength(0);
+    var distanceMatrix = new DistanceMatrix(DistanceHelper.GetDistanceMatrix(distanceMeasure, coordinates, null, dimension));
+    problem.DistanceMatrix = (DistanceMatrix)distanceMatrix.AsReadOnly();
+  }
+  
+  private static DistanceMeasure GetDistanceMeasure(ITSPEvaluator evaluator) {
+    if (evaluator is TSPEuclideanPathEvaluator)
+      return  DistanceMeasure.Euclidean;
+    if (evaluator is TSPRoundedEuclideanPathEvaluator)
+      return DistanceMeasure.RoundedEuclidean;
+    if (evaluator is TSPUpperEuclideanPathEvaluator)
+      return DistanceMeasure.UpperEuclidean;
+    if (evaluator is TSPGeoPathEvaluator)
+      return DistanceMeasure.Geo;
+    throw new InvalidOperationException("Unknown distance measure.");
   }
 }
@@ -249 +214 @@
 == Implementing New Models in HeuristicLab ==
 
-The class diagram below shows the simplified architecture of the `HeuristicLab.ExactOptimization` plugin. To implement a new model that can be easily accessed within HeuristicLab, implement the `ILinearProblemDefintion` interface. The `BuildModel` method is used to define your model using the linear solver wrapper of OR-Tools, the `Analyze` method is used to retrieve the solution values of your decision variables. As this works almost the same as defining a programmable model withing the GUI of HeuristicLab, you can have a look at the [#DefiningaMIPModel examples provided above].
+The class diagram below shows the simplified architecture of the `HeuristicLab.ExactOptimization` plugin. To implement a new model that can be easily accessed within HeuristicLab, implement the `ILinearProblemDefintion` interface.
 
 [[Image(ExactOptimization.png,100%)]]
+
+The `BuildModel` method is used to define your model using the linear solver wrapper of OR-Tools, the `Analyze` method is used to retrieve the solution values of your decision variables. The following C# Script shows the implementation of the 0-1 Knapsack Problem (class `KnapsackLinearModel`), which is quite similar to the [#KnapsackProblemKSP example script provided above], and the usage of this model (in the method `Main`) by solving it with all available solvers.
+
+{{{
+#!csharp
+using System;
+using System.Linq;
+using Google.OrTools.LinearSolver;
+using HeuristicLab.Common;
+using HeuristicLab.Core;
+using HeuristicLab.Data;
+using HeuristicLab.Encodings.BinaryVectorEncoding;
+using HeuristicLab.ExactOptimization.LinearProgramming;
+using HeuristicLab.Optimization;
+using HeuristicLab.Parameters;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Problems.Knapsack;
+using Variable = Google.OrTools.LinearSolver.Variable;
+
+public class KnapsackScript : HeuristicLab.Scripting.CSharpScriptBase {
+  public override void Main() {
+    var algorithm = new LinearProgrammingAlgorithm();
+    vars.Algorithm = algorithm;
+    algorithm.Problem.ProblemDefinition = new KnapsackLinearModel();
+    
+    foreach (var solver in algorithm.LinearSolverParameter.ValidValues) {
+      Console.WriteLine("========== " + solver.Name + " ==========");
+      
+      algorithm.Prepare();
+      algorithm.LinearSolver = solver;
+      algorithm.Start();
+      
+      if (algorithm.Results.Any()) {
+        algorithm.Results.ForEach(Console.WriteLine);
+      } else {
+        Console.WriteLine("Solver is not properly installed.");
+      }
+    }
+    
+    // you can also access the results afterwards, e.g.: 'algorithm.Runs.First().Results'    
+  }
+
+  [Item("Knapsack Linear Model", "Models a 0-1 knapsack problem.")]
+  [StorableClass]
+  public class KnapsackLinearModel : ParameterizedNamedItem, ILinearProblemDefinition {
+  
+    [Storable]
+    private IValueParameter<KnapsackProblem> problemParam;
+  
+    private Variable[] x;
+  
+    public KnapsackLinearModel() {
+      Parameters.Add(problemParam = new ValueParameter<KnapsackProblem>("Problem", new KnapsackProblem()));
+    }
+  
+    private KnapsackLinearModel(KnapsackLinearModel original, Cloner cloner)
+      : base(original, cloner) {
+      problemParam = cloner.Clone(original.problemParam);
+    }
+  
+    [StorableConstructor]
+    private KnapsackLinearModel(bool deserializing) : base(deserializing) { }
+  
+    public KnapsackProblem Problem {
+      get { return problemParam.Value; }
+      set { problemParam.Value = value; }
+    }
+  
+    public IValueParameter<KnapsackProblem> ProblemParameter {
+      get { return problemParam; }
+    }
+  
+    public void BuildModel(Solver solver) {
+      // Retrieve the problem data
+      var W = Problem.KnapsackCapacity.Value;
+      var weights = Problem.Weights;
+      var values = Problem.Values;
+      // Define the decision variables
+      x = solver.MakeBoolVarArray(values.Count());
+      // Define the constraints
+      solver.Add(weights.Select((w, i) => w * x[i]).ToArray().Sum() <= W);
+      // Define the objective
+      solver.Maximize(values.Select((v, i) => v * x[i]).ToArray().Sum());
+    }
+  
+    public void Analyze(Solver solver, ResultCollection results) {
+      // Retrieve the problem data
+      var capacity = Problem.KnapsackCapacity;
+      var weights = Problem.Weights;
+      var values = Problem.Values;
+      // Retrieve the solution values of the objective and the decision variables
+      var solution = new BinaryVector(x.Select(xi => xi.SolutionValue() == 1).ToArray());
+      var quality = new DoubleValue(solver.Objective().Value());
+      // Update the problem
+      if (Problem.BestKnownQuality == null || quality.Value > Problem.BestKnownQuality.Value) {
+        Problem.BestKnownSolution = solution;
+        Problem.BestKnownQuality = quality;
+      }
+      // Update the result
+      results.AddOrUpdateResult("BestKnapsackSolution", new KnapsackSolution(solution, quality, capacity, weights, values));
+    }
+  
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new KnapsackLinearModel(this, cloner);
+    }
+  }
+}
+}}}