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


Ignore:
Timestamp:
01/30/19 16:27:21 (3 weeks ago)
Author:
ddorfmei
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Documentation/Reference/ExactOptimization

    v1 v2  
    1313 * Network Flows.
    1414
    15 For a complete overview, see https://developers.google.com/optimization/introduction/overview. You can use all solvers in HeuristicLab, just create a C# Script and make sure the [https://aka.ms/vs/15/release/VC_redist.x64.exe Microsoft Visual C++ 2017 Redistributable (x64)] is installed. Note that most linear and mixed-integer solvers must be installed (and licensed) separately, see the next section for details. the `HeuristicLab.OrTools` plugin is currently only available on 64-bit Windows.
     15For a complete overview, see https://developers.google.com/optimization/introduction/overview. You can use all solvers in HeuristicLab, just create a C# Script and make sure the [https://aka.ms/vs/15/release/VC_redist.x64.exe Microsoft Visual C++ 2017 Redistributable (x64)] is installed. Note that most linear and mixed-integer solvers must be installed (and licensed) separately, see the [#Mixed-IntegerLinearProgrammingMIPMILP next section] for details. The `HeuristicLab.OrTools` plugin is currently only available on 64-bit Windows.
    1616
    1717== Mixed-Integer (Linear) Programming (MIP, MILP) ==
    1818
    19 OR-Tools contains a [https://developers.google.com/optimization/reference/linear_solver/linear_solver/ linear solver wrapper] that can be used to define a MIP model once and solve it with a range of MIP solvers. Some solvers are already built into OR-Tools (BOP, Cbc, Clp, Glop) but for most solvers OR-Tools have to be built from source code, this version then has a dependency on the external solver. HeurisicLab includes a custom version of OR-Tools that allows users to simply install additional solvers without depending on them.
     19OR-Tools contains a [https://developers.google.com/optimization/reference/linear_solver/linear_solver/ linear solver wrapper] that can be used to define a MIP model once and solve it with a range of MIP solvers. Some solvers are already built into OR-Tools (BOP, Cbc, Clp, Glop) but for most solvers OR-Tools have to be built from source code, this version then has a dependency on the external solver. HeurisicLab includes a custom version of OR-Tools that allows users to simply install additional solvers without depending on them. Download the solvers here, they are free for academic use:
     20 * [https://ibm.onthehub.com/WebStore/ProductSearchOfferingList.aspx?srch=ilog%20cplex CPLEX],
     21 * [http://www.gurobi.com/downloads/download-center Gurobi],
     22 * [https://www.gnu.org/software/glpk/#TOCdownloading GLPK] (currently not supported by HeuristicLab) and
     23 * [https://scip.zib.de/index.php#download SCIP].
     24
     25Make 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).
    2026
    2127For 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.
    2228
    23 The `HeuristicLab.ExactOptimization` plugin provides a GUI for MIP, just create a new ''Mixed-Integer Linear Programming (LP, MIP)'' algorithm, found under Algorithms, Exact. You can either load your model from a file (MPS, Google OR-Tools Protocol Buffers files) or define your model using a C# script and directly accessing the linear solver wrapper. The next two sections show the implementation of a [#KnapsackProblemKSP Knapsack Problem (KSP)] and a [#TravellingSalesmanProblemTSP Travelling Salesman Problem (TSP)].
    24 
    25 === Knapsack Problem (KSP) ===
    26 
    27 === Travelling Salesman Problem (TSP) ===
     29The `HeuristicLab.ExactOptimization` plugin provides a GUI for MIP, just create a new ''Mixed-Integer Linear Programming (LP, MIP)'' algorithm, found under ''Algorithms'', ''Exact''. You can either load your model from a file (MPS, Google OR-Tools Protocol Buffers files) or define your model using C# and directly accessing the linear solver wrapper. The [#DefininaMIPModel next section] shows the implementation of a [#KnapsackProblemKSP Knapsack Problem (KSP)] and a [#TravelingSalesmanProblemTSP Traveling Salesman Problem (TSP)].
     30
     31=== Defining a MIP Model ===
     32
     33A programmable MIP model requires you to implement the `BuildModel` method where you must define the decision variables, the constraints and the objective of your model. The `Analyze` method is used to retrieve the solution values of the decision variables, which can be added to the results to be accessible in the GUI. The `Initialize` method can be used for initialization.
     34
     35==== Knapsack Problem (KSP) ====
     36
     37The following MIP model can be pasted in HeuristicLab in the ''Problem'' tab of a ''Mixed-Integer Linear Programming (LP, MIP)'' algorithm. The `Analyze` method shows the definition of the [https://en.wikipedia.org/wiki/Knapsack_problem#Definition 0-1 Knapsack Problem]. Note that you can drag any instance of a ''Knapsack Problem (KSP)'' to the variables list and rename it to `Problem` (remove the default problem first).
     38
     39{{{
     40#!csharp
     41using System;
     42using System.Linq;
     43using System.Text;
     44using Google.OrTools.LinearSolver;
     45using HeuristicLab.Data;
     46using HeuristicLab.Encodings.BinaryVectorEncoding;
     47using HeuristicLab.ExactOptimization.LinearProgramming;
     48using HeuristicLab.Optimization;
     49using HeuristicLab.Problems.Knapsack;
     50
     51public class KnapsackLinearModel : CompiledProblemDefinition, ILinearProblemDefinition {
     52  private Variable[] x;
     53
     54  public override void Initialize() {
     55    if (vars.Contains("Problem"))
     56      return;
     57    vars["Problem"] = new KnapsackProblem();
     58  }
     59
     60  public void BuildModel(Solver solver) {
     61    // Retrieve the problem data
     62    var W = vars.Problem.KnapsackCapacity.Value;
     63    IntArray weights = vars.Problem.Weights;
     64    IntArray values = vars.Problem.Values;
     65    // Define the decision variables
     66    x = solver.MakeBoolVarArray(values.Count());
     67    // Define the constraints
     68    solver.Add(weights.Select((w, i) => w * x[i]).ToArray().Sum() <= W);
     69    // Define the objective
     70    solver.Maximize(values.Select((v, i) => v * x[i]).ToArray().Sum());
     71  }
     72
     73  public void Analyze(Solver solver, ResultCollection results) {
     74    // Retrieve the problem data
     75    var capacity = vars.Problem.KnapsackCapacity;
     76    var weights = vars.Problem.Weights;
     77    var values = vars.Problem.Values;
     78    // Retrieve the solution values of the objective and the decision variables
     79    var solution = new BinaryVector(x.Select(xi => xi.SolutionValue() == 1).ToArray());
     80    var quality = new DoubleValue(solver.Objective().Value());
     81    // Update the problem
     82    if (vars.Problem.BestKnownQuality == null || quality.Value > vars.Problem.BestKnownQuality.Value) {
     83      vars.Problem.BestKnownSolution = solution;
     84      vars.Problem.BestKnownQuality = quality;
     85    }
     86    // Update the result
     87    results.AddOrUpdateResult("BestKnapsackSolution", new KnapsackSolution(solution, quality, capacity, weights, values));
     88  }
     89}
     90}}}
     91
     92==== Traveling Salesman Problem (TSP) ====
     93
     94The following MIP model can be pasted in HeuristicLab in the ''Problem'' tab of a ''Mixed-Integer Linear Programming (LP, MIP)'' algorithm. The `Analyze` method shows the definition of the [https://en.wikipedia.org/wiki/Travelling_salesman_problem#Miller-Tucker-Zemlin_formulation Miller-Tucker-Zemlin formulation of the Traveling Salesman Problem]. Note that you can drag any instance of a ''Traveling Salesman Problem (TSP)'' to the variables list and rename it to `Problem` (remove the default problem first).
     95
     96{{{
     97#!csharp
     98using System;
     99using System.Collections.Generic;
     100using System.Linq;
     101using Google.OrTools.LinearSolver;
     102using HeuristicLab.Data;
     103using HeuristicLab.Encodings.PermutationEncoding;
     104using HeuristicLab.ExactOptimization.LinearProgramming;
     105using HeuristicLab.Optimization;
     106using HeuristicLab.Problems.TravelingSalesman;
     107
     108public class TravelingSalesmanLinearModel : CompiledProblemDefinition, ILinearProblemDefinition {
     109  private Variable[,] x;
     110
     111  public override void Initialize() {
     112    if (vars.Contains("Problem"))
     113      return;
     114    vars["Problem"] = new TravelingSalesmanProblem();
     115  }
     116
     117  public void BuildModel(Solver solver) {
     118    // Miller-Tucker-Zemlin formulation
     119    TravelingSalesmanProblem problem = vars.Problem;
     120    DistanceMatrixHelper.CalculateDistanceMatrix(problem);
     121    var c = problem.DistanceMatrix;
     122    var n = c.Rows;
     123    var N = Enumerable.Range(0, n).ToList();
     124    // Define the decision variables
     125    x = solver.MakeBoolVarArray(n, n);
     126    var u = solver.MakeNumVarArray(n, 0, n - 1);
     127    // Define the constraints
     128    foreach (var j in N) {
     129      solver.Add(N.Where(i => i != j).Select(i => x[i, j]).ToArray().Sum() == 1);
     130    }
     131    foreach (var i in N) {
     132      solver.Add(N.Where(j => j != i).Select(j => x[i, j]).ToArray().Sum() == 1);
     133    }
     134    for (var i = 1; i < n; i++) {
     135      for (var j = 1; j < n; j++) {
     136        solver.Add(u[i] - u[j] + n * x[i, j] <= n - 1);
     137      }
     138    }
     139    // Define the objective
     140    solver.Minimize(
     141      (from i in N
     142       from j in N
     143       where i != j
     144       select c[i, j] * x[i, j]
     145      ).ToArray().Sum()
     146    );
     147  }
     148
     149  public void Analyze(Solver solver, ResultCollection results) {
     150    // Retrieve the problem data
     151    var coordinates = vars.Problem.Coordinates;
     152    // Retrieve the solution values of the objective and the decision variables
     153    var solution = new Permutation(PermutationTypes.RelativeUndirected, GetTour(x));
     154    var quality = new DoubleValue(solver.Objective().Value());
     155    // Update the problem
     156    if (vars.Problem.BestKnownQuality == null || quality.Value < vars.Problem.BestKnownQuality.Value) {
     157      vars.Problem.BestKnownSolution = solution;
     158      vars.Problem.BestKnownQuality = quality;
     159    }
     160    // Update the result
     161    results.AddOrUpdateResult("Best TSP Solution", new PathTSPTour(coordinates, solution, quality));
     162  }
     163 
     164  private static int[] GetTour(Variable[,] x) {
     165    var n = x.GetLength(0);
     166    var tour = new List<int> { 0 };
     167
     168    while (true) {
     169      for (var i = 0; i < n; i++) {
     170        if (x[tour.Last(), i].SolutionValue() > 0) {
     171          if (i == tour[0])
     172            return tour.ToArray();
     173          tour.Add(i);
     174          break;
     175        }
     176      }
     177    }
     178  }
     179
     180  public static class DistanceMatrixHelper {
     181    private static double CalculateDistanceEuclideanPath(double x1, double y1, double x2, double y2) {
     182      return Math.Sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
     183    }
     184
     185    private static double CalculateDistanceRoundedEuclideanPath(double x1, double y1, double x2, double y2) {
     186      return Math.Round(Math.Sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
     187    }
     188
     189    private static double CalculateDistanceUpperEuclideanPath(double x1, double y1, double x2, double y2) {
     190      return Math.Ceiling(Math.Sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
     191    }
     192
     193    private const double PI = 3.141592;
     194    private const double RADIUS = 6378.388;
     195
     196    private static double CalculateDistanceGeoPath(double x1, double y1, double x2, double y2) {
     197      double latitude1, longitude1, latitude2, longitude2;
     198      double q1, q2, q3;
     199      double length;
     200
     201      latitude1 = ConvertToRadian(x1);
     202      longitude1 = ConvertToRadian(y1);
     203      latitude2 = ConvertToRadian(x2);
     204      longitude2 = ConvertToRadian(y2);
     205
     206      q1 = Math.Cos(longitude1 - longitude2);
     207      q2 = Math.Cos(latitude1 - latitude2);
     208      q3 = Math.Cos(latitude1 + latitude2);
     209
     210      length = (int)(RADIUS * Math.Acos(0.5 * ((1.0 + q1) * q2 - (1.0 - q1) * q3)) + 1.0);
     211      return (length);
     212    }
     213
     214    private static double ConvertToRadian(double x) {
     215      return PI * (Math.Truncate(x) + 5.0 * (x - Math.Truncate(x)) / 3.0) / 180.0;
     216    }
     217
     218    private static double CalculateDistance(ITSPEvaluator evaluator, double x1, double y1, double x2, double y2) {
     219      if (evaluator is TSPEuclideanPathEvaluator)
     220        return CalculateDistanceEuclideanPath(x1, y1, x2, y2);
     221      if (evaluator is TSPRoundedEuclideanPathEvaluator)
     222        return CalculateDistanceRoundedEuclideanPath(x1, y1, x2, y2);
     223      if (evaluator is TSPUpperEuclideanPathEvaluator)
     224        return CalculateDistanceUpperEuclideanPath(x1, y1, x2, y2);
     225      if (evaluator is TSPGeoPathEvaluator)
     226        return CalculateDistanceGeoPath(x1, y1, x2, y2);
     227      throw new InvalidOperationException("Unkown distance measure.");
     228    }
     229
     230    public static void CalculateDistanceMatrix(TravelingSalesmanProblem problem) {
     231      var dm = problem.DistanceMatrix;
     232      if (dm != null)
     233        return;
     234     
     235      // calculate distance matrix
     236      var c = problem.Coordinates;
     237      if (c == null) throw new InvalidOperationException("Neither a distance matrix nor coordinates were given.");
     238      dm = new DistanceMatrix(c.Rows, c.Rows);
     239      for (var i = 0; i < dm.Rows; i++) {
     240        for (var j = 0; j < dm.Columns; j++)     
     241          dm[i, j] = CalculateDistance(problem.Evaluator, c[i, 0], c[i, 1], c[j, 0], c[j, 1]);
     242      }
     243      problem.DistanceMatrix = (DistanceMatrix)dm.AsReadOnly();
     244    }
     245  }
     246}
     247}}}
    28248
    29249== Implementing New Models in HeuristicLab ==
    30250
     251The 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].
     252
     253[[Image(ExactOptimization.png,100%)]]