Changeset 15454

Timestamp:

11/07/17 08:24:24 (7 years ago)

Author:

rhanghof

Message:

#2817

• Extreme point bin packing does not need the occupation layer anymore
• Changes at the fitting algorithm. Now they are packing the items as in the paper of S. Martello, D. Pisinger, D. Vigo described

Location:

branches/2817-BinPackingSpeedup

Files:

• HeuristicLab 3.3.sln (modified) (2 diffs)
• HeuristicLab.Problems.BinPacking.Views/3.3/HeuristicLab.Problems.BinPacking.Views-3.3.csproj (modified) (1 diff)
• HeuristicLab.Problems.BinPacking/3.3/3D/BinPacking3D.cs (modified) (14 diffs)
• HeuristicLab.Problems.BinPacking/3.3/3D/Decoder (added)
• HeuristicLab.Problems.BinPacking/3.3/3D/Decoder/ExtremePointPermutationDecoder.cs (added)
• HeuristicLab.Problems.BinPacking/3.3/3D/Geometry (added)
• HeuristicLab.Problems.BinPacking/3.3/3D/Geometry/Line3D.cs (added)
• HeuristicLab.Problems.BinPacking/3.3/3D/Geometry/Plane3D.cs (added)
• HeuristicLab.Problems.BinPacking/3.3/3D/Geometry/Vector3D.cs (added)
• HeuristicLab.Problems.BinPacking/3.3/3D/Instances/RandomInstanceProvider.cs (modified) (7 diffs)
• HeuristicLab.Problems.BinPacking/3.3/3D/Instances/RandomInstanceProviderWithSRand.cs (deleted)
• HeuristicLab.Problems.BinPacking/3.3/3D/Packer (added)
• HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPacker.cs (added)
• HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerFirstFit.cs (added)
• HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerFreeVolumeBestFit.cs (added)
• HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerResidualSpaceBestFit.cs (added)
• HeuristicLab.Problems.BinPacking/3.3/3D/PackingPosition.cs (modified) (1 diff)
• HeuristicLab.Problems.BinPacking/3.3/Algorithms/3D/ExtremePointAlgorithm.cs (modified) (9 diffs)
• HeuristicLab.Problems.BinPacking/3.3/BinPacking.cs (modified) (2 diffs)
• HeuristicLab.Problems.BinPacking/3.3/HeuristicLab.Problems.BinPacking-3.3.csproj (modified) (3 diffs)
• HeuristicLab.Problems.BinPacking/3.3/Random (added)
• HeuristicLab.Problems.BinPacking/3.3/Random/SRand48.cs (added)
• HeuristicLab.Tests/HeuristicLab.Problems.Bin-Packing-3.3/AlgorithmTest.cs (modified) (12 diffs)

branches/2817-BinPackingSpeedup/HeuristicLab 3.3.sln

@@ -2 +2 @@
 Microsoft Visual Studio Solution File, Format Version 12.00
 # Visual Studio 15
-VisualStudioVersion = 15.0.26430.15
+VisualStudioVersion = 15.0.26228.9
 MinimumVisualStudioVersion = 10.0.40219.1
 Project("{2150E333-8FDC-42A3-9474-1A3956D46DE8}") = "Solution Items", "Solution Items", "{96396439-A764-4022-A8D2-BE021449B8D1}"
@@ -462 +462 @@
 EndProject
 Global
+  GlobalSection(Performance) = preSolution
+    HasPerformanceSessions = true
+  EndGlobalSection
   GlobalSection(SolutionConfigurationPlatforms) = preSolution
     Debug|Any CPU = Debug|Any CPU

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

@@ -167 +167 @@
       <Name>HeuristicLab.Problems.BinPacking-3.3</Name>
       <Private>False</Private>
+    </ProjectReference>
+    <ProjectReference Include="..\..\HeuristicLab.Problems.Instances.Views\3.3\HeuristicLab.Problems.Instances.Views-3.3.csproj">
+      <Project>{B1BA398F-953F-4C3A-B07B-1E5E17A27DD9}</Project>
+      <Name>HeuristicLab.Problems.Instances.Views-3.3</Name>
+    </ProjectReference>
+    <ProjectReference Include="..\..\HeuristicLab.Problems.Instances\3.3\HeuristicLab.Problems.Instances-3.3.csproj">
+      <Project>{3540E29E-4793-49E7-8EE2-FEA7F61C3994}</Project>
+      <Name>HeuristicLab.Problems.Instances-3.3</Name>
     </ProjectReference>
   </ItemGroup>

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

@@ -27 +27 @@
 using HeuristicLab.Common;
 using HeuristicLab.Problems.BinPacking;
+using HeuristicLab.Problems.BinPacking3D.Geometry;
 
 namespace HeuristicLab.Problems.BinPacking3D {
@@ -38 +39 @@
     public BinPacking3D(PackingShape binShape)
       : base(binShape) {
-      ResidualSpace = new Dictionary<PackingPosition, Tuple<int,int,int>>();
+      ResidualSpace = new Dictionary<PackingPosition, Tuple<int, int, int>>();
       AddExtremePoint(binShape.Origin);
       InitializeOccupationLayers();
@@ -63 +64 @@
       #endregion
     }
+
+    #region New methods for bin packer class
+
+    public void AddItem(int itemID, PackingItem item, PackingPosition position) {
+      Items[itemID] = item;
+      Positions[itemID] = position;
+      ExtremePoints.Remove(position);
+      ResidualSpace.Remove(position);
+    }
+
+    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 {*/
+      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);
+      }
+      //}
+    }
+
+
+
+    /// <summary>
+    /// 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
+    /// 
+    /// Unfortunatelly this method does not support item rotation
+    /// </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) {
+      var b1 = CheckItemDimensions(item);
+      var b2 = ItemCanBePlaced(item, position);
+      var b3 = CheckStackingConstraints(item, position, stackingConstraints);
+
+      return b1 && b2 && b3;
+    }
+
+    /// <summary>
+    /// Compares the dimensions of a given item and the current bin. 
+    /// </summary>
+    /// <param name="item"></param>
+    /// <returns>Returns true if the dimensions of an given item are less or equal to the bin.</returns>
+    private bool CheckItemDimensions(PackingItem item) {
+      return BinShape.Width >= item.Width && BinShape.Height >= item.Height && BinShape.Depth >= item.Depth;
+    }
+
+    /// <summary>
+    /// Returns true if a given item can be placed in the current bin
+    /// </summary>
+    /// <param name="givenItem"></param>
+    /// <param name="givenItemPosition"></param>
+    /// <returns></returns>
+    private bool ItemCanBePlaced(PackingItem givenItem, PackingPosition givenItemPosition) {
+      // Check if the boundings of the bin would injured
+      if (givenItemPosition.X + givenItem.Width > BinShape.Width ||
+          givenItemPosition.Y + givenItem.Height > BinShape.Height ||
+          givenItemPosition.Z + givenItem.Depth > BinShape.Depth) {
+        return false;
+      }
+
+      //if the given item collides with any other item, it can not be placed
+      foreach (var item in Items) {
+        if (ItemsCollides(new Tuple<PackingPosition, PackingItem>(Positions[item.Key], item.Value),
+                          new Tuple<PackingPosition, PackingItem>(givenItemPosition, givenItem))) {
+          return false;
+        }
+      }
+      return true;     
+    }
+
+    /// <summary>
+    /// Checks if two given items in a space collides
+    /// </summary>
+    /// <param name="t1"></param>
+    /// <param name="t2"></param>
+    /// <returns></returns>
+    bool ItemsCollides(Tuple<PackingPosition, PackingItem> t1, Tuple<PackingPosition, PackingItem> t2) {
+      var position1 = t1.Item1;
+      var item1 = t1.Item2;
+      var position2 = t2.Item1;
+      var item2 = t2.Item2;
+      var cx = (position2.X == position1.X) || (position2.X < position1.X && position2.X + item2.Width > position1.X) || (position2.X > position1.X && position1.X + item1.Width > position2.X);
+      var cy = (position2.Y == position1.Y) || (position2.Y < position1.Y && position2.Y + item2.Height > position1.Y) || (position2.Y > position1.Y && position1.Y + item1.Height > position2.Y);
+      var cz = (position2.Z == position1.Z) || (position2.Z < position1.Z && position2.Z + item2.Depth > position1.Z) || (position2.Z > position1.Z && position1.Z + item1.Depth > position2.Z);
+      return cx && cy && cz;
+    }
+
+    /// <summary>
+    /// Checks the stacking constraints. This method depends that the given item can be placed at this position
+    /// </summary>
+    /// <param name="item"></param>
+    /// <param name="position"></param>
+    /// <param name="stackingConstraints"></param>
+    /// <returns></returns>
+    private bool CheckStackingConstraints(PackingItem item, PackingPosition position, bool stackingConstraints) {
+      if (position.Y == 0 || !stackingConstraints && HasOnePointWithAnItemBelow(item, position)) {
+        return true;
+      }
+
+      return IsStaticStable(item, position) && IsWeightSupported(item, position);
+    }
+
+
+    /// <summary>
+    /// Checks if a given item has any point lieing on another item.
+    /// </summary>
+    /// <param name="item"></param>
+    /// <param name="position"></param>
+    /// <returns></returns>
+    public bool HasOnePointWithAnItemBelow(PackingItem item, PackingPosition position) {
+      bool p1, p2, p3, p4;
+      PointsLiesOnAnItems(item, position, out p1, out p2, out p3, out p4);
+
+      return p1 || p2 || p3 || p4;
+    }
+
+    /// <summary>
+    /// Checks if a given item is static stable.
+    /// A item is static stable if all edges have an object below.
+    /// </summary>
+    /// <param name="item"></param>
+    /// <param name="position"></param>
+    /// <returns></returns>
+    public override bool IsStaticStable(PackingItem item, PackingPosition position) {
+      bool p1, p2, p3, p4;
+      PointsLiesOnAnItems(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.
+    /// p1 ... p3 represents one point on the bottom side of an given item.
+    /// +---------+
+    /// |p1     p2|
+    /// |         |
+    /// |p4     p3|
+    /// +---------+
+    /// </summary>
+    /// <param name="item">Given item</param>
+    /// <param name="position">Given item position</param>
+    /// <param name="p1"></param>
+    /// <param name="p2"></param>
+    /// <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) {
+      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP1;
+      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP2;
+      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP3;
+      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP4;
+
+      GetItemsUnderItemWithContact(item, position, out itemsP1, out itemsP2, out itemsP3, out itemsP4);
+
+      p1 = itemsP1.Where(x => position.X < x.Item1.X + x.Item2.Width && position.Z < x.Item1.Z + x.Item2.Depth).Any();
+      p2 = itemsP2.Where(x => position.X + item.Width > x.Item1.X && position.Z < x.Item1.Z + x.Item2.Depth).Any();
+      p3 = itemsP3.Where(x => position.X + item.Width > x.Item1.X && position.Z + item.Depth > x.Item1.Z).Any();
+      p4 = itemsP4.Where(x => position.X < x.Item1.X + x.Item2.Width && position.Z + item.Depth > x.Item1.Z).Any();
+    }
+
+
+    /// <summary>
+    /// 
+    /// </summary>
+    /// <param name="item"></param>
+    /// <param name="position"></param>
+    /// <param name="itemsP1"></param>
+    /// <param name="itemsP2"></param>
+    /// <param name="itemsP3"></param>
+    /// <param name="itemsP4"></param>
+    private void GetItemsUnderItemWithContact(PackingItem item, PackingPosition position,
+                                   out IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP1,
+                                   out IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP2,
+                                   out IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP3,
+                                   out IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP4) {
+      itemsP1 = GetItemsBelowForPosition(new PackingPosition(0, position.X, position.Y, position.Z, false));
+      itemsP2 = GetItemsBelowForPosition(new PackingPosition(0, position.X + item.Width - 1, position.Y, position.Z, false));
+      itemsP3 = GetItemsBelowForPosition(new PackingPosition(0, position.X, position.Y, position.Z + item.Depth - 1, false));
+      itemsP4 = GetItemsBelowForPosition(new PackingPosition(0, position.X + item.Width - 1, position.Y, position.Z + item.Depth - 1, false));
+
+    }
+
+    /// <summary>
+    /// Returns a collection of items which are below a given point. 
+    /// The top side of every item is at the same level as the Y-coordinate of the given position.
+    /// </summary>
+    /// <param name="position"></param>
+    /// <returns></returns>
+    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBelowForPosition(PackingPosition position) {
+      return GetItemsBelow(position).Where(x => (x.Item1.Y + x.Item2.Height) == position.Y);
+    }
+
+
+    /// <summary>
+    /// Checks if a given the weight of an given item is supportet by the items below.
+    /// </summary>
+    /// <param name="item"></param>
+    /// <param name="position"></param>
+    /// <returns></returns>
+    public bool IsWeightSupported(PackingItem item, PackingPosition position) {
+      if (position.Y == 0) {
+        return true;
+      }
+      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP1;
+      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP2;
+      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP3;
+      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP4;
+
+      GetItemsUnderItemWithContact(item, position, out itemsP1, out itemsP2, out itemsP3, out itemsP4);
+
+      return itemsP1.Where(x => x.Item2.SupportsStacking(item)).Any() &&
+        itemsP2.Where(x => x.Item2.SupportsStacking(item)).Any() &&
+        itemsP3.Where(x => x.Item2.SupportsStacking(item)).Any() &&
+        itemsP4.Where(x => x.Item2.SupportsStacking(item)).Any();
+    }
+
+
+
+    #endregion
 
     public override void PackItem(int itemID, PackingItem item, PackingPosition position) {
@@ -83 +317 @@
     }
 
+
+
     protected override void GenerateNewExtremePointsForNewItem(PackingItem newItem, PackingPosition position) {
       int newWidth = position.Rotated ? newItem.Depth : newItem.Width;
@@ -168 +404 @@
     }
 
+
     private bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, Tuple<int, int, int> residualSpace) {
       var eps = ExtremePoints.Where(x => !pos.Equals(x) && pos.IsInside(x, ResidualSpace[x]));
@@ -204 +441 @@
 
     #region Projections
-        
+
     private Vector3D ProjectBackward(Vector3D pos) {
       var line = new Line3D(pos, new Vector3D(0, 0, -1));
@@ -268 +505 @@
     #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));
@@ -298 +539 @@
         .Select(x => Tuple.Create(x.Position, x.Item));
     }
+
+    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBelow(PackingPosition pos) {
+      var line = new Line3D(pos, new Vector3D(0, 1, 0));
+      return Items.Select(x => new {
+        Item = x.Value,
+        Position = Positions[x.Key],
+        Intersection = line.Intersect(new Plane3D(Positions[x.Key], x.Value, Side.Top))
+      }).Where(x => x.Intersection != null && x.Intersection.Y <= pos.Y)
+        .Select(x => Tuple.Create(x.Position, x.Item));
+    }
+
+    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBehind(PackingPosition pos) {
+      var line = new Line3D(pos, new Vector3D(0, 0, 1));
+      return Items.Select(x => new {
+        Item = x.Value,
+        Position = Positions[x.Key],
+        Intersection = line.Intersect(new Plane3D(Positions[x.Key], x.Value, Side.Front))
+      }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
+        .Select(x => Tuple.Create(x.Position, x.Item));
+    }
+
+    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsOnLeft(PackingPosition pos) {
+      var line = new Line3D(pos, new Vector3D(1, 0, 0));
+      return Items.Select(x => new {
+        Item = x.Value,
+        Position = Positions[x.Key],
+        Intersection = line.Intersect(new Plane3D(Positions[x.Key], x.Value, Side.Right))
+      }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
+        .Select(x => Tuple.Create(x.Position, x.Item));
+    }
+
     #endregion
+
+
 
     public override PackingPosition FindExtremePointForItem(PackingItem item, bool rotated, bool stackingConstraints) {
@@ -316 +590 @@
     }
 
-    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)));
-    }
+  
 
     #region Sliding based packing    
@@ -425 +694 @@
       return shortestSide;
     }
-    public override bool IsStaticStable(PackingItem item, PackingPosition position) {
-      //Static stability is given, if item is placed on the ground
-      if (position.Y == 0)
-        return true;
-
-      if (IsPointOccupied(new PackingPosition(0, position.X, position.Y - 1, position.Z))
-        && IsPointOccupied(new PackingPosition(0, position.X + item.Width - 1, position.Y - 1, position.Z))
-        && IsPointOccupied(new PackingPosition(0, position.X, position.Y - 1, position.Z + item.Depth - 1))
-        && IsPointOccupied(new PackingPosition(0, position.X + item.Width - 1, position.Y - 1, position.Z + item.Depth - 1)))
-        return true;
-
-      return false;
-    }
-
-    public bool IsSupportedByAtLeastOnePoint(PackingItem item, PackingPosition position) {
-      if (position.Y == 0)
-        return true;
-
-      int y = position.Y - 1;
-      for (int x = position.X; x < position.X + item.Width; x++)
-        for (int z = position.Z; z < position.Z + item.Depth; z++)
-          if (IsPointOccupied(new PackingPosition(0, x, y, z)))
-            return true;
-
-      return false;
-    }
-    public bool IsWeightSupported(PackingItem item, PackingPosition ep) {
-      if (ep.Y == 0)
-        return true;
-
-      if (Items[PointOccupation(new PackingPosition(0, ep.X, ep.Y - 1, ep.Z))].SupportsStacking(item)
-        && Items[PointOccupation(new PackingPosition(0, ep.X + item.Width - 1, ep.Y - 1, ep.Z))].SupportsStacking(item)
-        && Items[PointOccupation(new PackingPosition(0, ep.X, ep.Y - 1, ep.Z + item.Depth - 1))].SupportsStacking(item)
-        && Items[PointOccupation(new PackingPosition(0, ep.X + item.Width - 1, ep.Y - 1, ep.Z + item.Depth - 1))].SupportsStacking(item))
-        return true;
-
-      return false;
-    }
+    
 
     protected override void InitializeOccupationLayers() {
@@ -488 +720 @@
       return result;
     }
-    
+
     public void UpdateResidualSpace(PackingItem item, PackingPosition pos) {
       foreach (var ep in ExtremePoints.ToList()) {
@@ -509 +741 @@
           }
         }
-        if (ep.Z <= pos.Z && 
+
+        if (ep.Z <= pos.Z &&
             ep.Y >= pos.Y && ep.Y < pos.Y + item.Height &&
             ep.X >= pos.X && ep.X < pos.X + width) {
@@ -517 +750 @@
           changed = true;
         }
+
         if (changed) {
           if (IsNonZero(rs) && !IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep), rs)) {
@@ -529 +763 @@
     }
 
-    #region Helper classes for vector math
-    private class Vector3D {
-      public int X;
-      public int Y;
-      public int Z;
-      public Vector3D() { }
-      public Vector3D(int x, int y, int z) {
-        X = x;
-        Y = y;
-        Z = z;
-      }
-      public Vector3D(PackingPosition pos) {
-        X = pos.X;
-        Y = pos.Y;
-        Z = pos.Z;
-      }
-      public static Vector3D AlongX(Vector3D pos, PackingItem item) {
-        return new Vector3D(
-          pos.X + item.Width,
-          pos.Y,
-          pos.Z
-        );
-      }
-      public static Vector3D AlongY(Vector3D pos, PackingItem item) {
-        return new Vector3D(
-          pos.X,
-          pos.Y + item.Height,
-          pos.Z
-        );
-      }
-      public static Vector3D AlongZ(Vector3D pos, PackingItem item) {
-        return new Vector3D(
-          pos.X,
-          pos.Y,
-          pos.Z + item.Depth
-        );
-      }
-      public static Vector3D AlongX(PackingPosition pos, PackingItem item) {
-        return new Vector3D(
-          pos.X + item.Width,
-          pos.Y,
-          pos.Z
-        );
-      }
-      public static Vector3D AlongY(PackingPosition pos, PackingItem item) {
-        return new Vector3D(
-          pos.X,
-          pos.Y + item.Height,
-          pos.Z
-        );
-      }
-      public static Vector3D AlongZ(PackingPosition pos, PackingItem item) {
-        return new Vector3D(
-          pos.X,
-          pos.Y,
-          pos.Z + item.Depth
-        );
-      }
-
-      public Vector3D Cross(Vector3D b) {
-        return new Vector3D(
-          Y * b.Z - Z * b.Y,
-          -X * b.Z + Z * b.X,
-          X * b.Y - Y * b.X
-        );
-      }
-
-      public bool IsInside(PackingPosition pos, Tuple<int, int, int> rs) {
-        return X >= pos.X && X < pos.X + rs.Item1
-          && Y >= pos.Y && Y < pos.Y + rs.Item2
-          && Z >= pos.Z && Z < pos.Z + rs.Item3;
-      }
-
-      public static int operator *(Vector3D a, Vector3D b) {
-        return a.X * b.X + a.Y * b.Y + a.Z * b.Z;
-      }
-      public static Vector3D operator *(int a, Vector3D b) {
-        return new Vector3D(a * b.X, a * b.Y, a * b.Z);
-      }
-      public static Vector3D operator *(Vector3D a, int b) {
-        return new Vector3D(a.X * b, a.Y * b, a.Z * b);
-      }
-      public static Vector3D operator +(Vector3D a, Vector3D b) {
-        return new Vector3D(a.X + b.X, a.Y + b.Y, a.Z + b.Z);
-      }
-      public static Vector3D operator -(Vector3D a, Vector3D b) {
-        return new Vector3D(a.X - b.X, a.Y - b.Y, a.Z - b.Z);
-      }
-
-      public override bool Equals(object obj) {
-        var packPos = obj as PackingPosition;
-        if (packPos != null) {
-          return X == packPos.X && Y == packPos.Y && Z == packPos.Z;
-        }
-        var vec = obj as Vector3D;
-        if (vec != null) {
-          return X == vec.X && Y == vec.Y && Z == vec.Z;
-        }
-        return false;
-      }
-    }
-
-    // A line is given as a point and a directing vector
-    private class Line3D {
-      public Vector3D Point;
-      public Vector3D Direction;
-
-      public Line3D(Vector3D point, Vector3D direction) {
-        Point = point;
-        Direction = direction;
-      }
-      public Line3D(PackingPosition position, Vector3D direction) {
-        Point = new Vector3D(position);
-        Direction = direction;
-      }
-
-      public bool Intersects(Plane3D plane) {
-        return plane.Intersects(this);
-      }
-
-      public Vector3D Intersect(Plane3D plane) {
-        return plane.Intersect(this);
-      }
-    }
-
-    private enum Side { Top, Left, Bottom, Right, Front, Back }
-    // A plane is given as a point and two directing vectors
-    private class Plane3D {
-      public Vector3D Point { get; private set; }
-      public Vector3D Direction1 { get; private set; }
-      public Vector3D Direction2 { get; private set; }
-      public Vector3D Normal { get; private set; }
-      private int rhs;
-
-      public Plane3D(PackingShape bin, Side side) {
-        switch (side) {
-          case Side.Top: // ZX plane
-            Point = new Vector3D(0, bin.Height, 0);
-            Direction1 = new Vector3D(0, 0, bin.Depth);
-            Direction2 = new Vector3D(bin.Width, 0, 0);
-            break;
-          case Side.Left: // ZY plane
-            Point = new Vector3D(0, 0, 0);
-            Direction1 = new Vector3D(0, 0, bin.Depth);
-            Direction2 = new Vector3D(0, bin.Height, 0);
-            break;
-          case Side.Bottom: // XZ plane
-            Point = new Vector3D(0, 0, 0);
-            Direction1 = new Vector3D(bin.Width, 0, 0);
-            Direction2 = new Vector3D(0, 0, bin.Depth);
-            break;
-          case Side.Right: // YZ plane
-            Point = new Vector3D(bin.Width, 0, 0);
-            Direction1 = new Vector3D(0, bin.Height, 0);
-            Direction2 = new Vector3D(0, 0, bin.Depth);
-            break;
-          case Side.Front: // XY plane
-            Point = new Vector3D(0, 0, bin.Depth);
-            Direction1 = new Vector3D(bin.Width, 0, 0);
-            Direction2 = new Vector3D(0, bin.Height, 0);
-            break;
-          case Side.Back: // YX plane
-            Point = new Vector3D(0, 0, 0);
-            Direction1 = new Vector3D(0, bin.Height, 0);
-            Direction2 = new Vector3D(bin.Width, 0, 0);
-            break;
-        }
-        Normal = Direction1.Cross(Direction2);
-        rhs = 0;
-      }
-
-      public Plane3D(PackingPosition pos, PackingItem item, Side side) {
-        // the directing vectors are chosen such that normal always points outside the packing item
-        switch (side) {
-          case Side.Top: // ZX plane
-            Point = new Vector3D(pos.X, pos.Y + item.Height, pos.Z);
-            Direction1 = new Vector3D(0, 0, pos.Rotated ? item.Width : item.Depth);
-            Direction2 = new Vector3D(pos.Rotated ? item.Depth : item.Width, 0, 0);
-            break;
-          case Side.Left: // ZY plane
-            Point = new Vector3D(pos.X, pos.Y, pos.Z);
-            Direction1 = new Vector3D(0, 0, pos.Rotated ? item.Width : item.Depth);
-            Direction2 = new Vector3D(0, item.Height, 0);
-            break;
-          case Side.Bottom: // XZ plane
-            Point = new Vector3D(pos.X, pos.Y, pos.Z);
-            Direction1 = new Vector3D(pos.Rotated ? item.Depth : item.Width, 0, 0);
-            Direction2 = new Vector3D(0, 0, pos.Rotated ? item.Width : item.Depth);
-            break;
-          case Side.Right: // YZ plane
-            Point = new Vector3D(pos.X + (pos.Rotated ? item.Depth : item.Width), pos.Y, pos.Z);
-            Direction1 = new Vector3D(0, item.Height, 0);
-            Direction2 = new Vector3D(0, 0, pos.Rotated ? item.Width : item.Depth);
-            break;
-          case Side.Front: // XY plane
-            Point = new Vector3D(pos.X, pos.Y, pos.Z + (pos.Rotated ? item.Width : item.Depth));
-            Direction1 = new Vector3D(pos.Rotated ? item.Depth : item.Width, 0, 0);
-            Direction2 = new Vector3D(0, item.Height, 0);
-            break;
-          case Side.Back: // YX plane
-            Point = new Vector3D(pos.X, pos.Y, pos.Z);
-            Direction1 = new Vector3D(0, item.Height, 0);
-            Direction2 = new Vector3D(pos.Rotated ? item.Depth : item.Width, 0, 0);
-            break;
-        }
-        Normal = Direction1.Cross(Direction2);
-        rhs = Normal.X * Point.X + Normal.Y * Point.Y + Normal.Z * Point.Z;
-      }
-
-      public bool IsElementOf(Vector3D point) {
-        return Normal.X * point.X + Normal.Y * point.Y + Normal.Z * point.Z == rhs;
-      }
-
-      public bool Intersects(Line3D line) {
-        return Intersect(line) != null;
-      }
-
-      public Vector3D Intersect(Line3D line) {
-        var denom = Normal * line.Direction;
-        if (denom == 0) {
-          // dir is perpendicular to the normal vector of the plane
-          // this means they intersect if p1 is element of the plane
-          // also the plane does not stretch infinitely, but is bound
-          // to the parallelogram spanned by the point and the two
-          // directing vectors
-          if (IsElementOf(line.Point) && IsWithinDirectionalVectors(line.Point))
-            return line.Point;
-          else return null;
-        }
-        var intersect = line.Point + ((Normal * (Point - line.Point)) / denom) * line.Direction;
-        if (IsWithinDirectionalVectors(intersect)) return intersect;
-        return null;
-      }
-
-      public bool IsWithinDirectionalVectors(Vector3D point) {
-        return point.X >= Point.X && (Direction1.X + Direction2.X == 0 || (point.X < Point.X + Direction1.X || point.X < Point.X + Direction2.X))
-            && point.Y >= Point.Y && (Direction1.Y + Direction2.Y == 0 || (point.Y < Point.Y + Direction1.Y || point.Y < Point.Y + Direction2.Y))
-            && point.Z >= Point.Z && (Direction1.Z + Direction2.Z == 0 || (point.Z < Point.Z + Direction1.Z || point.Z < Point.Z + Direction2.Z));
-      }
-    }
-    #endregion
+
   }
 }

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

@@ -26 +26 @@
 using System.IO;
 using System.Linq;
+using System.Reflection;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
 using HeuristicLab.Problems.Instances;
 using HeuristicLab.Random;
-
-namespace HeuristicLab.Problems.BinPacking3D {
+using HeuristicLab.Problems.BinPacking.Random;
+
+namespace HeuristicLab.Problems.BinPacking3D.Instances {
   // make sure that for each class we have a separate entry in the problem instance providers
+
   public class RandomInstanceClass1Provider : RandomInstanceProvider {
-    public RandomInstanceClass1Provider() : base() { @class = 1; binWidth = binHeight = binDepth = 100; }
-  }
+    public RandomInstanceClass1Provider() : base(new SRand48()) { @class = 1; binWidth = binHeight = binDepth = 100; }
+
+  }
+
   public class RandomInstanceClass2Provider : RandomInstanceProvider {
-    public RandomInstanceClass2Provider() : base() { @class = 2; binWidth = binHeight = binDepth = 100; }
+    public RandomInstanceClass2Provider() : base(new SRand48()) { @class = 2; binWidth = binHeight = binDepth = 100; }
+
   }
   public class RandomInstanceClass3Provider : RandomInstanceProvider {
-    public RandomInstanceClass3Provider() : base() { @class = 3; binWidth = binHeight = binDepth = 100; }
+    public RandomInstanceClass3Provider() : base(new SRand48()) { @class = 3; binWidth = binHeight = binDepth = 100; }
+
   }
   public class RandomInstanceClass4Provider : RandomInstanceProvider {
-    public RandomInstanceClass4Provider() : base() { @class = 4; binWidth = binHeight = binDepth = 100; }
+    public RandomInstanceClass4Provider() : base(new SRand48()) { @class = 4; binWidth = binHeight = binDepth = 100; }
+
   }
   public class RandomInstanceClass5Provider : RandomInstanceProvider {
-    public RandomInstanceClass5Provider() : base() { @class = 5; binWidth = binHeight = binDepth = 100; }
+    public RandomInstanceClass5Provider() : base(new SRand48()) { @class = 5; binWidth = binHeight = binDepth = 100; }
+
   }
 
   public class RandomInstanceClass6Provider : RandomInstanceProvider {
-    public RandomInstanceClass6Provider() : base() {
+    public RandomInstanceClass6Provider() : base(new SRand48()) {
       @class = 6;
       binWidth = binHeight = binDepth = 10;
     }
     protected override void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
-      w = rand.Next(1, 11);
-      h = rand.Next(1, 11);
-      d = rand.Next(1, 11);
+      w = rand.Next(1, 10);
+      h = rand.Next(1, 10);
+      d = rand.Next(1, 10);
     }
   }
   public class RandomInstanceClass7Provider : RandomInstanceProvider {
-    public RandomInstanceClass7Provider() : base() {
+    public RandomInstanceClass7Provider() : base(new SRand48()) {
       @class = 7;
       binWidth = binHeight = binDepth = 40;
     }
     protected override void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
-      w = rand.Next(1, 36);
-      h = rand.Next(1, 36);
-      d = rand.Next(1, 36);
+      w = rand.Next(1, 35);
+      h = rand.Next(1, 35);
+      d = rand.Next(1, 35);
     }
   }
   public class RandomInstanceClass8Provider : RandomInstanceProvider {
-    public RandomInstanceClass8Provider() : base() {
+    public RandomInstanceClass8Provider() : base(new SRand48()) {
       @class = 8;
       binWidth = binHeight = binDepth = 100;
     }
     protected override void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
-      w = rand.Next(1, 101);
-      h = rand.Next(1, 101);
-      d = rand.Next(1, 101);
+      w = rand.Next(1, 100);
+      h = rand.Next(1, 100);
+      d = rand.Next(1, 100);
     }
   }
@@ -88 +97 @@
   public abstract class RandomInstanceProvider : ProblemInstanceProvider<BPPData>, IProblemInstanceProvider<BPPData> {
 
+    /// <summary>
+    /// Number of created test items. This items are used for packing them into the bin
+    /// </summary>
+    private readonly int[] _numberOfGeneratedTestItems = new int[] { 10, 15, 20, 25, 30, 35, 40, 45, 50, 60, 70, 80, 90, 100, 150, 200 };
+
+    /// <summary>
+    /// Number of instance for which should be created for each instance
+    /// </summary>
+    private readonly int _numberOfGeneratedInstances;
+
+    /// <summary>
+    /// Random generator for creating random packing items.
+    /// </summary>
+    private readonly IRandom _randomGenerator;
 
 
@@ -93 +116 @@
     protected int binWidth, binHeight, binDepth;
 
+    #region Common information for displaying on the ui
+
     public override string Name {
       get { return string.Format("Martello, Pisinger, Vigo (class={0})", @class); }
@@ -109 +134 @@
     }
 
-    public RandomInstanceProvider() : base() { }
-
+    #endregion
+
+
+    public RandomInstanceProvider(IRandom randomGenerator, int numberOfGeneratedInstances = 10, int[] numberOfGeneratedTestItems = null) : base() {
+      _numberOfGeneratedInstances = numberOfGeneratedInstances;
+      if (numberOfGeneratedTestItems != null) {
+        _numberOfGeneratedTestItems = numberOfGeneratedTestItems;
+      }
+      _randomGenerator = randomGenerator;
+    }
+
+
+    /// <summary>
+    /// Returns a collection of data descriptors. Each descriptor contains the seed for the random generator.
+    /// </summary>
+    /// <returns></returns>
     public override IEnumerable<IDataDescriptor> GetDataDescriptors() {
       // 10 classes
-      var rand = new MersenneTwister(1234); // fixed seed to makes sure that instances are always the same
-      foreach (int numItems in new int[] { 10, 15, 20, 25, 30, 35, 40, 45, 50, 60, 70, 80, 90 }) {
-        // get class parameters
-        // generate 30 different instances for each class
-        foreach (int instance in Enumerable.Range(1, 30)) {
+      foreach (int numItems in _numberOfGeneratedTestItems) {
+        for (int instance = 1; instance <= _numberOfGeneratedInstances; instance++) {
           string name = string.Format("n={0}-id={1:00} (class={2})", numItems, instance, @class);
-          var dd = new RandomDataDescriptor(name, name, numItems, @class, seed: rand.Next());
-          yield return dd;
+          /* As in the test programm of Silvano Martello, David Pisinger, Daniele Vigo given, 
+           * the seed of the instance provider will be calculated by adding the number of generated items and teh instance number.
+           * This guarantees that the instances will always be the same
+           */
+          yield return new RandomDataDescriptor(name, name, numItems, @class, seed: numItems + instance);
         }
       }
     }
+
 
     public override BPPData LoadData(IDataDescriptor dd) {
       var randDd = dd as RandomDataDescriptor;
-      if (randDd == null)
+      if (randDd == null) {
         throw new NotSupportedException("Cannot load data descriptor " + dd);
+      }
 
       var data = new BPPData() {
@@ -134 +175 @@
         Items = new PackingItem[randDd.NumItems]
       };
-      var instanceRand = new MersenneTwister((uint)randDd.Seed);
+      _randomGenerator.Reset(randDd.Seed);
       for (int i = 0; i < randDd.NumItems; i++) {
         int w, h, d;
-        SampleItemParameters(instanceRand, out w, out h, out d);
+        SampleItemParameters(_randomGenerator, out w, out h, out d);
         data.Items[i] = new PackingItem(w, h, d, data.BinShape);
       }
@@ -143 +184 @@
     }
 
-    // default implementation for class 1 .. 5
+
+    /// <summary>
+    /// Generates the dimensions for a item by using the given random generator
+    /// </summary>
+    /// <param name="rand">Given random generator</param>
+    /// <param name="w">Calculated width of the item</param>
+    /// <param name="h">Calculated height of the item</param>
+    /// <param name="d">Calculated depth of the item</param>
     protected virtual void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
-      // for classes 1 - 5
       Contract.Assert(@class >= 1 && @class <= 5);
-      var weights = new double[] { 0.1, 0.1, 0.1, 0.1, 0.1 };
+      /*var weights = new double[] { 0.1, 0.1, 0.1, 0.1, 0.1 };
       weights[@class - 1] = 0.6;
       var type = Enumerable.Range(1, 5).SampleProportional(rand, 1, weights).First();
-
-      int minW, maxW;
-      int minH, maxH;
-      int minD, maxD;
-      GetItemParameters(type, rand, binWidth, binHeight, binDepth,
-        out minW, out maxW, out minH, out maxH, out minD, out maxD);
-
-      w = rand.Next(minW, maxW + 1);
-      h = rand.Next(minH, maxH + 1);
-      d = rand.Next(minD, maxD + 1);
-    }
-
-    private void GetItemParameters(int type, IRandom rand,
-      int w, int h, int d,
-      out int minW, out int maxW, out int minH, out int maxH, out int minD, out int maxD) {
+      */
+
+      // as by Martello and Vigo
+      int type = @class;
+      if (type <= 5) {
+        var t = rand.Next(1, 10);
+        if (t <= 5) {
+          type = t;
+        }
+      }
+
       switch (type) {
-        case 1: {
-            minW = 1;
-            maxW = w / 2; // integer division on purpose (see paper)
-            minH = h * 2 / 3;
-            maxH = h;
-            minD = d * 2 / 3;
-            maxD = d;
-            break;
-          }
-        case 2: {
-            minW = w * 2 / 3;
-            maxW = w;
-            minH = 1;
-            maxH = h / 2;
-            minD = d * 2 / 3;
-            maxD = d;
-            break;
-          }
-        case 3: {
-            minW = w * 2 / 3;
-            maxW = w;
-            minH = h * 2 / 3;
-            maxH = h;
-            minD = 1;
-            maxD = d / 2;
-            break;
-          }
-        case 4: {
-            minW = w / 2;
-            maxW = w;
-            minH = h / 2;
-            maxH = h;
-            minD = d / 2;
-            maxD = d;
-            break;
-          }
-        case 5: {
-            minW = 1;
-            maxW = w / 2;
-            minH = 1;
-            maxH = h / 2;
-            minD = 1;
-            maxD = d / 2;
-            break;
-          }
-        default: {
-            throw new InvalidProgramException();
-          }
-      }
-    }
+        case 1:
+          CreateInstanceDimensionsType1(rand, out w, out h, out d);
+          break;
+        case 2:
+          CreateInstanceDimensionsType2(rand, out w, out h, out d);
+          break;
+        case 3:
+          CreateInstanceDimensionsType3(rand, out w, out h, out d);
+          break;
+        case 4:
+          CreateInstanceDimensionsType4(rand, out w, out h, out d);
+          break;
+        case 5:
+          CreateInstanceDimensionsType5(rand, out w, out h, out d);
+          break;
+        default:
+          throw new InvalidProgramException();
+      }
+    }
+
+
+    #region Instance dimensions generators for type 1 - 5
+    private void CreateInstanceDimensionsType1(IRandom rand, out int w, out int h, out int d) {
+      w = rand.Next(1, binWidth / 2);
+      h = rand.Next((binHeight * 2) / 3, binHeight);
+      d = rand.Next((binDepth * 2) / 3, binDepth);
+    }
+
+    private void CreateInstanceDimensionsType2(IRandom rand, out int w, out int h, out int d) {
+      w = rand.Next(((binWidth * 2) / 3), binWidth);
+      h = rand.Next(1, binHeight / 2);
+      d = rand.Next(((binDepth * 2) / 3), binDepth);
+    }
+
+    private void CreateInstanceDimensionsType3(IRandom rand, out int w, out int h, out int d) {
+      w = rand.Next(((binWidth * 2) / 3), binWidth);
+      h = rand.Next(((binHeight * 2) / 3), binHeight);
+      d = rand.Next(1, binDepth / 2);
+    }
+    private void CreateInstanceDimensionsType4(IRandom rand, out int w, out int h, out int d) {
+      w = rand.Next(binWidth / 2, binWidth);
+      h = rand.Next(binHeight / 2, binHeight);
+      d = rand.Next(binDepth / 2, binDepth);
+    }
+    private void CreateInstanceDimensionsType5(IRandom rand, out int w, out int h, out int d) {
+      w = rand.Next(1, binWidth / 2);
+      h = rand.Next(1, binHeight / 2);
+      d = rand.Next(1, binDepth / 2);
+    }
+
+    #endregion
+
+
 
     public override bool CanImportData {
@@ -242 +288 @@
           else
             writer.WriteLine("{0,-5} {1,-5} {2,-5}", instance.Items[i].Width, instance.Items[i].Height, instance.Items[i].Depth);
-
         }
         writer.Flush();
       }
     }
-
   }
 }

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

@@ -103 +103 @@
     #region IComparable<PackingPosition> Members
 
+    /// <summary>
+    /// Compares two packing positions by their coordinates. 
+    /// The order of comparing is z -> x -> y.
+    /// </summary>
+    /// <param name="other"></param>
+    /// <returns></returns>
     public int CompareTo(PackingPosition other) {
       int result = Z.CompareTo(other.Z);

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

@@ -32 +32 @@
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Problems.BinPacking3D.Packer;
 
 namespace HeuristicLab.Problems.BinPacking3D {
-  
+
   public enum SortingMethod { All, Given, VolumeHeight, HeightVolume, AreaHeight, HeightArea, ClusteredAreaHeight, ClusteredHeightArea }
   public enum FittingMethod { All, FirstFit, ResidualSpaceBestFit, FreeVolumeBestFit }
@@ -86 +87 @@
       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)));
-      
+
       Problem = new PermutationProblem();
     }
@@ -93 +94 @@
       return new ExtremePointAlgorithm(this, cloner);
     }
-    
+
     [StorableHook(HookType.AfterDeserialization)]
     private void AfterDeserialization() {
     }
 
+    /// <summary>
+    /// Runs the extreme point algorithm and adds the results to the property <see cref="Result"/>
+    /// </summary>
+    /// <param name="token"></param>
     protected override void Run(CancellationToken token) {
       var items = Problem.Items;
@@ -109 +114 @@
         fitting = Enum.GetValues(typeof(FittingMethod)).Cast<FittingMethod>().Where(x => x != FittingMethod.All).ToArray();
       }
+
+      //
       var result = GetBest(bin, items, sorting, fitting, token);
-      if (result == null) throw new InvalidOperationException("No result obtained!");
-
-      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)));
+      if (result == null) {
+        throw new InvalidOperationException("No result obtained!");
+      }
+
+      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();
@@ -128 +133 @@
         new PercentValue(Math.Round(binUtil.Evaluate(result.Item1), 3))));
 
-      if (result.Item3.HasValue && sorting.Length > 1)
+      if (result.Item3.HasValue && sorting.Length > 1) {
         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)
+      }
+
+      if (result.Item4.HasValue && fitting.Length > 1) {
         Results.Add(new Result("Best Fitting Method",
           "The fitting method that found the best solution",
           new EnumValue<FittingMethod>(result.Item4.Value)));
+      }
     }
 
@@ -146 +154 @@
         foreach (var sort in sortings) {
           var result = Optimize(bin, items, sort, fit, DeltaParameter.Value.Value, Problem.UseStackingConstraints, Problem.SolutionEvaluator, token);
-          if (double.IsNaN(result.Item2) || double.IsInfinity(result.Item2)) continue;
-          if (double.IsNaN(best)
-            || Problem.Maximization && result.Item2 > best
-            || !Problem.Maximization && result.Item2 < best) {
+          if (double.IsNaN(result.Item2) || double.IsInfinity(result.Item2)) {
+            continue;
+          }
+
+          if (double.IsNaN(best) || Problem.Maximization && result.Item2 > best || !Problem.Maximization && result.Item2 < best) {
             bestSolution = result.Item1;
             best = result.Item2;
@@ -155 +164 @@
             bestFitting = fit;
           }
-          if (token.IsCancellationRequested) return Tuple.Create(bestSolution, best, bestSorting, bestFitting);
+          if (token.IsCancellationRequested) {
+            return Tuple.Create(bestSolution, best, bestSorting, bestFitting);
+          }
         }
       }
-      if (double.IsNaN(best)) return null;
+      if (double.IsNaN(best)) {
+        return null;
+      }
       return Tuple.Create(bestSolution, best, bestSorting, bestFitting);
     }
 
     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);
+      }
+      
+
+      
+    }
+
+
+
+    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;
+    }
+
+    /// <summary>
+    /// Returns a new permutation of the given items depending on the sorting method
+    /// </summary>
+    /// <param name="bin"></param>
+    /// <param name="items"></param>
+    /// <param name="sortingMethod"></param>
+    /// <param name="delta"></param>
+    /// <returns></returns>
+    private static Permutation SortItemsBySortingMethod(PackingShape bin, IList<PackingItem> items, SortingMethod sortingMethod, double delta) {
       Permutation sorted = null;
-      switch (sorting) {
+      switch (sortingMethod) {
         case SortingMethod.Given:
           sorted = new Permutation(PermutationTypes.Absolute, Enumerable.Range(0, items.Count).ToArray());
@@ -216 +279 @@
                         .Select(x => x.Index).ToArray());
           break;
-        default: throw new ArgumentException("Unknown sorting method: " + sorting);
-      }
-      
+        default:
+          throw new ArgumentException("Unknown sorting method: " + sortingMethod);
+      }
+      return sorted;
+    }
+
+    /// <summary>
+    /// Returns a decoder depending on the given fitting method
+    /// </summary>
+    /// <param name="fittingMethod"></param>
+    /// <returns></returns>
+    private static ExtremePointPermutationDecoderBase GetDecoderByFittingMethod(FittingMethod fittingMethod) {
       ExtremePointPermutationDecoderBase decoder = null;
-      switch (fitting) {
+      switch (fittingMethod) {
         case FittingMethod.FirstFit:
           decoder = new ExtremePointPermutationDecoder();
@@ -230 +302 @@
           decoder = new ResidualSpaceBestFitExtremePointPermutationDecoder();
           break;
-        default: throw new ArgumentException("Unknown fitting method: " + fitting);
-      }
-
-      var sol = decoder.Decode(sorted, bin, items, stackingConstraints);
-      var fit = evaluator.Evaluate(sol);
-
-      return Tuple.Create(sol, fit);
+        default:
+          throw new ArgumentException("Unknown fitting method: " + fittingMethod);
+      }
+      return decoder;
     }
   }

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

@@ -37 +37 @@
     #region Properties
     [Storable]
+
+    //key = item id
     public ObservableDictionary<int, TPos> Positions { get; private set; }
 
     [Storable]
+    //key = item id
     public ObservableDictionary<int, TItem> Items { get; private set; }
 
@@ -138 +141 @@
       return false;
     }
+
+    /// <summary>
+    /// 
+    /// </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
+      //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;

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

@@ -103 +103 @@
     <Compile Include="2D\ProblemBase.cs" />
     <Compile Include="2D\Solution.cs" />
+    <Compile Include="3D\Packer\BinPacker.cs" />
+    <Compile Include="3D\Packer\BinPackerFirstFit.cs" />
     <Compile Include="3D\BinPacking3D.cs" />
+    <Compile Include="3D\Decoder\ExtremePointPermutationDecoder.cs" />
     <Compile Include="3D\Evaluators\BinUtilizationEvaluator.cs" />
     <Compile Include="3D\Evaluators\PackingRatioEvaluator.cs" />
-    <Compile Include="3D\Instances\RandomInstanceProviderWithSRand.cs" />
+    <Compile Include="3D\Instances\RandomInstanceProvider.cs" />
+    <Compile Include="3D\Geometry\Line3D.cs" />
+    <Compile Include="3D\Geometry\Plane3D.cs" />
+    <Compile Include="3D\Geometry\Vector3D.cs" />
+    <Compile Include="3D\Packer\BinPackerFreeVolumeBestFit.cs" />
+    <Compile Include="3D\Packer\BinPackerResidualSpaceBestFit.cs" />
     <Compile Include="Algorithms\3D\ExtremePointAlgorithm.cs" />
     <Compile Include="3D\Instances\ThreeDInstanceDescriptor.cs" />
@@ -112 +120 @@
     <Compile Include="3D\Instances\RandomDataDescriptor.cs" />
     <Compile Include="3D\Instances\RealWorldContainerPackingInstanceProvider.cs" />
-    <Compile Include="3D\Instances\RandomInstanceProvider.cs" />
     <Compile Include="3D\Instances\ThreeDInstanceParser.cs" />
     <Compile Include="3D\IntegerVectorEncoding\BottomLeftIntegerVectorDecoder.cs" />
@@ -150 +157 @@
     <Compile Include="Plugin.cs" />
     <Compile Include="Properties\AssemblyInfo.cs" />
+    <Compile Include="Random\SRand48.cs" />
   </ItemGroup>
   <ItemGroup>

branches/2817-BinPackingSpeedup/HeuristicLab.Tests/HeuristicLab.Problems.Bin-Packing-3.3/AlgorithmTest.cs

@@ -3 +3 @@
 using Microsoft.VisualStudio.TestTools.UnitTesting;
 using HeuristicLab.Problems.BinPacking3D;
+using HeuristicLab.Problems.BinPacking3D.Instances;
 using System.Collections.Generic;
 using System.Linq;
@@ -30 +31 @@
 
       var referenceItemLists = ReadReferenceItemLists();
-      TestRandomInstanceProviderByClass(new RandomInstanceClass1ProviderWithSRand(), referenceItemLists);
-      TestRandomInstanceProviderByClass(new RandomInstanceClass2ProviderWithSRand(), referenceItemLists);
-      TestRandomInstanceProviderByClass(new RandomInstanceClass3ProviderWithSRand(), referenceItemLists);
-      TestRandomInstanceProviderByClass(new RandomInstanceClass4ProviderWithSRand(), referenceItemLists);
-      TestRandomInstanceProviderByClass(new RandomInstanceClass5ProviderWithSRand(), referenceItemLists);
-      TestRandomInstanceProviderByClass(new RandomInstanceClass6ProviderWithSRand(), referenceItemLists);
-      TestRandomInstanceProviderByClass(new RandomInstanceClass7ProviderWithSRand(), referenceItemLists);
-      TestRandomInstanceProviderByClass(new RandomInstanceClass8ProviderWithSRand(), referenceItemLists);
+      TestRandomInstanceProviderByClass(new RandomInstanceClass1Provider(), referenceItemLists);
+      TestRandomInstanceProviderByClass(new RandomInstanceClass2Provider(), referenceItemLists);
+      TestRandomInstanceProviderByClass(new RandomInstanceClass3Provider(), referenceItemLists);
+      TestRandomInstanceProviderByClass(new RandomInstanceClass4Provider(), referenceItemLists);
+      TestRandomInstanceProviderByClass(new RandomInstanceClass5Provider(), referenceItemLists);
+      TestRandomInstanceProviderByClass(new RandomInstanceClass6Provider(), referenceItemLists);
+      TestRandomInstanceProviderByClass(new RandomInstanceClass7Provider(), referenceItemLists);
+      TestRandomInstanceProviderByClass(new RandomInstanceClass8Provider(), referenceItemLists);
 
     }
@@ -79 +80 @@
     }
 
-    private void TestRandomInstanceProviderByClass(RandomInstanceProviderWithSRand randomInstanceProvider, IDictionary<string, List<Dimension>> referenceItems) {
+    private void TestRandomInstanceProviderByClass(RandomInstanceProvider randomInstanceProvider, IDictionary<string, List<Dimension>> referenceItems) {
 
       var dataDescriptors = randomInstanceProvider.GetDataDescriptors();
@@ -111 +112 @@
     [TestCategory("Problems.BinPacking")]
     public void TestExtremePointAlgorithmClass1() {
-      TestExtremePointAlgorithm(new RandomInstanceClass1ProviderWithSRand(), 1);
+      TestExtremePointAlgorithm(new RandomInstanceClass1Provider(), 1);
     }
 
@@ -117 +118 @@
     [TestCategory("Problems.BinPacking")]
     public void TestExtremePointAlgorithmClass2() {
-      TestExtremePointAlgorithm(new RandomInstanceClass2ProviderWithSRand(), 2);
+      TestExtremePointAlgorithm(new RandomInstanceClass2Provider(), 2);
     }
 
@@ -123 +124 @@
     [TestCategory("Problems.BinPacking")]
     public void TestExtremePointAlgorithmClass3() {
-      TestExtremePointAlgorithm(new RandomInstanceClass3ProviderWithSRand(), 3);
+      TestExtremePointAlgorithm(new RandomInstanceClass3Provider(), 3);
     }
 
@@ -129 +130 @@
     [TestCategory("Problems.BinPacking")]
     public void TestExtremePointAlgorithmClass4() {
-      TestExtremePointAlgorithm(new RandomInstanceClass4ProviderWithSRand(), 4);
+      TestExtremePointAlgorithm(new RandomInstanceClass4Provider(), 4);
     }
 
@@ -135 +136 @@
     [TestCategory("Problems.BinPacking")]
     public void TestExtremePointAlgorithmClass5() {
-      TestExtremePointAlgorithm(new RandomInstanceClass5ProviderWithSRand(), 5);
+      TestExtremePointAlgorithm(new RandomInstanceClass5Provider(), 5);
     }
 
@@ -141 +142 @@
     [TestCategory("Problems.BinPacking")]
     public void TestExtremePointAlgorithmClass6() {
-      TestExtremePointAlgorithm(new RandomInstanceClass6ProviderWithSRand(), 6);
+      TestExtremePointAlgorithm(new RandomInstanceClass6Provider(), 6);
     }
 
@@ -147 +148 @@
     [TestCategory("Problems.BinPacking")]
     public void TestExtremePointAlgorithmClass7() {
-      TestExtremePointAlgorithm(new RandomInstanceClass7ProviderWithSRand(), 7);
+      TestExtremePointAlgorithm(new RandomInstanceClass7Provider(), 7);
     }
 
@@ -153 +154 @@
     [TestCategory("Problems.BinPacking")]
     public void TestExtremePointAlgorithmClass8() {
-      TestExtremePointAlgorithm(new RandomInstanceClass8ProviderWithSRand(), 8);
-    }
-
-    private void TestExtremePointAlgorithm(RandomInstanceProviderWithSRand randomInstanceProvider, int @class) {
+      TestExtremePointAlgorithm(new RandomInstanceClass8Provider(), 8);
+    }
+
+    private void TestExtremePointAlgorithm(RandomInstanceProvider randomInstanceProvider, int @class) {
       foreach (SortingMethod sortingMethod in Enum.GetValues(typeof(SortingMethod))) {
         //foreach (FittingMethod fittingMethod in Enum.GetValues(typeof(FittingMethod))) {
@@ -168 +169 @@
 
 
-    private void TestExtremePointAlgorithmByParameters(RandomInstanceProviderWithSRand randomInstanceProvider, int @class, SortingMethod sortingMethod, FittingMethod fittingMethod) {
+    private void TestExtremePointAlgorithmByParameters(RandomInstanceProvider randomInstanceProvider, int @class, SortingMethod sortingMethod, FittingMethod fittingMethod) {
       var dataDescriptors = randomInstanceProvider.GetDataDescriptors();
       var referenceValues = GetReferenceAlgorithmValues();