Changeset 15462 for branches/2817-BinPackingSpeedup

Timestamp:

11/08/17 16:30:41 (7 years ago)

Author:

rhanghof

Message:

#2817
-Added unit tests for bin packing 3d.
-The items can now be sorted by the material.

Location:

branches/2817-BinPackingSpeedup

Files:

• HeuristicLab.Problems.BinPacking/3.3/3D/BinPacking3D.cs (modified) (17 diffs)
• HeuristicLab.Problems.BinPacking/3.3/3D/Decoder/ExtremePointPermutationDecoder.cs (modified) (4 diffs)
• HeuristicLab.Problems.BinPacking/3.3/3D/Evaluators/PackingRatioEvaluator.cs (modified) (1 diff)
• HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPacker.cs (modified) (3 diffs)
• HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerFirstFit.cs (modified) (4 diffs)
• HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerFreeVolumeBestFit.cs (modified) (3 diffs)
• HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerResidualSpaceBestFit.cs (modified) (5 diffs)
• HeuristicLab.Problems.BinPacking/3.3/3D/PackingPosition.cs (modified) (1 diff)
• HeuristicLab.Problems.BinPacking/3.3/3D/PermutationEncoding/PermutationProblem.cs (modified) (2 diffs)
• HeuristicLab.Problems.BinPacking/3.3/Algorithms/3D/ExtremePointAlgorithm.cs (modified) (9 diffs)
• HeuristicLab.Problems.BinPacking/3.3/HeuristicLab.Problems.BinPacking-3.3.csproj (modified) (5 diffs)
• HeuristicLab.Tests/HeuristicLab.Tests.csproj (modified) (1 diff)

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

@@ -67 +67 @@
     #region New methods for bin packer class
 
-    public void AddItem(int itemID, PackingItem item, PackingPosition position) {
+    public override void PackItem(int itemID, PackingItem item, PackingPosition position) {
       Items[itemID] = item;
       Positions[itemID] = position;
@@ -74 +74 @@
     }
 
+    /// <summary>
+    /// Updates the extreme points of the bin
+    /// </summary>
+    /// <param name="item"></param>
+    /// <param name="position"></param>
+    /// <param name="stackingConstraints"></param>
     public void UpdateExtremePoints(PackingItem item, PackingPosition position, bool stackingConstraints) {
-      /*if (stackingConstraints) {
-        AddExtremePoint(new PackingPosition(position.AssignedBin, position.X + item.Width, position.Y, position.Z));
-        AddExtremePoint(new PackingPosition(position.AssignedBin, position.X, position.Y + item.Height, position.Z));
-        AddExtremePoint(new PackingPosition(position.AssignedBin, position.X, position.Y, position.Z + item.Depth));
-      } else {*/
+      if (stackingConstraints) {
+        UpdateExtremePointsWithStackingConstriants(item, position);
+      } else {
+        UpdateExtremePointsWithoutStackingConstriants(item, position);
+      }
+    }
+
+    /// <summary>
+    /// Updates the extreme points of the bin. 
+    /// As there is no need to project the extreme points to the next side of an item, the extreme points are only generated for the current item.
+    /// </summary>
+    /// <param name="item"></param>
+    /// <param name="position"></param>
+    private void UpdateExtremePointsWithStackingConstriants(PackingItem newItem, PackingPosition position) {
+
+      //UpdateExtremePointsWithoutStackingConstriants(newItem, position);
+      //return;
+
+      int newWidth = position.Rotated ? newItem.Depth : newItem.Width;
+      int newDepth = position.Rotated ? newItem.Width : newItem.Depth;
+      var ep1 = new PackingPosition(position.AssignedBin, position.X + newWidth, position.Y, position.Z);
+      var ep2 = new PackingPosition(position.AssignedBin, position.X, position.Y + newItem.Height, position.Z);
+      var ep3 = new PackingPosition(position.AssignedBin, position.X, position.Y, position.Z + newDepth);
+      AddExtremePoint(ep1);
+      AddExtremePoint(ep2);
+      AddExtremePoint(ep3);
+
+      /*
+      ExtremePoints.Add(ep1);
+      ExtremePoints.Add(ep2);
+      ExtremePoints.Add(ep3);
+
+      var rs1 = CalculateResidualSpace(CreateRs(ep1));
+      var rs2 = CalculateResidualSpace(CreateRs(ep2));
+      var rs3 = CalculateResidualSpace(CreateRs(ep3));
+      ResidualSpace.Add(ep1, rs1);
+      ResidualSpace.Add(ep2, rs2);
+      ResidualSpace.Add(ep3, rs3);*/
+    }
+
+
+    /*private bool AddExtremePoint(PackingPosition position) {
+      if ()
+
+      return true;
+    }
+
+    
+    private bool AddExtremePoint(PackingPosition pos) {
+      if (ExtremePoints.Add(pos)) {
+        var rs = CalculateResidualSpace(new Vector3D(pos));
+        ResidualSpace.Add(pos, rs);
+        // Check if existing extreme points are shadowed by the new point
+        // That is, their residual space fit entirely into the residual space of the new point
+        foreach (var ep in ExtremePoints.Where(x => x != pos && new Vector3D(x).IsInside(pos, rs)).ToList()) {
+          if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep), ResidualSpace[ep], pos, rs)) {
+            ExtremePoints.Remove(ep);
+            ResidualSpace.Remove(ep);
+          }
+        }
+        return true;
+      }
+      return false;
+    }*/
+
+
+    private Tuple<int, int, int> CalculateResidualSpace(Vector3D pos) {
+      var itemPos = Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] });
+      Vector3D limit = new Vector3D() { X = BinShape.Width, Y = BinShape.Height, Z = BinShape.Depth };
+      if (pos.X < limit.X && pos.Y < limit.Y && pos.Z < limit.Z) {
+        var rightLimit = ProjectRight(pos);
+        var upLimit = ProjectUp(pos);
+        var forwardLimit = ProjectForward(pos);
+        if (rightLimit.X > 0) {
+          limit.X = rightLimit.X;
+        }
+        if (upLimit.Y > 0) {
+          limit.Y = upLimit.Y;
+        }
+        if (forwardLimit.Z > 0) {
+          limit.Z = forwardLimit.Z;
+        }
+      }
+
+      
+      
+      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);
+    }
+
+
+    private Vector3D CreateRs(PackingPosition position) {
+      return new Vector3D() { X = position.X, Y = position.Y, Z = position.Z };
+    }
+
+    private void UpdateExtremePointsWithoutStackingConstriants(PackingItem item, PackingPosition position) {
       GenerateNewExtremePointsForNewItem(item, position);
 
@@ -92 +193 @@
         GenerateNewExtremePointsForNewItem(right.Item2, right.Item1);
       }
-      //}
     }
 
@@ -147 +247 @@
         }
       }
-      return true;     
+      return true;
     }
 
@@ -156 +256 @@
     /// <param name="t2"></param>
     /// <returns></returns>
-    bool ItemsCollides(Tuple<PackingPosition, PackingItem> t1, Tuple<PackingPosition, PackingItem> t2) {
+    private bool ItemsCollides(Tuple<PackingPosition, PackingItem> t1, Tuple<PackingPosition, PackingItem> t2) {
       var position1 = t1.Item1;
       var item1 = t1.Item2;
@@ -189 +289 @@
     /// <param name="position"></param>
     /// <returns></returns>
-    public bool HasOnePointWithAnItemBelow(PackingItem item, PackingPosition position) {
+    private bool HasOnePointWithAnItemBelow(PackingItem item, PackingPosition position) {
       bool p1, p2, p3, p4;
-      PointsLiesOnAnItems(item, position, out p1, out p2, out p3, out p4);
+      PointsLiesOnAnItem(item, position, out p1, out p2, out p3, out p4);
 
       return p1 || p2 || p3 || p4;
@@ -205 +305 @@
     public override bool IsStaticStable(PackingItem item, PackingPosition position) {
       bool p1, p2, p3, p4;
-      PointsLiesOnAnItems(item, position, out p1, out p2, out p3, out p4);
+      PointsLiesOnAnItem(item, position, out p1, out p2, out p3, out p4);
       return p1 && p2 && p3 && p4;
     }
 
     /// <summary>
-    /// This method sets the out parameters p1 ... p3 if the point lies on another item.
+    /// This method sets the out parameters p1 ... p4 if the point lies on another item.
     /// p1 ... p3 represents one point on the bottom side of an given item.
     /// +---------+
@@ -224 +324 @@
     /// <param name="p3"></param>
     /// <param name="p4"></param>
-    public void PointsLiesOnAnItems(PackingItem item, PackingPosition position, out bool p1, out bool p2, out bool p3, out bool p4) {
+    private void PointsLiesOnAnItem(PackingItem item, PackingPosition position, out bool p1, out bool p2, out bool p3, out bool p4) {
       IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP1;
       IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP2;
@@ -240 +340 @@
 
     /// <summary>
-    /// 
+    /// This method returns a collection for the out parameters itemsP1 ... itemsP4 with the items below
+    /// itemsP1 ... itemsP4 represents one point on the bottom side of an given item.
+    /// +---------+
+    /// |p1     p2|
+    /// |         |
+    /// |p4     p3|
+    /// +---------+
     /// </summary>
     /// <param name="item"></param>
@@ -277 +383 @@
     /// <param name="position"></param>
     /// <returns></returns>
-    public bool IsWeightSupported(PackingItem item, PackingPosition position) {
+    private bool IsWeightSupported(PackingItem item, PackingPosition position) {
       if (position.Y == 0) {
         return true;
@@ -298 +404 @@
     #endregion
 
-    public override void PackItem(int itemID, PackingItem item, PackingPosition position) {
-      // base call is deliberately omitted, because UpdateResidualSpace needs to be fitted in before
-      // generating new extreme points
-      Items[itemID] = item;
-      Positions[itemID] = position;
-      ExtremePoints.Remove(position);
-      ResidualSpace.Remove(position);
-      UpdateResidualSpace(item, position);
-      GenerateNewExtremePointsForNewItem(item, position);
-      // if an item is fit in below, before, or left of another its extreme points have to be regenerated
-      foreach (var above in GetItemsAbove(position))
-        GenerateNewExtremePointsForNewItem(above.Item2, above.Item1);
-      foreach (var front in GetItemsInfront(position))
-        GenerateNewExtremePointsForNewItem(front.Item2, front.Item1);
-      foreach (var right in GetItemsOnRight(position))
-        GenerateNewExtremePointsForNewItem(right.Item2, right.Item1);
-      AddNewItemToOccupationLayers(itemID, item, position);
-    }
-
-
-
+    /// <summary>
+    /// Generates new extreme points for a given item and its position.
+    /// It also recalcualtes the residual space and removes the extreme points which are not needed any more.
+    /// </summary>
+    /// <param name="newItem"></param>
+    /// <param name="position"></param>
     protected override void GenerateNewExtremePointsForNewItem(PackingItem newItem, PackingPosition position) {
       int newWidth = position.Rotated ? newItem.Depth : newItem.Width;
@@ -404 +495 @@
     }
 
-
     private bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, Tuple<int, int, int> residualSpace) {
       var eps = ExtremePoints.Where(x => !pos.Equals(x) && pos.IsInside(x, ResidualSpace[x]));
@@ -432 +522 @@
     }
 
-    private Tuple<int, int, int> CalculateResidualSpace(Vector3D pos) {
+    private Tuple<int, int, int> CalculateResidualSpace1(Vector3D pos) {
       var itemPos = Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] });
       var rightLimit = ProjectRight(pos);
@@ -505 +595 @@
     #region Get items
 
-    /// <summary>
-    /// 
-    /// </summary>
-    /// <param name="pos"></param>
-    /// <returns></returns>
     private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsAbove(PackingPosition pos) {
       var line = new Line3D(pos, new Vector3D(0, 1, 0));
@@ -573 +658 @@
 
 
-
+    #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,
@@ -590 +676 @@
     }
 
-  
-
-    #region Sliding based packing    
+
+
+
     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,
-        BinShape.Width - (rotated ? item.Depth : item.Width),
-        BinShape.Height - item.Height,
-        BinShape.Depth - (rotated ? item.Width : item.Depth), rotated);
-      //Slide the item as far as possible to the bottom
-      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), stackingConstraints)
-      || IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition), stackingConstraints)) {
-          //Slide the item as far as possible to the back
-          while (IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition), stackingConstraints)) {
-            currentPosition = PackingPosition.MoveBack(currentPosition);
-          }
-          if (IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition), stackingConstraints))
-            currentPosition = PackingPosition.MoveLeft(currentPosition);
-        }
-        if (IsPositionFeasible(item, PackingPosition.MoveDown(currentPosition), stackingConstraints))
-          currentPosition = PackingPosition.MoveDown(currentPosition);
-      }
-
-      return IsPositionFeasible(item, currentPosition, stackingConstraints) ? currentPosition : null;
+      throw new NotSupportedException();
     }
 
     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, stackingConstraints);
-        if (position != null) {
-          PackItem(temp[i], item, position);
-          sequence.Remove(temp[i]);
-        }
-      }
+      throw new NotSupportedException();
     }
     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], stackingConstraints);
-        if (position != null) {
-          PackItem(temp[i], item, position);
-          sequence.Remove(temp[i]);
-        }
-      }
+      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
-    public override void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints) {
-      var temp = new List<int>(sequence);
-      foreach (int itemID in temp) {
-        var item = items[itemID];
-        var positionFound = FindExtremePointForItem(item, false, stackingConstraints);
-        if (positionFound != null) {
-          PackItem(itemID, item, positionFound);
-          sequence.Remove(itemID);
-        }
-      }
-    }
-    public override 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) {
-        var item = items[itemID];
-        var positionFound = FindExtremePointForItem(item, rotationArray[itemID], stackingConstraints);
-        if (positionFound != null) {
-          PackItem(itemID, item, positionFound);
-          sequence.Remove(itemID);
-        }
-      }
-    }
-    public override int ShortestPossibleSideFromPoint(PackingPosition position) {
-
-      int shortestSide = int.MaxValue;
-      int width = BinShape.Width;
-      int height = BinShape.Height;
-      int depth = BinShape.Depth;
-
-      if (position.X >= width || position.Y >= height || position.Z >= depth)
-        return shortestSide;
-
-      PackingPosition current = new PackingPosition(0, position.X, position.Y, position.Z);
-      while (current.X < width && IsPointOccupied(current)) { current = PackingPosition.MoveRight(current); }
-      if (current.X - position.X < shortestSide)
-        shortestSide = current.X - position.X;
-
-
-      current = new PackingPosition(0, position.X, position.Y, position.Z);
-      while (current.Y < height && IsPointOccupied(current)) { current = PackingPosition.MoveUp(current); }
-      if (current.Y - position.Y < shortestSide)
-        shortestSide = current.Y - position.Y;
-
-
-      current = new PackingPosition(0, position.X, position.Y, position.Z);
-      while (current.Z < depth && IsPointOccupied(current)) { current = PackingPosition.MoveFront(current); }
-      if (current.Z - position.Z < shortestSide)
-        shortestSide = current.Z - position.Z;
-
-      return shortestSide;
-    }
-    
-
-    protected override void InitializeOccupationLayers() {
-      for (int i = 0; i * 10 <= BinShape.Depth; i += 1) {
-        OccupationLayers[i] = new List<int>();
-      }
-    }
-    protected override void AddNewItemToOccupationLayers(int itemID, PackingItem item, PackingPosition position) {
-      int z1 = position.Z / 10;
-      int z2 = (position.Z + (position.Rotated ? item.Width : item.Depth)) / 10;
-
-      for (int i = z1; i <= z2; i++)
-        OccupationLayers[i].Add(itemID);
-    }
-    protected override List<int> GetLayerItemIDs(PackingPosition position) {
-      return OccupationLayers[position.Z / 10];
-    }
-    protected override List<int> GetLayerItemIDs(PackingItem item, PackingPosition position) {
-      List<int> result = new List<int>();
-      int z1 = position.Z / 10;
-      int z2 = (position.Z + (position.Rotated ? item.Width : item.Depth)) / 10;
-
-      for (int i = z1; i <= z2; i++)
-        result.AddRange(OccupationLayers[i]);
-      return result;
-    }
+
 
     public void UpdateResidualSpace(PackingItem item, PackingPosition pos) {
@@ -762 +760 @@
       return;
     }
-
-
   }
 }

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

@@ -1 @@
-using HeuristicLab.Core;
+#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2016 Joseph Helm and Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using HeuristicLab.Core;
 using HeuristicLab.Encodings.PermutationEncoding;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
@@ -17 +38 @@
   [Item("Extreme-point Permutation Decoder (3d) Base", "Base class for 3d decoders")]
   [StorableClass]
-  public class ExtremePointPermutationDecoder : Item, IDecoder<Permutation> {
+  public class ExtremePointPermutationDecoder : Item, IDecoder<Permutation>
+    //where TBinPacker : BinPacker, new ()
+    {
 
     [StorableConstructor]
     protected ExtremePointPermutationDecoder(bool deserializing) : base(deserializing) { }
-    protected ExtremePointPermutationDecoder(ExtremePointPermutationDecoderBase original, Cloner cloner)
+    protected ExtremePointPermutationDecoder(ExtremePointPermutationDecoder original, Cloner cloner)
       : base(original, cloner) {
     }
@@ -34 +57 @@
 
     public override IDeepCloneable Clone(Cloner cloner) {
-      throw new NotImplementedException();
+      return new ExtremePointPermutationDecoder(this, cloner);
     }
 
@@ -49 +72 @@
     public Solution Decode(Permutation permutation, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
       Solution solution = new Solution(binShape, useExtremePoints: true, stackingConstraints: useStackingConstraints);
-      
-      foreach (var packedBin in _binPacker.PackItems()) {
+      foreach (var packedBin in _binPacker.PackItems(permutation, binShape, items, useStackingConstraints)) {
         solution.Bins.Add(packedBin);
       }

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

@@ -47 +47 @@
     }
 
-    /* 
-        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>
+    /// 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>
     public static double CalculatePackingRatio(Solution solution) {
       int nrOfBins = solution.NrOfBins;

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

@@ -1 @@
-using HeuristicLab.Core;
+#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2016 Joseph Helm and Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using HeuristicLab.Core;
 using HeuristicLab.Encodings.PermutationEncoding;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
@@ -13 +34 @@
   [StorableClass]
   public abstract class BinPacker {
-    protected Permutation _permutation;
-    protected PackingShape _binShape;
-    protected IList<PackingItem> _items;
-    protected bool _useStackingConstraints;
+    
+    public BinPacker() { }
 
     /// <summary>
     /// Packs all items of the bin packer and returns a collection of BinPacking3D objects
     /// </summary>
+    /// <param name="sortedItems">Permutation of items sorted by a sorting method. The value of each permutation index references to the index of the items list</param>
+    /// <param name="binShape">Bin for storing the items</param>
+    /// <param name="items">A list of packing items which should be assigned to a bin</param>
+    /// <param name="useStackingConstraints">Flag for using stacking constraints</param>
     /// <returns></returns>
-    public abstract IList<BinPacking3D> PackItems();
+    public abstract IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints);
 
-    /// <summary>
-    /// Tries to pack the remainig items into a given BinPacking3D object. Each item could be packed into the BinPacking3D object will be removed from the list of remaining ids
-    /// </summary>
-    /// <param name="remainingIds">List of remaining ids. After the method has been executed the list has to have less items</param>
-    /// <param name="items">List of packing items. Some of the items will be assigned to the BinPacking3D object</param>
-    /// <param name="packingBin">This object will be filled with some of the given items</param>
-    protected void PackRemainingItems(ref IList<int> remainingIds, ref BinPacking3D packingBin, IList<PackingItem> items, bool useStackingConstraints, Dictionary<int, bool> rotationArray) {
-
-      foreach (var itemId in new List<int>(remainingIds)) {
-        bool rotated = rotationArray == null ? false : rotationArray[itemId];
-        PackingPosition position = FindPackingPositionForItem(packingBin, items[itemId], useStackingConstraints, rotated);
-        // 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);
-          remainingIds.Remove(itemId);
-        }
-      }
-    }
+    
 
     /// <summary>
@@ -52 +58 @@
     protected void PackItem(ref BinPacking3D packingBin, int itemId, PackingItem packingItem, PackingPosition position, bool useStackingConstraints) {
 
-      packingBin.AddItem(itemId, packingItem, position);
+      packingBin.PackItem(itemId, packingItem, position);
       packingBin.UpdateResidualSpace(packingItem, position);
       packingBin.UpdateExtremePoints(packingItem, position, useStackingConstraints);

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

@@ -1 @@
-using HeuristicLab.Core;
+#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2016 Joseph Helm and Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using HeuristicLab.Core;
 using HeuristicLab.Encodings.PermutationEncoding;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
@@ -14 +35 @@
   public class BinPackerFirstFit : BinPacker {
 
-    public BinPackerFirstFit(Permutation permutation, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
-      _permutation = permutation;
-      _binShape = binShape;
-      _items = items;
-      _useStackingConstraints = useStackingConstraints;
-    }
-
+    public BinPackerFirstFit() : base() { }    
 
     /// <summary>
@@ -26 +41 @@
     /// </summary>
     /// <returns>Returns a collection of bin packing 3d objects. Each object represents a bin and the packed items</returns>
-    public override IList<BinPacking3D> PackItems() {
+    public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
       IList<BinPacking3D> packingList = new List<BinPacking3D>();
-      IList<int> remainingIds = new List<int>(_permutation);
+      IList<int> remainingIds = new List<int>(sortedItems);
 
       while (remainingIds.Count > 0) {
-        BinPacking3D packingBin = new BinPacking3D(_binShape);
-        PackRemainingItems(ref remainingIds, ref packingBin, _items, _useStackingConstraints, null);
+        BinPacking3D packingBin = new BinPacking3D(binShape);
+        PackRemainingItems(ref remainingIds, ref packingBin, items, useStackingConstraints, null);
         packingList.Add(packingBin);
       }
@@ -38 +53 @@
       return packingList;
     }
+
+    /// <summary>
+    /// Tries to pack the remainig items into a given BinPacking3D object. Each item could be packed into the BinPacking3D object will be removed from the list of remaining ids
+    /// </summary>
+    /// <param name="remainingIds">List of remaining ids. After the method has been executed the list has to have less items</param>
+    /// <param name="items">List of packing items. Some of the items will be assigned to the BinPacking3D object</param>
+    /// <param name="packingBin">This object will be filled with some of the given items</param>
+    protected void PackRemainingItems(ref IList<int> remainingIds, ref BinPacking3D packingBin, IList<PackingItem> items, bool useStackingConstraints, Dictionary<int, bool> rotationArray) {
+
+      foreach (var itemId in new List<int>(remainingIds)) {
+        bool rotated = rotationArray == null ? false : rotationArray[itemId];
+        PackingPosition position = FindPackingPositionForItem(packingBin, items[itemId], useStackingConstraints, rotated);
+        // 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);
+          remainingIds.Remove(itemId);
+        }
+      }
+    }
   }
 }

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

@@ -1 @@
-using HeuristicLab.Core;
+#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2016 Joseph Helm and Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using HeuristicLab.Core;
 using HeuristicLab.Encodings.PermutationEncoding;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
@@ -12 +33 @@
   [StorableClass]
   public class BinPackerFreeVolumeBestFit : BinPacker {
-    public BinPackerFreeVolumeBestFit(Permutation permutation, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
-      _permutation = permutation;
-      _binShape = binShape;
-      _items = items;
-      _useStackingConstraints = useStackingConstraints;
-    }
 
-    public override IList<BinPacking3D> PackItems() {
+    public BinPackerFreeVolumeBestFit() : base() { }
+
+    public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
       IList<BinPacking3D> packingList = new List<BinPacking3D>();
-      IList<int> remainingIds = new List<int>(_permutation);
-      
+      IList<int> remainingIds = new List<int>(sortedItems);
+
 
       foreach (int remainingId in remainingIds) {
         var sortedBins = packingList.OrderBy(x => x.FreeVolume);
-        PackingItem item = _items[remainingId];
+        var z = sortedBins.ToList();
+
+        PackingItem item = items[remainingId];
         bool positionFound = false;
 
         foreach (var packingBin in sortedBins) {
-          PackingPosition position = FindPackingPositionForItem(packingBin, item, _useStackingConstraints, false);
+          PackingPosition position = FindPackingPositionForItem(packingBin, item, useStackingConstraints, false);
           positionFound = position != null;
           var bin = packingBin;
           if (positionFound) {
-            PackItem(ref bin, remainingId, item, position, _useStackingConstraints);
+            PackItem(ref bin, remainingId, item, position, useStackingConstraints);
             break;
-          }            
+          }
         }
 
         if (!positionFound) {
-          BinPacking3D packingBin = new BinPacking3D(_binShape);
-          PackingPosition position = FindPackingPositionForItem(packingBin, item, _useStackingConstraints, false);
+          BinPacking3D packingBin = new BinPacking3D(binShape);
+          PackingPosition position = FindPackingPositionForItem(packingBin, item, useStackingConstraints, false);
 
           if (position == null) {
@@ -47 +66 @@
           }
 
-          PackItem(ref packingBin, remainingId, item, position, _useStackingConstraints);
+          PackItem(ref packingBin, remainingId, item, position, useStackingConstraints);
           packingList.Add(packingBin);
         }

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

@@ -1 @@
-using HeuristicLab.Core;
+#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2016 Joseph Helm and Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using HeuristicLab.Core;
 using HeuristicLab.Encodings.PermutationEncoding;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
@@ -12 +33 @@
   [StorableClass]
   public class BinPackerResidualSpaceBestFit : BinPacker {
-    public BinPackerResidualSpaceBestFit(Permutation permutation, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
-      _permutation = permutation;
-      _binShape = binShape;
-      _items = items;
-      _useStackingConstraints = useStackingConstraints;
-    }
 
+    public BinPackerResidualSpaceBestFit() : base() { }/*
+    public BinPackerResidualSpaceBestFit(Permutation permutation, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints)
+      : base(permutation, binShape, items, useStackingConstraints) { }
+      */
     /// <summary>
     /// Packs the items into the bins by using a best fit residual space algorithm.
@@ -25 +44 @@
     /// </summary>
     /// <returns></returns>
-    public override IList<BinPacking3D> PackItems() {
+    public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
       IList<BinPacking3D> packingList = new List<BinPacking3D>();
-      IList<int> remainingIds = new List<int>(_permutation);
+      IList<int> remainingIds = new List<int>(sortedItems);
       bool rotated = false;
 
       foreach (var remainingId in remainingIds) {
-        PackingItem item = _items[remainingId];
+        PackingItem item = items[remainingId];
         var residualSpacePoints = GetResidualSpaceForAllPoints(packingList, item);
         var sortedPoints = residualSpacePoints.OrderBy(x => x.Item3);
@@ -37 +56 @@
 
         foreach (var point in sortedPoints) {
-          if (point.Item1.IsPositionFeasible(item, point.Item2, _useStackingConstraints)) {
+          if (point.Item1.IsPositionFeasible(item, point.Item2, useStackingConstraints)) {
             var binPacking = point.Item1;
-            PackItem(ref binPacking, remainingId, item, point.Item2, _useStackingConstraints);
+            PackItem(ref binPacking, remainingId, item, point.Item2, useStackingConstraints);
             packed = true;
             break;
@@ -46 +65 @@
 
         if (!packed) {
-          BinPacking3D binPacking = new BinPacking3D(_binShape);
-          var position = FindPackingPositionForItem(binPacking, item, _useStackingConstraints, rotated);
+          BinPacking3D binPacking = new BinPacking3D(binShape);
+          var position = FindPackingPositionForItem(binPacking, item, useStackingConstraints, rotated);
           if (position != null) {
-            PackItem(ref binPacking, remainingId, item, position, _useStackingConstraints);
+            PackItem(ref 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/PackingPosition.cs

@@ -115 +115 @@
       if (result == 0)
         result = Y.CompareTo(other.Y);
-
+      
       return result;
 

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

@@ -30 +30 @@
 using HeuristicLab.Optimization.Operators;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Problems.BinPacking3D.Decoder;
+using HeuristicLab.Problems.BinPacking3D.Packer;
 
 namespace HeuristicLab.Problems.BinPacking3D {
@@ -47 +49 @@
     public PermutationProblem()
       : base() {
-      Decoder = new ExtremePointPermutationDecoder(); // default decoder
+      Decoder = new ExtremePointPermutationDecoder(new BinPackerFirstFit()); // default decoder
 
       Encoding = new PermutationEncoding(EncodedSolutionName, Items.Count, PermutationTypes.Absolute);

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

@@ -33 +33 @@
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 using HeuristicLab.Problems.BinPacking3D.Packer;
+using HeuristicLab.Problems.BinPacking3D.Decoder;
+
+using HeuristicLab.Problems.BinPacking3D.Sorting;
 
 namespace HeuristicLab.Problems.BinPacking3D {
@@ -74 +77 @@
       get { return deltaParameter; }
     }
+
+    [Storable]
+    private readonly IValueParameter<BoolValue> sortByMaterialParameter;
+
+    public IValueParameter<BoolValue> SortByMaterialParameter {
+      get { return sortByMaterialParameter; }
+    }    
 
     [StorableConstructor]
@@ -84 +94 @@
     }
     public ExtremePointAlgorithm() {
-      Parameters.Add(sortingMethodParameter = new ValueParameter<EnumValue<SortingMethod>>("SortingMethod", "In which order the items should be packed.", new EnumValue<SortingMethod>(SortingMethod.All)));
-      Parameters.Add(fittingMethodParameter = new ValueParameter<EnumValue<FittingMethod>>("FittingMethod", "Which method to fit should be used.", new EnumValue<FittingMethod>(FittingMethod.All)));
-      Parameters.Add(deltaParameter = new ValueParameter<PercentValue>("Delta", "[1;100]% Clustered sorting methods use a delta parameter to determine the clusters.", new PercentValue(.1)));
+      Parameters.Add(sortingMethodParameter = new ValueParameter<EnumValue<SortingMethod>>(
+        "SortingMethod", "In which order the items should be packed.", new EnumValue<SortingMethod>(SortingMethod.All)));
+
+      Parameters.Add(fittingMethodParameter = new ValueParameter<EnumValue<FittingMethod>>(
+        "FittingMethod", "Which method to fit should be used.", new EnumValue<FittingMethod>(FittingMethod.All)));
+
+      Parameters.Add(deltaParameter = new ValueParameter<PercentValue>(
+        "Delta", "[1;100]% Clustered sorting methods use a delta parameter to determine the clusters.", new PercentValue(.1)));
+
+      Parameters.Add(sortByMaterialParameter = new ValueParameter<BoolValue>(
+        "SortByMaterial", "If this parameter is set, the items will be sorted by their material first", new BoolValue(true)));
 
       Problem = new PermutationProblem();
@@ -146 +164 @@
     }
 
+    /// <summary>
+    /// Retunrs the best solution for the given parameters
+    /// </summary>
+    /// <param name="bin"></param>
+    /// <param name="items"></param>
+    /// <param name="sortings"></param>
+    /// <param name="fittings"></param>
+    /// <param name="token"></param>
+    /// <returns></returns>
     private Tuple<Solution, double, SortingMethod?, FittingMethod?> GetBest(PackingShape bin, IList<PackingItem> items, SortingMethod[] sortings, FittingMethod[] fittings, CancellationToken token) {
       SortingMethod? bestSorting = null;
@@ -153 +180 @@
       foreach (var fit in fittings) {
         foreach (var sort in sortings) {
-          var result = Optimize(bin, items, sort, fit, DeltaParameter.Value.Value, Problem.UseStackingConstraints, Problem.SolutionEvaluator, token);
+          IDecoder<Permutation> decoder = new ExtremePointPermutationDecoder(BinPackerFactory.CreateBinPacker(fit));
+          Permutation sortedItems;
+          if (SortByMaterialParameter.Value.Value) {
+            sortedItems = SortItemsByMaterialAndSortingMethod(bin, items, sort, DeltaParameter.Value.Value);
+          } else {
+            sortedItems = SortItemsBySortingMethod(bin, items, sort, DeltaParameter.Value.Value);
+          }
+                    
+          var result = Optimize(sortedItems, bin, items, Problem.UseStackingConstraints, decoder, Problem.SolutionEvaluator);
+
           if (double.IsNaN(result.Item2) || double.IsInfinity(result.Item2)) {
             continue;
@@ -175 +211 @@
     }
 
-    private static Tuple<Solution, double> Optimize(PackingShape bin, IList<PackingItem> items, SortingMethod sorting, FittingMethod fitting, double delta, bool stackingConstraints, IEvaluator evaluator, CancellationToken token) {
-      Permutation sortedItems = SortItemsBySortingMethod(bin, items, sorting, delta);
-
-      if (false) {// alt
-        ExtremePointPermutationDecoderBase decoder = GetDecoderByFittingMethod(fitting);
-        var sol = decoder.Decode(sortedItems, bin, items, stackingConstraints);
-        var fit = evaluator.Evaluate(sol);
-
-        return Tuple.Create(sol, fit);
-      } else {
-        Decoder.ExtremePointPermutationDecoder decoder = new Decoder.ExtremePointPermutationDecoder(GetBinPackerByFittingMethod(fitting, sortedItems, bin, items, stackingConstraints));
-
-        var sol = decoder.Decode(sortedItems, bin, items, stackingConstraints);
-        var fit = evaluator.Evaluate(sol);
-
-        return Tuple.Create(sol, fit);
-      }
+    /// <summary>
+    /// Returns a tuple with the solution and the packing ratio depending on the given parameters
+    /// </summary>
+    /// <param name="sortedItems"></param>
+    /// <param name="bin"></param>
+    /// <param name="items"></param>
+    /// <param name="stackingConstraints"></param>
+    /// <param name="decoder"></param>
+    /// <param name="evaluator"></param>
+    /// <returns></returns>
+    private static Tuple<Solution, double> Optimize(Permutation sortedItems, PackingShape bin, IList<PackingItem> items, bool stackingConstraints, IDecoder<Permutation> decoder, IEvaluator evaluator) { 
       
-
-      
-    }
-
-
-
-    private static BinPacker GetBinPackerByFittingMethod(FittingMethod fittingMethod, Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
-      BinPacker binPacker = null;
-      switch (fittingMethod) {
-        case FittingMethod.FirstFit:
-          binPacker = new BinPackerFirstFit(sortedItems, binShape, items, useStackingConstraints);
-          break;
-        case FittingMethod.FreeVolumeBestFit:
-          binPacker = new BinPackerFreeVolumeBestFit(sortedItems, binShape, items, useStackingConstraints);
-          break;
-        case FittingMethod.ResidualSpaceBestFit:
-          binPacker = new BinPackerResidualSpaceBestFit(sortedItems, binShape, items, useStackingConstraints);
-          break;
-        default:
-          throw new ArgumentException("Unknown fitting method: " + fittingMethod);
-      }
-      return binPacker;
-    }
+      var sol = decoder.Decode(sortedItems, bin, items, stackingConstraints);
+      var fit = evaluator.Evaluate(sol);
+
+      return Tuple.Create(sol, fit);
+    }
+    
 
     /// <summary>
@@ -225 +238 @@
     /// <param name="delta"></param>
     /// <returns></returns>
-    private static Permutation SortItemsBySortingMethod(PackingShape bin, IList<PackingItem> items, SortingMethod sortingMethod, double delta) {
+    private Permutation SortItemsBySortingMethod(PackingShape bin, IList<PackingItem> items, SortingMethod sortingMethod, double delta) {
       Permutation sorted = null;
+      
       switch (sortingMethod) {
         case SortingMethod.Given:
@@ -232 +246 @@
           break;
         case SortingMethod.VolumeHeight:
-          sorted = new Permutation(PermutationTypes.Absolute,
-                    items.Select((v, i) => new { Index = i, Item = v })
-                         .OrderByDescending(x => x.Item.Depth * x.Item.Width * x.Item.Height)
-                         .ThenByDescending(x => x.Item.Height)
-                         .Select(x => x.Index).ToArray());
+          sorted = items.SortByVolumeHeight();
           break;
         case SortingMethod.HeightVolume:
-          sorted = new Permutation(PermutationTypes.Absolute,
-                    items.Select((v, i) => new { Index = i, Item = v })
-                         .OrderByDescending(x => x.Item.Height)
-                         .ThenByDescending(x => x.Item.Depth * x.Item.Width * x.Item.Height)
-                         .Select(x => x.Index).ToArray());
+          sorted = items.SortByMaterialHeightVolume();
           break;
         case SortingMethod.AreaHeight:
-          sorted = new Permutation(PermutationTypes.Absolute,
-                    items.Select((v, i) => new { Index = i, Item = v })
-                         .OrderByDescending(x => x.Item.Depth * x.Item.Width)
-                         .ThenByDescending(x => x.Item.Height)
-                         .Select(x => x.Index).ToArray());
+          sorted = items.SortByMaterialAreaHeight();
           break;
         case SortingMethod.HeightArea:
-          sorted = new Permutation(PermutationTypes.Absolute,
-                    items.Select((v, i) => new { Index = i, Item = v })
-                         .OrderByDescending(x => x.Item.Height)
-                         .ThenByDescending(x => x.Item.Depth * x.Item.Width)
-                         .Select(x => x.Index).ToArray());
+          sorted = items.SortByMaterialHeightArea();
           break;
         case SortingMethod.ClusteredAreaHeight:
-          double clusterRange = bin.Width * bin.Depth * delta;
-          sorted = new Permutation(PermutationTypes.Absolute,
-                    items.Select((v, i) => new { Index = i, Item = v, ClusterId = (int)(Math.Ceiling(v.Width * v.Depth / clusterRange)) })
-                        .GroupBy(x => x.ClusterId)
-                        .Select(x => new { Cluster = x.Key, Items = x.OrderByDescending(y => y.Item.Height).ToList() })
-                        .OrderByDescending(x => x.Cluster)
-                        .SelectMany(x => x.Items)
-                        .Select(x => x.Index).ToArray());
+          sorted = items.SortByMaterialClusteredAreaHeight(bin, delta);
           break;
         case SortingMethod.ClusteredHeightArea:
-          double clusterRange2 = bin.Height * delta;
-          sorted = new Permutation(PermutationTypes.Absolute,
-                    items.Select((v, i) => new { Index = i, Item = v, ClusterId = (int)(Math.Ceiling(v.Height / clusterRange2)) })
-                        .GroupBy(x => x.ClusterId)
-                        .Select(x => new { Cluster = x.Key, Items = x.OrderByDescending(y => y.Item.Depth * y.Item.Width).ToList() })
-                        .OrderByDescending(x => x.Cluster)
-                        .SelectMany(x => x.Items)
-                        .Select(x => x.Index).ToArray());
+          sorted = items.SortByMaterialClusteredHeightArea(bin, delta);
           break;
         default:
@@ -286 +270 @@
 
     /// <summary>
-    /// Returns a decoder depending on the given fitting method
-    /// </summary>
-    /// <param name="fittingMethod"></param>
+    /// Returns a new permutation of the given items depending on the material and sorting method
+    /// </summary>
+    /// <param name="bin"></param>
+    /// <param name="items"></param>
+    /// <param name="sortingMethod"></param>
+    /// <param name="delta"></param>
     /// <returns></returns>
-    private static ExtremePointPermutationDecoderBase GetDecoderByFittingMethod(FittingMethod fittingMethod) {
-      ExtremePointPermutationDecoderBase decoder = null;
-      switch (fittingMethod) {
-        case FittingMethod.FirstFit:
-          decoder = new ExtremePointPermutationDecoder();
-          break;
-        case FittingMethod.FreeVolumeBestFit:
-          decoder = new FreeVolumeBestFitExtremePointPermutationDecoder();
-          break;
-        case FittingMethod.ResidualSpaceBestFit:
-          decoder = new ResidualSpaceBestFitExtremePointPermutationDecoder();
+    private Permutation SortItemsByMaterialAndSortingMethod(PackingShape bin, IList<PackingItem> items, SortingMethod sortingMethod, double delta) {
+      Permutation sorted = null;
+
+      switch (sortingMethod) {
+        case SortingMethod.Given:
+          sorted = new Permutation(PermutationTypes.Absolute, Enumerable.Range(0, items.Count).ToArray());
+          break;
+        case SortingMethod.VolumeHeight:
+          sorted = items.SortByVolumeHeight();
+          break;
+        case SortingMethod.HeightVolume:
+          sorted = items.SortByHeightVolume();
+          break;
+        case SortingMethod.AreaHeight:
+          sorted = items.SortByAreaHeight();
+          break;
+        case SortingMethod.HeightArea:
+          sorted = items.SortByHeightArea();
+          break;
+        case SortingMethod.ClusteredAreaHeight:
+          sorted = items.SortByClusteredAreaHeight(bin, delta);
+          break;
+        case SortingMethod.ClusteredHeightArea:
+          sorted = items.SortByClusteredHeightArea(bin, delta);
           break;
         default:
-          throw new ArgumentException("Unknown fitting method: " + fittingMethod);
-      }
-      return decoder;
-    }
+          throw new ArgumentException("Unknown sorting method: " + sortingMethod);
+      }
+      return sorted;
+    }
+
+
+
+    #region Sorting methods    
+
+    #endregion
   }
 }

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

@@ -104 +104 @@
     <Compile Include="2D\Solution.cs" />
     <Compile Include="3D\Packer\BinPacker.cs" />
+    <Compile Include="3D\Packer\BinPackerFactory.cs" />
     <Compile Include="3D\Packer\BinPackerFirstFit.cs" />
     <Compile Include="3D\BinPacking3D.cs" />
@@ -115 +116 @@
     <Compile Include="3D\Packer\BinPackerFreeVolumeBestFit.cs" />
     <Compile Include="3D\Packer\BinPackerResidualSpaceBestFit.cs" />
-    <Compile Include="Algorithms\3D\ExtremePointAlgorithm.cs" />
     <Compile Include="3D\Instances\ThreeDInstanceDescriptor.cs" />
     <Compile Include="3D\Instances\BPPData.cs" />
     <Compile Include="3D\Instances\RandomDataDescriptor.cs" />
     <Compile Include="3D\Instances\RealWorldContainerPackingInstanceProvider.cs" />
-    <Compile Include="3D\Instances\ThreeDInstanceParser.cs" />
+    <Compile Include="3D\IntegerVectorEncoding\ThreeDInstanceParser.cs" />
     <Compile Include="3D\IntegerVectorEncoding\BottomLeftIntegerVectorDecoder.cs" />
     <Compile Include="3D\IntegerVectorEncoding\ExtremePointIntegerVectorDecoder.cs" />
@@ -132 +132 @@
     <Compile Include="3D\PackingPosition.cs" />
     <Compile Include="3D\PackingShape.cs" />
-    <Compile Include="3D\PermutationEncoding\BottomLeftPermutationDecoder.cs" />
-    <Compile Include="3D\PermutationEncoding\ResidualSpaceBestFitExtremePointPermutationDecoder.cs" />
-    <Compile Include="3D\PermutationEncoding\FreeVolumeBestFitExtremePointPermutationDecoder.cs" />
-    <Compile Include="3D\PermutationEncoding\ExtremePointPermutationDecoderBase.cs" />
-    <Compile Include="3D\PermutationEncoding\ExtremePointPermutationDecoder.cs" />
     <Compile Include="3D\PermutationEncoding\PermutationProblem.cs" />
     <Compile Include="3D\PermutationEncoding\Swap2MoveEvaluator.cs" />
@@ -142 +137 @@
     <Compile Include="3D\ProblemBase.cs" />
     <Compile Include="3D\Solution.cs" />
+    <Compile Include="3D\Sorting\PackingItemSorter.cs" />
+    <Compile Include="Algorithms\3D\ExtremePointAlgorithm.cs" />
     <Compile Include="BinPacking.cs" />
     <Compile Include="Interfaces\IPackingItem.cs">
@@ -165 +162 @@
     <None Include="Plugin.cs.frame" />
   </ItemGroup>
-  <ItemGroup />
+  <ItemGroup>
+    <Folder Include="3D\Algorithms\" />
+  </ItemGroup>
   <ItemGroup>
     <ProjectReference Include="..\..\HeuristicLab.Analysis\3.3\HeuristicLab.Analysis-3.3.csproj">

branches/2817-BinPackingSpeedup/HeuristicLab.Tests/HeuristicLab.Tests.csproj

@@ -583 +583 @@
     <Compile Include="HeuristicLab.PluginInfraStructure-3.3\InstallationManagerTest.cs" />
     <Compile Include="HeuristicLab.PluginInfraStructure-3.3\TypeExtensionsTest.cs" />
-    <Compile Include="HeuristicLab.Problems.Bin-Packing-3.3\AlgorithmTest.cs" />
+    <Compile Include="HeuristicLab.Problems.Bin-Packing-3.3\3D\AlgorithmTest.cs" />
+    <Compile Include="HeuristicLab.Problems.Bin-Packing-3.3\3D\PermutationSortingTest.cs" />
+    <Compile Include="HeuristicLab.Problems.Bin-Packing-3.3\3D\ExtremePointAlgorithmTest.cs" />
+    <Compile Include="HeuristicLab.Problems.Bin-Packing-3.3\Utils\TestUtils.cs" />
     <Compile Include="HeuristicLab.Problems.DataAnalysis-3.4\ThresholdCalculatorsTest.cs" />
     <Compile Include="HeuristicLab.Problems.DataAnalysis-3.4\OnlineCalculatorPerformanceTest.cs" />