Changeset 15473 for branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking

Timestamp:

11/15/17 12:30:13 (7 years ago)

Author:

rhanghof

Message:

#2817:
-Added unit tests
-Refactoring of bp 3D

Location:

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3

Files:

• 2D/BinPacking2D.cs (modified) (13 diffs)
• 3D/Algorithms/ExtremePointAlgorithm.cs (added)
• 3D/BinPacking3D.cs (modified) (7 diffs)
• 3D/Decoder (deleted)
• 3D/Encoding (added)
• 3D/Encoding/ExtremePointPermutationDecoder.cs (added)
• 3D/Encoding/IDecoder.cs (added)
• 3D/Encoding/PermutationProblem.cs (added)
• 3D/Evaluators/BinUtilizationEvaluator.cs (modified) (2 diffs)
• 3D/Evaluators/IEvaluator.cs (added)
• 3D/Evaluators/MoveEvaluatorBase.cs (added)
• 3D/Evaluators/PackingRatioEvaluator.cs (modified) (2 diffs)
• 3D/Evaluators/Swap2MoveEvaluator.cs (added)
• 3D/Evaluators/TranslocationMoveEvaluator.cs (added)
• 3D/IOperator.cs (added)
• 3D/Instances/BPPData.cs (modified) (3 diffs)
• 3D/Instances/RandomInstanceProvider.cs (modified) (1 diff)
• 3D/Instances/RealWorldContainerPackingInstanceProvider.cs (modified) (1 diff)
• 3D/Instances/ThreeDInstanceParser.cs (added)
• 3D/IntegerVectorEncoding (deleted)
• 3D/Interfaces (deleted)
• 3D/MoveEvaluatorBase.cs (deleted)
• 3D/Packer/BinPacker.cs (modified) (1 diff)
• 3D/Packer/BinPackerFirstFit.cs (modified) (1 diff)
• 3D/Packer/BinPackerFreeVolumeBestFit.cs (modified) (2 diffs)
• 3D/Packer/BinPackerResidualSpaceBestFit.cs (modified) (2 diffs)
• 3D/PermutationEncoding (deleted)
• 3D/ProblemBase.cs (modified) (1 diff)
• 3D/Sorting/PackingItemSorter.cs (deleted)
• 3D/Sorting/PermutationPackingItemSorter.cs (added)
• Algorithms (deleted)
• BinPacking.cs (modified) (3 diffs)
• HeuristicLab.Problems.BinPacking-3.3.csproj (modified) (3 diffs)

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/2D/BinPacking2D.cs

@@ -34 +34 @@
     public BinPacking2D(PackingShape binShape)
       : base(binShape) {
+      OccupationLayers = new Dictionary<int, List<int>>();
       ExtremePoints.Add(binShape.Origin);
       InitializeOccupationLayers();
@@ -40 +41 @@
     [StorableConstructor]
     protected BinPacking2D(bool deserializing) : base(deserializing) { }
-    protected BinPacking2D(BinPacking2D original, Cloner cloner) : base(original, cloner) { }
+    protected BinPacking2D(BinPacking2D original, Cloner cloner) : base(original, cloner) {
+      this.OccupationLayers = new Dictionary<int, List<int>>();
+      foreach (var kvp in original.OccupationLayers) {
+        OccupationLayers.Add(kvp.Key, new List<int>(kvp.Value));
+      }
+    }
     public override IDeepCloneable Clone(Cloner cloner) {
       return new BinPacking2D(this, cloner);
     }
+
+    [Storable]
+    protected Dictionary<int, List<int>> OccupationLayers { get; set; }
 
     protected override void GenerateNewExtremePointsForNewItem(PackingItem newItem, PackingPosition position) {
@@ -75 +84 @@
     }
 
-    public override PackingPosition FindExtremePointForItem(PackingItem item, bool rotated, bool stackingConstraints) {
+    public PackingPosition FindExtremePointForItem(PackingItem item, bool rotated, bool stackingConstraints) {
       PackingItem rotatedItem = new PackingItem(
         rotated ? item.Height : item.Width,
@@ -91 +100 @@
       return null;
     }
-    public override PackingPosition FindPositionBySliding(PackingItem item, bool rotated, bool stackingConstraints) {
+
+    public override void PackItem(int itemID, PackingItem item, PackingPosition position) {
+      Items[itemID] = item;
+      Positions[itemID] = position;
+      ExtremePoints.Remove(position);
+      GenerateNewExtremePointsForNewItem(item, position);
+
+      AddNewItemToOccupationLayers(itemID, item, position);
+    }
+
+    public bool PackItemIfFeasible(int itemID, PackingItem item, PackingPosition position, bool stackingConstraints) {
+      if (IsPositionFeasible(item, position, stackingConstraints)) {
+        PackItem(itemID, item, position);
+        return true;
+      }
+      return false;
+    }
+
+    /// <summary>
+    /// 
+    /// </summary>
+    /// <param name="item"></param>
+    /// <param name="position"></param>
+    /// <param name="stackingConstraints"></param>
+    /// <returns></returns>
+    public override bool IsPositionFeasible(PackingItem item, PackingPosition 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))
+        return false;
+
+      foreach (var id in GetLayerItemIDs(item, position)) {
+        if (Items[id].Overlaps(Positions[id], position, item))
+          return false;
+      }
+
+      return true;
+    }
+
+
+    public PackingPosition FindPositionBySliding(PackingItem item, bool rotated, bool stackingConstraints) {
       PackingPosition currentPosition = new PackingPosition(0,
         BinShape.Width - (rotated ? item.Height : item.Width),
@@ -109 +160 @@
     }
 
-    public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints) {
+    public 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++) {
@@ -120 +171 @@
       }
     }
-    public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items, Dictionary<int, bool> rotationArray, bool stackingConstraints) {
+    public 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++) {
@@ -131 +182 @@
       }
     }
-    public override void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints) {
+    public void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints) {
       var temp = new List<int>(sequence);
       foreach (int itemID in temp) {
@@ -143 +194 @@
     }
     
-    public override void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints, Dictionary<int, bool> rotationArray) {
+    public void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints, Dictionary<int, bool> rotationArray) {
       var temp = new List<int>(sequence);
       foreach (int itemID in temp) {
@@ -155 +206 @@
     }
 
-    public override int ShortestPossibleSideFromPoint(PackingPosition position) {
+    public int ShortestPossibleSideFromPoint(PackingPosition position) {
       int shortestSide = int.MaxValue;
       int width = BinShape.Width;
@@ -179 +230 @@
       throw new NotSupportedException();
     }
-    protected override void InitializeOccupationLayers() {
+    protected void InitializeOccupationLayers() {
       for (int i = 0; i * 10 <= BinShape.Width; i += 1) {
         OccupationLayers[i] = new List<int>();
@@ -185 +236 @@
     }
 
-    protected override void AddNewItemToOccupationLayers(int itemID, PackingItem item, PackingPosition position) {
+    protected void AddNewItemToOccupationLayers(int itemID, PackingItem item, PackingPosition position) {
       int x1 = position.X / 10;
       int x2 = (position.X + (position.Rotated ? item.Height : item.Width)) / 10;
@@ -192 +243 @@
         OccupationLayers[i].Add(itemID);
     }
-    protected override List<int> GetLayerItemIDs(PackingPosition position) {
+    protected List<int> GetLayerItemIDs(PackingPosition position) {
       return OccupationLayers[position.X / 10];
     }
-    protected override List<int> GetLayerItemIDs(PackingItem item, PackingPosition position) {
+    protected List<int> GetLayerItemIDs(PackingItem item, PackingPosition position) {
       List<int> result = new List<int>();
       int x1 = position.X / 10;
@@ -205 +256 @@
       return result;
     }
+    
+
+    public int PointOccupation(PackingPosition position) {
+      foreach (var id in GetLayerItemIDs(position)) {
+        if (Items[id].EnclosesPoint(Positions[id], position))
+          return id;
+      }
+      return -1;
+    }
+
+    public bool IsPointOccupied(PackingPosition position) {
+      foreach (var id in GetLayerItemIDs(position)) {
+        if (Items[id].EnclosesPoint(Positions[id], position))
+          return true;
+      }
+      return false;
+    }
   }
 }

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/BinPacking3D.cs

@@ -41 +41 @@
       ResidualSpace = new Dictionary<PackingPosition, Tuple<int, int, int>>();
       AddExtremePoint(binShape.Origin);
-      InitializeOccupationLayers();
     }
     [StorableConstructor]
@@ -64 +63 @@
       #endregion
     }
-
-    #region New methods for bin packer class
 
     /// <summary>
@@ -114 +111 @@
       AddExtremePoint(ep3);
     }
-        
+
     private Tuple<int, int, int> CalculateResidualSpace(Vector3D pos) {
       var itemPos = Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] });
@@ -132 +129 @@
         }
       }
-      
-      if (limit.X - pos.X <= 0 || limit.Y - pos.Y <= 0  || limit.Z - pos.Z <= 0) {
+
+      if (limit.X - pos.X <= 0 || limit.Y - pos.Y <= 0 || limit.Z - pos.Z <= 0) {
         return Tuple.Create(0, 0, 0);
-      }      
+      }
       return Tuple.Create(limit.X - pos.X, limit.Y - pos.Y, limit.Z - pos.Z);
     }
@@ -363 +360 @@
         itemsP4.Where(x => x.Item2.SupportsStacking(item)).Any();
     }
-
-
-
-    #endregion
+    
 
     /// <summary>
@@ -501 +495 @@
       return false;
     }
-        
+
     #region Projections
 
@@ -629 +623 @@
     #endregion
 
-
-    #region Sliding based packing  and obsolet methods 
-    public override PackingPosition FindExtremePointForItem(PackingItem item, bool rotated, bool stackingConstraints) {
-      throw new NotSupportedException();
-      PackingItem newItem = new PackingItem(
-        rotated ? item.Depth : item.Width,
-        item.Height,
-        rotated ? item.Width : item.Depth,
-        item.TargetBin, item.Weight, item.Material);
-
-      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;
-      }
-      return null;
-    }
-
-
-
-
-    public override PackingPosition FindPositionBySliding(PackingItem item, bool rotated, bool stackingConstraints) {
-      throw new NotSupportedException();
-    }
-
-    public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints) {
-      throw new NotSupportedException();
-    }
-    public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items, Dictionary<int, bool> rotationArray, bool stackingConstraints) {
-      throw new NotSupportedException();
-    }
-
-
-    public override void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints) {
-      throw new NotSupportedException();
-    }
-
-    public override void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints, Dictionary<int, bool> rotationArray) {
-      throw new NotSupportedException();
-    }
-
-    public override int ShortestPossibleSideFromPoint(PackingPosition position) {
-      throw new NotSupportedException();
-    }
-
-
-    protected override void InitializeOccupationLayers() {
-    }
-    protected override void AddNewItemToOccupationLayers(int itemID, PackingItem item, PackingPosition position) {
-    }
-
-
-    protected override List<int> GetLayerItemIDs(PackingPosition position) {
-      return null;
-    }
-    protected override List<int> GetLayerItemIDs(PackingItem item, PackingPosition position) {
-      return null;
-    }
-    #endregion
 
 

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Evaluators/BinUtilizationEvaluator.cs

@@ -26 +26 @@
 using HeuristicLab.Common;
 
-namespace HeuristicLab.Problems.BinPacking3D {
+namespace HeuristicLab.Problems.BinPacking3D.Evaluators {
   // NOTE: same implementation as for 2d problem
   [Item("Bin-Utilization Evaluator (3d)", "Calculates the overall utilization of bin space.")]
@@ -43 +43 @@
 
     #region IEvaluator Members
+
+    /// <summary>
+    /// Calculates the bin utilization in percent.
+    /// </summary>
+    /// <param name="solution"></param>
+    /// <returns>Returns the calculated bin utilization of all bins in percent.</returns>
     public double Evaluate(Solution solution) {
       return CalculateBinUtilization(solution);

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Evaluators/PackingRatioEvaluator.cs

@@ -26 +26 @@
 using HeuristicLab.Common;
 
-namespace HeuristicLab.Problems.BinPacking3D {
+namespace HeuristicLab.Problems.BinPacking3D.Evaluators {
   // NOTE: same implementation as for 2d problem
   [Item("Packing-Ratio Evaluator (3d)", "Calculates the ratio between packed and unpacked space.")]
@@ -43 +43 @@
 
     #region IEvaluator Members
+
+    /// <summary>
+    /// Calculates the packing ratio for the solution.
+    /// The packing ration is calculated as followed:
+    /// Falkenauer:1996 - A Hybrid Grouping Genetic Algorithm for Bin Packing
+    /// fBPP = (SUM[i=1..N](Fi / C)^k)/N
+    /// N.......the number of bins used in the solution,
+    /// Fi......the sum of sizes of the items in the bin i (the fill of the bin),
+    /// C.......the bin capacity and
+    /// k.......a constant, k>1.
+    /// </summary>
+    /// <param name="solution"></param>
+    /// <returns>Returns the calculated packing ratio of the bins in the given solution.</returns>
     public double Evaluate(Solution solution) {
       return CalculatePackingRatio(solution);

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Instances/BPPData.cs

@@ -22 +22 @@
 
 
-namespace HeuristicLab.Problems.BinPacking3D {
+namespace HeuristicLab.Problems.BinPacking3D.Instances {
 
+  /// <summary>
+  /// Represents an instance which contains bin packing problem data.
+  /// </summary>
   public class BPPData {
     /// <summary>
@@ -29 +32 @@
     /// </summary>
     public string Name { get; set; }
+
     /// <summary>
     /// Optional! The description of the instance
@@ -38 +42 @@
     /// </summary>
     public int NumItems { get { return Items == null ? 0 : Items.Length; } }
+
+    /// <summary>
+    /// Assigned packing shape
+    /// </summary>
     public PackingShape BinShape { get; set; }
+
+    /// <summary>
+    /// Array with assigned packing items
+    /// </summary>
     public PackingItem[] Items { get; set; }
+    
     /// <summary>
     /// Optional! The quality of the best-known solution.

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Instances/RandomInstanceProvider.cs

@@ -164 +164 @@
     }
 
-
+    /// <summary>
+    /// Loads the data from the given data descriptor. 
+    /// It retuns a bin packing problem data instance with the data of the random instance provider.
+    /// </summary>
+    /// <param name="dd"></param>
+    /// <returns></returns>
     public override BPPData LoadData(IDataDescriptor dd) {
       var randDd = dd as RandomDataDescriptor;

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Instances/RealWorldContainerPackingInstanceProvider.cs

@@ -28 +28 @@
 using System.Text.RegularExpressions;
 using HeuristicLab.Problems.Instances;
+using HeuristicLab.Problems.BinPacking3D.Instances;
 
 namespace HeuristicLab.Problems.BinPacking3D {

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPacker.cs

@@ -54 +54 @@
     /// <param name="packingItem"></param>
     /// <param name="position"></param>
-    protected void PackItem(ref BinPacking3D packingBin, int itemId, PackingItem packingItem, PackingPosition position, bool useStackingConstraints) {
+    protected virtual void PackItem(BinPacking3D packingBin, int itemId, PackingItem packingItem, PackingPosition position, bool useStackingConstraints) {
 
       packingBin.PackItem(itemId, packingItem, position);

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerFirstFit.cs

@@ -67 +67 @@
         // if a valid packing position could be found, the current item can be added to the given bin
         if (position != null) {
-          PackItem(ref packingBin, itemId, items[itemId], position, useStackingConstraints);
+          PackItem(packingBin, itemId, items[itemId], position, useStackingConstraints);
           remainingIds.Remove(itemId);
         }

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerFreeVolumeBestFit.cs

@@ -64 +64 @@
           var bin = packingBin;
           if (positionFound) {
-            PackItem(ref bin, remainingId, item, position, useStackingConstraints);
+            PackItem(bin, remainingId, item, position, useStackingConstraints);
             break;
           }
@@ -77 +77 @@
           }
 
-          PackItem(ref packingBin, remainingId, item, position, useStackingConstraints);
+          PackItem(packingBin, remainingId, item, position, useStackingConstraints);
           packingList.Add(packingBin);
         }

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerResidualSpaceBestFit.cs

@@ -56 +56 @@
           if (point.Item1.IsPositionFeasible(item, point.Item2, useStackingConstraints)) {
             var binPacking = point.Item1;
-            PackItem(ref binPacking, remainingId, item, point.Item2, useStackingConstraints);
+            PackItem(binPacking, remainingId, item, point.Item2, useStackingConstraints);
             packed = true;
             break;
@@ -66 +66 @@
           var position = FindPackingPositionForItem(binPacking, item, useStackingConstraints, rotated);
           if (position != null) {
-            PackItem(ref binPacking, remainingId, item, position, useStackingConstraints);
+            PackItem(binPacking, remainingId, item, position, useStackingConstraints);
           } else {
             throw new InvalidOperationException("Item " + remainingId + " cannot be packed in an empty bin.");

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ProblemBase.cs

@@ -30 +30 @@
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 using HeuristicLab.Problems.Instances;
+using HeuristicLab.Problems.BinPacking3D.Encoding;
+using HeuristicLab.Problems.BinPacking3D.Evaluators;
+using HeuristicLab.Problems.BinPacking3D.Instances;
 
 namespace HeuristicLab.Problems.BinPacking3D {

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/BinPacking.cs

@@ -51 +51 @@
     public SortedSet<TPos> ExtremePoints { get; protected set; }
 
-    [Storable]
-    protected Dictionary<int, List<int>> OccupationLayers { get; set; }
-    
-    #endregion Properties
+    public double PackingDensity {
+      get {
+        double result = 0;
+        foreach (var entry in Items)
+          result += entry.Value.Volume;
+        result /= BinShape.Volume;
+        return result;
+      }
+    }
 
     public int FreeVolume {
       get { return BinShape.Volume - Items.Sum(x => x.Value.Volume); }
     }
-
+    #endregion Properties
+    
     protected BinPacking(TBin binShape)
       : base() {
@@ -66 +72 @@
       BinShape = (TBin)binShape.Clone();
       ExtremePoints = new SortedSet<TPos>();
-      OccupationLayers = new Dictionary<int, List<int>>();
     }
 
     [StorableConstructor]
     protected BinPacking(bool deserializing) : base(deserializing) { }
+
     protected BinPacking(BinPacking<TPos, TBin, TItem> original, Cloner cloner)
       : base(original, cloner) {
@@ -83 +89 @@
       this.BinShape = (TBin)original.BinShape.Clone(cloner);
       this.ExtremePoints = new SortedSet<TPos>(original.ExtremePoints.Select(p => cloner.Clone(p)));
-      this.OccupationLayers = new Dictionary<int, List<int>>();
-      foreach (var kvp in original.OccupationLayers) {
-        OccupationLayers.Add(kvp.Key, new List<int>(kvp.Value));
-      }
     }
-
+    
+    /// <summary>
+    /// Generate new extreme points for a given item
+    /// </summary>
+    /// <param name="item"></param>
+    /// <param name="position"></param>
     protected abstract void GenerateNewExtremePointsForNewItem(TItem item, TPos position);
-
-    public abstract TPos FindExtremePointForItem(TItem item, bool rotated, bool stackingConstraints);
-    public abstract TPos FindPositionBySliding(TItem item, bool rotated, bool stackingConstraints);
-
-    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 void ExtremePointBasedPacking(ref IList<int> sequence, IList<TItem> items, bool stackingConstraints, Dictionary<int, bool> rotationArray);
-
-    public virtual void PackItem(int itemID, TItem item, TPos position) {
-      Items[itemID] = item;
-      Positions[itemID] = position;
-      ExtremePoints.Remove(position);
-      GenerateNewExtremePointsForNewItem(item, position);
-      
-      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;
-    }
-
-    public double PackingDensity {
-      get {
-        double result = 0;
-        foreach (var entry in Items)
-          result += entry.Value.Volume;
-        result /= BinShape.Volume;
-        return result;
-      }
-    }
-
-
-    public int PointOccupation(TPos position) {
-      foreach (var id in GetLayerItemIDs(position)) {
-        if (Items[id].EnclosesPoint(Positions[id], position))
-          return id;
-      }
-      return -1;
-    }
-
-    public bool IsPointOccupied(TPos position) {
-      foreach (var id in GetLayerItemIDs(position)) {
-        if (Items[id].EnclosesPoint(Positions[id], position))
-          return true;
-      }
-      return false;
-    }
-
+    
     /// <summary>
-    /// 
+    /// Packs an item into the bin packing
+    /// </summary>
+    /// <param name="itemID"></param>
+    /// <param name="item"></param>
+    /// <param name="position"></param>
+    public abstract void PackItem(int itemID, TItem item, TPos position);
+    
+    /// <summary>
+    /// Checks if the given position is feasible for the given item
     /// </summary>
     /// <param name="item"></param>
     /// <param name="position"></param>
     /// <param name="stackingConstraints"></param>
-    /// <returns></returns>
-    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))
-        return false;
+    /// <returns>Returns true if the given position is feasible for the given item</returns>
+    public abstract bool IsPositionFeasible(TItem item, TPos position, bool stackingConstraints);
 
-      foreach (var id in GetLayerItemIDs(item, position)) {
-        if (Items[id].Overlaps(Positions[id], position, item))
-          return false;
-      }
-
-      return true;
-    }
+    /// <summary>
+    /// Checks if the given item is static stable on the given position
+    /// </summary>
+    /// <param name="measures">Item</param>
+    /// <param name="position">Position of the item</param>
+    /// <returns>Returns true if the given item is static stable on the given position</returns>
+    public abstract bool IsStaticStable(TItem measures, TPos position);
     
-    public abstract int ShortestPossibleSideFromPoint(TPos position);
-    public abstract bool IsStaticStable(TItem measures, TPos position);
-
-    protected abstract void InitializeOccupationLayers();
-    protected abstract void AddNewItemToOccupationLayers(int itemID, TItem item, TPos position);
-    protected abstract List<int> GetLayerItemIDs(TPos position);
-    protected abstract List<int> GetLayerItemIDs(TItem item, TPos position);
+    
   }
 }

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/HeuristicLab.Problems.BinPacking-3.3.csproj

@@ -107 +107 @@
     <Compile Include="3D\Packer\BinPackerFirstFit.cs" />
     <Compile Include="3D\BinPacking3D.cs" />
-    <Compile Include="3D\Decoder\ExtremePointPermutationDecoder.cs" />
+    <Compile Include="3D\Encoding\ExtremePointPermutationDecoder.cs" />
     <Compile Include="3D\Evaluators\BinUtilizationEvaluator.cs" />
     <Compile Include="3D\Evaluators\PackingRatioEvaluator.cs" />
@@ -120 +120 @@
     <Compile Include="3D\Instances\RandomDataDescriptor.cs" />
     <Compile Include="3D\Instances\RealWorldContainerPackingInstanceProvider.cs" />
-    <Compile Include="3D\IntegerVectorEncoding\ThreeDInstanceParser.cs" />
-    <Compile Include="3D\IntegerVectorEncoding\BottomLeftIntegerVectorDecoder.cs" />
-    <Compile Include="3D\IntegerVectorEncoding\ExtremePointIntegerVectorDecoder.cs" />
-    <Compile Include="3D\IntegerVectorEncoding\IntegerVectorDecoderBase.cs" />
-    <Compile Include="3D\IntegerVectorEncoding\IntegerVectorProblem.cs" />
-    <Compile Include="3D\Interfaces\IDecoder.cs" />
-    <Compile Include="3D\Interfaces\IEvaluator.cs" />
-    <Compile Include="3D\Interfaces\IOperator.cs" />
-    <Compile Include="3D\MoveEvaluatorBase.cs" />
+    <Compile Include="3D\Instances\ThreeDInstanceParser.cs" />
+    <Compile Include="3D\Encoding\IDecoder.cs" />
+    <Compile Include="3D\Evaluators\IEvaluator.cs" />
+    <Compile Include="3D\IOperator.cs" />
+    <Compile Include="3D\Evaluators\MoveEvaluatorBase.cs" />
     <Compile Include="3D\PackingItem.cs" />
     <Compile Include="3D\PackingPosition.cs" />
     <Compile Include="3D\PackingShape.cs" />
-    <Compile Include="3D\PermutationEncoding\PermutationProblem.cs" />
-    <Compile Include="3D\PermutationEncoding\Swap2MoveEvaluator.cs" />
-    <Compile Include="3D\PermutationEncoding\TranslocationMoveEvaluator.cs" />
+    <Compile Include="3D\Encoding\PermutationProblem.cs" />
+    <Compile Include="3D\Evaluators\Swap2MoveEvaluator.cs" />
+    <Compile Include="3D\Evaluators\TranslocationMoveEvaluator.cs" />
     <Compile Include="3D\ProblemBase.cs" />
     <Compile Include="3D\Solution.cs" />
-    <Compile Include="3D\Sorting\PackingItemSorter.cs" />
-    <Compile Include="Algorithms\3D\ExtremePointAlgorithm.cs" />
+    <Compile Include="3D\Sorting\PermutationPackingItemSorter.cs" />
+    <Compile Include="3D\Algorithms\ExtremePointAlgorithm.cs" />
     <Compile Include="BinPacking.cs" />
     <Compile Include="Interfaces\IPackingItem.cs">
@@ -162 +158 @@
     <None Include="Plugin.cs.frame" />
   </ItemGroup>
-  <ItemGroup>
-    <Folder Include="3D\Algorithms\" />
-  </ItemGroup>
+  <ItemGroup />
   <ItemGroup>
     <ProjectReference Include="..\..\HeuristicLab.Analysis\3.3\HeuristicLab.Analysis-3.3.csproj">