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

Last change on this file since 16373 was 16373, checked in by ddorfmei, 7 months ago

#2931:

  • upgraded Google OR-Tools to version 6.10
  • added TextValue and TextValueView to be able to display and edit a multiline string
  • added parameter to set solver specific parameters for supported solvers
  • added support for the Protocol Buffers representation of models (import/export)
  • added import of MPS models
  • added pause/stop functionality to CplexSolver and GlpkSolver
  • refactored wrapper (LinearSolver and related enums)
  • added new algorithm category Exact for LinearProgrammingAlgorithm
File size: 6.8 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 HeuristicLab.Analysis;
26using HeuristicLab.Common;
27using HeuristicLab.Core;
28using HeuristicLab.Data;
29using HeuristicLab.Parameters;
30using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
31
32namespace HeuristicLab.MathematicalOptimization.LinearProgramming.Algorithms.Solvers.Base {
33
34  [StorableClass]
35  public class IncrementalSolver : Solver, IIncrementalSolver {
36
37    [Storable]
38    protected readonly IValueParameter<TimeSpanValue> qualityUpdateIntervalParam;
39
40    private IndexedDataRow<double> bpcRow;
41
42    private IndexedDataRow<double> qpcRow;
43
44    [Storable]
45    private IndexedDataTable<double> qualityPerClock;
46
47    [StorableConstructor]
48    protected IncrementalSolver(bool deserializing)
49      : base(deserializing) {
50    }
51
52    public IncrementalSolver() {
53      Parameters.Add(qualityUpdateIntervalParam =
54        new ValueParameter<TimeSpanValue>(nameof(QualityUpdateInterval),
55          "Time interval before solver is paused, results are retrieved and solver is resumed. " +
56          "Set to zero for no intermediate results and faster solving.", new TimeSpanValue(new TimeSpan(0, 0, 10))));
57      problemTypeParam.Value.ValueChanged += (sender, args) => {
58        if (SupportsQualityUpdate) {
59          if (!Parameters.Contains(qualityUpdateIntervalParam)) {
60            Parameters.Add(qualityUpdateIntervalParam);
61          }
62        } else {
63          Parameters.Remove(qualityUpdateIntervalParam);
64        }
65      };
66    }
67
68    protected IncrementalSolver(IncrementalSolver original, Cloner cloner)
69        : base(original, cloner) {
70      problemTypeParam = cloner.Clone(original.problemTypeParam);
71      qualityUpdateIntervalParam = cloner.Clone(original.qualityUpdateIntervalParam);
72      if (original.qualityPerClock != null)
73        qualityPerClock = cloner.Clone(original.qualityPerClock);
74    }
75
76    public virtual bool SupportsQualityUpdate => true;
77
78    public TimeSpan QualityUpdateInterval {
79      get => qualityUpdateIntervalParam.Value.Value;
80      set => qualityUpdateIntervalParam.Value.Value = value;
81    }
82
83    protected virtual TimeSpan TimeLimit => QualityUpdateInterval;
84
85    public override void Solve(LinearProgrammingAlgorithm algorithm, CancellationToken cancellationToken) {
86      if (!SupportsQualityUpdate || QualityUpdateInterval == TimeSpan.Zero) {
87        base.Solve(algorithm, cancellationToken);
88        return;
89      }
90
91      var timeLimit = algorithm.TimeLimit;
92      var unlimitedRuntime = timeLimit == TimeSpan.Zero;
93
94      if (!unlimitedRuntime) {
95        timeLimit -= algorithm.ExecutionTime;
96      }
97
98      var iterations = (long)timeLimit.TotalMilliseconds / (long)QualityUpdateInterval.TotalMilliseconds;
99      var remaining = timeLimit - TimeSpan.FromMilliseconds(iterations * QualityUpdateInterval.TotalMilliseconds);
100      var validResultStatuses = new[] { ResultStatus.NotSolved, ResultStatus.Feasible };
101
102      while (unlimitedRuntime || iterations > 0) {
103        if (cancellationToken.IsCancellationRequested)
104          return;
105
106        base.Solve(algorithm, TimeLimit);
107        UpdateQuality(algorithm);
108
109        var resultStatus = ((EnumValue<ResultStatus>)algorithm.Results[nameof(solver.ResultStatus)].Value).Value;
110        if (!validResultStatuses.Contains(resultStatus))
111          return;
112
113        if (!unlimitedRuntime)
114          iterations--;
115      }
116
117      if (remaining > TimeSpan.Zero) {
118        base.Solve(algorithm, remaining);
119        UpdateQuality(algorithm);
120      }
121    }
122
123    private void UpdateQuality(LinearProgrammingAlgorithm algorithm) {
124      if (!algorithm.Results.Exists(r => r.Name == "QualityPerClock")) {
125        qualityPerClock = new IndexedDataTable<double>("Quality per Clock");
126        qpcRow = new IndexedDataRow<double>("Objective Value");
127        bpcRow = new IndexedDataRow<double>("Bound");
128        algorithm.Results.AddOrUpdateResult("QualityPerClock", qualityPerClock);
129      }
130
131      var resultStatus = ((EnumValue<ResultStatus>)algorithm.Results[nameof(solver.ResultStatus)].Value).Value;
132
133      if (new[] { ResultStatus.Abnormal, ResultStatus.NotSolved, ResultStatus.Unbounded }.Contains(resultStatus))
134        return;
135
136      var objective = ((DoubleValue)algorithm.Results[$"Best{nameof(solver.ObjectiveValue)}"].Value).Value;
137      var bound = solver.IsMip ? ((DoubleValue)algorithm.Results[$"Best{nameof(solver.ObjectiveBound)}"].Value).Value : double.NaN;
138      var time = algorithm.ExecutionTime.TotalSeconds;
139
140      if (!qpcRow.Values.Any()) {
141        if (!double.IsInfinity(objective) && !double.IsNaN(objective)) {
142          qpcRow.Values.Add(Tuple.Create(time, objective));
143          qpcRow.Values.Add(Tuple.Create(time, objective));
144          qualityPerClock.Rows.Add(qpcRow);
145          algorithm.Results.AddOrUpdateResult($"Best{nameof(solver.ObjectiveValue)}FoundAt", new TimeSpanValue(TimeSpan.FromSeconds(time)));
146        }
147      } else {
148        var previousBest = qpcRow.Values.Last().Item2;
149        qpcRow.Values[qpcRow.Values.Count - 1] = Tuple.Create(time, objective);
150        if (!objective.IsAlmost(previousBest)) {
151          qpcRow.Values.Add(Tuple.Create(time, objective));
152          algorithm.Results.AddOrUpdateResult($"Best{nameof(solver.ObjectiveValue)}FoundAt", new TimeSpanValue(TimeSpan.FromSeconds(time)));
153        }
154      }
155
156      if (!solver.IsMip)
157        return;
158
159      if (!bpcRow.Values.Any()) {
160        if (!double.IsInfinity(bound) && !double.IsNaN(bound)) {
161          bpcRow.Values.Add(Tuple.Create(time, bound));
162          bpcRow.Values.Add(Tuple.Create(time, bound));
163          qualityPerClock.Rows.Add(bpcRow);
164        }
165      } else {
166        var previousBest = bpcRow.Values.Last().Item2;
167        bpcRow.Values[bpcRow.Values.Count - 1] = Tuple.Create(time, bound);
168        if (!bound.IsAlmost(previousBest)) {
169          bpcRow.Values.Add(Tuple.Create(time, bound));
170        }
171      }
172    }
173  }
174}
Note: See TracBrowser for help on using the repository browser.