source: branches/1614_GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/LocalSolverNet/GQAPIntegerSolver.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: 7.2 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 Integer (GQAP)", "LocalSolver algorithm solving the GQAP using integer decision variables")]
36  [StorableClass]
37  [Creatable(CreatableAttribute.Categories.Algorithms)]
38  public sealed class GQAPIntegerSolver : 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 obj;
55    private LocalSolver localSolver;
56
57
58    [StorableConstructor]
59    private GQAPIntegerSolver(bool deserializing) : base(deserializing) { }
60    private GQAPIntegerSolver(GQAPIntegerSolver original, Cloner cloner)
61    : base(original, cloner) {
62    }
63    public GQAPIntegerSolver() {
64    }
65
66    public override IDeepCloneable Clone(Cloner cloner) {
67      return new GQAPIntegerSolver(this, cloner);
68    }
69
70    private double prevObj;
71    private DateTime lastUpdate;
72    private CancellationToken token;
73
74    private void LocalSolverOnIterationTicked(LocalSolver ls, LSCallbackType type) {
75      IResult result;
76      Context.Iterations++;
77      if ((DateTime.UtcNow - lastUpdate) > TimeSpan.FromSeconds(1)) {
78        if (Results.TryGetValue("Iterations", out result))
79          ((IntValue)result.Value).Value = Context.Iterations;
80        else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
81        lastUpdate = DateTime.UtcNow;
82      }
83
84      if (token.IsCancellationRequested) localSolver.Stop();
85
86      var curObj = obj.GetDoubleValue();
87
88      if (curObj >= prevObj) return;
89      prevObj = curObj;
90      Context.BestQuality = curObj;
91           
92      if (Results.TryGetValue("BestQuality", out result))
93        ((DoubleValue)result.Value).Value = Context.BestQuality;
94      else Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality)));
95
96      var locations = Problem.ProblemInstance.Capacities.Length;
97      var best = new int[Problem.ProblemInstance.Demands.Length];
98      for (var i = 0; i < best.Length; i++) {
99        best[i] = (int)x[i].GetIntValue();
100      }
101      var bestVec = new IntegerVector(best);
102      var eval = Problem.ProblemInstance.Evaluate(bestVec);
103      Context.BestSolution = new GQAPSolution(bestVec, eval);
104
105      var scope = Context.ToScope(new GQAPSolution(new IntegerVector(best), (Evaluation)eval.Clone()), Problem.ProblemInstance.ToSingleObjective(eval));
106      Context.ReplaceIncumbent(scope);
107
108      if (Results.TryGetValue("BestSolution", out result))
109        result.Value = Context.BestSolution;
110      else Results.Add(new Result("BestSolution", Context.BestSolution));
111
112      Context.RunOperator(Analyzer, CancellationToken.None);
113    }
114
115    protected override void Initialize(CancellationToken cancellationToken) {
116      base.Initialize(cancellationToken);
117
118      prevObj = double.MaxValue;
119    }
120
121    protected override void Run(CancellationToken cancellationToken) {
122      var qpc = ((MultiAnalyzer)Analyzer).Operators.OfType<QualityPerClockAnalyzer>().FirstOrDefault();
123      if (qpc != null) {
124        qpc.LastUpdateTimeParameter.ActualName = Context.LastUpdateTimeParameter.Name;
125      }
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] = location l, f ... facility/equipment
136      x = new LSExpression[data.Demands.Length];
137      for (int f = 0; f < data.Demands.Length; f++) {
138        x[f] = model.Int(0, data.Capacities.Length - 1);
139      }
140
141      // All locations contain not more equipments than there is capacity for
142      for (int l = 0; l < data.Capacities.Length; l++) {
143        var util = model.Sum();
144        for (var f = 0; f < data.Demands.Length; f++)
145          util.AddOperand((x[f] == l) * data.Demands[f]);
146        model.Constraint(util <= data.Capacities[l]);
147      }
148
149      // Create distances as an array to be accessed by an at operator
150      var distancesJagged = new double[data.Capacities.Length][];
151      for (var i = 0; i < data.Capacities.Length; i++) {
152        distancesJagged[i] = new double[data.Capacities.Length];
153        for (var j = 0; j < data.Capacities.Length; j++)
154          distancesJagged[i][j] = data.Distances[i, j];
155      }
156      var installJagged = new double[data.Demands.Length][];
157      for (var i = 0; i < data.Demands.Length; i++) {
158        installJagged[i] = new double[data.Capacities.Length];
159        for (var j = 0; j < data.Capacities.Length; j++)
160          installJagged[i][j] = data.InstallationCosts[i, j];
161      }
162      LSExpression distancesArray = model.Array(distancesJagged);
163      LSExpression installCostsArray = model.Array(installJagged);
164
165      // Minimize the sum of product distance*flow
166      obj = model.Sum();
167      for (int f1 = 0; f1 < data.Demands.Length; f1++) {
168        for (int f2 = 0; f2 < data.Demands.Length; f2++) {
169          obj.AddOperand(data.TransportationCosts * data.Weights[f1, f2] * distancesArray[x[f1], x[f2]]);
170        }
171        obj.AddOperand(installCostsArray[f1, x[f1]]);
172      }
173
174      model.Minimize(obj);
175
176      try {
177        model.Close();
178
179        // Parameterizes the solver.
180        LSPhase phase = localSolver.CreatePhase();
181        phase.SetTimeLimit((int)Math.Ceiling(MaximumRuntime.TotalSeconds));
182
183        localSolver.AddCallback(LSCallbackType.IterationTicked, LocalSolverOnIterationTicked);
184
185        Context.LastUpdateTimeParameter.Value = new DateTimeValue(DateTime.UtcNow);
186
187        localSolver.Solve();
188      } finally {
189        localSolver.Dispose();
190      }
191
192      Context.RunOperator(Analyzer, CancellationToken.None);
193    }
194  }
195}
Note: See TracBrowser for help on using the repository browser.