Changeset 14146


Ignore:
Timestamp:
07/21/16 10:19:55 (13 months ago)
Author:
gkronber
Message:

#1966: new implementation for 2d bin packing problem with permutation encoding

Location:
branches/HeuristicLab.BinPacking
Files:
1 added
11 edited
10 moved

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.2D/3.3/BinPacking2D.cs

    r14128 r14146  
    120120    }
    121121
    122     public override void SlidingBasedPacking(ref List<int> sequence, ItemList<PackingItem> items) {
     122    public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items) {
    123123      var temp = new List<int>(sequence);
    124124      for (int i = 0; i < temp.Count; i++) {
     
    131131      }
    132132    }
    133     public override void SlidingBasedPacking(ref List<int> sequence, ItemList<PackingItem> items, Dictionary<int, bool> rotationArray) {
     133    public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items, Dictionary<int, bool> rotationArray) {
    134134      var temp = new List<int>(sequence);
    135135      for (int i = 0; i < temp.Count; i++) {
     
    142142      }
    143143    }
    144     public override void ExtremePointBasedPacking(ref List<int> sequence, ItemList<PackingItem> items, bool stackingConstraints) {
     144    public override void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints) {
    145145      var temp = new List<int>(sequence);
    146146      foreach (int itemID in temp) {
     
    153153      }
    154154    }
    155     public override void ExtremePointBasedPacking(ref List<int> sequence, ItemList<PackingItem> items, bool stackingConstraints, Dictionary<int, bool> rotationArray) {
     155    public override void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints, Dictionary<int, bool> rotationArray) {
    156156      var temp = new List<int>(sequence);
    157157      foreach (int itemID in temp) {
     
    187187    }
    188188    public override bool IsStaticStable(PackingItem item, PackingPosition position) {
    189       throw new NotImplementedException();
     189      throw new NotSupportedException();
    190190    }
    191191
  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.2D/3.3/HeuristicLab.Problems.BinPacking2D-3.3.csproj

    r14128 r14146  
    163163  <ItemGroup>
    164164    <Compile Include="BinPacking2D.cs" />
    165     <Compile Include="Decoders\EP\ExtremePointPackingSequenceDecoder2D.cs">
    166       <SubType>Code</SubType>
    167     </Compile>
     165    <Compile Include="BinUtilizationEvaluator.cs" />
     166    <Compile Include="ExtremePointPermutationDecoder.cs" />
    168167    <Compile Include="Instances\BPPData.cs" />
    169168    <Compile Include="Instances\RandomDataDescriptor.cs" />
    170169    <Compile Include="Instances\RandomInstanceProvider.cs" />
     170    <Compile Include="Interfaces\IEvaluator.cs" />
     171    <Compile Include="Interfaces\IPermutationDecoder.cs" />
    171172    <Compile Include="Interfaces\I2DGVDecoder.cs" />
    172173    <Compile Include="Interfaces\I2DMCVDecoder.cs" />
    173174    <Compile Include="Interfaces\I2DOperator.cs" />
    174175    <Compile Include="Interfaces\I2DPSDecoder.cs" />
     176    <Compile Include="MoveEvaluators\TranslocationMoveEvaluator.cs">
     177      <SubType>Code</SubType>
     178    </Compile>
    175179    <Compile Include="PackingItem.cs" />
    176180    <Compile Include="PackingPosition.cs" />
     
    193197    </ProjectReference>
    194198  </ItemGroup>
    195   <ItemGroup>
    196     <Folder Include="Decoders\BL\" />
    197     <Folder Include="MoveEvaluators\" />
    198   </ItemGroup>
     199  <ItemGroup />
    199200  <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />
    200201  <PropertyGroup>
  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.2D/3.3/PackingRatioEvaluator.cs

    r14050 r14146  
    2020#endregion
    2121
    22 
     22using System;
     23using System.Linq;
    2324using HeuristicLab.Core;
    2425using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2526using HeuristicLab.Common;
     27using HeuristicLab.Data;
     28using HeuristicLab.Encodings.PackingEncoding;
    2629using HeuristicLab.Problems.BinPacking;
     30using System.Collections.Generic;
    2731
    2832namespace HeuristicLab.Problems.BinPacking2D {
    29   [Item("Packing-Ratio Evaluator (2d)", "Calculates the ratio between packed and unpacked space. Found in Falkenauer:1996")]
     33  [Item("Packing-Ratio Evaluator (2d)", "Calculates the ratio between packed and unpacked space.")]
    3034  [StorableClass]
    31   public class PackingRatioEvaluator : PackingRatioEvaluator<PackingPosition, PackingShape, PackingItem> {
     35  public class PackingRatioEvaluator : Item, IEvaluator {
    3236
    3337    [StorableConstructor]
    34     protected PackingRatioEvaluator (bool deserializing) : base(deserializing) { }
    35     protected PackingRatioEvaluator (PackingRatioEvaluator original, Cloner cloner)
     38    protected PackingRatioEvaluator(bool deserializing) : base(deserializing) { }
     39    protected PackingRatioEvaluator(PackingRatioEvaluator original, Cloner cloner)
    3640      : base(original, cloner) {
    3741    }
     
    4044      return new PackingRatioEvaluator(this, cloner);
    4145    }
     46
     47    #region IEvaluator Members
     48    public double Evaluate(Solution solution) {
     49      return CalculatePackingRatio(solution);
     50    }
     51
     52    /*
     53        Falkenauer:1996 - A Hybrid Grouping Genetic Algorithm for Bin Packing
     54       
     55        fBPP = (SUM[i=1..N](Fi / C)^k)/N
     56        N.......the number of bins used in the solution,
     57        Fi......the sum of sizes of the items in the bin i (the fill of the bin),
     58        C.......the bin capacity and
     59        k.......a constant, k>1.
     60     */
     61    public static double CalculatePackingRatio(Solution solution) {
     62      int nrOfBins = solution.NrOfBins;
     63      double result = 0;
     64      const double k = 2;
     65      for (int i = 0; i < nrOfBins; i++) {
     66        var f = solution.BinPackings[i].ItemMeasures.Sum(kvp => kvp.Value.Volume);
     67        var c = solution.BinPackings[i].BinMeasures.Volume;
     68        result += Math.Pow(f / c, k);
     69      }
     70
     71      result = result / nrOfBins;
     72      return result;
     73    }
     74
     75    #endregion
    4276  }
    4377}
  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.2D/3.3/PackingSequenceProblem.cs

    r14128 r14146  
    2323
    2424using System;
    25 using System.CodeDom;
     25using System.Collections.Generic;
    2626using System.Linq;
    27 using System.Text;
    2827using HeuristicLab.Common;
    2928using HeuristicLab.Core;
     
    3130using HeuristicLab.Encodings.PermutationEncoding;
    3231using HeuristicLab.Optimization;
     32using HeuristicLab.Parameters;
    3333using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    3434using HeuristicLab.Problems.BinPacking;
    3535using HeuristicLab.Problems.BinPacking2D;
     36using HeuristicLab.Problems.Instances;
     37using HeuristicLab.Random;
    3638
    3739namespace HeuristicLab.Problems.BinPacking2d {
     40  [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.")]
    3841  [StorableClass]
    3942  [Creatable(Category = CreatableAttribute.Categories.CombinatorialProblems, Priority = 300)]
    40   public class PackingSequenceProblem : PackingSequenceProblem<Permutation, PermutationEncoding> {
     43  public sealed class PackingSequenceProblem : SingleObjectiveBasicProblem<PermutationEncoding>, IProblemInstanceConsumer<BPPData>, IProblemInstanceExporter<BPPData> {
     44    private readonly string SolutionEvaluatorParameterName = "SolutionEvaluator";
     45    #region Default Instance
     46    private static readonly BPPData DefaultInstance = new BPPData() {
     47      Name = "2D BPP Default Instance",
     48      Description = "The default instance for 2D Bin Packing.",
     49      BinShape = new PackingShape(20, 16),
     50      Items = new PackingItem[] {
     51        new PackingItem(3,  8, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
     52        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
     53        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
     54        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
     55        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
     56        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
     57        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
     58        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
     59        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
     60        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
     61        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
     62        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
     63        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
     64        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
     65        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
     66        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
     67        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
     68        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
     69        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
     70        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
     71        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
     72        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
     73        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
     74        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
     75        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
     76        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
     77        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
     78        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
     79        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
     80        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
     81        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
     82        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
     83        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
     84        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
     85        new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
     86        new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
     87        new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0}
     88      },
     89    };
     90    #endregion
     91
     92    #region parameter properties
     93    public IValueParameter<IPermutationDecoder> DecoderParameter {
     94      get { return (IValueParameter<IPermutationDecoder>)Parameters["Decoder"]; }
     95    }
     96    public IValueParameter<BinPacking2D.IEvaluator> SolutionEvaluatorParameter {
     97      get { return (IValueParameter<BinPacking2D.IEvaluator>)Parameters[SolutionEvaluatorParameterName]; }
     98    }
     99    public IValueParameter<ReadOnlyItemList<PackingItem>> ItemsParameter {
     100      get { return (IValueParameter<ReadOnlyItemList<PackingItem>>)Parameters["Items"]; }
     101    }
     102    public IValueParameter<PackingShape> BinShapeParameter {
     103      get { return (IValueParameter<PackingShape>)Parameters["BinShape"]; }
     104    }
     105    public IValueParameter<Solution> BestKnownSolutionParameter {
     106      get { return (IValueParameter<Solution>)Parameters["BestKnownSolution"]; }
     107    }
     108    public IFixedValueParameter<IntValue> LowerBoundParameter {
     109      get { return (IFixedValueParameter<IntValue>)Parameters["LowerBound"]; }
     110    }
     111    #endregion
     112
     113    #region properties
     114    public IPermutationDecoder Decoder {
     115      get { return DecoderParameter.Value; }
     116      set { DecoderParameter.Value = value; }
     117    }
     118    public new BinPacking2D.IEvaluator SolutionEvaluator {
     119      get { return SolutionEvaluatorParameter.Value; }
     120      set { SolutionEvaluatorParameter.Value = value; }
     121    }
     122    public ReadOnlyItemList<PackingItem> Items {
     123      get { return ItemsParameter.Value; }
     124      set { ItemsParameter.Value = value; }
     125    }
     126    public PackingShape BinShape {
     127      get { return BinShapeParameter.Value; }
     128      set { BinShapeParameter.Value = value; }
     129    }
     130    public Solution BestKnownSolution {
     131      get { return BestKnownSolutionParameter.Value; }
     132      set { BestKnownSolutionParameter.Value = value; }
     133    }
     134    public int LowerBound {
     135      get { return LowerBoundParameter.Value.Value; }
     136    }
     137    public int NumberOfItems {
     138      get { return Items == null ? 0 : Items.Count; }
     139    }
     140    #endregion
    41141
    42142    // persistence
    43143    [StorableConstructor]
    44     protected PackingSequenceProblem(bool deserializing) : base(deserializing) { }
    45     [StorableHook(HookType.AfterDeserialization)]
    46     private void AfterDeserialization() { }
    47 
    48     public override bool Maximization {
    49       get { return true; }
    50     }
    51 
     144    private PackingSequenceProblem(bool deserializing) : base(deserializing) { }
    52145
    53146    // cloning
    54     protected PackingSequenceProblem(PackingSequenceProblem original, Cloner cloner)
     147    private PackingSequenceProblem(PackingSequenceProblem original, Cloner cloner)
    55148      : base(original, cloner) {
    56     }
    57 
    58     protected PackingSequenceProblem() : base() { }
    59 
    60 
     149      RegisterEventHandlers();
     150    }
     151
     152    public PackingSequenceProblem()
     153      : base() {
     154      var defaultEvaluator = new PackingRatioEvaluator();
     155      var defaultDecoder = new ExtremePointPermutationDecoder();
     156      Parameters.Add(new ValueParameter<IPermutationDecoder>("Decoder", "The decoder translates a permutation to a packing solution candidiates", defaultDecoder));
     157      Parameters.Add(new ValueParameter<BinPacking2D.IEvaluator>(SolutionEvaluatorParameterName, "The evaluator calculates qualities of solution candidates", defaultEvaluator));
     158      Parameters.Add(new ValueParameter<ReadOnlyItemList<PackingItem>>("Items", "The items which must be packed into bins"));
     159      Parameters.Add(new ValueParameter<PackingShape>("BinShape", "The size of bins into which items must be packed"));
     160      Parameters.Add(new OptionalValueParameter<Solution>("BestKnownSolution", "The best solution found so far"));
     161      Parameters.Add(new FixedValueParameter<IntValue>("LowerBound", "A lower bound for the number of bins that is necessary to pack all items"));
     162
     163      Load(DefaultInstance);
     164
     165      Encoding = new PermutationEncoding("PackingSequence", Items.Count, PermutationTypes.Absolute);
     166      AddOperators();
     167      RegisterEventHandlers();
     168    }
    61169    public override IDeepCloneable Clone(Cloner cloner) {
    62170      return new PackingSequenceProblem(this, cloner);
    63171    }
    64172
     173    [StorableHook(HookType.AfterDeserialization)]
     174    private void AfterDeserialization() {
     175      RegisterEventHandlers();
     176    }
     177
     178
     179    private void AddOperators() {
     180      Operators.Add(new StochasticInsertionMultiMoveGenerator());
     181      Operators.Add(new ExhaustiveInsertionMoveGenerator());
     182      Operators.Add(new TranslocationMoveMaker());
     183      Operators.Add(new TranslocationMoveEvaluator());
     184      Operators.Add(new TranslocationMoveTabuMaker());
     185
     186      Operators.RemoveAll(x => x is SingleObjectiveMoveGenerator);
     187      Operators.RemoveAll(x => x is SingleObjectiveMoveMaker);
     188      Operators.RemoveAll(x => x is SingleObjectiveMoveEvaluator);
     189
     190      Encoding.ConfigureOperators(Operators.OfType<IOperator>());
     191    }
     192
     193    private void RegisterEventHandlers() {
     194      // update encoding length when number of items is changed
     195      ItemsParameter.ValueChanged += (sender, args) => Encoding.Length = Items.Count;
     196    }
     197
     198    public override bool Maximization { get { return true; } }
     199
    65200
    66201    public override double Evaluate(Individual individual, IRandom random) {
    67       var permutation = individual.Permutation();
    68       var decoder = new ExtremePointPackingSequenceDecoder2D();
    69       var packingPlan = decoder.CreatePackingPlanFromEncoding(permutation, Bin, Items);
    70       var ratio = PackingRatioEvaluator.CalculatePackingRatio(packingPlan);
    71       return ratio.Value;
     202      var permutation = individual.Permutation("PackingSequence");
     203      var decoder = Decoder;
     204      var solution = decoder.Decode(permutation, BinShape, Items);
     205      return SolutionEvaluator.Evaluate(solution);
    72206    }
    73207
    74208    public override void Analyze(Individual[] individuals, double[] qualities, ResultCollection results, IRandom random) {
    75209      base.Analyze(individuals, qualities, results, random);
    76       Analyze(individuals.Select(i => i.Permutation()).ToArray(), qualities, results, random);
    77     }
     210      Analyze(individuals.Select(i => i.Permutation("PackingSequence")).ToArray(), qualities, results, random);
     211    }
     212
     213    public void Analyze(Permutation[] individuals, double[] qualities, ResultCollection results, IRandom random) {
     214      var bestSolutionResultName = "Best Packing Solution";
     215      var numContainersResultName = "Nr of Containers";
     216      var binUtilResultName = "Overall Bin Utilization";
     217
     218      if (!results.ContainsKey(bestSolutionResultName)) results.Add(new Result(bestSolutionResultName, typeof(Solution)));
     219      if (!results.ContainsKey(numContainersResultName)) results.Add(new Result(numContainersResultName, typeof(IntValue)));
     220      if (!results.ContainsKey(binUtilResultName)) results.Add(new Result(binUtilResultName, typeof(DoubleValue)));
     221
     222
     223      // find index of item with max quality
     224      int bestIdx = 0;
     225      for (int j = 1; j < qualities.Length; j++)
     226        if (qualities[j] > qualities[bestIdx]) bestIdx = j;
     227
     228
     229      // update best solution so far
     230      var bestSolution = results[bestSolutionResultName].Value as Solution;
     231      if (bestSolution == null ||
     232        bestSolution.Quality.Value < qualities[bestIdx]) {
     233
     234        var newBestSolution = Decoder.Decode(individuals[bestIdx], BinShape, Items);
     235        newBestSolution.Quality = new DoubleValue(qualities[bestIdx]);
     236        results[bestSolutionResultName].Value = newBestSolution;
     237        results[numContainersResultName].Value = new IntValue(newBestSolution.NrOfBins);
     238        results[binUtilResultName].Value = new DoubleValue(BinUtilizationEvaluator.CalculateBinUtilization(newBestSolution));
     239
     240        // update best known solution
     241        var bestKnownQuality = BestKnownQualityParameter.Value;
     242        if (bestKnownQuality == null ||
     243            bestKnownQuality.Value < qualities[bestIdx]) {
     244          BestKnownQualityParameter.ActualValue = new DoubleValue(qualities[bestIdx]);
     245          BestKnownSolutionParameter.ActualValue = newBestSolution;
     246        }
     247      }
     248    }
     249
     250
     251    #region Problem instance handling
     252    public void Load(BPPData data) {
     253      BestKnownSolutionParameter.Value = null;
     254      BestKnownQualityParameter.Value = null;
     255
     256      if (data.BestKnownQuality.HasValue)
     257        BestKnownQuality = data.BestKnownQuality.Value;
     258
     259      BinShape = data.BinShape;
     260      var items = new ItemList<PackingItem>(data.Items);
     261      items.Sort((x, y) => y.CompareTo(x));
     262      Items = items.AsReadOnly();
     263
     264      ApplyHorizontalOrientation();
     265      LowerBoundParameter.Value.Value = CalculateLowerBound();
     266    }
     267
     268
     269    public BPPData Export() {
     270      return new BPPData {
     271        Name = Name,
     272        Description = Description,
     273        BinShape = BinShape,
     274        Items = Items.ToArray()
     275      };
     276    }
     277    #endregion
     278
     279
     280    #region helpers
     281    private void ApplyHorizontalOrientation() {
     282      BinShape.ApplyHorizontalOrientation();
     283      foreach (var shape in Items) {
     284        shape.ApplyHorizontalOrientation();
     285      }
     286    }
     287
     288    private int CalculateLowerBound() {
     289      //This is the obvious continuous lower bound calculation; Martello and Vigo proposed a better way but it has not been implemented yet;
     290      int itemsVol = Items.Select(x => x.Volume).Sum();
     291      int binVol = BinShape.Volume;
     292      return (itemsVol + binVol - 1) / (binVol);
     293    }
     294
     295    #endregion
    78296  }
    79297}
  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.3D/3.3/BinPacking3D.cs

    r14049 r14146  
    197197    }
    198198
    199     public override void SlidingBasedPacking(ref List<int> sequence, ItemList<PackingItem> itemMeasures) {
     199    public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> itemMeasures) {
    200200      var temp = new List<int>(sequence);
    201201      for (int i = 0; i < temp.Count; i++) {
     
    208208      }
    209209    }
    210     public override void SlidingBasedPacking(ref List<int> sequence, ItemList<PackingItem> itemMeasures, Dictionary<int, bool> rotationArray) {
     210    public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> itemMeasures, Dictionary<int, bool> rotationArray) {
    211211      var temp = new List<int>(sequence);
    212212      for (int i = 0; i < temp.Count; i++) {
     
    219219      }
    220220    }
    221     public override void ExtremePointBasedPacking(ref List<int> sequence, ItemList<PackingItem> itemMeasures, bool stackingConstraints) {
     221    public override void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> itemMeasures, bool stackingConstraints) {
    222222      var temp = new List<int>(sequence);
    223223      foreach (int itemID in temp) {
     
    230230      }
    231231    }
    232     public override void ExtremePointBasedPacking(ref List<int> sequence, ItemList<PackingItem> itemMeasures, bool stackingConstraints, Dictionary<int, bool> rotationArray) {
     232    public override void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> itemMeasures, bool stackingConstraints, Dictionary<int, bool> rotationArray) {
    233233      var temp = new List<int>(sequence);
    234234      foreach (int itemID in temp) {
  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.3D/3.3/HeuristicLab.Problems.BinPacking3D-3.3.csproj

    r14128 r14146  
    163163  <ItemGroup>
    164164    <Compile Include="BinPacking3D.cs" />
    165     <Compile Include="DecoderInterfaces\I3DGVDecoder.cs" />
    166     <Compile Include="DecoderInterfaces\I3DMCVDecoder.cs" />
    167     <Compile Include="DecoderInterfaces\I3DPSDecoder.cs" />
    168     <Compile Include="Decoders\DBL\DeepestBottomLeftPackingSequenceDecoder.cs" />
    169     <Compile Include="Decoders\EP\ExtremePointPackingSequenceDecoder3D.cs" />
    170165    <Compile Include="I3DOperator.cs" />
    171166    <Compile Include="Instances\BPPData.cs" />
    172167    <Compile Include="Instances\RandomDataDescriptor.cs" />
    173168    <Compile Include="Instances\RandomInstanceProvider.cs" />
    174     <Compile Include="MoveEvaluators\PackingMoveEvaluator3DGV.cs" />
    175     <Compile Include="MoveEvaluators\PackingMoveEvaluator3DMCV.cs" />
    176     <Compile Include="MoveEvaluators\PackingMoveEvaluator3DPS.cs" />
    177169    <Compile Include="PackingItem.cs" />
    178170    <Compile Include="PackingPosition.cs" />
    179     <Compile Include="PackingRatioEvaluator.cs" />
    180171    <Compile Include="PackingShape.cs" />
    181172    <Compile Include="Plugin.cs" />
  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Encodings/PackingPlans/BinPacking.cs

    r14128 r14146  
    3131  [Item("BinPacking", "Represents a single-bin packing for a bin-packing problem.")]
    3232  [StorableClass]
    33   public abstract class BinPacking<D,B,I> : Item
     33  public abstract class BinPacking<D, B, I> : Item
    3434    where D : class, IPackingPosition
    3535    where B : PackingShape<D>
    36     where I : PackingShape<D>, IPackingItem {
     36    where I : PackingShape<D> {
    3737    #region Properties
    3838    [Storable]
    39     public ObservableDictionary<int, D> ItemPositions { get; private set; } 
     39    public ObservableDictionary<int, D> ItemPositions { get; private set; }
    4040
    4141    [Storable]
     
    4343
    4444    [Storable]
    45     public B BinMeasures { get; private set; } 
     45    public B BinMeasures { get; private set; }
    4646
    4747    [Storable]
     
    5353    #endregion Properties
    5454
    55     protected BinPacking(B binMeasures) : base() {   
     55    protected BinPacking(B binMeasures)
     56      : base() {
    5657      ItemPositions = new ObservableDictionary<int, D>();
    5758      ItemMeasures = new ObservableDictionary<int, I>();
     
    6465    [StorableConstructor]
    6566    protected BinPacking(bool deserializing) : base(deserializing) { }
    66     protected BinPacking(BinPacking<D,B,I> original, Cloner cloner)
     67    protected BinPacking(BinPacking<D, B, I> original, Cloner cloner)
    6768      : base(original, cloner) {
    6869      this.ItemPositions = new ObservableDictionary<int, D>(original.ItemPositions);
    6970      this.ItemMeasures = new ObservableDictionary<int, I>(original.ItemMeasures);
    70         this.BinMeasures = (B)original.BinMeasures.Clone(cloner);
    71         this.OccupationLayers = new Dictionary<int, List<int>>(original.OccupationLayers);
     71      this.BinMeasures = (B)original.BinMeasures.Clone(cloner);
     72      this.OccupationLayers = new Dictionary<int, List<int>>(original.OccupationLayers);
    7273    }
    73    
     74
    7475    protected abstract void GenerateNewExtremePointsForNewItem(I measures, D position);
    7576
     
    7778    public abstract D FindPositionBySliding(I measures, bool rotated);
    7879
    79     public abstract void SlidingBasedPacking(ref List<int> sequence, ItemList<I> itemMeasures);
    80     public abstract void SlidingBasedPacking(ref List<int> sequence, ItemList<I> itemMeasures, Dictionary<int, bool> rotationArray);
    81     public abstract void ExtremePointBasedPacking(ref List<int> sequence, ItemList<I> itemMeasures, bool stackingConstraints);
    82     public abstract void ExtremePointBasedPacking(ref List<int> sequence, ItemList<I> itemMeasures, bool stackingConstraints, Dictionary<int, bool> rotationArray);
     80    public abstract void SlidingBasedPacking(ref IList<int> sequence, IList<I> itemMeasures);
     81    public abstract void SlidingBasedPacking(ref IList<int> sequence, IList<I> itemMeasures, Dictionary<int, bool> rotationArray);
     82    public abstract void ExtremePointBasedPacking(ref IList<int> sequence, IList<I> itemMeasures, bool stackingConstraints);
     83    public abstract void ExtremePointBasedPacking(ref IList<int> sequence, IList<I> itemMeasures, bool stackingConstraints, Dictionary<int, bool> rotationArray);
    8384
    8485    public void PackItem(int itemID, I measures, D position) {
     
    8889      foreach (int id in ItemMeasures.Select(x => x.Key))
    8990        GenerateNewExtremePointsForNewItem(ItemMeasures[id], ItemPositions[id]);
    90      
    91        
    92       //GenerateNewExtremePointsForNewItem(measures, position);
    93       //OccupiedPoints.OccupyPoints(measures, position, itemID);
    9491
    9592      AddNewItemToOccupationLayers(itemID, measures, position);
    9693    }
    9794
    98     public double PackingDensity { 
     95    public double PackingDensity {
    9996      get {
    10097        double result = 0;
     
    108105
    109106    public int PointOccupation(D position) {
    110       //foreach (var ipEntry in ItemPositions) {
    111       //  if (ItemMeasures[ipEntry.Key].EnclosesPoint(ipEntry.Value, position))
    112       //    return ipEntry.Key;
    113       //}
    114107      foreach (var id in GetLayerItemIDs(position)) {
    115108        if (ItemMeasures[id].EnclosesPoint(ItemPositions[id], position))
     
    120113
    121114    public bool IsPointOccupied(D position) {
    122       //foreach (var ipEntry in ItemPositions) {
    123       //  if (ItemMeasures[ipEntry.Key].EnclosesPoint(ipEntry.Value, position))
    124       //    return true;
    125       //}     
    126115      foreach (var id in GetLayerItemIDs(position)) {
    127116        if (ItemMeasures[id].EnclosesPoint(ItemPositions[id], position))
     
    135124        return false;
    136125
    137       //foreach (var ipEntry in ItemPositions) {
    138       //  if (ItemMeasures[ipEntry.Key].Overlaps(ipEntry.Value, position, measures))
    139       //    return false;
    140       //}
    141126      foreach (var id in GetLayerItemIDs(measures, position)) {
    142127        if (ItemMeasures[id].Overlaps(ItemPositions[id], position, measures))
     
    146131      return true;
    147132    }
    148     public abstract int ShortestPossibleSideFromPoint (D position);
    149     public abstract bool IsStaticStable (I measures, D position);
     133    public abstract int ShortestPossibleSideFromPoint(D position);
     134    public abstract bool IsStaticStable(I measures, D position);
    150135
    151136
     
    154139    protected abstract List<int> GetLayerItemIDs(D position);
    155140    protected abstract List<int> GetLayerItemIDs(I measures, D position);
    156   }   
     141  }
    157142}
  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Encodings/PackingPlans/PackingPlan.cs

    r14128 r14146  
    2121
    2222using System;
    23 using System.Collections.Generic;
    2423using System.Linq;
    2524using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     
    2827using HeuristicLab.Data;
    2928using HeuristicLab.Collections;
    30 using HeuristicLab.Encodings.IntegerVectorEncoding;
    3129using HeuristicLab.Problems.BinPacking;
    32 using HeuristicLab.Encodings.PermutationEncoding;
    3330
    3431namespace HeuristicLab.Encodings.PackingEncoding {
  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/HeuristicLab.Problems.BinPacking-3.3.csproj

    r14128 r14146  
    158158  </ItemGroup>
    159159  <ItemGroup>
    160     <Compile Include="Analyzers\BestBinPackingSolutionAnalyzer.cs" />
    161     <Compile Include="Analyzers\BinPackingAnalyzer.cs" />
    162160    <Compile Include="Encodings\PackingPlans\BinPacking.cs" />
    163161    <Compile Include="Encodings\PackingPlans\PackingPlan.cs" />
     
    165163    <Compile Include="Encodings\PackingSolutionCrossover.cs" />
    166164    <Compile Include="Encodings\PackingSolutionManipulator.cs" />
    167     <Compile Include="Evaluators\BinUtilizationEvaluator.cs" />
    168     <Compile Include="Evaluators\DecodingEvaluator.cs" />
    169     <Compile Include="Evaluators\EvaluatorBase.cs" />
    170     <Compile Include="Evaluators\PackingRatioEvaluator.cs" />
    171165    <Compile Include="Interfaces\IDecodingEvaluator.cs" />
    172     <Compile Include="Interfaces\IEvaluator.cs" />
    173166    <Compile Include="Interfaces\IPackingPosition.cs" />
    174167    <Compile Include="Interfaces\IPackingSequenceMoveOperator.cs" />
     
    188181    <Compile Include="Interfaces\IPackingShape.cs" />
    189182    <Compile Include="PackingDimensions.cs" />
    190     <Compile Include="PackingMoveEvaluator.cs" />
    191183    <Compile Include="Interfaces\IPackingItem.cs" />
    192184    <Compile Include="Interfaces\IPackingPlan.cs" />
     
    194186    <Compile Include="PackingSolutionDecoder.cs" />
    195187    <Compile Include="Plugin.cs" />
    196     <Compile Include="PackingSequenceProblem.cs" />
    197188    <Compile Include="Properties\AssemblyInfo.cs" />
    198189  </ItemGroup>
     
    202193    <None Include="Plugin.cs.frame" />
    203194  </ItemGroup>
    204   <ItemGroup />
     195  <ItemGroup>
     196    <Folder Include="Evaluators\" />
     197  </ItemGroup>
    205198  <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />
    206199  <PropertyGroup>
  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Interfaces/IEvaluator.cs

    r14051 r14146  
    2424
    2525namespace HeuristicLab.Problems.BinPacking {
    26   public interface IEvaluator : ISingleObjectiveEvaluator {
    27      ILookupParameter<IPackingPlan> PackingPlanParameter { get; }
     26  public interface IEvaluator : IItem {
     27     double Evaluate(Solution )
    2828  }
    2929}
  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/PackingMoveEvaluator.cs

    r14128 r14146  
    103103      return base.Apply();
    104104    }
     105
     106
    105107  }
    106108}
Note: See TracChangeset for help on using the changeset viewer.