1 | using System;
|
---|
2 | using System.Linq;
|
---|
3 | using System.Threading;
|
---|
4 | using Google.OrTools.LinearSolver;
|
---|
5 | using HeuristicLab.Analysis;
|
---|
6 | using HeuristicLab.Common;
|
---|
7 | using HeuristicLab.Core;
|
---|
8 | using HeuristicLab.Data;
|
---|
9 | using HeuristicLab.Parameters;
|
---|
10 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
|
---|
11 |
|
---|
12 | namespace HeuristicLab.MathematicalOptimization.LinearProgramming.Algorithms.Solvers.Base {
|
---|
13 |
|
---|
14 | [StorableClass]
|
---|
15 | public class IncrementalSolver : Solver, IIncrementalSolver {
|
---|
16 | [Storable]
|
---|
17 | protected readonly IValueParameter<BoolValue> incrementalityParam;
|
---|
18 |
|
---|
19 | [Storable]
|
---|
20 | protected readonly IValueParameter<TimeSpanValue> qualityUpdateIntervalParam;
|
---|
21 |
|
---|
22 | private IndexedDataRow<double> bpcRow;
|
---|
23 |
|
---|
24 | private IndexedDataRow<double> qpcRow;
|
---|
25 |
|
---|
26 | [Storable]
|
---|
27 | private IndexedDataTable<double> qualityPerClock;
|
---|
28 |
|
---|
29 | public IncrementalSolver() {
|
---|
30 | Parameters.Add(incrementalityParam = new ValueParameter<BoolValue>(nameof(Incrementality),
|
---|
31 | "Advanced usage: incrementality from one solve to the next.",
|
---|
32 | new BoolValue(MPSolverParameters.kDefaultIncrementality == MPSolverParameters.INCREMENTALITY_ON)));
|
---|
33 | Parameters.Add(qualityUpdateIntervalParam =
|
---|
34 | new ValueParameter<TimeSpanValue>(nameof(QualityUpdateInterval),
|
---|
35 | "Time interval before solver is paused, resuls are retrieved and solver is resumed.",
|
---|
36 | new TimeSpanValue(new TimeSpan(0, 0, 10))));
|
---|
37 |
|
---|
38 | incrementalityParam.Value.ValueChanged += (sender, args) => {
|
---|
39 | if (((BoolValue)sender).Value) {
|
---|
40 | qualityUpdateIntervalParam.Value = new TimeSpanValue(qualityUpdateIntervalParam.Value.Value);
|
---|
41 | } else {
|
---|
42 | qualityUpdateIntervalParam.Value = (TimeSpanValue)qualityUpdateIntervalParam.Value.AsReadOnly();
|
---|
43 | }
|
---|
44 | };
|
---|
45 | }
|
---|
46 |
|
---|
47 | protected IncrementalSolver(IncrementalSolver original, Cloner cloner)
|
---|
48 | : base(original, cloner) {
|
---|
49 | programmingTypeParam = cloner.Clone(original.programmingTypeParam);
|
---|
50 | qualityUpdateIntervalParam = cloner.Clone(original.qualityUpdateIntervalParam);
|
---|
51 | incrementalityParam = cloner.Clone(original.incrementalityParam);
|
---|
52 | if (original.qualityPerClock != null)
|
---|
53 | qualityPerClock = cloner.Clone(original.qualityPerClock);
|
---|
54 | }
|
---|
55 |
|
---|
56 | public bool Incrementality {
|
---|
57 | get => incrementalityParam.Value.Value;
|
---|
58 | set => incrementalityParam.Value.Value = value;
|
---|
59 | }
|
---|
60 |
|
---|
61 | public TimeSpan QualityUpdateInterval {
|
---|
62 | get => qualityUpdateIntervalParam.Value.Value;
|
---|
63 | set => qualityUpdateIntervalParam.Value.Value = value;
|
---|
64 | }
|
---|
65 |
|
---|
66 | public override void Solve(LinearProgrammingAlgorithm algorithm, CancellationToken cancellationToken) {
|
---|
67 | if (!Incrementality) {
|
---|
68 | base.Solve(algorithm, cancellationToken);
|
---|
69 | return;
|
---|
70 | }
|
---|
71 |
|
---|
72 | var timeLimit = algorithm.TimeLimit;
|
---|
73 | var unlimitedRuntime = timeLimit == TimeSpan.Zero;
|
---|
74 |
|
---|
75 | if (!unlimitedRuntime) {
|
---|
76 | var wallTime = ((TimeSpanValue)algorithm.Results.SingleOrDefault(r => r.Name == "Wall Time")?.Value)?.Value;
|
---|
77 | if (wallTime.HasValue) {
|
---|
78 | timeLimit -= wallTime.Value;
|
---|
79 | }
|
---|
80 | }
|
---|
81 |
|
---|
82 | var iterations = (long)timeLimit.TotalMilliseconds / (long)QualityUpdateInterval.TotalMilliseconds;
|
---|
83 | var remaining = timeLimit - TimeSpan.FromMilliseconds(iterations * QualityUpdateInterval.TotalMilliseconds);
|
---|
84 | var validResultStatuses = new[] { ResultStatus.NOT_SOLVED, ResultStatus.FEASIBLE };
|
---|
85 |
|
---|
86 | while (unlimitedRuntime || iterations > 0) {
|
---|
87 | base.Solve(algorithm, QualityUpdateInterval, true);
|
---|
88 | UpdateQuality(algorithm);
|
---|
89 |
|
---|
90 | var resultStatus = ((EnumValue<ResultStatus>)algorithm.Results["Result Status"].Value).Value;
|
---|
91 | if (!validResultStatuses.Contains(resultStatus) || cancellationToken.IsCancellationRequested)
|
---|
92 | return;
|
---|
93 |
|
---|
94 | if (!unlimitedRuntime)
|
---|
95 | iterations--;
|
---|
96 | }
|
---|
97 |
|
---|
98 | if (remaining > TimeSpan.Zero) {
|
---|
99 | base.Solve(algorithm, remaining, true);
|
---|
100 | UpdateQuality(algorithm);
|
---|
101 | }
|
---|
102 | }
|
---|
103 |
|
---|
104 | private void UpdateQuality(LinearProgrammingAlgorithm algorithm) {
|
---|
105 | if (!algorithm.Results.Exists(r => r.Name == "QualityPerClock")) {
|
---|
106 | qualityPerClock = new IndexedDataTable<double>("Quality per Clock");
|
---|
107 | qpcRow = new IndexedDataRow<double>("First-hit Graph Objective");
|
---|
108 | bpcRow = new IndexedDataRow<double>("First-hit Graph Bound");
|
---|
109 | algorithm.Results.AddOrUpdateResult("QualityPerClock", qualityPerClock);
|
---|
110 | }
|
---|
111 |
|
---|
112 | var resultStatus = ((EnumValue<ResultStatus>)algorithm.Results["Result Status"].Value).Value;
|
---|
113 |
|
---|
114 | if (new[] { ResultStatus.ABNORMAL, ResultStatus.NOT_SOLVED, ResultStatus.UNBOUNDED }.Contains(resultStatus))
|
---|
115 | return;
|
---|
116 |
|
---|
117 | var objective = ((DoubleValue)algorithm.Results["Best Objective Value"].Value).Value;
|
---|
118 | var bound = ((DoubleValue)algorithm.Results["Best Objective Bound"].Value).Value;
|
---|
119 | var time = algorithm.ExecutionTime.TotalSeconds;
|
---|
120 |
|
---|
121 | if (!qpcRow.Values.Any()) {
|
---|
122 | if (!double.IsInfinity(objective) && !double.IsNaN(objective)) {
|
---|
123 | qpcRow.Values.Add(Tuple.Create(time, objective));
|
---|
124 | qpcRow.Values.Add(Tuple.Create(time, objective));
|
---|
125 | qualityPerClock.Rows.Add(qpcRow);
|
---|
126 | algorithm.Results.AddOrUpdateResult("Best Solution Found At", new TimeSpanValue(TimeSpan.FromSeconds(time)));
|
---|
127 | }
|
---|
128 | } else {
|
---|
129 | var previousBest = qpcRow.Values.Last().Item2;
|
---|
130 | qpcRow.Values[qpcRow.Values.Count - 1] = Tuple.Create(time, objective);
|
---|
131 | if (!objective.IsAlmost(previousBest)) {
|
---|
132 | qpcRow.Values.Add(Tuple.Create(time, objective));
|
---|
133 | algorithm.Results.AddOrUpdateResult("Best Solution Found At", new TimeSpanValue(TimeSpan.FromSeconds(time)));
|
---|
134 | }
|
---|
135 | }
|
---|
136 |
|
---|
137 | if (!bpcRow.Values.Any()) {
|
---|
138 | if (!double.IsInfinity(bound) && !double.IsNaN(bound)) {
|
---|
139 | bpcRow.Values.Add(Tuple.Create(time, bound));
|
---|
140 | bpcRow.Values.Add(Tuple.Create(time, bound));
|
---|
141 | qualityPerClock.Rows.Add(bpcRow);
|
---|
142 | }
|
---|
143 | } else {
|
---|
144 | var previousBest = bpcRow.Values.Last().Item2;
|
---|
145 | bpcRow.Values[bpcRow.Values.Count - 1] = Tuple.Create(time, bound);
|
---|
146 | if (!bound.IsAlmost(previousBest)) {
|
---|
147 | bpcRow.Values.Add(Tuple.Create(time, bound));
|
---|
148 | }
|
---|
149 | }
|
---|
150 | }
|
---|
151 | }
|
---|
152 | } |
---|