source: branches/1614_GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/LocalSolverNet/GQAPBinarySolver.cs @ 17328

#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 <http://www.gnu.org/licenses/>.
 */
#endregion

using System;
using System.Threading;
using HEAL.Attic;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.IntegerVectorEncoding;
using HeuristicLab.Optimization;
using localsolver;

namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.LocalSolverNet {
  [Item("LocalSolver Binary (GQAP)", "LocalSolver algorithm solving the GQAP using 0-1 decision variables")]
  [StorableType("E9040268-4240-4EF7-8E9A-6991D0831D06")]
  [Creatable(CreatableAttribute.Categories.Algorithms)]
  public sealed class GQAPBinarySolver : ContextAlgorithm<LocalSolverContext, IntegerVectorEncoding> {
    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 GQAPBinarySolver(StorableConstructorFlag _) : base(_) { }
    private GQAPBinarySolver(GQAPBinarySolver original, Cloner cloner)
    : base(original, cloner) {
    }
    public GQAPBinarySolver() {
      Problem = new GQAP();
      MaximumEvaluationsParameter.Hidden = true;
      MaximumIterationsParameter.Hidden = true;
    }

    public override IDeepCloneable Clone(Cloner cloner) {
      return new GQAPBinarySolver(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 i = 0; i < best.Length; i++) {
        for (var j = 0; j < locations; j++) {
          if (x[i][j].GetIntValue() == 1) {
            best[i] = j;
            break;
          }
        }
      }
      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
      LSModel model = localSolver.GetModel();

      var data = Problem.ProblemInstance;

      // x[f,l] = 1 if equipments f is on location l, 0 otherwise
      x = new LSExpression[data.Demands.Length][];
      for (int f = 0; f < data.Demands.Length; f++) {
        x[f] = new LSExpression[data.Capacities.Length];
        for (int l = 0; l < data.Capacities.Length; l++) {
          x[f][l] = model.Bool();
        }
      }

      // All equipments are installed in exactly 1 location
      for (int f = 0; f < data.Demands.Length; f++) {
        LSExpression nbLocationsAssigned = model.Sum();
        for (int l = 0; l < data.Capacities.Length; l++) {
          nbLocationsAssigned.AddOperand(x[f][l]);
        }
        model.Constraint(nbLocationsAssigned == 1);
      }

      // All locations contain not more equipments than there is capacity for
      for (int l = 0; l < data.Capacities.Length; l++) {
        LSExpression assignedDemand = model.Sum();
        for (int f = 0; f < data.Demands.Length; f++) {
          assignedDemand.AddOperand(x[f][l] * data.Demands[f]);
        }
        model.Constraint(assignedDemand <= data.Capacities[l]);
      }

      // Index of the assigned location of equipment f
      equipmentsOnLocations = new LSExpression[data.Demands.Length];
      for (int f = 0; f < data.Demands.Length; f++) {
        equipmentsOnLocations[f] = model.Sum();
        for (int l = 0; l < data.Capacities.Length; l++) {
          equipmentsOnLocations[f].AddOperand(l * x[f][l]);
        }
      }

      // Create distances as an array to be accessed by an at operator
      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];
      }
      LSExpression distancesArray = model.Array(distancesJagged);
      LSExpression installCostsArray = model.Array(installJagged);

      // Minimize the sum of product distance*flow
      obj = model.Sum();
      for (int f1 = 0; f1 < data.Demands.Length; f1++) {
        for (int f2 = 0; f2 < data.Demands.Length; f2++) {
          obj.AddOperand(data.TransportationCosts * data.Weights[f1, f2] * distancesArray[equipmentsOnLocations[f1], equipmentsOnLocations[f2]]);
        }
        obj.AddOperand(installCostsArray[f1, equipmentsOnLocations[f1]]);
      }

      model.Minimize(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 = obj.GetDoubleValue();
        if (curObj < prevObj)
          UpdateSolution(curObj);

        localSolver.RemoveCallback(LSCallbackType.IterationTicked, LocalSolverOnIterationTicked);
      } finally {
        localSolver.Dispose();
      }

      Context.RunOperator(Analyzer, CancellationToken.None);
    }
  }
}