Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 16582 was 16582, checked in by ddorfmei, 5 years ago

#2931: solved the issues found during the review

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 HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
33
34namespace HeuristicLab.ExactOptimization.LinearProgramming {
35
36  [StorableClass]
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(bool deserializing)
68      : base(deserializing) {
69    }
70
71    protected IncrementalLinearSolver(IncrementalLinearSolver original, Cloner cloner)
72      : base(original, cloner) {
73      problemTypeParam = cloner.Clone(original.problemTypeParam);
74      qualityUpdateIntervalParam = cloner.Clone(original.qualityUpdateIntervalParam);
75      if (original.qualityPerClock != null)
76        qualityPerClock = cloner.Clone(original.qualityPerClock);
77    }
78
79    public TimeSpan QualityUpdateInterval {
80      get => qualityUpdateIntervalParam.Value.Value;
81      set => qualityUpdateIntervalParam.Value.Value = value;
82    }
83
84    public IValueParameter<TimeSpanValue> QualityUpdateIntervalParameter => qualityUpdateIntervalParam;
85
86    public virtual bool SupportsQualityUpdate => true;
87
88    protected virtual TimeSpan IntermediateTimeLimit => QualityUpdateInterval;
89
90    public override void Reset() {
91      base.Reset();
92      stopwatch.Reset();
93      executionTime = TimeSpan.Zero;
94    }
95
96    public override void Solve(ILinearProblemDefinition problemDefinition,
97      ResultCollection results, CancellationToken cancellationToken) {
98      if (!SupportsQualityUpdate || QualityUpdateInterval == TimeSpan.Zero) {
99        base.Solve(problemDefinition, results, cancellationToken);
100        return;
101      }
102
103      var timeLimit = TimeLimit;
104      var unlimitedRuntime = timeLimit == TimeSpan.Zero;
105
106      if (!unlimitedRuntime) {
107        timeLimit -= executionTime;
108      }
109
110      var iterations = (long)timeLimit.TotalMilliseconds / (long)QualityUpdateInterval.TotalMilliseconds;
111      var remaining = timeLimit - TimeSpan.FromMilliseconds(iterations * QualityUpdateInterval.TotalMilliseconds);
112      var validResultStatuses = new[] { ResultStatus.NotSolved, ResultStatus.Feasible };
113
114      while (unlimitedRuntime || iterations > 0) {
115        if (cancellationToken.IsCancellationRequested)
116          return;
117
118        stopwatch.Start();
119        Solve(problemDefinition, results, IntermediateTimeLimit);
120        stopwatch.Stop();
121        executionTime += stopwatch.Elapsed;
122        UpdateQuality(results, executionTime);
123
124        var resultStatus = ((EnumValue<ResultStatus>)results["ResultStatus"].Value).Value;
125        if (!validResultStatuses.Contains(resultStatus))
126          return;
127
128        if (!unlimitedRuntime)
129          iterations--;
130      }
131
132      if (remaining > TimeSpan.Zero) {
133        Solve(problemDefinition, results, remaining);
134        UpdateQuality(results, executionTime);
135      }
136    }
137
138    private void UpdateQuality(ResultCollection results, TimeSpan executionTime) {
139      IndexedDataRow<double> qpcRow;
140      IndexedDataRow<double> bpcRow;
141
142      if (!results.Exists(r => r.Name == "QualityPerClock")) {
143        qualityPerClock = new IndexedDataTable<double>("Quality per Clock");
144        qpcRow = new IndexedDataRow<double>("Objective Value");
145        bpcRow = new IndexedDataRow<double>("Bound");
146        qualityPerClock.Rows.Add(qpcRow);
147        qualityPerClock.Rows.Add(bpcRow);
148        results.AddOrUpdateResult("QualityPerClock", qualityPerClock);
149      } else {
150        qpcRow = qualityPerClock.Rows["Objective Value"];
151        bpcRow = qualityPerClock.Rows["Bound"];
152      }
153
154      var resultStatus = ((EnumValue<ResultStatus>)results["ResultStatus"].Value).Value;
155
156      if (new[] { ResultStatus.Abnormal, ResultStatus.NotSolved, ResultStatus.Unbounded }.Contains(resultStatus))
157        return;
158
159      var objective = ((DoubleValue)results["BestObjectiveValue"].Value).Value;
160      var bound = solver.IsMip() ? ((DoubleValue)results["BestObjectiveBound"].Value).Value : double.NaN;
161      var time = executionTime.TotalSeconds;
162
163      if (!qpcRow.Values.Any()) {
164        if (!double.IsInfinity(objective) && !double.IsNaN(objective)) {
165          qpcRow.Values.Add(Tuple.Create(time, objective));
166          qpcRow.Values.Add(Tuple.Create(time, objective));
167          results.AddOrUpdateResult("BestObjectiveValueFoundAt", new TimeSpanValue(TimeSpan.FromSeconds(time)));
168        }
169      } else {
170        var previousBest = qpcRow.Values.Last().Item2;
171        qpcRow.Values[qpcRow.Values.Count - 1] = Tuple.Create(time, objective);
172        if (!objective.IsAlmost(previousBest)) {
173          qpcRow.Values.Add(Tuple.Create(time, objective));
174          results.AddOrUpdateResult("BestObjectiveValueFoundAt", new TimeSpanValue(TimeSpan.FromSeconds(time)));
175        }
176      }
177
178      if (!solver.IsMip())
179        return;
180
181      if (!bpcRow.Values.Any()) {
182        if (!double.IsInfinity(bound) && !double.IsNaN(bound)) {
183          bpcRow.Values.Add(Tuple.Create(time, bound));
184          bpcRow.Values.Add(Tuple.Create(time, bound));
185        }
186      } else {
187        var previousBest = bpcRow.Values.Last().Item2;
188        bpcRow.Values[bpcRow.Values.Count - 1] = Tuple.Create(time, bound);
189        if (!bound.IsAlmost(previousBest)) {
190          bpcRow.Values.Add(Tuple.Create(time, bound));
191        }
192      }
193    }
194  }
195}
Note: See TracBrowser for help on using the repository browser.