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."); |
| 219 | |
| 220 | 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. |
| 221 | |
| 222 | {{{ |
| 223 | #!csharp |
| 224 | using System; |
| 225 | using System.Linq; |
| 226 | using Google.OrTools.LinearSolver; |
| 227 | using HeuristicLab.Common; |
| 228 | using HeuristicLab.Core; |
| 229 | using HeuristicLab.Data; |
| 230 | using HeuristicLab.Encodings.BinaryVectorEncoding; |
| 231 | using HeuristicLab.ExactOptimization.LinearProgramming; |
| 232 | using HeuristicLab.Optimization; |
| 233 | using HeuristicLab.Parameters; |
| 234 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; |
| 235 | using HeuristicLab.Problems.Knapsack; |
| 236 | using Variable = Google.OrTools.LinearSolver.Variable; |
| 237 | |
| 238 | public 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 | }}} |