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

Last change on this file since 16736 was 16736, checked in by ddorfmei, 5 months ago

#2931: Upgraded persistence to HEAL.Attic

File size: 7.3 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.Diagnostics;
24using System.Linq;
25using System.Threading;
26using HeuristicLab.Analysis;
27using HeuristicLab.Common;
28using HeuristicLab.Core;
29using HeuristicLab.Data;
30using HeuristicLab.Optimization;
31using HeuristicLab.Parameters;
32using HEAL.Attic;
33
34namespace HeuristicLab.ExactOptimization.LinearProgramming {
35
36  [StorableType("8730ECDD-8F38-47C2-B0D9-2B1F38FC0A27")]
37  public class IncrementalLinearSolver : LinearSolver, IIncrementalLinearSolver {
38
39    [Storable]
40    protected readonly IValueParameter<TimeSpanValue> qualityUpdateIntervalParam;
41
42    private readonly Stopwatch stopwatch = new Stopwatch();
43
44    [Storable]
45    private TimeSpan executionTime = TimeSpan.Zero;
46
47    [Storable]
48    private IndexedDataTable<double> qualityPerClock;
49
50    public IncrementalLinearSolver() {
51      Parameters.Add(qualityUpdateIntervalParam =
52        new ValueParameter<TimeSpanValue>(nameof(QualityUpdateInterval),
53          "Time interval before solver is paused, results are retrieved and solver is resumed. " +
54          "Set to zero for no intermediate results and faster solving.", new TimeSpanValue(new TimeSpan(0, 0, 10))));
55      problemTypeParam.Value.ValueChanged += (sender, args) => {
56        if (SupportsQualityUpdate) {
57          if (!Parameters.Contains(qualityUpdateIntervalParam)) {
58            Parameters.Add(qualityUpdateIntervalParam);
59          }
60        } else {
61          Parameters.Remove(qualityUpdateIntervalParam);
62        }
63      };
64    }
65
66    [StorableConstructor]
67    protected IncrementalLinearSolver(StorableConstructorFlag _) : base(_) { }
68
69    protected IncrementalLinearSolver(IncrementalLinearSolver original, Cloner cloner)
70      : base(original, cloner) {
71      problemTypeParam = cloner.Clone(original.problemTypeParam);
72      qualityUpdateIntervalParam = cloner.Clone(original.qualityUpdateIntervalParam);
73      if (original.qualityPerClock != null)
74        qualityPerClock = cloner.Clone(original.qualityPerClock);
75    }
76
77    public TimeSpan QualityUpdateInterval {
78      get => qualityUpdateIntervalParam.Value.Value;
79      set => qualityUpdateIntervalParam.Value.Value = value;
80    }
81
82    public IValueParameter<TimeSpanValue> QualityUpdateIntervalParameter => qualityUpdateIntervalParam;
83
84    public virtual bool SupportsQualityUpdate => true;
85
86    protected virtual TimeSpan IntermediateTimeLimit => QualityUpdateInterval;
87
88    public override void Reset() {
89      base.Reset();
90      stopwatch.Reset();
91      executionTime = TimeSpan.Zero;
92    }
93
94    public override void Solve(ILinearProblemDefinition problemDefinition,
95      ResultCollection results, CancellationToken cancellationToken) {
96      if (!SupportsQualityUpdate || QualityUpdateInterval == TimeSpan.Zero) {
97        base.Solve(problemDefinition, results, cancellationToken);
98        return;
99      }
100
101      var timeLimit = TimeLimit;
102      var unlimitedRuntime = timeLimit == TimeSpan.Zero;
103
104      if (!unlimitedRuntime) {
105        timeLimit -= executionTime;
106      }
107
108      var iterations = (long)timeLimit.TotalMilliseconds / (long)QualityUpdateInterval.TotalMilliseconds;
109      var remaining = timeLimit - TimeSpan.FromMilliseconds(iterations * QualityUpdateInterval.TotalMilliseconds);
110      var validResultStatuses = new[] { ResultStatus.NotSolved, ResultStatus.Feasible };
111
112      while (unlimitedRuntime || iterations > 0) {
113        if (cancellationToken.IsCancellationRequested)
114          return;
115
116        stopwatch.Start();
117        Solve(problemDefinition, results, IntermediateTimeLimit);
118        stopwatch.Stop();
119        executionTime += stopwatch.Elapsed;
120        UpdateQuality(results, executionTime);
121
122        var resultStatus = ((EnumValue<ResultStatus>)results["ResultStatus"].Value).Value;
123        if (!validResultStatuses.Contains(resultStatus))
124          return;
125
126        if (!unlimitedRuntime)
127          iterations--;
128      }
129
130      if (remaining > TimeSpan.Zero) {
131        Solve(problemDefinition, results, remaining);
132        UpdateQuality(results, executionTime);
133      }
134    }
135
136    private void UpdateQuality(ResultCollection results, TimeSpan executionTime) {
137      IndexedDataRow<double> qpcRow;
138      IndexedDataRow<double> bpcRow;
139
140      if (!results.Exists(r => r.Name == "QualityPerClock")) {
141        qualityPerClock = new IndexedDataTable<double>("Quality per Clock");
142        qpcRow = new IndexedDataRow<double>("Objective Value");
143        bpcRow = new IndexedDataRow<double>("Bound");
144        qualityPerClock.Rows.Add(qpcRow);
145        qualityPerClock.Rows.Add(bpcRow);
146        results.AddOrUpdateResult("QualityPerClock", qualityPerClock);
147      } else {
148        qpcRow = qualityPerClock.Rows["Objective Value"];
149        bpcRow = qualityPerClock.Rows["Bound"];
150      }
151
152      var resultStatus = ((EnumValue<ResultStatus>)results["ResultStatus"].Value).Value;
153
154      if (new[] { ResultStatus.Abnormal, ResultStatus.NotSolved, ResultStatus.Unbounded }.Contains(resultStatus))
155        return;
156
157      var objective = ((DoubleValue)results["BestObjectiveValue"].Value).Value;
158      var bound = solver.IsMip() ? ((DoubleValue)results["BestObjectiveBound"].Value).Value : double.NaN;
159      var time = executionTime.TotalSeconds;
160
161      if (!qpcRow.Values.Any()) {
162        if (!double.IsInfinity(objective) && !double.IsNaN(objective)) {
163          qpcRow.Values.Add(Tuple.Create(time, objective));
164          qpcRow.Values.Add(Tuple.Create(time, objective));
165          results.AddOrUpdateResult("BestObjectiveValueFoundAt", new TimeSpanValue(TimeSpan.FromSeconds(time)));
166        }
167      } else {
168        var previousBest = qpcRow.Values.Last().Item2;
169        qpcRow.Values[qpcRow.Values.Count - 1] = Tuple.Create(time, objective);
170        if (!objective.IsAlmost(previousBest)) {
171          qpcRow.Values.Add(Tuple.Create(time, objective));
172          results.AddOrUpdateResult("BestObjectiveValueFoundAt", new TimeSpanValue(TimeSpan.FromSeconds(time)));
173        }
174      }
175
176      if (!solver.IsMip())
177        return;
178
179      if (!bpcRow.Values.Any()) {
180        if (!double.IsInfinity(bound) && !double.IsNaN(bound)) {
181          bpcRow.Values.Add(Tuple.Create(time, bound));
182          bpcRow.Values.Add(Tuple.Create(time, bound));
183        }
184      } else {
185        var previousBest = bpcRow.Values.Last().Item2;
186        bpcRow.Values[bpcRow.Values.Count - 1] = Tuple.Create(time, bound);
187        if (!bound.IsAlmost(previousBest)) {
188          bpcRow.Values.Add(Tuple.Create(time, bound));
189        }
190      }
191    }
192  }
193}
Note: See TracBrowser for help on using the repository browser.