source: branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.2D/3.3/PackingSequenceProblem.cs @ 14146

#region License Information

/* HeuristicLab
 * Copyright (C) 2002-2016 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.Collections.Generic;
using System.Linq;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.PermutationEncoding;
using HeuristicLab.Optimization;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using HeuristicLab.Problems.BinPacking;
using HeuristicLab.Problems.BinPacking2D;
using HeuristicLab.Problems.Instances;
using HeuristicLab.Random;

namespace HeuristicLab.Problems.BinPacking2d {
  [Item("Bin Packing Problem (2D, permutation encoding) (BPP)", "Represents a two-dimensional bin-packing problem using only bins with identical measures and bins/items with rectangular shapes.")]
  [StorableClass]
  [Creatable(Category = CreatableAttribute.Categories.CombinatorialProblems, Priority = 300)]
  public sealed class PackingSequenceProblem : SingleObjectiveBasicProblem<PermutationEncoding>, IProblemInstanceConsumer<BPPData>, IProblemInstanceExporter<BPPData> {
    private readonly string SolutionEvaluatorParameterName = "SolutionEvaluator";
    #region Default Instance
    private static readonly BPPData DefaultInstance = new BPPData() {
      Name = "2D BPP Default Instance",
      Description = "The default instance for 2D Bin Packing.",
      BinShape = new PackingShape(20, 16),
      Items = new PackingItem[] {
        new PackingItem(3,  8, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0}
      },
    };
    #endregion

    #region parameter properties
    public IValueParameter<IPermutationDecoder> DecoderParameter {
      get { return (IValueParameter<IPermutationDecoder>)Parameters["Decoder"]; }
    }
    public IValueParameter<BinPacking2D.IEvaluator> SolutionEvaluatorParameter {
      get { return (IValueParameter<BinPacking2D.IEvaluator>)Parameters[SolutionEvaluatorParameterName]; }
    }
    public IValueParameter<ReadOnlyItemList<PackingItem>> ItemsParameter {
      get { return (IValueParameter<ReadOnlyItemList<PackingItem>>)Parameters["Items"]; }
    }
    public IValueParameter<PackingShape> BinShapeParameter {
      get { return (IValueParameter<PackingShape>)Parameters["BinShape"]; }
    }
    public IValueParameter<Solution> BestKnownSolutionParameter {
      get { return (IValueParameter<Solution>)Parameters["BestKnownSolution"]; }
    }
    public IFixedValueParameter<IntValue> LowerBoundParameter {
      get { return (IFixedValueParameter<IntValue>)Parameters["LowerBound"]; }
    }
    #endregion

    #region properties
    public IPermutationDecoder Decoder {
      get { return DecoderParameter.Value; }
      set { DecoderParameter.Value = value; }
    }
    public new BinPacking2D.IEvaluator SolutionEvaluator {
      get { return SolutionEvaluatorParameter.Value; }
      set { SolutionEvaluatorParameter.Value = value; }
    }
    public ReadOnlyItemList<PackingItem> Items {
      get { return ItemsParameter.Value; }
      set { ItemsParameter.Value = value; }
    }
    public PackingShape BinShape {
      get { return BinShapeParameter.Value; }
      set { BinShapeParameter.Value = value; }
    }
    public Solution BestKnownSolution {
      get { return BestKnownSolutionParameter.Value; }
      set { BestKnownSolutionParameter.Value = value; }
    }
    public int LowerBound {
      get { return LowerBoundParameter.Value.Value; }
    }
    public int NumberOfItems {
      get { return Items == null ? 0 : Items.Count; }
    }
    #endregion

    // persistence
    [StorableConstructor]
    private PackingSequenceProblem(bool deserializing) : base(deserializing) { }

    // cloning
    private PackingSequenceProblem(PackingSequenceProblem original, Cloner cloner)
      : base(original, cloner) {
      RegisterEventHandlers();
    }

    public PackingSequenceProblem()
      : base() {
      var defaultEvaluator = new PackingRatioEvaluator();
      var defaultDecoder = new ExtremePointPermutationDecoder();
      Parameters.Add(new ValueParameter<IPermutationDecoder>("Decoder", "The decoder translates a permutation to a packing solution candidiates", defaultDecoder));
      Parameters.Add(new ValueParameter<BinPacking2D.IEvaluator>(SolutionEvaluatorParameterName, "The evaluator calculates qualities of solution candidates", defaultEvaluator));
      Parameters.Add(new ValueParameter<ReadOnlyItemList<PackingItem>>("Items", "The items which must be packed into bins"));
      Parameters.Add(new ValueParameter<PackingShape>("BinShape", "The size of bins into which items must be packed"));
      Parameters.Add(new OptionalValueParameter<Solution>("BestKnownSolution", "The best solution found so far"));
      Parameters.Add(new FixedValueParameter<IntValue>("LowerBound", "A lower bound for the number of bins that is necessary to pack all items"));

      Load(DefaultInstance);

      Encoding = new PermutationEncoding("PackingSequence", Items.Count, PermutationTypes.Absolute);
      AddOperators();
      RegisterEventHandlers();
    }
    public override IDeepCloneable Clone(Cloner cloner) {
      return new PackingSequenceProblem(this, cloner);
    }

    [StorableHook(HookType.AfterDeserialization)]
    private void AfterDeserialization() {
      RegisterEventHandlers();
    }


    private void AddOperators() {
      Operators.Add(new StochasticInsertionMultiMoveGenerator());
      Operators.Add(new ExhaustiveInsertionMoveGenerator());
      Operators.Add(new TranslocationMoveMaker());
      Operators.Add(new TranslocationMoveEvaluator());
      Operators.Add(new TranslocationMoveTabuMaker());

      Operators.RemoveAll(x => x is SingleObjectiveMoveGenerator);
      Operators.RemoveAll(x => x is SingleObjectiveMoveMaker);
      Operators.RemoveAll(x => x is SingleObjectiveMoveEvaluator);

      Encoding.ConfigureOperators(Operators.OfType<IOperator>());
    }

    private void RegisterEventHandlers() {
      // update encoding length when number of items is changed
      ItemsParameter.ValueChanged += (sender, args) => Encoding.Length = Items.Count;
    }

    public override bool Maximization { get { return true; } }


    public override double Evaluate(Individual individual, IRandom random) {
      var permutation = individual.Permutation("PackingSequence");
      var decoder = Decoder;
      var solution = decoder.Decode(permutation, BinShape, Items);
      return SolutionEvaluator.Evaluate(solution);
    }

    public override void Analyze(Individual[] individuals, double[] qualities, ResultCollection results, IRandom random) {
      base.Analyze(individuals, qualities, results, random);
      Analyze(individuals.Select(i => i.Permutation("PackingSequence")).ToArray(), qualities, results, random);
    }

    public void Analyze(Permutation[] individuals, double[] qualities, ResultCollection results, IRandom random) {
      var bestSolutionResultName = "Best Packing Solution";
      var numContainersResultName = "Nr of Containers";
      var binUtilResultName = "Overall Bin Utilization";

      if (!results.ContainsKey(bestSolutionResultName)) results.Add(new Result(bestSolutionResultName, typeof(Solution)));
      if (!results.ContainsKey(numContainersResultName)) results.Add(new Result(numContainersResultName, typeof(IntValue)));
      if (!results.ContainsKey(binUtilResultName)) results.Add(new Result(binUtilResultName, typeof(DoubleValue)));


      // find index of item with max quality
      int bestIdx = 0;
      for (int j = 1; j < qualities.Length; j++)
        if (qualities[j] > qualities[bestIdx]) bestIdx = j;


      // update best solution so far
      var bestSolution = results[bestSolutionResultName].Value as Solution;
      if (bestSolution == null ||
        bestSolution.Quality.Value < qualities[bestIdx]) {

        var newBestSolution = Decoder.Decode(individuals[bestIdx], BinShape, Items);
        newBestSolution.Quality = new DoubleValue(qualities[bestIdx]);
        results[bestSolutionResultName].Value = newBestSolution;
        results[numContainersResultName].Value = new IntValue(newBestSolution.NrOfBins);
        results[binUtilResultName].Value = new DoubleValue(BinUtilizationEvaluator.CalculateBinUtilization(newBestSolution));

        // update best known solution
        var bestKnownQuality = BestKnownQualityParameter.Value;
        if (bestKnownQuality == null ||
            bestKnownQuality.Value < qualities[bestIdx]) {
          BestKnownQualityParameter.ActualValue = new DoubleValue(qualities[bestIdx]);
          BestKnownSolutionParameter.ActualValue = newBestSolution;
        }
      }
    }


    #region Problem instance handling
    public void Load(BPPData data) {
      BestKnownSolutionParameter.Value = null;
      BestKnownQualityParameter.Value = null;

      if (data.BestKnownQuality.HasValue)
        BestKnownQuality = data.BestKnownQuality.Value;

      BinShape = data.BinShape;
      var items = new ItemList<PackingItem>(data.Items);
      items.Sort((x, y) => y.CompareTo(x));
      Items = items.AsReadOnly();

      ApplyHorizontalOrientation();
      LowerBoundParameter.Value.Value = CalculateLowerBound();
    }


    public BPPData Export() {
      return new BPPData {
        Name = Name,
        Description = Description,
        BinShape = BinShape,
        Items = Items.ToArray()
      };
    }
    #endregion


    #region helpers
    private void ApplyHorizontalOrientation() {
      BinShape.ApplyHorizontalOrientation();
      foreach (var shape in Items) {
        shape.ApplyHorizontalOrientation();
      }
    }

    private int CalculateLowerBound() {
      //This is the obvious continuous lower bound calculation; Martello and Vigo proposed a better way but it has not been implemented yet;
      int itemsVol = Items.Select(x => x.Volume).Sum();
      int binVol = BinShape.Volume;
      return (itemsVol + binVol - 1) / (binVol);
    }

    #endregion
  }
}