Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/HeuristicLab.ExactOptimization/3.3/LinearProgramming/Algorithms/Solvers/Base/IncrementalLinearSolver.cs @ 16910

Last change on this file since 16910 was 16910, checked in by abeham, 5 years ago

#2931: merged to trunk

  • Fixed references in plugins
  • Fixed output path
  • Removed app.config from views plugin
  • Reverted changes to PathValue and FileValue and their respective views
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      executionTime = TimeSpan.Zero;
91    }
92
93    public override void Solve(ILinearProblemDefinition problemDefinition,
94      ResultCollection results, CancellationToken cancellationToken) {
95      if (!SupportsQualityUpdate || QualityUpdateInterval == TimeSpan.Zero) {
96        base.Solve(problemDefinition, results, cancellationToken);
97        return;
98      }
99
100      var timeLimit = TimeLimit;
101      var unlimitedRuntime = timeLimit == TimeSpan.Zero;
102
103      if (!unlimitedRuntime) {
104        timeLimit -= executionTime;
105      }
106
107      var iterations = (long)timeLimit.TotalMilliseconds / (long)QualityUpdateInterval.TotalMilliseconds;
108      var remaining = timeLimit - TimeSpan.FromMilliseconds(iterations * QualityUpdateInterval.TotalMilliseconds);
109      var validResultStatuses = new[] { ResultStatus.NotSolved, ResultStatus.Feasible };
110
111      while (unlimitedRuntime || iterations > 0) {
112        if (cancellationToken.IsCancellationRequested)
113          return;
114
115        stopwatch.Restart();
116        Solve(problemDefinition, results, IntermediateTimeLimit);
117        stopwatch.Stop();
118        executionTime += stopwatch.Elapsed;
119        UpdateQuality(results, executionTime);
120
121        var resultStatus = ((EnumValue<ResultStatus>)results["ResultStatus"].Value).Value;
122        if (!validResultStatuses.Contains(resultStatus))
123          return;
124
125        if (!unlimitedRuntime)
126          iterations--;
127      }
128
129      if (remaining > TimeSpan.Zero) {
130        Solve(problemDefinition, results, remaining);
131        UpdateQuality(results, executionTime);
132      }
133    }
134
135    private void UpdateQuality(ResultCollection results, TimeSpan executionTime) {
136      IndexedDataRow<double> qpcRow;
137      IndexedDataRow<double> bpcRow;
138
139      if (!results.Exists(r => r.Name == "QualityPerClock")) {
140        qualityPerClock = new IndexedDataTable<double>("Quality per Clock");
141        qpcRow = new IndexedDataRow<double>("Objective Value");
142        bpcRow = new IndexedDataRow<double>("Bound");
143        qualityPerClock.Rows.Add(qpcRow);
144        qualityPerClock.Rows.Add(bpcRow);
145        results.AddOrUpdateResult("QualityPerClock", qualityPerClock);
146      } else {
147        qpcRow = qualityPerClock.Rows["Objective Value"];
148        bpcRow = qualityPerClock.Rows["Bound"];
149      }
150
151      var resultStatus = ((EnumValue<ResultStatus>)results["ResultStatus"].Value).Value;
152
153      if (new[] { ResultStatus.Abnormal, ResultStatus.NotSolved, ResultStatus.Unbounded }.Contains(resultStatus))
154        return;
155
156      var objective = ((DoubleValue)results["BestObjectiveValue"].Value).Value;
157      var bound = solver.IsMip() ? ((DoubleValue)results["BestObjectiveBound"].Value).Value : double.NaN;
158      var time = executionTime.TotalSeconds;
159
160      if (!qpcRow.Values.Any()) {
161        if (!double.IsInfinity(objective) && !double.IsNaN(objective)) {
162          qpcRow.Values.Add(Tuple.Create(time, objective));
163          qpcRow.Values.Add(Tuple.Create(time, objective));
164          results.AddOrUpdateResult("BestObjectiveValueFoundAt", new TimeSpanValue(TimeSpan.FromSeconds(time)));
165        }
166      } else {
167        var previousBest = qpcRow.Values.Last().Item2;
168        qpcRow.Values[qpcRow.Values.Count - 1] = Tuple.Create(time, objective);
169        if (!objective.IsAlmost(previousBest)) {
170          qpcRow.Values.Add(Tuple.Create(time, objective));
171          results.AddOrUpdateResult("BestObjectiveValueFoundAt", new TimeSpanValue(TimeSpan.FromSeconds(time)));
172        }
173      }
174
175      if (!solver.IsMip())
176        return;
177
178      if (!bpcRow.Values.Any()) {
179        if (!double.IsInfinity(bound) && !double.IsNaN(bound)) {
180          bpcRow.Values.Add(Tuple.Create(time, bound));
181          bpcRow.Values.Add(Tuple.Create(time, bound));
182        }
183      } else {
184        var previousBest = bpcRow.Values.Last().Item2;
185        bpcRow.Values[bpcRow.Values.Count - 1] = Tuple.Create(time, bound);
186        if (!bound.IsAlmost(previousBest)) {
187          bpcRow.Values.Add(Tuple.Create(time, bound));
188        }
189      }
190    }
191  }
192}
Note: See TracBrowser for help on using the repository browser.