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) === |
| 29 | 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 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 | |
| 33 | A 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 | |
| 37 | The 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 |
| 41 | using System; |
| 42 | using System.Linq; |
| 43 | using System.Text; |
| 44 | using Google.OrTools.LinearSolver; |
| 45 | using HeuristicLab.Data; |
| 46 | using HeuristicLab.Encodings.BinaryVectorEncoding; |
| 47 | using HeuristicLab.ExactOptimization.LinearProgramming; |
| 48 | using HeuristicLab.Optimization; |
| 49 | using HeuristicLab.Problems.Knapsack; |
| 50 | |
| 51 | public 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 | |
| 94 | The 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 |
| 98 | using System; |
| 99 | using System.Collections.Generic; |
| 100 | using System.Linq; |
| 101 | using Google.OrTools.LinearSolver; |
| 102 | using HeuristicLab.Data; |
| 103 | using HeuristicLab.Encodings.PermutationEncoding; |
| 104 | using HeuristicLab.ExactOptimization.LinearProgramming; |
| 105 | using HeuristicLab.Optimization; |
| 106 | using HeuristicLab.Problems.TravelingSalesman; |
| 107 | |
| 108 | public 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 | }}} |