#region License Information
/* HeuristicLab
* Copyright (C) 2002-2017 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.Threading;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.IntegerVectorEncoding;
using HeuristicLab.Optimization;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using localsolver;
namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.LocalSolverNet {
[Item("LocalSolver List (GQAP)", "LocalSolver algorithm solving the GQAP using list decision variables")]
[StorableClass]
[Creatable(CreatableAttribute.Categories.Algorithms)]
public sealed class GQAPListSolver : ContextAlgorithm {
public override bool SupportsPause {
get { return false; }
}
public override Type ProblemType {
get { return typeof(GQAP); }
}
public new GQAP Problem {
get { return (GQAP)base.Problem; }
set { base.Problem = value; }
}
// LS Program variables
private LSExpression[] x;
private LSExpression[] equipmentsOnLocations;
private LSExpression obj;
private LocalSolver localSolver;
[StorableConstructor]
private GQAPListSolver(bool deserializing) : base(deserializing) { }
private GQAPListSolver(GQAPListSolver original, Cloner cloner)
: base(original, cloner) {
}
public GQAPListSolver() {
Problem = new GQAP();
MaximumEvaluationsParameter.Hidden = true;
MaximumIterationsParameter.Hidden = true;
}
public override IDeepCloneable Clone(Cloner cloner) {
return new GQAPListSolver(this, cloner);
}
private double prevObj;
private DateTime lastUpdate;
private CancellationToken token;
private void LocalSolverOnIterationTicked(LocalSolver ls, LSCallbackType type) {
IResult result;
Context.Iterations++;
if ((DateTime.UtcNow - lastUpdate) > TimeSpan.FromSeconds(1)) {
if (Results.TryGetValue("Iterations", out result))
((IntValue)result.Value).Value = Context.Iterations;
else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
lastUpdate = DateTime.UtcNow;
}
if (token.IsCancellationRequested) localSolver.Stop();
var curObj = obj.GetDoubleValue();
if (curObj >= prevObj) return;
UpdateSolution(curObj);
Context.RunOperator(Analyzer, CancellationToken.None);
if (StoppingCriterion()) localSolver.Stop();
}
private void UpdateSolution(double obj) {
IResult result;
prevObj = obj;
Context.BestQuality = obj;
if (Results.TryGetValue("BestQuality", out result))
((DoubleValue)result.Value).Value = Context.BestQuality;
else Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality)));
var locations = Problem.ProblemInstance.Capacities.Length;
var best = new int[Problem.ProblemInstance.Demands.Length];
for (var j = 0; j < locations; j++) {
var xcol = x[j].GetCollectionValue();
for (var i = 0; i < xcol.Count(); i++) {
var equip = xcol.Get(i);
best[equip] = j;
}
}
var bestVec = new IntegerVector(best);
var eval = Problem.ProblemInstance.Evaluate(bestVec);
Context.BestSolution = new GQAPSolution(bestVec, eval);
var scope = Context.ToScope(new GQAPSolution(new IntegerVector(best), (Evaluation)eval.Clone()), Problem.ProblemInstance.ToSingleObjective(eval));
Context.ReplaceIncumbent(scope);
if (Results.TryGetValue("BestSolution", out result))
result.Value = Context.BestSolution;
else Results.Add(new Result("BestSolution", Context.BestSolution));
}
protected override void Initialize(CancellationToken cancellationToken) {
base.Initialize(cancellationToken);
prevObj = double.MaxValue;
}
protected override void Run(CancellationToken cancellationToken) {
base.Run(cancellationToken);
token = cancellationToken;
lastUpdate = DateTime.UtcNow.AddSeconds(-1);
localSolver = new LocalSolver();
// Declares the optimization model
var model = localSolver.GetModel();
var data = Problem.ProblemInstance;
x = new LSExpression[data.Capacities.Length];
// x[f,l] = 1 if equipments f is on location l, 0 otherwise
for (int r = 0; r < data.Capacities.Length; r++) {
x[r] = model.List(data.Demands.Length);
}
// All equipments are installed in exactly 1 location
model.Constraint(model.Partition(x));
var demandsArray = model.Array(data.Demands);
// Create distances as an array to be accessed by an at operator
var weightsJagged = new double[data.Demands.Length][];
for (var i = 0; i < data.Demands.Length; i++) {
weightsJagged[i] = new double[data.Demands.Length];
for (var j = 0; j < data.Demands.Length; j++) {
weightsJagged[i][j] = data.Weights[i, j];
}
}
var distancesJagged = new double[data.Capacities.Length][];
for (var i = 0; i < data.Capacities.Length; i++) {
distancesJagged[i] = new double[data.Capacities.Length];
for (var j = 0; j < data.Capacities.Length; j++)
distancesJagged[i][j] = data.Distances[i, j];
}
var installJagged = new double[data.Demands.Length][];
for (var i = 0; i < data.Demands.Length; i++) {
installJagged[i] = new double[data.Capacities.Length];
for (var j = 0; j < data.Capacities.Length; j++)
installJagged[i][j] = data.InstallationCosts[i, j];
}
var weightsArray = model.Array(weightsJagged);
var distancesArray = model.Array(distancesJagged);
var installCostsArray = model.Array(installJagged);
obj = model.Sum();
// All locations contain not more equipments than there is capacity for
for (int l = 0; l < data.Capacities.Length; l++) {
var c = model.Count(x[l]);
var demandSelector = model.Function(i => demandsArray[x[l][i]]);
var assignedDemand = model.Sum(model.Range(0, c), demandSelector);
model.Constraint(assignedDemand <= data.Capacities[l]);
var installCostSelector = model.Function(i => installCostsArray[x[l][i], l]);
var installCosts = model.Sum(model.Range(0, c), installCostSelector);
obj.AddOperand(installCosts);
// Flow to other equipments
for (int k = 0; k < data.Capacities.Length; k++) {
var kc = model.Count(x[k]);
var flowCostSelector = model.Function(j => model.Sum(model.Range(0, c), model.Function(i => weightsArray[x[l][i], x[k][j]] * distancesArray[l, k] * data.TransportationCosts)));
obj.AddOperand(model.Sum(model.Range(0, kc), flowCostSelector));
}
}
model.Minimize(this.obj);
try {
model.Close();
// Parameterizes the solver.
LSPhase phase = localSolver.CreatePhase();
phase.SetTimeLimit((int)Math.Ceiling(MaximumRuntime.TotalSeconds));
localSolver.AddCallback(LSCallbackType.IterationTicked, LocalSolverOnIterationTicked);
localSolver.Solve();
var curObj = this.obj.GetDoubleValue();
if (curObj < prevObj)
UpdateSolution(curObj);
localSolver.RemoveCallback(LSCallbackType.IterationTicked, LocalSolverOnIterationTicked);
} finally {
localSolver.Dispose();
}
Context.RunOperator(Analyzer, CancellationToken.None);
}
}
}