source: branches/1614_GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/LocalSolverNet/GQAPIntegerSolver.cs @ 15713

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

#1614:

  • added additional constraint to benchmark data generator and updated one instance that was affected by this
  • added fitness landscape characteristics for the GQAP
  • fixed RLD analysis view to compensate for empty convergence graphs
  • fixed CPLEX solvers not using the obj value when the solver terminates (callback is not called if proven optimal solution is found)
  • added code for local solver to also check on final quality
File size: 7.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.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 Integer (GQAP)", "LocalSolver algorithm solving the GQAP using integer decision variables")]
34  [StorableClass]
35  [Creatable(CreatableAttribute.Categories.Algorithms)]
36  public sealed class GQAPIntegerSolver : 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 obj;
53    private LocalSolver localSolver;
54
55
56    [StorableConstructor]
57    private GQAPIntegerSolver(bool deserializing) : base(deserializing) { }
58    private GQAPIntegerSolver(GQAPIntegerSolver original, Cloner cloner)
59    : base(original, cloner) {
60    }
61    public GQAPIntegerSolver() {
62      Problem = new GQAP();
63      MaximumEvaluationsParameter.Hidden = true;
64      MaximumIterationsParameter.Hidden = true;
65    }
66
67    public override IDeepCloneable Clone(Cloner cloner) {
68      return new GQAPIntegerSolver(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      UpdateSolution(curObj);
91
92      Context.RunOperator(Analyzer, CancellationToken.None);
93
94      if (StoppingCriterion()) localSolver.Stop();
95    }
96
97    private void UpdateSolution(double obj) {
98      IResult result;
99      prevObj = obj;
100      Context.BestQuality = obj;
101
102      if (Results.TryGetValue("BestQuality", out result))
103        ((DoubleValue)result.Value).Value = Context.BestQuality;
104      else Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality)));
105
106      var locations = Problem.ProblemInstance.Capacities.Length;
107      var best = new int[Problem.ProblemInstance.Demands.Length];
108      for (var i = 0; i < best.Length; i++) {
109        best[i] = (int)x[i].GetIntValue();
110      }
111      var bestVec = new IntegerVector(best);
112      var eval = Problem.ProblemInstance.Evaluate(bestVec);
113      Context.BestSolution = new GQAPSolution(bestVec, eval);
114
115      var scope = Context.ToScope(new GQAPSolution(new IntegerVector(best), (Evaluation)eval.Clone()), Problem.ProblemInstance.ToSingleObjective(eval));
116      Context.ReplaceIncumbent(scope);
117
118      if (Results.TryGetValue("BestSolution", out result))
119        result.Value = Context.BestSolution;
120      else Results.Add(new Result("BestSolution", Context.BestSolution));
121    }
122
123    protected override void Initialize(CancellationToken cancellationToken) {
124      base.Initialize(cancellationToken);
125
126      prevObj = double.MaxValue;
127    }
128
129    protected override void Run(CancellationToken cancellationToken) {
130      base.Run(cancellationToken);
131      token = cancellationToken;
132      lastUpdate = DateTime.UtcNow.AddSeconds(-1);
133      localSolver = new LocalSolver();
134
135      // Declares the optimization model
136      LSModel model = localSolver.GetModel();
137
138      var data = Problem.ProblemInstance;
139
140      // x[f] = location l, f ... facility/equipment
141      x = new LSExpression[data.Demands.Length];
142      for (int f = 0; f < data.Demands.Length; f++) {
143        x[f] = model.Int(0, data.Capacities.Length - 1);
144      }
145
146      // All locations contain not more equipments than there is capacity for
147      for (int l = 0; l < data.Capacities.Length; l++) {
148        var util = model.Sum();
149        for (var f = 0; f < data.Demands.Length; f++)
150          util.AddOperand((x[f] == l) * data.Demands[f]);
151        model.Constraint(util <= data.Capacities[l]);
152      }
153
154      // Create distances as an array to be accessed by an at operator
155      var distancesJagged = new double[data.Capacities.Length][];
156      for (var i = 0; i < data.Capacities.Length; i++) {
157        distancesJagged[i] = new double[data.Capacities.Length];
158        for (var j = 0; j < data.Capacities.Length; j++)
159          distancesJagged[i][j] = data.Distances[i, j];
160      }
161      var installJagged = new double[data.Demands.Length][];
162      for (var i = 0; i < data.Demands.Length; i++) {
163        installJagged[i] = new double[data.Capacities.Length];
164        for (var j = 0; j < data.Capacities.Length; j++)
165          installJagged[i][j] = data.InstallationCosts[i, j];
166      }
167      LSExpression distancesArray = model.Array(distancesJagged);
168      LSExpression installCostsArray = model.Array(installJagged);
169
170      // Minimize the sum of product distance*flow
171      obj = model.Sum();
172      for (int f1 = 0; f1 < data.Demands.Length; f1++) {
173        for (int f2 = 0; f2 < data.Demands.Length; f2++) {
174          obj.AddOperand(data.TransportationCosts * data.Weights[f1, f2] * distancesArray[x[f1], x[f2]]);
175        }
176        obj.AddOperand(installCostsArray[f1, x[f1]]);
177      }
178
179      model.Minimize(obj);
180
181      try {
182        model.Close();
183
184        // Parameterizes the solver.
185        LSPhase phase = localSolver.CreatePhase();
186        phase.SetTimeLimit((int)Math.Ceiling(MaximumRuntime.TotalSeconds));
187
188        localSolver.AddCallback(LSCallbackType.IterationTicked, LocalSolverOnIterationTicked);
189
190        localSolver.Solve();
191
192        var curObj = obj.GetDoubleValue();
193        if (curObj < prevObj)
194          UpdateSolution(curObj);
195
196        localSolver.RemoveCallback(LSCallbackType.IterationTicked, LocalSolverOnIterationTicked);
197      } finally {
198        localSolver.Dispose();
199      }
200
201      Context.RunOperator(Analyzer, CancellationToken.None);
202    }
203  }
204}
Note: See TracBrowser for help on using the repository browser.