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


Ignore:
Timestamp:
01/31/19 13:50:06 (3 months ago)
Author:
ddorfmei
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Documentation/Reference/ExactOptimization

    v2 v3  
    2323 * [https://scip.zib.de/index.php#download SCIP].
    2424
    25 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).
     25Make 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).
     26
     27[[Image(MixedIntegerLinearProgramming.png)]]
    2628
    2729For 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.
     
    106108using HeuristicLab.Problems.TravelingSalesman;
    107109
     110using HeuristicLab.Problems.Instances;
     111
    108112public class TravelingSalesmanLinearModel : CompiledProblemDefinition, ILinearProblemDefinition {
    109113  private Variable[,] x;
     
    118122    // Miller-Tucker-Zemlin formulation
    119123    TravelingSalesmanProblem problem = vars.Problem;
    120     DistanceMatrixHelper.CalculateDistanceMatrix(problem);
     124    CalculateDistanceMatrix(problem);   
    121125    var c = problem.DistanceMatrix;
    122126    var n = c.Rows;
     
    178182  }
    179183
    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     }
     184  private static void CalculateDistanceMatrix(TravelingSalesmanProblem problem) {
     185    if (problem.DistanceMatrix != null)
     186      return;
     187   
     188    // calculate distance matrix
     189    var distanceMeasure = GetDistanceMeasure(problem.Evaluator);
     190    var coordinates = problem.Coordinates.CloneAsMatrix();
     191   
     192    if (coordinates == null)
     193      throw new InvalidOperationException("Neither a distance matrix nor coordinates were given.");
     194   
     195    var dimension = coordinates.GetLength(0);
     196    var distanceMatrix = new DistanceMatrix(DistanceHelper.GetDistanceMatrix(distanceMeasure, coordinates, null, dimension));
     197    problem.DistanceMatrix = (DistanceMatrix)distanceMatrix.AsReadOnly();
     198  }
     199 
     200  private static DistanceMeasure GetDistanceMeasure(ITSPEvaluator evaluator) {
     201    if (evaluator is TSPEuclideanPathEvaluator)
     202      return  DistanceMeasure.Euclidean;
     203    if (evaluator is TSPRoundedEuclideanPathEvaluator)
     204      return DistanceMeasure.RoundedEuclidean;
     205    if (evaluator is TSPUpperEuclideanPathEvaluator)
     206      return DistanceMeasure.UpperEuclidean;
     207    if (evaluator is TSPGeoPathEvaluator)
     208      return DistanceMeasure.Geo;
     209    throw new InvalidOperationException("Unknown distance measure.");
    245210  }
    246211}
     
    249214== Implementing New Models in HeuristicLab ==
    250215
    251 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].
     216The 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.
    252217
    253218[[Image(ExactOptimization.png,100%)]]
     219
     220The `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.
     221
     222{{{
     223#!csharp
     224using System;
     225using System.Linq;
     226using Google.OrTools.LinearSolver;
     227using HeuristicLab.Common;
     228using HeuristicLab.Core;
     229using HeuristicLab.Data;
     230using HeuristicLab.Encodings.BinaryVectorEncoding;
     231using HeuristicLab.ExactOptimization.LinearProgramming;
     232using HeuristicLab.Optimization;
     233using HeuristicLab.Parameters;
     234using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     235using HeuristicLab.Problems.Knapsack;
     236using Variable = Google.OrTools.LinearSolver.Variable;
     237
     238public class KnapsackScript : HeuristicLab.Scripting.CSharpScriptBase {
     239  public override void Main() {
     240    var algorithm = new LinearProgrammingAlgorithm();
     241    vars.Algorithm = algorithm;
     242    algorithm.Problem.ProblemDefinition = new KnapsackLinearModel();
     243   
     244    foreach (var solver in algorithm.LinearSolverParameter.ValidValues) {
     245      Console.WriteLine("========== " + solver.Name + " ==========");
     246     
     247      algorithm.Prepare();
     248      algorithm.LinearSolver = solver;
     249      algorithm.Start();
     250     
     251      if (algorithm.Results.Any()) {
     252        algorithm.Results.ForEach(Console.WriteLine);
     253      } else {
     254        Console.WriteLine("Solver is not properly installed.");
     255      }
     256    }
     257   
     258    // you can also access the results afterwards, e.g.: 'algorithm.Runs.First().Results'   
     259  }
     260
     261  [Item("Knapsack Linear Model", "Models a 0-1 knapsack problem.")]
     262  [StorableClass]
     263  public class KnapsackLinearModel : ParameterizedNamedItem, ILinearProblemDefinition {
     264 
     265    [Storable]
     266    private IValueParameter<KnapsackProblem> problemParam;
     267 
     268    private Variable[] x;
     269 
     270    public KnapsackLinearModel() {
     271      Parameters.Add(problemParam = new ValueParameter<KnapsackProblem>("Problem", new KnapsackProblem()));
     272    }
     273 
     274    private KnapsackLinearModel(KnapsackLinearModel original, Cloner cloner)
     275      : base(original, cloner) {
     276      problemParam = cloner.Clone(original.problemParam);
     277    }
     278 
     279    [StorableConstructor]
     280    private KnapsackLinearModel(bool deserializing) : base(deserializing) { }
     281 
     282    public KnapsackProblem Problem {
     283      get { return problemParam.Value; }
     284      set { problemParam.Value = value; }
     285    }
     286 
     287    public IValueParameter<KnapsackProblem> ProblemParameter {
     288      get { return problemParam; }
     289    }
     290 
     291    public void BuildModel(Solver solver) {
     292      // Retrieve the problem data
     293      var W = Problem.KnapsackCapacity.Value;
     294      var weights = Problem.Weights;
     295      var values = Problem.Values;
     296      // Define the decision variables
     297      x = solver.MakeBoolVarArray(values.Count());
     298      // Define the constraints
     299      solver.Add(weights.Select((w, i) => w * x[i]).ToArray().Sum() <= W);
     300      // Define the objective
     301      solver.Maximize(values.Select((v, i) => v * x[i]).ToArray().Sum());
     302    }
     303 
     304    public void Analyze(Solver solver, ResultCollection results) {
     305      // Retrieve the problem data
     306      var capacity = Problem.KnapsackCapacity;
     307      var weights = Problem.Weights;
     308      var values = Problem.Values;
     309      // Retrieve the solution values of the objective and the decision variables
     310      var solution = new BinaryVector(x.Select(xi => xi.SolutionValue() == 1).ToArray());
     311      var quality = new DoubleValue(solver.Objective().Value());
     312      // Update the problem
     313      if (Problem.BestKnownQuality == null || quality.Value > Problem.BestKnownQuality.Value) {
     314        Problem.BestKnownSolution = solution;
     315        Problem.BestKnownQuality = quality;
     316      }
     317      // Update the result
     318      results.AddOrUpdateResult("BestKnapsackSolution", new KnapsackSolution(solution, quality, capacity, weights, values));
     319    }
     320 
     321    public override IDeepCloneable Clone(Cloner cloner) {
     322      return new KnapsackLinearModel(this, cloner);
     323    }
     324  }
     325}
     326}}}