Changeset 15229 for branches

Timestamp:

07/13/17 15:22:59 (7 years ago)

Author:

abeham

Message:

#2762:

• Implemented review comments
• Fixed ResidualSpaceBestFitExtremePointPermutationDecoder by sorting from smallest to largest (merit function should be minimized)
• Some restructuring of the methods

Location:

branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3

Files:

• 2D/BinPacking2D.cs (modified) (3 diffs)
• 2D/IntegerVectorEncoding/BottomLeftIntegerVectorDecoder.cs (modified) (2 diffs)
• 2D/PermutationEncoding/BottomLeftPermutationDecoder.cs (modified) (1 diff)
• 3D/BinPacking3D.cs (modified) (8 diffs)
• 3D/Instances/ContainerPackingInstances.zip (moved) (moved from branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/3D/Instances/3D-Instances.zip)
• 3D/Instances/RealWorldContainerPackingInstanceProvider.cs (moved) (moved from branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/3D/Instances/RealisticInstanceProvider.cs) (2 diffs)
• 3D/Instances/ThreeDInstanceParser.cs (modified) (2 diffs)
• 3D/IntegerVectorEncoding/BottomLeftIntegerVectorDecoder.cs (modified) (2 diffs)
• 3D/PermutationEncoding/BottomLeftPermutationDecoder.cs (modified) (1 diff)
• 3D/PermutationEncoding/ExtremePointPermutationDecoder.cs (modified) (1 diff)
• 3D/PermutationEncoding/ExtremePointPermutationDecoderBase.cs (modified) (2 diffs)
• 3D/PermutationEncoding/FreeVolumeBestFitExtremePointPermutationDecoder.cs (modified) (2 diffs)
• 3D/PermutationEncoding/ResidualSpaceBestFitExtremePointPermutationDecoder.cs (modified) (2 diffs)
• Algorithms/3D/ExtremePointAlgorithm.cs (modified) (6 diffs)
• BinPacking.cs (modified) (4 diffs)
• HeuristicLab.Problems.BinPacking-3.3.csproj (modified) (2 diffs)

branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/2D/BinPacking2D.cs

@@ -88 +88 @@
       };
 
-      int epIndex = 0;
-      while (epIndex < ExtremePoints.Count && (!IsPositionFeasible(rotatedItem, ExtremePoints.ElementAt(epIndex)))) { epIndex++; }
-
-      if (epIndex < ExtremePoints.Count) {
-        var currentPoint = ExtremePoints.ElementAt(epIndex);
-
-        var result = new PackingPosition(currentPoint.AssignedBin, currentPoint.X, currentPoint.Y, rotated);
+      var ep = ExtremePoints.Where(x => IsPositionFeasible(rotatedItem, x, stackingConstraints)).FirstOrDefault();
+      if (ep != null) {
+        var result = new PackingPosition(ep.AssignedBin, ep.X, ep.Y, rotated);
         return result;
       }
       return null;
     }
-    public override PackingPosition FindPositionBySliding(PackingItem item, bool rotated) {
+    public override PackingPosition FindPositionBySliding(PackingItem item, bool rotated, bool stackingConstraints) {
       PackingPosition currentPosition = new PackingPosition(0,
         BinShape.Width - (rotated ? item.Height : item.Width),
         BinShape.Height - (rotated ? item.Width : item.Height), rotated);
       //Slide the item as far as possible to the left
-      while (IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition))
-        || IsPositionFeasible(item, PackingPosition.MoveDown(currentPosition))) {
+      while (IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition), stackingConstraints)
+        || IsPositionFeasible(item, PackingPosition.MoveDown(currentPosition), stackingConstraints)) {
         //Slide the item as far as possible to the bottom
-        while (IsPositionFeasible(item, PackingPosition.MoveDown(currentPosition))) {
+        while (IsPositionFeasible(item, PackingPosition.MoveDown(currentPosition), stackingConstraints)) {
           currentPosition = PackingPosition.MoveDown(currentPosition);
         }
-        if (IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition)))
+        if (IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition), stackingConstraints))
           currentPosition = PackingPosition.MoveLeft(currentPosition);
       }
 
-      return IsPositionFeasible(item, currentPosition) ? currentPosition : null;
-    }
-
-    public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items) {
+      return IsPositionFeasible(item, currentPosition, stackingConstraints) ? currentPosition : null;
+    }
+
+    public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints) {
       var temp = new List<int>(sequence);
       for (int i = 0; i < temp.Count; i++) {
         var item = items[temp[i]];
-        var position = FindPositionBySliding(item, false);
+        var position = FindPositionBySliding(item, false, stackingConstraints);
         if (position != null) {
           PackItem(temp[i], item, position);
@@ -128 +124 @@
       }
     }
-    public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items, Dictionary<int, bool> rotationArray) {
+    public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items, Dictionary<int, bool> rotationArray, bool stackingConstraints) {
       var temp = new List<int>(sequence);
       for (int i = 0; i < temp.Count; i++) {
         var item = items[temp[i]];
-        var position = FindPositionBySliding(item, rotationArray[temp[i]]);
+        var position = FindPositionBySliding(item, rotationArray[temp[i]], stackingConstraints);
         if (position != null) {
           PackItem(temp[i], item, position);
@@ -150 +146 @@
       }
     }
-    public override bool ExtremePointBasedPacking(int itemID, IList<PackingItem> items, bool stackingConstraints) {
-      var item = items[itemID];
-      var positionFound = FindExtremePointForItem(item, false, stackingConstraints);
-      if (positionFound != null) {
-        PackItem(itemID, item, positionFound);
-        return true;
-      }
-      return false;
-    }
     
     public override void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints, Dictionary<int, bool> rotationArray) {

branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/2D/IntegerVectorEncoding/BottomLeftIntegerVectorDecoder.cs

@@ -47 +47 @@
 
     protected override PackingPosition FindPositionForItem(BinPacking2D bp, PackingItem item) {
-      return bp.FindPositionBySliding(item, rotated: false);
+      return bp.FindPositionBySliding(item, rotated: false, stackingConstraints: false);
     }
 
@@ -54 +54 @@
       ref IList<int> remainingIDs, IList<PackingItem> items) {
       var bp = new BinPacking2D(partialSolution.BinShape);
-      bp.SlidingBasedPacking(ref remainingIDs, items);
+      bp.SlidingBasedPacking(ref remainingIDs, items, stackingConstraints: false);
       return bp;
     }

branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/2D/PermutationEncoding/BottomLeftPermutationDecoder.cs

@@ -46 +46 @@
       while (remainingIDs.Count > 0) {
         var bp = new BinPacking2D(binShape);
-        bp.SlidingBasedPacking(ref remainingIDs, items);
+        bp.SlidingBasedPacking(ref remainingIDs, items, stackingConstraints: false);
         result.Bins.Add(bp);
       }

branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/3D/BinPacking3D.cs

@@ -144 +144 @@
 
     public override PackingPosition FindExtremePointForItem(PackingItem item, bool rotated, bool stackingConstraints) {
-
       PackingItem newItem = new PackingItem(
         rotated ? item.Depth : item.Width,
@@ -151 +150 @@
         item.TargetBin, item.Weight, item.Material);
 
-      int epIndex = 0;
-      while (epIndex < ExtremePoints.Count && (
-        !IsPositionFeasible(newItem, ExtremePoints.ElementAt(epIndex))
-        || !IsSupportedByAtLeastOnePoint(newItem, ExtremePoints.ElementAt(epIndex))
-        || (stackingConstraints && !IsStaticStable(newItem, ExtremePoints.ElementAt(epIndex)))
-        || (stackingConstraints && !IsWeightSupported(newItem, ExtremePoints.ElementAt(epIndex)))
-      )) { epIndex++; }
-
-      if (epIndex < ExtremePoints.Count) {
-        var origPoint = ExtremePoints.ElementAt(epIndex);
-        var result = new PackingPosition(origPoint.AssignedBin, origPoint.X, origPoint.Y, origPoint.Z, rotated);
+      var ep = ExtremePoints.Where(x => IsPositionFeasible(newItem, x, stackingConstraints)).FirstOrDefault();
+      if (ep != null) {
+        var result = new PackingPosition(ep.AssignedBin, ep.X, ep.Y, ep.Z, rotated);
         return result;
       }
@@ -167 +158 @@
     }
 
-    public override PackingPosition FindPositionBySliding(PackingItem item, bool rotated) {
-      //TODO: does not support stacking constraints yet
+    public override bool IsPositionFeasible(PackingItem item, PackingPosition position, bool stackingConstraints) {
+      var feasible = base.IsPositionFeasible(item, position, stackingConstraints);
+      return feasible
+        && IsSupportedByAtLeastOnePoint(item, position)
+        && (!stackingConstraints || (IsStaticStable(item, position) && IsWeightSupported(item, position)));
+    }
+
+    public override PackingPosition FindPositionBySliding(PackingItem item, bool rotated, bool stackingConstraints) {
       //Starting-position at upper right corner (=left bottom point of item-rectangle is at position item.width,item.height)
       PackingPosition currentPosition = new PackingPosition(0,
@@ -175 +172 @@
         BinShape.Depth - (rotated ? item.Width : item.Depth), rotated);
       //Slide the item as far as possible to the bottom
-      while (IsPositionFeasible(item, PackingPosition.MoveDown(currentPosition))
-        || IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition))
-        || IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition))) {
+      while (IsPositionFeasible(item, PackingPosition.MoveDown(currentPosition), stackingConstraints)
+        || IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition), stackingConstraints)
+        || IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition), stackingConstraints)) {
         //Slide the item as far as possible to the left
-        while (IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition))
-      || IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition))) {
+        while (IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition), stackingConstraints)
+      || IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition), stackingConstraints)) {
           //Slide the item as far as possible to the back
-          while (IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition))) {
+          while (IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition), stackingConstraints)) {
             currentPosition = PackingPosition.MoveBack(currentPosition);
           }
-          if (IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition)))
+          if (IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition), stackingConstraints))
             currentPosition = PackingPosition.MoveLeft(currentPosition);
         }
-        if (IsPositionFeasible(item, PackingPosition.MoveDown(currentPosition)))
+        if (IsPositionFeasible(item, PackingPosition.MoveDown(currentPosition), stackingConstraints))
           currentPosition = PackingPosition.MoveDown(currentPosition);
       }
 
-      return IsPositionFeasible(item, currentPosition) ? currentPosition : null;
-    }
-
-    public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items) {
+      return IsPositionFeasible(item, currentPosition, stackingConstraints) ? currentPosition : null;
+    }
+
+    public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints) {
       var temp = new List<int>(sequence);
       for (int i = 0; i < temp.Count; i++) {
         var item = items[temp[i]];
-        var position = FindPositionBySliding(item, false);
+        var position = FindPositionBySliding(item, false, stackingConstraints);
         if (position != null) {
           PackItem(temp[i], item, position);
@@ -206 +203 @@
       }
     }
-    public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items, Dictionary<int, bool> rotationArray) {
+    public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items, Dictionary<int, bool> rotationArray, bool stackingConstraints) {
       var temp = new List<int>(sequence);
       for (int i = 0; i < temp.Count; i++) {
         var item = items[temp[i]];
-        var position = FindPositionBySliding(item, rotationArray[i]);
+        var position = FindPositionBySliding(item, rotationArray[i], stackingConstraints);
         if (position != null) {
           PackItem(temp[i], item, position);
@@ -231 +228 @@
       }
     }
-    public override bool ExtremePointBasedPacking(int itemID, IList<PackingItem> items, bool stackingConstraints) {
-      var item = items[itemID];
-      var positionFound = FindExtremePointForItem(item, false, stackingConstraints);
-      if (positionFound != null) {
-       PackItem(itemID, item, positionFound);
-       return true;
-      }
-      return false;
-    }
     public override void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints, Dictionary<int, bool> rotationArray) {
       var temp = new List<int>(sequence);
@@ -319 +307 @@
       return false;
     }
-
 
     protected override void InitializeOccupationLayers() {
@@ -370 +357 @@
       return;
     }
-    public int GetResidualSpace(PackingItem item, PackingPosition ep) {
-      return ((ResidualSpace[ep].Item1 - item.Width) +
-          (ResidualSpace[ep].Item2 - item.Height) +
-          (ResidualSpace[ep].Item3 - item.Depth));
-      }
-    }
   }
+}

branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/3D/Instances/RealWorldContainerPackingInstanceProvider.cs

@@ -30 +30 @@
 
 namespace HeuristicLab.Problems.BinPacking3D {
-  public class RealisticInstanceProvider : ProblemInstanceProvider<BPPData> {
-    protected virtual string FileName { get { return "3D-Instances"; } }
-
-    protected int binWidth, binHeight, binDepth;
-
+  public sealed class RealWorldContainerPackingInstanceProvider : ProblemInstanceProvider<BPPData> {
+    private string FileName { get { return "ContainerPackingInstances"; } }
+    
     public override string Name {
-      get { return "Realistic"; }
+      get { return "Real-world Container Packing"; }
     }
 
     public override string Description {
-      get { return "Problem instances derived from real-world data."; }
+      get { return "Problem instances derived from real-world container packing data."; }
     }
 
@@ -51 +49 @@
     }
 
-    public RealisticInstanceProvider() : base() { }
+    public RealWorldContainerPackingInstanceProvider() : base() { }
 
     public override IEnumerable<IDataDescriptor> GetDataDescriptors() {

branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/3D/Instances/ThreeDInstanceParser.cs

@@ -34 +34 @@
     public void Parse(Stream stream) {
       var reader = new StreamReader(stream);
-      var length = GetNextInteger(reader).Value;
-      var width = GetNextInteger(reader).Value;
-      var height = GetNextInteger(reader).Value;
-      var maxWeight = GetNextInteger(reader).Value;
+      var length = GetNextInteger(reader);
+      var width = GetNextInteger(reader);
+      var height = GetNextInteger(reader);
+      var maxWeight = GetNextInteger(reader);
       Bin = new PackingShape(width, height, length);
       Items = new List<PackingItem>();
       while (true) {
         try {
-          var id = GetNextInteger(reader).Value;
-          var pieces = GetNextInteger(reader).Value;
-          length = GetNextInteger(reader).Value;
-          width = GetNextInteger(reader).Value;
-          height = GetNextInteger(reader).Value;
-          var weight = GetNextInteger(reader).Value;
-          var stack = GetNextInteger(reader).Value;
-          var rotate = GetNextInteger(reader).Value;
-          var tilt = GetNextInteger(reader).Value;
+          var id = GetNextInteger(reader);
+          var pieces = GetNextInteger(reader);
+          length = GetNextInteger(reader);
+          width = GetNextInteger(reader);
+          height = GetNextInteger(reader);
+          var weight = GetNextInteger(reader);
+          var stack = GetNextInteger(reader);
+          var material = GetNextInteger(reader);
+          var rotate = GetNextInteger(reader);
+          var tilt = GetNextInteger(reader);
           for (var i = 0; i < pieces; i++) {
-            Items.Add(new PackingItem(width, height, length, Bin, weight, 1));
+            Items.Add(new PackingItem(width, height, length, Bin, weight, material));
           }
         } catch (InvalidOperationException) {
@@ -60 +61 @@
     }
 
-    private int? GetNextInteger(StreamReader reader) {
+    private int GetNextInteger(StreamReader reader) {
       var next = reader.Read();
       var builder = new StringBuilder();
       while (next >= 0 && !char.IsDigit((char)next)) next = reader.Read();
-      if (next == -1) return null;
+      if (next == -1) throw new InvalidOperationException("No further integer available");
       while (char.IsDigit((char)next)) {
         builder.Append((char)next);

branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/3D/IntegerVectorEncoding/BottomLeftIntegerVectorDecoder.cs

@@ -54 +54 @@
 
     protected override PackingPosition FindPositionForItem(BinPacking3D bp, PackingItem item, bool useStackingConstraints) {
-      return bp.FindPositionBySliding(item, rotated: false);
+      return bp.FindPositionBySliding(item, rotated: false, stackingConstraints: useStackingConstraints);
     }
 
@@ -61 +61 @@
       ref IList<int> remainingIDs, IList<PackingItem> items, bool useStackingConstraints) {
       var bp = new BinPacking3D(partialSolution.BinShape);
-      bp.SlidingBasedPacking(ref remainingIDs, items);
+      bp.SlidingBasedPacking(ref remainingIDs, items, useStackingConstraints);
       return bp;
     }

branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/3D/PermutationEncoding/BottomLeftPermutationDecoder.cs

@@ -46 +46 @@
       while (remainingIDs.Count > 0) {
         var bp = new BinPacking3D(binShape);
-        bp.SlidingBasedPacking(ref remainingIDs, items);
+        bp.SlidingBasedPacking(ref remainingIDs, items, useStackingConstraints);
         result.Bins.Add(bp);
       }

branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/3D/PermutationEncoding/ExtremePointPermutationDecoder.cs

@@ -45 +45 @@
 
     public override Solution Decode(Permutation permutation, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
+      return Apply(permutation, binShape, items, useStackingConstraints);
+    }
+
+    public static Solution Apply(Permutation permutation, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
       Solution result = new Solution(binShape, useExtremePoints: true, stackingConstraints: useStackingConstraints);
       IList<int> remainingIDs = new List<int>(permutation);

branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/3D/PermutationEncoding/ExtremePointPermutationDecoderBase.cs

@@ -19 +19 @@
  */
 #endregion
-
-using System;
+ 
 using System.Collections.Generic;
-using System.Linq;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -41 +39 @@
 
     public abstract Solution Decode(Permutation permutation, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints);
-
-    public virtual bool FindExtremePointForItem(Dictionary<Tuple<BinPacking3D, PackingPosition>, int> PointsSpace, PackingItem item, bool rotated, bool stackingConstraints, out BinPacking3D bin, out PackingPosition pos) {
-
-      PackingItem newItem = new PackingItem(
-        rotated ? item.Depth : item.Width,
-        item.Height,
-        rotated ? item.Width : item.Depth,
-        item.TargetBin, item.Weight, item.Material);
-
-      var EPoints = PointsSpace.Keys.ToList();
-      BinPacking3D bp;
-      PackingPosition position;
-      int epIndex = 0;
-      while (epIndex < EPoints.Count && (
-        !(((bp = EPoints.ElementAt(epIndex).Item1)).IsPositionFeasible(newItem, (position = EPoints.ElementAt(epIndex).Item2)))
-        || !bp.IsSupportedByAtLeastOnePoint(newItem, position)
-        || (stackingConstraints && !bp.IsStaticStable(newItem, position))
-        || (stackingConstraints && !bp.IsWeightSupported(newItem, position))
-      )) { epIndex++; }
-
-      if (epIndex < EPoints.Count) {
-        bin = EPoints.ElementAt(epIndex).Item1;
-        var origPoint = EPoints.ElementAt(epIndex).Item2;
-        pos = new PackingPosition(origPoint.AssignedBin, origPoint.X, origPoint.Y, origPoint.Z, rotated);
-
-        return true;
-      }
-      bin = null;
-      pos = null;
-      return false;
-    }
-
-    public virtual Dictionary<Tuple<BinPacking3D, PackingPosition>, int> GetResidualSpaceAllPoints(Solution solution, PackingItem item) {
-      Dictionary<Tuple<BinPacking3D, PackingPosition>, int> result = new Dictionary<Tuple<BinPacking3D, PackingPosition>, int>();
-      foreach (BinPacking3D bp in solution.Bins) {
-        foreach (var ep in bp.ExtremePoints) {
-          result.Add(Tuple.Create(bp, ep), bp.GetResidualSpace(item, ep));
-        }
-      }
-      return result;
-    }
-
-    public virtual bool ExtremePointBasedPacking(Dictionary<Tuple<BinPacking3D, PackingPosition>, int> PointsSpace, int itemID, IList<PackingItem> items, bool stackingConstraints) {
-      BinPacking3D bp;
-      PackingPosition positionFound;
-      var item = items[itemID];
-      if (FindExtremePointForItem(PointsSpace, item, false, stackingConstraints, out bp, out positionFound)) {
-        bp.PackItem(itemID, item, positionFound);
-        return true;
-      }
-      return false;
-    }
   }
 }

branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/3D/PermutationEncoding/FreeVolumeBestFitExtremePointPermutationDecoder.cs

@@ -44 +44 @@
 
     public override Solution Decode(Permutation permutation, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
+      return Apply(permutation, binShape, items, useStackingConstraints);
+    }
+
+    public static Solution Apply(Permutation permutation, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
       Solution result = new Solution(binShape, useExtremePoints: true, stackingConstraints: useStackingConstraints);
       IList<int> remainingIDs = new List<int>(permutation);
@@ -51 +55 @@
       foreach (int ID in remainingIDs) {
         var sortedBins = result.Bins.OrderBy(x => x.FreeVolume);
-        var notPacked = 0;
-        foreach (BinPacking3D bp in sortedBins) {
-          if (!bp.ExtremePointBasedPacking(ID, items, stackingConstraints: useStackingConstraints)) { notPacked++; } else break;
+        var item = items[ID];
+        var posFound = false;
+        foreach (var bp in sortedBins) {
+          var pos = bp.FindExtremePointForItem(item, false, useStackingConstraints);
+          posFound = pos != null;
+          if (posFound) {
+            bp.PackItem(ID, item, pos);
+            break;
+          }
         }
-        if (notPacked == result.NrOfBins) {
+        if (!posFound) {
           var bp = new BinPacking3D(binShape);
-          bp.ExtremePointBasedPacking(ID, items, stackingConstraints: useStackingConstraints);
+          var pos = bp.FindExtremePointForItem(item, false, useStackingConstraints);
+          if (pos == null) throw new InvalidOperationException("Item " + ID + " cannot be packed in empty bin.");
+          bp.PackItem(ID, item, pos);
           result.Bins.Add(bp);
         }

branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/3D/PermutationEncoding/ResidualSpaceBestFitExtremePointPermutationDecoder.cs

@@ -44 +44 @@
 
     public override Solution Decode(Permutation permutation, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
+      return Apply(permutation, binShape, items, useStackingConstraints);
+    }
+
+    public static Solution Apply(Permutation permutation, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
       Solution result = new Solution(binShape, useExtremePoints: true, stackingConstraints: useStackingConstraints);
       IList<int> remainingIDs = new List<int>(permutation);
-      Dictionary<Tuple<BinPacking3D,PackingPosition>, int> points = new Dictionary<Tuple<BinPacking3D,PackingPosition>,int>();
       var bpg = new BinPacking3D(binShape);
       bpg.ExtremePointBasedPacking(ref remainingIDs, items, stackingConstraints: useStackingConstraints);
       result.Bins.Add(bpg);
       foreach (int ID in remainingIDs) {
-        points = GetResidualSpaceAllPoints(result, items[ID]);
-        var sortedPoints = points.OrderByDescending(x => x.Value).ToDictionary(x => x.Key, x => x.Value);
-        if (!ExtremePointBasedPacking(sortedPoints, ID, items, stackingConstraints: useStackingConstraints)) { 
+        var item = items[ID];
+        var points = GetResidualSpaceAllPoints(result, item);
+        var sortedPoints = points.OrderBy(x => x.Item3);
+        var packed = false;
+        foreach (var p in sortedPoints) {
+          packed = p.Item1.PackItemIfFeasible(ID, item, p.Item2, useStackingConstraints);
+          if (packed) break;
+        }
+        if (!packed) {
+          // pack item in a new bin
           var bp = new BinPacking3D(binShape);
-          bp.ExtremePointBasedPacking(ID, items, stackingConstraints: useStackingConstraints);
+          var positionFound = bp.FindExtremePointForItem(item, false, useStackingConstraints);
+          if (positionFound != null) {
+            bp.PackItem(ID, item, positionFound);
+          } else throw new InvalidOperationException("Item " + ID + " cannot be packed in an empty bin.");
           result.Bins.Add(bp);
         }
@@ -62 +75 @@
       return result;
     }
+
+    public static IList<Tuple<BinPacking3D, PackingPosition, int>> GetResidualSpaceAllPoints(Solution solution, PackingItem item) {
+      var result = new List<Tuple<BinPacking3D, PackingPosition, int>>();
+      foreach (BinPacking3D bp in solution.Bins) {
+        foreach (var ep in bp.ExtremePoints) {
+          var rs = bp.ResidualSpace[ep];
+          if (rs.Item1 < item.Width || rs.Item2 < item.Height || rs.Item3 < item.Depth) continue;
+          result.Add(Tuple.Create(bp, ep, GetResidualMerit(rs, item, ep)));
+        }
+      }
+      return result;
+    }
+
+    private static int GetResidualMerit(Tuple<int, int, int> rs, PackingItem item, PackingPosition ep) {
+      return ((rs.Item1 - item.Width) +
+          (rs.Item2 - item.Height) +
+          (rs.Item3 - item.Depth));
+    }
   }
 }

branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/Algorithms/3D/ExtremePointAlgorithm.cs

@@ -41 +41 @@
   [StorableClass]
   [Creatable(CreatableAttribute.Categories.SingleSolutionAlgorithms, Priority = 180)]
-  public class ExtremePointAlgorithm : BasicAlgorithm {
+  public sealed class ExtremePointAlgorithm : BasicAlgorithm {
 
     public override Type ProblemType {
@@ -57 +57 @@
 
     [Storable]
-    private IValueParameter<EnumValue<SortingMethod>> sortingMethodParameter;
+    private readonly IValueParameter<EnumValue<SortingMethod>> sortingMethodParameter;
     public IValueParameter<EnumValue<SortingMethod>> SortingMethodParameter {
       get { return sortingMethodParameter; }
@@ -63 +63 @@
 
     [Storable]
-    private IValueParameter<EnumValue<FittingMethod>> fittingMethodParameter;
+    private readonly IValueParameter<EnumValue<FittingMethod>> fittingMethodParameter;
     public IValueParameter<EnumValue<FittingMethod>> FittingMethodParameter {
       get { return fittingMethodParameter; }
@@ -69 +69 @@
 
     [Storable]
-    private IValueParameter<PercentValue> deltaParameter;
+    private readonly IValueParameter<PercentValue> deltaParameter;
     public IValueParameter<PercentValue> DeltaParameter {
       get { return deltaParameter; }
@@ -75 +75 @@
 
     [StorableConstructor]
-    protected ExtremePointAlgorithm(bool deserializing) : base(deserializing) { }
-    protected ExtremePointAlgorithm(ExtremePointAlgorithm original, Cloner cloner)
+    private ExtremePointAlgorithm(bool deserializing) : base(deserializing) { }
+    private ExtremePointAlgorithm(ExtremePointAlgorithm original, Cloner cloner)
       : base(original, cloner) {
       sortingMethodParameter = cloner.Clone(original.sortingMethodParameter);
@@ -112 +112 @@
       if (result == null) throw new InvalidOperationException("No result obtained!");
 
-      Results.Add(new Result("Best Solution", result.Item1));
-      Results.Add(new Result("Best Solution Quality", new DoubleValue(result.Item2)));
+      Results.Add(new Result("Best Solution",
+        "The best found solution",
+        result.Item1));
+      Results.Add(new Result("Best Solution Quality",
+        "The quality of the best found solution according to the evaluator",
+        new DoubleValue(result.Item2)));
 
       var binUtil = new BinUtilizationEvaluator();
       var packRatio = new PackingRatioEvaluator();
-      Results.Add(new Result("Best Solution Bin Count", new IntValue(result.Item1.NrOfBins)));
-      Results.Add(new Result("Best Solution Bin Utilization", new PercentValue(Math.Round(binUtil.Evaluate(result.Item1), 3))));
+      Results.Add(new Result("Best Solution Bin Count",
+        "The number of bins in the best found solution",
+        new IntValue(result.Item1.NrOfBins)));
+      Results.Add(new Result("Best Solution Bin Utilization",
+        "The utilization given in percentage as calculated by the BinUtilizationEvaluator (total used space / total available space)",
+        new PercentValue(Math.Round(binUtil.Evaluate(result.Item1), 3))));
 
       if (result.Item3.HasValue && sorting.Length > 1)
-        Results.Add(new Result("Best Sorting Method", new EnumValue<SortingMethod>(result.Item3.Value)));
+        Results.Add(new Result("Best Sorting Method",
+          "The sorting method that found the best solution",
+          new EnumValue<SortingMethod>(result.Item3.Value)));
       if (result.Item4.HasValue && fitting.Length > 1)
-        Results.Add(new Result("Best Fitting Method", new EnumValue<FittingMethod>(result.Item4.Value)));
+        Results.Add(new Result("Best Fitting Method",
+          "The fitting method that found the best solution",
+          new EnumValue<FittingMethod>(result.Item4.Value)));
     }
 

branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/BinPacking.cs

@@ -90 +90 @@
 
     public abstract TPos FindExtremePointForItem(TItem item, bool rotated, bool stackingConstraints);
-    public abstract TPos FindPositionBySliding(TItem item, bool rotated);
+    public abstract TPos FindPositionBySliding(TItem item, bool rotated, bool stackingConstraints);
 
-    public abstract void SlidingBasedPacking(ref IList<int> sequence, IList<TItem> items);
-    public abstract void SlidingBasedPacking(ref IList<int> sequence, IList<TItem> items, Dictionary<int, bool> rotationArray);
+    public abstract void SlidingBasedPacking(ref IList<int> sequence, IList<TItem> items, bool stackingConstraints);
+    public abstract void SlidingBasedPacking(ref IList<int> sequence, IList<TItem> items, Dictionary<int, bool> rotationArray, bool stackingConstraints);
     public abstract void ExtremePointBasedPacking(ref IList<int> sequence, IList<TItem> items, bool stackingConstraints);
-    public abstract bool ExtremePointBasedPacking(int ID, IList<TItem> items, bool stackingConstraints);
     public abstract void ExtremePointBasedPacking(ref IList<int> sequence, IList<TItem> items, bool stackingConstraints, Dictionary<int, bool> rotationArray);
 
-    public void PackItem(int itemID, TItem item, TPos position) {
+    public virtual void PackItem(int itemID, TItem item, TPos position) {
       Items[itemID] = item;
       Positions[itemID] = position;
@@ -107 +106 @@
       
       AddNewItemToOccupationLayers(itemID, item, position);
+    }
+    public virtual bool PackItemIfFeasible(int itemID, TItem item, TPos position, bool stackingConstraints) {
+      if (IsPositionFeasible(item, position, stackingConstraints)) {
+        PackItem(itemID, item, position);
+        return true;
+      }
+      return false;
     }
 
@@ -135 +141 @@
       return false;
     }
-    public bool IsPositionFeasible(TItem item, TPos position) {
+    public virtual bool IsPositionFeasible(TItem item, TPos position, bool stackingConstraints) {
       //In this case feasability is defined as following: 1. the item fits into the bin-borders; 2. the point is supported by something; 3. the item does not collide with another already packed item
       if (!BinShape.Encloses(position, item))
@@ -147 +153 @@
       return true;
     }
+    
     public abstract int ShortestPossibleSideFromPoint(TPos position);
     public abstract bool IsStaticStable(TItem measures, TPos position);

branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/HeuristicLab.Problems.BinPacking-3.3.csproj

@@ -172 +172 @@
     <Compile Include="3D\Instances\BPPData.cs" />
     <Compile Include="3D\Instances\RandomDataDescriptor.cs" />
-    <Compile Include="3D\Instances\RealisticInstanceProvider.cs" />
+    <Compile Include="3D\Instances\RealWorldContainerPackingInstanceProvider.cs" />
     <Compile Include="3D\Instances\RandomInstanceProvider.cs" />
     <Compile Include="3D\Instances\ThreeDInstanceParser.cs" />
@@ -213 +213 @@
   </ItemGroup>
   <ItemGroup>
-    <EmbeddedResource Include="3D\Instances\3D-Instances.zip" />
+    <EmbeddedResource Include="3D\Instances\ContainerPackingInstances.zip" />
     <None Include="HeuristicLab.snk" />
     <None Include="Properties\AssemblyInfo.cs.frame" />