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

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

#2931:

  • moved views to separate plugin HeuristicLab.MathematicalOptimization.Views
  • added button in LinearProgrammingProblemView to select the problem definition type
  • added views for problem definitions
  • added ExportFile parameter to LinearProgrammingAlgorithm
  • extended FileValue and FileValueView by the option to save a file
  • code cleanup
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.Optimization;
30using HeuristicLab.Parameters;
31using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
32
33namespace HeuristicLab.MathematicalOptimization.LinearProgramming {
34
35  [StorableClass]
36  public class IncrementalLinearSolver : LinearSolver, IIncrementalLinearSolver {
37    [Storable] protected readonly IValueParameter<TimeSpanValue> qualityUpdateIntervalParam;
38
39    private IndexedDataRow<double> bpcRow;
40
41    private IndexedDataRow<double> qpcRow;
42
43    [Storable] private IndexedDataTable<double> qualityPerClock;
44
45    public IncrementalLinearSolver() {
46      Parameters.Add(qualityUpdateIntervalParam =
47        new ValueParameter<TimeSpanValue>(nameof(QualityUpdateInterval),
48          "Time interval before solver is paused, results are retrieved and solver is resumed. " +
49          "Set to zero for no intermediate results and faster solving.", new TimeSpanValue(new TimeSpan(0, 0, 10))));
50      problemTypeParam.Value.ValueChanged += (sender, args) => {
51        if (SupportsQualityUpdate) {
52          if (!Parameters.Contains(qualityUpdateIntervalParam)) {
53            Parameters.Add(qualityUpdateIntervalParam);
54          }
55        } else {
56          Parameters.Remove(qualityUpdateIntervalParam);
57        }
58      };
59    }
60
61    [StorableConstructor]
62    protected IncrementalLinearSolver(bool deserializing)
63      : base(deserializing) {
64    }
65
66    protected IncrementalLinearSolver(IncrementalLinearSolver original, Cloner cloner)
67      : base(original, cloner) {
68      problemTypeParam = cloner.Clone(original.problemTypeParam);
69      qualityUpdateIntervalParam = cloner.Clone(original.qualityUpdateIntervalParam);
70      if (original.qualityPerClock != null)
71        qualityPerClock = cloner.Clone(original.qualityPerClock);
72    }
73
74    public TimeSpan QualityUpdateInterval {
75      get => qualityUpdateIntervalParam.Value.Value;
76      set => qualityUpdateIntervalParam.Value.Value = value;
77    }
78
79    public virtual bool SupportsQualityUpdate => true;
80    protected virtual TimeSpan IntermediateTimeLimit => QualityUpdateInterval;
81
82    public override void Solve(ILinearProgrammingProblemDefinition problemDefinition, ref TimeSpan executionTime,
83      ResultCollection results, CancellationToken cancellationToken) {
84      if (!SupportsQualityUpdate || QualityUpdateInterval == TimeSpan.Zero) {
85        base.Solve(problemDefinition, ref executionTime, results, cancellationToken);
86        return;
87      }
88
89      var timeLimit = TimeLimit;
90      var unlimitedRuntime = timeLimit == TimeSpan.Zero;
91
92      if (!unlimitedRuntime) {
93        timeLimit -= executionTime;
94      }
95
96      var iterations = (long)timeLimit.TotalMilliseconds / (long)QualityUpdateInterval.TotalMilliseconds;
97      var remaining = timeLimit - TimeSpan.FromMilliseconds(iterations * QualityUpdateInterval.TotalMilliseconds);
98      var validResultStatuses = new[] { ResultStatus.NotSolved, ResultStatus.Feasible };
99
100      while (unlimitedRuntime || iterations > 0) {
101        if (cancellationToken.IsCancellationRequested)
102          return;
103
104        Solve(problemDefinition, results, IntermediateTimeLimit);
105        UpdateQuality(results, executionTime);
106
107        var resultStatus = ((EnumValue<ResultStatus>)results["ResultStatus"].Value).Value;
108        if (!validResultStatuses.Contains(resultStatus))
109          return;
110
111        if (!unlimitedRuntime)
112          iterations--;
113      }
114
115      if (remaining > TimeSpan.Zero) {
116        Solve(problemDefinition, results, remaining);
117        UpdateQuality(results, executionTime);
118      }
119    }
120
121    private void UpdateQuality(ResultCollection results, TimeSpan executionTime) {
122      if (!results.Exists(r => r.Name == "QualityPerClock")) {
123        qualityPerClock = new IndexedDataTable<double>("Quality per Clock");
124        qpcRow = new IndexedDataRow<double>("Objective Value");
125        bpcRow = new IndexedDataRow<double>("Bound");
126        results.AddOrUpdateResult("QualityPerClock", qualityPerClock);
127      }
128
129      var resultStatus = ((EnumValue<ResultStatus>)results["ResultStatus"].Value).Value;
130
131      if (new[] { ResultStatus.Abnormal, ResultStatus.NotSolved, ResultStatus.Unbounded }.Contains(resultStatus))
132        return;
133
134      var objective = ((DoubleValue)results["BestObjectiveValue"].Value).Value;
135      var bound = solver.IsMIP() ? ((DoubleValue)results["BestObjectiveBound"].Value).Value : double.NaN;
136      var time = executionTime.TotalSeconds;
137
138      if (!qpcRow.Values.Any()) {
139        if (!double.IsInfinity(objective) && !double.IsNaN(objective)) {
140          qpcRow.Values.Add(Tuple.Create(time, objective));
141          qpcRow.Values.Add(Tuple.Create(time, objective));
142          qualityPerClock.Rows.Add(qpcRow);
143          results.AddOrUpdateResult("BestObjectiveValueFoundAt", new TimeSpanValue(TimeSpan.FromSeconds(time)));
144        }
145      } else {
146        var previousBest = qpcRow.Values.Last().Item2;
147        qpcRow.Values[qpcRow.Values.Count - 1] = Tuple.Create(time, objective);
148        if (!objective.IsAlmost(previousBest)) {
149          qpcRow.Values.Add(Tuple.Create(time, objective));
150          results.AddOrUpdateResult("BestObjectiveValueFoundAt", new TimeSpanValue(TimeSpan.FromSeconds(time)));
151        }
152      }
153
154      if (!solver.IsMIP())
155        return;
156
157      if (!bpcRow.Values.Any()) {
158        if (!double.IsInfinity(bound) && !double.IsNaN(bound)) {
159          bpcRow.Values.Add(Tuple.Create(time, bound));
160          bpcRow.Values.Add(Tuple.Create(time, bound));
161          qualityPerClock.Rows.Add(bpcRow);
162        }
163      } else {
164        var previousBest = bpcRow.Values.Last().Item2;
165        bpcRow.Values[bpcRow.Values.Count - 1] = Tuple.Create(time, bound);
166        if (!bound.IsAlmost(previousBest)) {
167          bpcRow.Values.Add(Tuple.Create(time, bound));
168        }
169      }
170    }
171  }
172}
Note: See TracBrowser for help on using the repository browser.