#region License Information /* HeuristicLab * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL) * * This file is part of HeuristicLab. * * HeuristicLab is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * HeuristicLab is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with HeuristicLab. If not, see . */ #endregion using System; using System.Linq; using System.Threading; using HeuristicLab.Analysis; using HeuristicLab.Common; using HeuristicLab.Core; using HeuristicLab.Data; using HeuristicLab.Parameters; using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; namespace HeuristicLab.MathematicalOptimization.LinearProgramming.Algorithms.Solvers.Base { [StorableClass] public class IncrementalSolver : Solver, IIncrementalSolver { [Storable] protected readonly IValueParameter qualityUpdateIntervalParam; private IndexedDataRow bpcRow; private IndexedDataRow qpcRow; [Storable] private IndexedDataTable qualityPerClock; [StorableConstructor] protected IncrementalSolver(bool deserializing) : base(deserializing) { } public IncrementalSolver() { Parameters.Add(qualityUpdateIntervalParam = new ValueParameter(nameof(QualityUpdateInterval), "Time interval before solver is paused, results are retrieved and solver is resumed. " + "Set to zero for no intermediate results and faster solving.", new TimeSpanValue(new TimeSpan(0, 0, 10)))); problemTypeParam.Value.ValueChanged += (sender, args) => { if (SupportsQualityUpdate) { if (!Parameters.Contains(qualityUpdateIntervalParam)) { Parameters.Add(qualityUpdateIntervalParam); } } else { Parameters.Remove(qualityUpdateIntervalParam); } }; } protected IncrementalSolver(IncrementalSolver original, Cloner cloner) : base(original, cloner) { problemTypeParam = cloner.Clone(original.problemTypeParam); qualityUpdateIntervalParam = cloner.Clone(original.qualityUpdateIntervalParam); if (original.qualityPerClock != null) qualityPerClock = cloner.Clone(original.qualityPerClock); } public virtual bool SupportsQualityUpdate => true; public TimeSpan QualityUpdateInterval { get => qualityUpdateIntervalParam.Value.Value; set => qualityUpdateIntervalParam.Value.Value = value; } protected virtual TimeSpan TimeLimit => QualityUpdateInterval; public override void Solve(LinearProgrammingAlgorithm algorithm, CancellationToken cancellationToken) { if (!SupportsQualityUpdate || QualityUpdateInterval == TimeSpan.Zero) { base.Solve(algorithm, cancellationToken); return; } var timeLimit = algorithm.TimeLimit; var unlimitedRuntime = timeLimit == TimeSpan.Zero; if (!unlimitedRuntime) { timeLimit -= algorithm.ExecutionTime; } var iterations = (long)timeLimit.TotalMilliseconds / (long)QualityUpdateInterval.TotalMilliseconds; var remaining = timeLimit - TimeSpan.FromMilliseconds(iterations * QualityUpdateInterval.TotalMilliseconds); var validResultStatuses = new[] { ResultStatus.NotSolved, ResultStatus.Feasible }; while (unlimitedRuntime || iterations > 0) { if (cancellationToken.IsCancellationRequested) return; base.Solve(algorithm, TimeLimit); UpdateQuality(algorithm); var resultStatus = ((EnumValue)algorithm.Results[nameof(solver.ResultStatus)].Value).Value; if (!validResultStatuses.Contains(resultStatus)) return; if (!unlimitedRuntime) iterations--; } if (remaining > TimeSpan.Zero) { base.Solve(algorithm, remaining); UpdateQuality(algorithm); } } private void UpdateQuality(LinearProgrammingAlgorithm algorithm) { if (!algorithm.Results.Exists(r => r.Name == "QualityPerClock")) { qualityPerClock = new IndexedDataTable("Quality per Clock"); qpcRow = new IndexedDataRow("Objective Value"); bpcRow = new IndexedDataRow("Bound"); algorithm.Results.AddOrUpdateResult("QualityPerClock", qualityPerClock); } var resultStatus = ((EnumValue)algorithm.Results[nameof(solver.ResultStatus)].Value).Value; if (new[] { ResultStatus.Abnormal, ResultStatus.NotSolved, ResultStatus.Unbounded }.Contains(resultStatus)) return; var objective = ((DoubleValue)algorithm.Results[$"Best{nameof(solver.ObjectiveValue)}"].Value).Value; var bound = solver.IsMip ? ((DoubleValue)algorithm.Results[$"Best{nameof(solver.ObjectiveBound)}"].Value).Value : double.NaN; var time = algorithm.ExecutionTime.TotalSeconds; if (!qpcRow.Values.Any()) { if (!double.IsInfinity(objective) && !double.IsNaN(objective)) { qpcRow.Values.Add(Tuple.Create(time, objective)); qpcRow.Values.Add(Tuple.Create(time, objective)); qualityPerClock.Rows.Add(qpcRow); algorithm.Results.AddOrUpdateResult($"Best{nameof(solver.ObjectiveValue)}FoundAt", new TimeSpanValue(TimeSpan.FromSeconds(time))); } } else { var previousBest = qpcRow.Values.Last().Item2; qpcRow.Values[qpcRow.Values.Count - 1] = Tuple.Create(time, objective); if (!objective.IsAlmost(previousBest)) { qpcRow.Values.Add(Tuple.Create(time, objective)); algorithm.Results.AddOrUpdateResult($"Best{nameof(solver.ObjectiveValue)}FoundAt", new TimeSpanValue(TimeSpan.FromSeconds(time))); } } if (!solver.IsMip) return; if (!bpcRow.Values.Any()) { if (!double.IsInfinity(bound) && !double.IsNaN(bound)) { bpcRow.Values.Add(Tuple.Create(time, bound)); bpcRow.Values.Add(Tuple.Create(time, bound)); qualityPerClock.Rows.Add(bpcRow); } } else { var previousBest = bpcRow.Values.Last().Item2; bpcRow.Values[bpcRow.Values.Count - 1] = Tuple.Create(time, bound); if (!bound.IsAlmost(previousBest)) { bpcRow.Values.Add(Tuple.Create(time, bound)); } } } } }