source: branches/1614_GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/GQAPInstance.cs @ 16724

#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.Linq;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.IntegerVectorEncoding;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;

namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment {
  [Item("GQAP Instance", "Instance of a generalized quadratic assignment problem.")]
  [StorableClass]
  public class GQAPInstance : ParameterizedNamedItem {
    public static readonly string WeightsDescription = "The weights matrix describes the flows between the equipments.";
    public static readonly string DistancesDescription = "The distances matrix describes the distances between the locations at which the equipment can be installed.";
    public static readonly string InstallationCostsDescription = "The installation costs matrix describes the installation costs of installing equipment i at location j";
    public static readonly string DemandsDescription = "The demands vector describes the space requirements of the equipments.";
    public static readonly string CapacitiesDescription = "The capacities vector describes the available space at the locations.";
    public static readonly string TransportationCostsDescription = "The transportation cost represents the flow-unit per distance-unit cost factor. This value can also be set to 1 if these costs are factored into the weights matrix already.";
    public static readonly string EquipmentNamesDescription = "Optional: A list of names that describes the equipments.";
    public static readonly string LocationNamesDescription = "Optional: A list of names that describes the locations.";
    public static readonly string PenaltyLevelDescription = "The quality that an infeasible solution cannot surpass.";


    #region Parameter Properties
    [Storable]
    private ValueParameter<DoubleMatrix> weightsParam;
    public IValueParameter<DoubleMatrix> WeightsParameter {
      get { return weightsParam; }
    }
    [Storable]
    private ValueParameter<DoubleMatrix> distancesParam;
    public IValueParameter<DoubleMatrix> DistancesParameter {
      get { return distancesParam; }
    }
    [Storable]
    private ValueParameter<DoubleMatrix> installCostsParam;
    public IValueParameter<DoubleMatrix> InstallationCostsParameter {
      get { return installCostsParam; }
    }
    [Storable]
    private ValueParameter<DoubleArray> demandsParam;
    public IValueParameter<DoubleArray> DemandsParameter {
      get { return demandsParam; }
    }
    [Storable]
    private ValueParameter<DoubleArray> capacitiesParam;
    public IValueParameter<DoubleArray> CapacitiesParameter {
      get { return capacitiesParam; }
    }
    [Storable]
    private FixedValueParameter<DoubleValue> transportationCostsParam;
    public IFixedValueParameter<DoubleValue> TransportationCostsParameter {
      get { return transportationCostsParam; }
    }
    [Storable]
    private FixedValueParameter<DoubleValue> penaltyLevelParam;
    public IFixedValueParameter<DoubleValue> PenaltyLevelParameter {
      get { return penaltyLevelParam; }
    }
    [Storable]
    private OptionalValueParameter<StringArray> equipmentNamesParam;
    public OptionalValueParameter<StringArray> EquipmentNamesParameter {
      get { return equipmentNamesParam; }
    }
    [Storable]
    private OptionalValueParameter<StringArray> locationNamesParam;
    public OptionalValueParameter<StringArray> LocationNamesParameter {
      get { return locationNamesParam; }
    }
    #endregion

    #region Properties
    public DoubleMatrix Weights {
      get { return WeightsParameter.Value; }
      set { WeightsParameter.Value = value; }
    }
    public DoubleMatrix Distances {
      get { return DistancesParameter.Value; }
      set { DistancesParameter.Value = value; }
    }
    public DoubleMatrix InstallationCosts {
      get { return InstallationCostsParameter.Value; }
      set { InstallationCostsParameter.Value = value; }
    }
    public DoubleArray Demands {
      get { return DemandsParameter.Value; }
      set { DemandsParameter.Value = value; }
    }
    public DoubleArray Capacities {
      get { return CapacitiesParameter.Value; }
      set { CapacitiesParameter.Value = value; }
    }
    public double TransportationCosts {
      get { return TransportationCostsParameter.Value.Value; }
      set { TransportationCostsParameter.Value.Value = value; }
    }
    public double PenaltyLevel {
      get { return PenaltyLevelParameter.Value.Value; }
      set { PenaltyLevelParameter.Value.Value = value; }
    }
    public StringArray EquipmentNames {
      get { return EquipmentNamesParameter.Value; }
      set { EquipmentNamesParameter.Value = value; }
    }
    public StringArray LocationNames {
      get { return LocationNamesParameter.Value; }
      set { LocationNamesParameter.Value = value; }
    }
    #endregion

    [StorableConstructor]
    protected GQAPInstance(bool deserializing) : base(deserializing) { }
    protected GQAPInstance(GQAPInstance original, Cloner cloner)
      : base(original, cloner) {
      weightsParam = cloner.Clone(original.weightsParam);
      distancesParam = cloner.Clone(original.distancesParam);
      installCostsParam = cloner.Clone(original.installCostsParam);
      transportationCostsParam = cloner.Clone(original.transportationCostsParam);
      penaltyLevelParam = cloner.Clone(original.penaltyLevelParam);
      demandsParam = cloner.Clone(original.demandsParam);
      capacitiesParam = cloner.Clone(original.capacitiesParam);
      equipmentNamesParam = cloner.Clone(original.equipmentNamesParam);
      locationNamesParam = cloner.Clone(original.locationNamesParam);
    }
    public GQAPInstance() {
      Parameters.Add(weightsParam = new ValueParameter<DoubleMatrix>("Weights", WeightsDescription, new DoubleMatrix(), false));
      Parameters.Add(distancesParam = new ValueParameter<DoubleMatrix>("Distances", DistancesDescription, new DoubleMatrix(), false));
      Parameters.Add(installCostsParam = new ValueParameter<DoubleMatrix>("InstallationCosts", InstallationCostsDescription, new DoubleMatrix(), false));
      Parameters.Add(transportationCostsParam = new FixedValueParameter<DoubleValue>("TransportationCosts", TransportationCostsDescription, new DoubleValue(1)));
      Parameters.Add(penaltyLevelParam = new FixedValueParameter<DoubleValue>("PenaltyLevel", PenaltyLevelDescription, new DoubleValue(0), true));
      Parameters.Add(demandsParam = new ValueParameter<DoubleArray>("Demands", DemandsDescription, new DoubleArray(), false));
      Parameters.Add(capacitiesParam = new ValueParameter<DoubleArray>("Capacities", CapacitiesDescription, new DoubleArray(), false));
      Parameters.Add(equipmentNamesParam = new OptionalValueParameter<StringArray>("EquipmentNames", EquipmentNamesDescription, null, false));
      Parameters.Add(locationNamesParam = new OptionalValueParameter<StringArray>("LocationNames", LocationNamesDescription, null, false));

      weightsParam.ReactOnValueToStringChangedAndValueItemImageChanged = false;
      distancesParam.ReactOnValueToStringChangedAndValueItemImageChanged = false;
      installCostsParam.ReactOnValueToStringChangedAndValueItemImageChanged = false;
      demandsParam.ReactOnValueToStringChangedAndValueItemImageChanged = false;
      capacitiesParam.ReactOnValueToStringChangedAndValueItemImageChanged = false;

      Weights = new DoubleMatrix(5, 5);
      Weights[0, 0] = Weights[1, 1] = Weights[2, 2] = Weights[3, 3] = Weights[4, 4] = 0;
      Weights[0, 1] = Weights[1, 0] = Weights[0, 2] = Weights[2, 0] = Weights[0, 3] = Weights[3, 0] = Weights[0, 4] = Weights[4, 0] = 10;
      Weights[1, 2] = Weights[2, 1] = Weights[1, 3] = Weights[3, 1] = Weights[1, 4] = Weights[4, 1] = 5;
      Weights[2, 3] = Weights[3, 2] = Weights[2, 4] = Weights[4, 2] = 7.5;
      Weights[3, 4] = Weights[4, 3] = 2.5;

      Distances = new DoubleMatrix(3, 3);
      Distances[0, 0] = Distances[1, 1] = Distances[2, 2] = 0;
      Distances[0, 1] = Distances[1, 0] = Distances[1, 2] = Distances[2, 1] = 1;
      Distances[0, 2] = Distances[2, 0] = 2;

      InstallationCosts = new DoubleMatrix(5, 3);

      Demands = new DoubleArray(5);
      Demands[0] = 2; Demands[1] = 1; Demands[2] = 3; Demands[3] = 1; Demands[4] = 1;

      Capacities = new DoubleArray(3);
      Capacities[0] = 4; Capacities[1] = 1; Capacities[2] = 4;

      TransportationCosts = 1;

      CalculatePenaltyLevel();
    }

    public override IDeepCloneable Clone(Cloner cloner) {
      return new GQAPInstance(this, cloner);
    }

    public Evaluation Evaluate(IntegerVector assignment) {
      var evaluation = EvaluateIntegerVector(assignment, Demands, Capacities,
        InstallationCosts, Weights, Distances);
      return evaluation;
    }

    public double EvaluateSingleObjective(IntegerVector assignment) {
      return ToSingleObjective(Evaluate(assignment));
    }

    public static Evaluation EvaluateIntegerVector(IntegerVector assignment,
      DoubleArray demands, DoubleArray capacities, DoubleMatrix installCosts,
      DoubleMatrix weights, DoubleMatrix distances) {
      var flowDistanceQuality = 0.0;
      var installationQuality = 0.0;
      var overbookedCapacity = 0.0;
      int len = assignment.Length;
      var slack = capacities.ToArray();

      for (int i = 0; i < len; i++) {
        var assignI = assignment[i];
        installationQuality += installCosts[i, assignI];
        for (int j = 0; j < len; j++) {
          flowDistanceQuality += weights[i, j] * distances[assignI, assignment[j]];
        }
        if (slack[assignI] < 0) overbookedCapacity += demands[i];
        else if (slack[assignI] < demands[i]) overbookedCapacity += (demands[i] - slack[assignI]);
        slack[assignI] -= demands[i];
      }
      return new Evaluation(flowDistanceQuality, installationQuality, overbookedCapacity, slack);
    }

    public GQAPSolution ToEvaluatedSolution(IntegerVector assignment) {
      var evaluation = EvaluateIntegerVector(assignment, Demands, Capacities,
InstallationCosts, Weights, Distances);
      return new GQAPSolution(assignment, evaluation);
    }

    public bool IsFeasible(IntegerVector assignment) {
      int len = assignment.Length;
      var utilization = new double[Capacities.Length];
      for (var equip = 0; equip < len; equip++) {
        var loc = assignment[equip];
        utilization[loc] += Demands[equip];
        if (utilization[loc] > Capacities[loc])
          return false;
      }
      return true;
    }

    public double ToSingleObjective(Evaluation fitness) {
      return fitness.IsFeasible
        ? fitness.InstallationCosts + TransportationCosts * fitness.FlowCosts
        : PenaltyLevel + fitness.ExcessDemand;
    }

    public double[] ToMultiObjectiveStrict(Evaluation fitness) {
      return fitness.IsFeasible
        ? new double[] { fitness.InstallationCosts, TransportationCosts * fitness.FlowCosts }
        : new double[] { PenaltyLevel + fitness.ExcessDemand, PenaltyLevel + fitness.ExcessDemand };
    }

    public double[] ToMultiObjectiveRelaxed(Evaluation fitness) {
      return new double[] {
        fitness.InstallationCosts,
        TransportationCosts * fitness.FlowCosts,
        fitness.ExcessDemand };
    }

    public bool IsValid() {
      return Weights != null && Distances != null && Demands != null && Capacities != null && InstallationCosts != null
        && Weights.Rows == Weights.Columns && Weights.Rows == InstallationCosts.Rows
        && Distances.Rows == Distances.Columns && Distances.Rows == InstallationCosts.Columns
        && Demands.Length == Weights.Rows && Capacities.Length == Distances.Rows;
    }

    public void CalculatePenaltyLevel() {
      var flowQuality = Distances.Max() * Weights.Max() * Demands.Length * Demands.Length;
      var installQuality = InstallationCosts.Max() * Demands.Length;
      PenaltyLevel = installQuality + TransportationCosts * flowQuality;
    }
  }
}