source: branches/1614_GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/LocalSolverNet/GQAPBinarySolver.cs @ 15698

Last change on this file since 15698 was 15698, checked in by abeham, 3 years ago

#1614: Added random search and fixed execution time counting for commercial solvers

File size: 8.4 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.Linq;
24using System.Threading;
25using HeuristicLab.Analysis;
26using HeuristicLab.Common;
27using HeuristicLab.Core;
28using HeuristicLab.Data;
29using HeuristicLab.Encodings.IntegerVectorEncoding;
30using HeuristicLab.Optimization;
31using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
32using localsolver;
33
34namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.LocalSolverNet {
35  [Item("LocalSolver Binary (GQAP)", "LocalSolver algorithm solving the GQAP using 0-1 decision variables")]
36  [StorableClass]
37  [Creatable(CreatableAttribute.Categories.Algorithms)]
38  public sealed class GQAPBinarySolver : ContextAlgorithm<LocalSolverContext, IntegerVectorEncoding> {
39    public override bool SupportsPause {
40      get { return false; }
41    }
42
43    public override Type ProblemType {
44      get { return typeof(GQAP); }
45    }
46
47    public new GQAP Problem {
48      get { return (GQAP)base.Problem; }
49      set { base.Problem = value; }
50    }
51
52    // LS Program variables
53    private LSExpression[][] x;
54    private LSExpression[] equipmentsOnLocations;
55    private LSExpression obj;
56    private LocalSolver localSolver;
57
58
59    [StorableConstructor]
60    private GQAPBinarySolver(bool deserializing) : base(deserializing) { }
61    private GQAPBinarySolver(GQAPBinarySolver original, Cloner cloner)
62    : base(original, cloner) {
63    }
64    public GQAPBinarySolver() {
65    }
66
67    public override IDeepCloneable Clone(Cloner cloner) {
68      return new GQAPBinarySolver(this, cloner);
69    }
70
71    private double prevObj;
72    private DateTime lastUpdate;
73    private CancellationToken token;
74
75    private void LocalSolverOnIterationTicked(LocalSolver ls, LSCallbackType type) {
76      IResult result;
77      Context.Iterations++;
78      if ((DateTime.UtcNow - lastUpdate) > TimeSpan.FromSeconds(1)) {
79        if (Results.TryGetValue("Iterations", out result))
80          ((IntValue)result.Value).Value = Context.Iterations;
81        else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
82        lastUpdate = DateTime.UtcNow;
83      }
84
85      if (token.IsCancellationRequested) localSolver.Stop();
86
87      var curObj = obj.GetDoubleValue();
88
89      if (curObj >= prevObj) return;
90      prevObj = curObj;
91      Context.BestQuality = curObj;
92           
93      if (Results.TryGetValue("BestQuality", out result))
94        ((DoubleValue)result.Value).Value = Context.BestQuality;
95      else Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality)));
96
97      var locations = Problem.ProblemInstance.Capacities.Length;
98      var best = new int[Problem.ProblemInstance.Demands.Length];
99      for (var i = 0; i < best.Length; i++) {
100        for (var j = 0; j < locations; j++) {
101          if (x[i][j].GetIntValue() == 1) {
102            best[i] = j;
103            break;
104          }
105        }
106      }
107      var bestVec = new IntegerVector(best);
108      var eval = Problem.ProblemInstance.Evaluate(bestVec);
109      Context.BestSolution = new GQAPSolution(bestVec, eval);
110
111      var scope = Context.ToScope(new GQAPSolution(new IntegerVector(best), (Evaluation)eval.Clone()), Problem.ProblemInstance.ToSingleObjective(eval));
112      Context.ReplaceIncumbent(scope);
113
114      if (Results.TryGetValue("BestSolution", out result))
115        result.Value = Context.BestSolution;
116      else Results.Add(new Result("BestSolution", Context.BestSolution));
117
118      Context.RunOperator(Analyzer, CancellationToken.None);
119    }
120
121    protected override void Initialize(CancellationToken cancellationToken) {
122      base.Initialize(cancellationToken);
123
124      prevObj = double.MaxValue;
125    }
126
127    protected override void Run(CancellationToken cancellationToken) {
128      var qpc = ((MultiAnalyzer)Analyzer).Operators.OfType<QualityPerClockAnalyzer>().FirstOrDefault();
129      if (qpc != null) {
130        qpc.LastUpdateTimeParameter.ActualName = Context.LastUpdateTimeParameter.Name;
131      }
132      token = cancellationToken;
133      lastUpdate = DateTime.UtcNow.AddSeconds(-1);
134      localSolver = new LocalSolver();
135
136      // Declares the optimization model
137      LSModel model = localSolver.GetModel();
138
139      var data = Problem.ProblemInstance;
140
141      // x[f,l] = 1 if equipments f is on location l, 0 otherwise
142      x = new LSExpression[data.Demands.Length][];
143      for (int f = 0; f < data.Demands.Length; f++) {
144        x[f] = new LSExpression[data.Capacities.Length];
145        for (int l = 0; l < data.Capacities.Length; l++) {
146          x[f][l] = model.Bool();
147        }
148      }
149
150      // All equipments are installed in exactly 1 location
151      for (int f = 0; f < data.Demands.Length; f++) {
152        LSExpression nbLocationsAssigned = model.Sum();
153        for (int l = 0; l < data.Capacities.Length; l++) {
154          nbLocationsAssigned.AddOperand(x[f][l]);
155        }
156        model.Constraint(nbLocationsAssigned == 1);
157      }
158
159      // All locations contain not more equipments than there is capacity for
160      for (int l = 0; l < data.Capacities.Length; l++) {
161        LSExpression assignedDemand = model.Sum();
162        for (int f = 0; f < data.Demands.Length; f++) {
163          assignedDemand.AddOperand(x[f][l] * data.Demands[f]);
164        }
165        model.Constraint(assignedDemand <= data.Capacities[l]);
166      }
167
168      // Index of the assigned location of equipment f
169      equipmentsOnLocations = new LSExpression[data.Demands.Length];
170      for (int f = 0; f < data.Demands.Length; f++) {
171        equipmentsOnLocations[f] = model.Sum();
172        for (int l = 0; l < data.Capacities.Length; l++) {
173          equipmentsOnLocations[f].AddOperand(l * x[f][l]);
174        }
175      }
176
177      // Create distances as an array to be accessed by an at operator
178      var distancesJagged = new double[data.Capacities.Length][];
179      for (var i = 0; i < data.Capacities.Length; i++) {
180        distancesJagged[i] = new double[data.Capacities.Length];
181        for (var j = 0; j < data.Capacities.Length; j++)
182          distancesJagged[i][j] = data.Distances[i, j];
183      }
184      var installJagged = new double[data.Demands.Length][];
185      for (var i = 0; i < data.Demands.Length; i++) {
186        installJagged[i] = new double[data.Capacities.Length];
187        for (var j = 0; j < data.Capacities.Length; j++)
188          installJagged[i][j] = data.InstallationCosts[i, j];
189      }
190      LSExpression distancesArray = model.Array(distancesJagged);
191      LSExpression installCostsArray = model.Array(installJagged);
192
193      // Minimize the sum of product distance*flow
194      obj = model.Sum();
195      for (int f1 = 0; f1 < data.Demands.Length; f1++) {
196        for (int f2 = 0; f2 < data.Demands.Length; f2++) {
197          obj.AddOperand(data.TransportationCosts * data.Weights[f1, f2] * distancesArray[equipmentsOnLocations[f1], equipmentsOnLocations[f2]]);
198        }
199        obj.AddOperand(installCostsArray[f1, equipmentsOnLocations[f1]]);
200      }
201
202      model.Minimize(obj);
203
204      try {
205        model.Close();
206
207        // Parameterizes the solver.
208        LSPhase phase = localSolver.CreatePhase();
209        phase.SetTimeLimit((int)Math.Ceiling(MaximumRuntime.TotalSeconds));
210
211        localSolver.AddCallback(LSCallbackType.IterationTicked, LocalSolverOnIterationTicked);
212
213        Context.LastUpdateTimeParameter.Value = new DateTimeValue(DateTime.UtcNow);
214
215        localSolver.Solve();
216
217        localSolver.RemoveCallback(LSCallbackType.IterationTicked, LocalSolverOnIterationTicked);
218      } finally {
219        localSolver.Dispose();
220      }
221
222      Context.RunOperator(Analyzer, CancellationToken.None);
223    }
224  }
225}
Note: See TracBrowser for help on using the repository browser.