source: branches/1614_GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/LocalSolverNet/GQAPListSolver.cs @ 15758

Last change on this file since 15758 was 15758, checked in by abeham, 4 years ago

#1614: Added LocalSolver model based on lists

File size: 8.3 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 List (GQAP)", "LocalSolver algorithm solving the GQAP using list decision variables")]
34  [StorableClass]
35  [Creatable(CreatableAttribute.Categories.Algorithms)]
36  public sealed class GQAPListSolver : 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 GQAPListSolver(bool deserializing) : base(deserializing) { }
59    private GQAPListSolver(GQAPListSolver original, Cloner cloner)
60    : base(original, cloner) {
61    }
62    public GQAPListSolver() {
63      Problem = new GQAP();
64      MaximumEvaluationsParameter.Hidden = true;
65      MaximumIterationsParameter.Hidden = true;
66    }
67
68    public override IDeepCloneable Clone(Cloner cloner) {
69      return new GQAPListSolver(this, cloner);
70    }
71
72    private double prevObj;
73    private DateTime lastUpdate;
74    private CancellationToken token;
75
76    private void LocalSolverOnIterationTicked(LocalSolver ls, LSCallbackType type) {
77      IResult result;
78      Context.Iterations++;
79      if ((DateTime.UtcNow - lastUpdate) > TimeSpan.FromSeconds(1)) {
80        if (Results.TryGetValue("Iterations", out result))
81          ((IntValue)result.Value).Value = Context.Iterations;
82        else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
83        lastUpdate = DateTime.UtcNow;
84      }
85
86      if (token.IsCancellationRequested) localSolver.Stop();
87
88      var curObj = obj.GetDoubleValue();
89
90      if (curObj >= prevObj) return;
91      UpdateSolution(curObj);
92
93      Context.RunOperator(Analyzer, CancellationToken.None);
94
95      if (StoppingCriterion()) localSolver.Stop();
96    }
97
98    private void UpdateSolution(double obj) {
99      IResult result;
100      prevObj = obj;
101      Context.BestQuality = obj;
102
103      if (Results.TryGetValue("BestQuality", out result))
104        ((DoubleValue)result.Value).Value = Context.BestQuality;
105      else Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality)));
106
107      var locations = Problem.ProblemInstance.Capacities.Length;
108      var best = new int[Problem.ProblemInstance.Demands.Length];
109      for (var j = 0; j < locations; j++) {
110        var xcol = x[j].GetCollectionValue();
111        for (var i = 0; i < xcol.Count(); i++) {
112          var equip = xcol.Get(i);
113          best[equip] = j;
114        }
115      }
116      var bestVec = new IntegerVector(best);
117      var eval = Problem.ProblemInstance.Evaluate(bestVec);
118      Context.BestSolution = new GQAPSolution(bestVec, eval);
119
120      var scope = Context.ToScope(new GQAPSolution(new IntegerVector(best), (Evaluation)eval.Clone()), Problem.ProblemInstance.ToSingleObjective(eval));
121      Context.ReplaceIncumbent(scope);
122
123      if (Results.TryGetValue("BestSolution", out result))
124        result.Value = Context.BestSolution;
125      else Results.Add(new Result("BestSolution", Context.BestSolution));
126    }
127
128    protected override void Initialize(CancellationToken cancellationToken) {
129      base.Initialize(cancellationToken);
130
131      prevObj = double.MaxValue;
132    }
133
134    protected override void Run(CancellationToken cancellationToken) {
135      base.Run(cancellationToken);
136      token = cancellationToken;
137      lastUpdate = DateTime.UtcNow.AddSeconds(-1);
138      localSolver = new LocalSolver();
139
140      // Declares the optimization model
141      var model = localSolver.GetModel();
142
143      var data = Problem.ProblemInstance;
144
145      x = new LSExpression[data.Capacities.Length];
146      // x[f,l] = 1 if equipments f is on location l, 0 otherwise
147      for (int r = 0; r < data.Capacities.Length; r++) {
148        x[r] = model.List(data.Demands.Length);
149      }
150
151      // All equipments are installed in exactly 1 location
152      model.Constraint(model.Partition(x));
153
154      var demandsArray = model.Array(data.Demands);
155
156      // Create distances as an array to be accessed by an at operator
157      var weightsJagged = new double[data.Demands.Length][];
158      for (var i = 0; i < data.Demands.Length; i++) {
159        weightsJagged[i] = new double[data.Demands.Length];
160        for (var j = 0; j < data.Demands.Length; j++) {
161          weightsJagged[i][j] = data.Weights[i, j];
162        }
163      }
164      var distancesJagged = new double[data.Capacities.Length][];
165      for (var i = 0; i < data.Capacities.Length; i++) {
166        distancesJagged[i] = new double[data.Capacities.Length];
167        for (var j = 0; j < data.Capacities.Length; j++)
168          distancesJagged[i][j] = data.Distances[i, j];
169      }
170      var installJagged = new double[data.Demands.Length][];
171      for (var i = 0; i < data.Demands.Length; i++) {
172        installJagged[i] = new double[data.Capacities.Length];
173        for (var j = 0; j < data.Capacities.Length; j++)
174          installJagged[i][j] = data.InstallationCosts[i, j];
175      }
176      var weightsArray = model.Array(weightsJagged);
177      var distancesArray = model.Array(distancesJagged);
178      var installCostsArray = model.Array(installJagged);
179
180      obj = model.Sum();
181      // All locations contain not more equipments than there is capacity for
182      for (int l = 0; l < data.Capacities.Length; l++) {
183        var c = model.Count(x[l]);
184        var demandSelector = model.Function(i => demandsArray[x[l][i]]);
185        var assignedDemand = model.Sum(model.Range(0, c), demandSelector);
186        model.Constraint(assignedDemand <= data.Capacities[l]);
187
188        var installCostSelector = model.Function(i => installCostsArray[x[l][i], l]);
189        var installCosts = model.Sum(model.Range(0, c), installCostSelector);
190        obj.AddOperand(installCosts);
191       
192        // Flow to other equipments
193        for (int k = 0; k < data.Capacities.Length; k++) {
194          var kc = model.Count(x[k]);
195          var flowCostSelector = model.Function(j => model.Sum(model.Range(0, c), model.Function(i => weightsArray[x[l][i], x[k][j]] * distancesArray[l, k] * data.TransportationCosts)));
196          obj.AddOperand(model.Sum(model.Range(0, kc), flowCostSelector));
197        }
198      }
199
200      model.Minimize(this.obj);
201
202      try {
203        model.Close();
204
205        // Parameterizes the solver.
206        LSPhase phase = localSolver.CreatePhase();
207        phase.SetTimeLimit((int)Math.Ceiling(MaximumRuntime.TotalSeconds));
208
209        localSolver.AddCallback(LSCallbackType.IterationTicked, LocalSolverOnIterationTicked);
210
211        localSolver.Solve();
212
213        var curObj = this.obj.GetDoubleValue();
214        if (curObj < prevObj)
215          UpdateSolution(curObj);
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.