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 @ 16736

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

#2931: Upgraded persistence to HEAL.Attic

File size: 7.3 KB
RevLine 
[16288]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;
[16582]23using System.Diagnostics;
[16233]24using System.Linq;
25using System.Threading;
26using HeuristicLab.Analysis;
27using HeuristicLab.Common;
28using HeuristicLab.Core;
29using HeuristicLab.Data;
[16405]30using HeuristicLab.Optimization;
[16233]31using HeuristicLab.Parameters;
[16736]32using HEAL.Attic;
[16233]33
[16582]34namespace HeuristicLab.ExactOptimization.LinearProgramming {
[16233]35
[16736]36  [StorableType("8730ECDD-8F38-47C2-B0D9-2B1F38FC0A27")]
[16405]37  public class IncrementalLinearSolver : LinearSolver, IIncrementalLinearSolver {
[16288]38
[16582]39    [Storable]
40    protected readonly IValueParameter<TimeSpanValue> qualityUpdateIntervalParam;
[16233]41
[16582]42    private readonly Stopwatch stopwatch = new Stopwatch();
[16233]43
[16582]44    [Storable]
45    private TimeSpan executionTime = TimeSpan.Zero;
[16233]46
[16582]47    [Storable]
48    private IndexedDataTable<double> qualityPerClock;
49
[16405]50    public IncrementalLinearSolver() {
[16233]51      Parameters.Add(qualityUpdateIntervalParam =
52        new ValueParameter<TimeSpanValue>(nameof(QualityUpdateInterval),
[16373]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          }
[16233]60        } else {
[16373]61          Parameters.Remove(qualityUpdateIntervalParam);
[16233]62        }
63      };
64    }
65
[16405]66    [StorableConstructor]
[16736]67    protected IncrementalLinearSolver(StorableConstructorFlag _) : base(_) { }
[16405]68
69    protected IncrementalLinearSolver(IncrementalLinearSolver original, Cloner cloner)
70      : base(original, cloner) {
[16373]71      problemTypeParam = cloner.Clone(original.problemTypeParam);
[16233]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
[16582]82    public IValueParameter<TimeSpanValue> QualityUpdateIntervalParameter => qualityUpdateIntervalParam;
83
[16405]84    public virtual bool SupportsQualityUpdate => true;
[16582]85
[16405]86    protected virtual TimeSpan IntermediateTimeLimit => QualityUpdateInterval;
[16373]87
[16582]88    public override void Reset() {
89      base.Reset();
90      stopwatch.Reset();
91      executionTime = TimeSpan.Zero;
92    }
93
94    public override void Solve(ILinearProblemDefinition problemDefinition,
[16405]95      ResultCollection results, CancellationToken cancellationToken) {
[16373]96      if (!SupportsQualityUpdate || QualityUpdateInterval == TimeSpan.Zero) {
[16582]97        base.Solve(problemDefinition, results, cancellationToken);
[16233]98        return;
99      }
100
[16405]101      var timeLimit = TimeLimit;
[16233]102      var unlimitedRuntime = timeLimit == TimeSpan.Zero;
103
104      if (!unlimitedRuntime) {
[16405]105        timeLimit -= executionTime;
[16233]106      }
[16234]107
[16233]108      var iterations = (long)timeLimit.TotalMilliseconds / (long)QualityUpdateInterval.TotalMilliseconds;
109      var remaining = timeLimit - TimeSpan.FromMilliseconds(iterations * QualityUpdateInterval.TotalMilliseconds);
[16373]110      var validResultStatuses = new[] { ResultStatus.NotSolved, ResultStatus.Feasible };
[16233]111
112      while (unlimitedRuntime || iterations > 0) {
[16373]113        if (cancellationToken.IsCancellationRequested)
114          return;
115
[16582]116        stopwatch.Start();
[16405]117        Solve(problemDefinition, results, IntermediateTimeLimit);
[16582]118        stopwatch.Stop();
119        executionTime += stopwatch.Elapsed;
[16405]120        UpdateQuality(results, executionTime);
[16233]121
[16405]122        var resultStatus = ((EnumValue<ResultStatus>)results["ResultStatus"].Value).Value;
[16373]123        if (!validResultStatuses.Contains(resultStatus))
[16233]124          return;
125
126        if (!unlimitedRuntime)
127          iterations--;
128      }
129
130      if (remaining > TimeSpan.Zero) {
[16405]131        Solve(problemDefinition, results, remaining);
132        UpdateQuality(results, executionTime);
[16233]133      }
134    }
135
[16405]136    private void UpdateQuality(ResultCollection results, TimeSpan executionTime) {
[16582]137      IndexedDataRow<double> qpcRow;
138      IndexedDataRow<double> bpcRow;
139
[16405]140      if (!results.Exists(r => r.Name == "QualityPerClock")) {
[16233]141        qualityPerClock = new IndexedDataTable<double>("Quality per Clock");
[16373]142        qpcRow = new IndexedDataRow<double>("Objective Value");
143        bpcRow = new IndexedDataRow<double>("Bound");
[16582]144        qualityPerClock.Rows.Add(qpcRow);
145        qualityPerClock.Rows.Add(bpcRow);
[16405]146        results.AddOrUpdateResult("QualityPerClock", qualityPerClock);
[16582]147      } else {
148        qpcRow = qualityPerClock.Rows["Objective Value"];
149        bpcRow = qualityPerClock.Rows["Bound"];
[16233]150      }
151
[16405]152      var resultStatus = ((EnumValue<ResultStatus>)results["ResultStatus"].Value).Value;
[16233]153
[16373]154      if (new[] { ResultStatus.Abnormal, ResultStatus.NotSolved, ResultStatus.Unbounded }.Contains(resultStatus))
[16233]155        return;
156
[16405]157      var objective = ((DoubleValue)results["BestObjectiveValue"].Value).Value;
[16582]158      var bound = solver.IsMip() ? ((DoubleValue)results["BestObjectiveBound"].Value).Value : double.NaN;
[16405]159      var time = executionTime.TotalSeconds;
[16233]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));
[16405]165          results.AddOrUpdateResult("BestObjectiveValueFoundAt", new TimeSpanValue(TimeSpan.FromSeconds(time)));
[16233]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));
[16405]172          results.AddOrUpdateResult("BestObjectiveValueFoundAt", new TimeSpanValue(TimeSpan.FromSeconds(time)));
[16233]173        }
174      }
175
[16582]176      if (!solver.IsMip())
[16373]177        return;
178
[16233]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  }
[16288]193}
Note: See TracBrowser for help on using the repository browser.