source: branches/2931_OR-Tools_LP_MIP/HeuristicLab.MathematicalOptimization/3.3/LinearProgramming/Algorithms/Solvers/Base/IncrementalSolver.cs @ 16288

Last change on this file since 16288 was 16288, checked in by ddorfmei, 8 months ago

#2931:

  • added license information to all files
  • added missing storable and cloning constructors
  • fixed a bug that caused an exception when a Hive Slave tried to delete the files in the PluginTemp folder
File size: 7.2 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2018 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 Google.OrTools.LinearSolver;
26using HeuristicLab.Analysis;
27using HeuristicLab.Common;
28using HeuristicLab.Core;
29using HeuristicLab.Data;
30using HeuristicLab.Parameters;
31using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
32
33namespace HeuristicLab.MathematicalOptimization.LinearProgramming.Algorithms.Solvers.Base {
34
35  [StorableClass]
36  public class IncrementalSolver : Solver, IIncrementalSolver {
37
38    [Storable]
39    protected readonly IValueParameter<BoolValue> incrementalityParam;
40
41    [Storable]
42    protected readonly IValueParameter<TimeSpanValue> qualityUpdateIntervalParam;
43
44    private IndexedDataRow<double> bpcRow;
45
46    private IndexedDataRow<double> qpcRow;
47
48    [Storable]
49    private IndexedDataTable<double> qualityPerClock;
50
51    [StorableConstructor]
52    protected IncrementalSolver(bool deserializing)
53      : base(deserializing) {
54    }
55
56    public IncrementalSolver() {
57      Parameters.Add(incrementalityParam = new ValueParameter<BoolValue>(nameof(Incrementality),
58        "Advanced usage: incrementality from one solve to the next.",
59        new BoolValue(MPSolverParameters.kDefaultIncrementality == MPSolverParameters.INCREMENTALITY_ON)));
60      Parameters.Add(qualityUpdateIntervalParam =
61        new ValueParameter<TimeSpanValue>(nameof(QualityUpdateInterval),
62          "Time interval before solver is paused, resuls are retrieved and solver is resumed.",
63          new TimeSpanValue(new TimeSpan(0, 0, 10))));
64
65      incrementalityParam.Value.ValueChanged += (sender, args) => {
66        if (((BoolValue)sender).Value) {
67          qualityUpdateIntervalParam.Value = new TimeSpanValue(qualityUpdateIntervalParam.Value.Value);
68        } else {
69          qualityUpdateIntervalParam.Value = (TimeSpanValue)qualityUpdateIntervalParam.Value.AsReadOnly();
70        }
71      };
72    }
73
74    protected IncrementalSolver(IncrementalSolver original, Cloner cloner)
75        : base(original, cloner) {
76      programmingTypeParam = cloner.Clone(original.programmingTypeParam);
77      qualityUpdateIntervalParam = cloner.Clone(original.qualityUpdateIntervalParam);
78      incrementalityParam = cloner.Clone(original.incrementalityParam);
79      if (original.qualityPerClock != null)
80        qualityPerClock = cloner.Clone(original.qualityPerClock);
81    }
82
83    public bool Incrementality {
84      get => incrementalityParam.Value.Value;
85      set => incrementalityParam.Value.Value = value;
86    }
87
88    public TimeSpan QualityUpdateInterval {
89      get => qualityUpdateIntervalParam.Value.Value;
90      set => qualityUpdateIntervalParam.Value.Value = value;
91    }
92
93    public override void Solve(LinearProgrammingAlgorithm algorithm, CancellationToken cancellationToken) {
94      if (!Incrementality) {
95        base.Solve(algorithm, cancellationToken);
96        return;
97      }
98
99      var timeLimit = algorithm.TimeLimit;
100      var unlimitedRuntime = timeLimit == TimeSpan.Zero;
101
102      if (!unlimitedRuntime) {
103        var wallTime = ((TimeSpanValue)algorithm.Results.SingleOrDefault(r => r.Name == "Wall Time")?.Value)?.Value;
104        if (wallTime.HasValue) {
105          timeLimit -= wallTime.Value;
106        }
107      }
108
109      var iterations = (long)timeLimit.TotalMilliseconds / (long)QualityUpdateInterval.TotalMilliseconds;
110      var remaining = timeLimit - TimeSpan.FromMilliseconds(iterations * QualityUpdateInterval.TotalMilliseconds);
111      var validResultStatuses = new[] { ResultStatus.NOT_SOLVED, ResultStatus.FEASIBLE };
112
113      while (unlimitedRuntime || iterations > 0) {
114        base.Solve(algorithm, QualityUpdateInterval, true);
115        UpdateQuality(algorithm);
116
117        var resultStatus = ((EnumValue<ResultStatus>)algorithm.Results["Result Status"].Value).Value;
118        if (!validResultStatuses.Contains(resultStatus) || cancellationToken.IsCancellationRequested)
119          return;
120
121        if (!unlimitedRuntime)
122          iterations--;
123      }
124
125      if (remaining > TimeSpan.Zero) {
126        base.Solve(algorithm, remaining, true);
127        UpdateQuality(algorithm);
128      }
129    }
130
131    private void UpdateQuality(LinearProgrammingAlgorithm algorithm) {
132      if (!algorithm.Results.Exists(r => r.Name == "QualityPerClock")) {
133        qualityPerClock = new IndexedDataTable<double>("Quality per Clock");
134        qpcRow = new IndexedDataRow<double>("First-hit Graph Objective");
135        bpcRow = new IndexedDataRow<double>("First-hit Graph Bound");
136        algorithm.Results.AddOrUpdateResult("QualityPerClock", qualityPerClock);
137      }
138
139      var resultStatus = ((EnumValue<ResultStatus>)algorithm.Results["Result Status"].Value).Value;
140
141      if (new[] { ResultStatus.ABNORMAL, ResultStatus.NOT_SOLVED, ResultStatus.UNBOUNDED }.Contains(resultStatus))
142        return;
143
144      var objective = ((DoubleValue)algorithm.Results["Best Objective Value"].Value).Value;
145      var bound = ((DoubleValue)algorithm.Results["Best Objective Bound"].Value).Value;
146      var time = algorithm.ExecutionTime.TotalSeconds;
147
148      if (!qpcRow.Values.Any()) {
149        if (!double.IsInfinity(objective) && !double.IsNaN(objective)) {
150          qpcRow.Values.Add(Tuple.Create(time, objective));
151          qpcRow.Values.Add(Tuple.Create(time, objective));
152          qualityPerClock.Rows.Add(qpcRow);
153          algorithm.Results.AddOrUpdateResult("Best Solution Found At", new TimeSpanValue(TimeSpan.FromSeconds(time)));
154        }
155      } else {
156        var previousBest = qpcRow.Values.Last().Item2;
157        qpcRow.Values[qpcRow.Values.Count - 1] = Tuple.Create(time, objective);
158        if (!objective.IsAlmost(previousBest)) {
159          qpcRow.Values.Add(Tuple.Create(time, objective));
160          algorithm.Results.AddOrUpdateResult("Best Solution Found At", new TimeSpanValue(TimeSpan.FromSeconds(time)));
161        }
162      }
163
164      if (!bpcRow.Values.Any()) {
165        if (!double.IsInfinity(bound) && !double.IsNaN(bound)) {
166          bpcRow.Values.Add(Tuple.Create(time, bound));
167          bpcRow.Values.Add(Tuple.Create(time, bound));
168          qualityPerClock.Rows.Add(bpcRow);
169        }
170      } else {
171        var previousBest = bpcRow.Values.Last().Item2;
172        bpcRow.Values[bpcRow.Values.Count - 1] = Tuple.Create(time, bound);
173        if (!bound.IsAlmost(previousBest)) {
174          bpcRow.Values.Add(Tuple.Create(time, bound));
175        }
176      }
177    }
178  }
179}
Note: See TracBrowser for help on using the repository browser.