source: branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/LocalSolverNet/GQAPBinarySolver.cs @ 15633

Last change on this file since 15633 was 15633, checked in by abeham, 20 months ago

#1614: changed localsolver algorithms to run analyzer at the end

File size: 8.0 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2017 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Threading;
24using HeuristicLab.Common;
25using HeuristicLab.Core;
26using HeuristicLab.Data;
27using HeuristicLab.Encodings.IntegerVectorEncoding;
28using HeuristicLab.Optimization;
29using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
30using localsolver;
31
32namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.LocalSolverNet {
33  [Item("LocalSolver Binary (GQAP)", "LocalSolver algorithm solving the GQAP using 0-1 decision variables")]
34  [StorableClass]
35  [Creatable(CreatableAttribute.Categories.Algorithms)]
36  public sealed class GQAPBinarySolver : ContextAlgorithm<LocalSolverContext, IntegerVectorEncoding> {
37    public override bool SupportsPause {
38      get { return false; }
39    }
40
41    public override Type ProblemType {
42      get { return typeof(GQAP); }
43    }
44
45    public new GQAP Problem {
46      get { return (GQAP)base.Problem; }
47      set { base.Problem = value; }
48    }
49
50    // LS Program variables
51    private LSExpression[][] x;
52    private LSExpression[] equipmentsOnLocations;
53    private LSExpression obj;
54    private LocalSolver localSolver;
55
56
57    [StorableConstructor]
58    private GQAPBinarySolver(bool deserializing) : base(deserializing) { }
59    private GQAPBinarySolver(GQAPBinarySolver original, Cloner cloner)
60    : base(original, cloner) {
61    }
62    public GQAPBinarySolver() {
63    }
64
65    public override IDeepCloneable Clone(Cloner cloner) {
66      return new GQAPBinarySolver(this, cloner);
67    }
68
69    private double prevObj;
70    private DateTime lastUpdate;
71    private CancellationToken token;
72
73    private void LocalSolverOnIterationTicked(LocalSolver ls, LSCallbackType type) {
74      IResult result;
75      Context.Iterations++;
76      if ((DateTime.UtcNow - lastUpdate) > TimeSpan.FromSeconds(1)) {
77        if (Results.TryGetValue("Iterations", out result))
78          ((IntValue)result.Value).Value = Context.Iterations;
79        else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
80        lastUpdate = DateTime.UtcNow;
81      }
82
83      if (token.IsCancellationRequested) localSolver.Stop();
84
85      var curObj = obj.GetDoubleValue();
86
87      if (curObj >= prevObj) return;
88      prevObj = curObj;
89      Context.BestQuality = curObj;
90           
91      if (Results.TryGetValue("BestQuality", out result))
92        ((DoubleValue)result.Value).Value = Context.BestQuality;
93      else Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality)));
94
95      var locations = Problem.ProblemInstance.Capacities.Length;
96      var best = new int[Problem.ProblemInstance.Demands.Length];
97      for (var i = 0; i < best.Length; i++) {
98        for (var j = 0; j < locations; j++) {
99          if (x[i][j].GetIntValue() == 1) {
100            best[i] = j;
101            break;
102          }
103        }
104      }
105      var bestVec = new IntegerVector(best);
106      var eval = Problem.ProblemInstance.Evaluate(bestVec);
107      Context.BestSolution = new GQAPSolution(bestVec, eval);
108
109      var scope = Context.ToScope(new GQAPSolution(new IntegerVector(best), (Evaluation)eval.Clone()), Problem.ProblemInstance.ToSingleObjective(eval));
110      Context.ReplaceIncumbent(scope);
111
112      if (Results.TryGetValue("BestSolution", out result))
113        result.Value = Context.BestSolution;
114      else Results.Add(new Result("BestSolution", Context.BestSolution));
115
116      Context.RunOperator(Analyzer, CancellationToken.None);
117    }
118
119    protected override void Initialize(CancellationToken cancellationToken) {
120      base.Initialize(cancellationToken);
121
122      prevObj = double.MaxValue;
123    }
124
125    protected override void Run(CancellationToken cancellationToken) {
126      token = cancellationToken;
127      lastUpdate = DateTime.UtcNow.AddSeconds(-1);
128      localSolver = new LocalSolver();
129
130      // Declares the optimization model
131      LSModel model = localSolver.GetModel();
132
133      var data = Problem.ProblemInstance;
134
135      // x[f,l] = 1 if equipments f is on location l, 0 otherwise
136      x = new LSExpression[data.Demands.Length][];
137      for (int f = 0; f < data.Demands.Length; f++) {
138        x[f] = new LSExpression[data.Capacities.Length];
139        for (int l = 0; l < data.Capacities.Length; l++) {
140          x[f][l] = model.Bool();
141        }
142      }
143
144      // All equipments are installed in exactly 1 location
145      for (int f = 0; f < data.Demands.Length; f++) {
146        LSExpression nbLocationsAssigned = model.Sum();
147        for (int l = 0; l < data.Capacities.Length; l++) {
148          nbLocationsAssigned.AddOperand(x[f][l]);
149        }
150        model.Constraint(nbLocationsAssigned == 1);
151      }
152
153      // All locations contain not more equipments than there is capacity for
154      for (int l = 0; l < data.Capacities.Length; l++) {
155        LSExpression assignedDemand = model.Sum();
156        for (int f = 0; f < data.Demands.Length; f++) {
157          assignedDemand.AddOperand(x[f][l] * data.Demands[f]);
158        }
159        model.Constraint(assignedDemand <= data.Capacities[l]);
160      }
161
162      // Index of the assigned location of equipment f
163      equipmentsOnLocations = new LSExpression[data.Demands.Length];
164      for (int f = 0; f < data.Demands.Length; f++) {
165        equipmentsOnLocations[f] = model.Sum();
166        for (int l = 0; l < data.Capacities.Length; l++) {
167          equipmentsOnLocations[f].AddOperand(l * x[f][l]);
168        }
169      }
170
171      // Create distances as an array to be accessed by an at operator
172      var distancesJagged = new double[data.Capacities.Length][];
173      for (var i = 0; i < data.Capacities.Length; i++) {
174        distancesJagged[i] = new double[data.Capacities.Length];
175        for (var j = 0; j < data.Capacities.Length; j++)
176          distancesJagged[i][j] = data.Distances[i, j];
177      }
178      var installJagged = new double[data.Demands.Length][];
179      for (var i = 0; i < data.Demands.Length; i++) {
180        installJagged[i] = new double[data.Capacities.Length];
181        for (var j = 0; j < data.Capacities.Length; j++)
182          installJagged[i][j] = data.InstallationCosts[i, j];
183      }
184      LSExpression distancesArray = model.Array(distancesJagged);
185      LSExpression installCostsArray = model.Array(installJagged);
186
187      // Minimize the sum of product distance*flow
188      obj = model.Sum();
189      for (int f1 = 0; f1 < data.Demands.Length; f1++) {
190        for (int f2 = 0; f2 < data.Demands.Length; f2++) {
191          obj.AddOperand(data.TransportationCosts * data.Weights[f1, f2] * distancesArray[equipmentsOnLocations[f1], equipmentsOnLocations[f2]]);
192        }
193        obj.AddOperand(installCostsArray[f1, equipmentsOnLocations[f1]]);
194      }
195
196      model.Minimize(obj);
197
198      try {
199        model.Close();
200
201        // Parameterizes the solver.
202        LSPhase phase = localSolver.CreatePhase();
203        phase.SetTimeLimit((int)Math.Ceiling(MaximumRuntime.TotalSeconds));
204
205        localSolver.AddCallback(LSCallbackType.IterationTicked, LocalSolverOnIterationTicked);
206
207        localSolver.Solve();
208
209        localSolver.RemoveCallback(LSCallbackType.IterationTicked, LocalSolverOnIterationTicked);
210      } finally {
211        localSolver.Dispose();
212      }
213
214      Context.RunOperator(Analyzer, CancellationToken.None);
215    }
216  }
217}
Note: See TracBrowser for help on using the repository browser.