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

Timestamp:

02/28/18 14:05:31 (7 years ago)

Author:

rhanghof

Message:

#2817:

• Fixes for pruning

Location:

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

Files:

• ExtremePointCreation/PointProjectionBasedEPCreator.cs (modified) (3 diffs)
• ExtremePointPruning/ExtremePointPruning.cs (modified) (2 diffs)
• ExtremePointPruning/ExtremePointPruningFactory.cs (modified) (1 diff)
• ExtremePointPruning/IExtremePointPruning.cs (modified) (2 diffs)
• Packer/BinPackerFirstFit.cs (modified) (1 diff)
• Packer/BinPackerFormClosure.cs (modified) (1 diff)
• Packer/BinPackerFreeVolumeBestFit.cs (modified) (1 diff)
• Packer/BinPackerMinRSLeft.cs (modified) (6 diffs)
• Packer/BinPackerResidualSpaceBestFit.cs (modified) (1 diff)
• PackingItem.cs (modified) (5 diffs)

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

@@ -49 +49 @@
         return;
       }
-
+      
       // generate all new extreme points parallel. This speeds up the creator.
       var items = binPacking.Items.OrderBy(x => x.Value.Layer);
@@ -57 +57 @@
         GenerateNewExtremePointsForItem(binPacking, it, pos);
       });
-      ExtremePointPruningFactory.CreatePruning().PruneExtremePoints(ExtremePointPruningMethod.PruneBehind, new List<BinPacking3D>() { binPacking });
-
+      
       Parallel.ForEach(items.Where(x => x.Value.Layer >= item.Layer), i => {
         PackingItem it = i.Value;
@@ -64 +63 @@
         GenerateNewExtremePointsForItem(binPacking, it, pos);
       });
-      
+
       // remove not needed extreme points.
       foreach (var extremePoint in binPacking.ExtremePoints.ToList()) {

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

@@ -28 +28 @@
 namespace HeuristicLab.Problems.BinPacking3D.ExtremePointPruning {
   internal class ExtremePointPruning : IExtremePointPruning {
-    public void PruneExtremePoints(ExtremePointPruningMethod pruningMethod, PackingShape bin, Dictionary<BinPacking3D, List<KeyValuePair<int, PackingPosition>>> positions) {
-      if (pruningMethod == ExtremePointPruningMethod.PruneBehind) {
-        PruneExtremePointsBehind(bin, positions);
-      }
+    public void PruneExtremePoints(PackingShape bin, Dictionary<BinPacking3D, List<KeyValuePair<int, PackingPosition>>> positions) {
+      PruneExtremePointsBehind(bin, positions);
     }
 
-    public void PruneExtremePoints(ExtremePointPruningMethod pruningMethod, IList<BinPacking3D> binPackings) {
+    public void PruneExtremePoints(IList<BinPacking3D> binPackings) {
       if (binPackings.Count <= 0) {
         return;
@@ -47 +45 @@
       }
       PruneExtremePointsBehind(binPackings[0].BinShape, fixedPositions);
+    }
+
+    public void PruneExtremePoints(BinPacking3D binPacking, int layer) {
+      var pruningPositions = new List<KeyValuePair<int, PackingPosition>>();
+      var pruning = new Dictionary<BinPacking3D, List<KeyValuePair<int, PackingPosition>>>();
+      pruning.Add(binPacking, pruningPositions);
+      foreach (var item in binPacking.Items.Where(x => x.Value.Layer <= layer)) {
+        pruningPositions.Add(new KeyValuePair<int, PackingPosition>(item.Key, binPacking.Positions[item.Key]));
+      }
+
+      PruneExtremePointsBehind(binPacking.BinShape, pruning);
     }
 

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

@@ -28 +28 @@
 namespace HeuristicLab.Problems.BinPacking3D.ExtremePointPruning {
   public static class ExtremePointPruningFactory {
-    public static IExtremePointPruning CreatePruning() {
+    public static IExtremePointPruning CreatePruning(ExtremePointPruningMethod pruningMethod) {
       return new ExtremePointPruning();
     }

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

@@ -35 +35 @@
     /// <param name="bin"></param>
     /// <param name="positions"></param>
-    void PruneExtremePoints(ExtremePointPruningMethod pruningMethod, PackingShape bin, Dictionary<BinPacking3D, List<KeyValuePair<int, PackingPosition>>> positions);
+    void PruneExtremePoints(PackingShape bin, Dictionary<BinPacking3D, List<KeyValuePair<int, PackingPosition>>> positions);
 
     /// <summary>
@@ -42 +42 @@
     /// <param name="pruningMethod"></param>
     /// <param name="bins"></param>
-    void PruneExtremePoints(ExtremePointPruningMethod pruningMethod, IList<BinPacking3D> binPackings);
+    void PruneExtremePoints(IList<BinPacking3D> binPackings);
+
+    /// <summary>
+    /// Prunes the extreme points of the given bins depending on the given pruning method.
+    /// </summary>
+    /// <param name="pruningMethod"></param>
+    /// <param name="binPacking"></param>
+    /// <param name="layer"
+    void PruneExtremePoints(BinPacking3D binPacking, int layer);
   }
 }

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

@@ -63 +63 @@
       }
 
-      ExtremePointPruningFactory.CreatePruning().PruneExtremePoints(epPruningMethod, packingList);
+      ExtremePointPruningFactory.CreatePruning(epPruningMethod).PruneExtremePoints(packingList);
       return packingList;
     }

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

@@ -44 +44 @@
 
 
-      private bool ItemFitsBinShapeWidth(int itemId, PackingItem item, PackingShape binShape) {
+    private bool ItemFitsBinShapeWidth(int itemId, PackingItem item, PackingShape binShape) {
       item.Rotated = false;
       item.Tilted = false;

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

@@ -95 +95 @@
         }
       }
-      ExtremePointPruningFactory.CreatePruning().PruneExtremePoints(epPruningMethod, packingList);
+      ExtremePointPruningFactory.CreatePruning(epPruningMethod).PruneExtremePoints(packingList);
       return packingList.ToList();
     }

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

@@ -68 +68 @@
       }
 
-      ExtremePointPruningFactory.CreatePruning().PruneExtremePoints(epPruningMethod, packingList);
+      ExtremePointPruningFactory.CreatePruning(epPruningMethod).PruneExtremePoints(packingList);
 
       return packingList;
@@ -92 +92 @@
       }
 
-      ExtremePointPruningFactory.CreatePruning().PruneExtremePoints(epPruningMethod, packingList);
+      ExtremePointPruningFactory.CreatePruning(epPruningMethod).PruneExtremePoints(packingList);
     }
 
@@ -107 +107 @@
     protected virtual void PackRemainingItems(ref IList<int> remainingIds, ref BinPacking3D packingBin, IList<PackingItem> items, ExtremePointCreationMethod epCreationMethod, bool useStackingConstraints) {
       IExtremePointCreator extremePointCreator = ExtremePointCreatorFactory.CreateExtremePointCreator(epCreationMethod, useStackingConstraints);
-
+      
       var remainingNotWeightSupportedItems = new List<int>();
       foreach (var itemId in new List<int>(remainingIds)) {
-        var item = items[itemId];        
+        var item = items[itemId];
+        var clonedPackingBin = packingBin.Clone() as BinPacking3D;
+        ExtremePointPruningFactory.CreatePruning(ExtremePointPruningMethod.PruneBehind).PruneExtremePoints(clonedPackingBin, item.Layer - 1);
 
         // If an item doesn't support any weight it should have a minimum waste of the residual space.
@@ -119 +121 @@
           remainingNotWeightSupportedItems.Add(itemId);
         } else if (!item.IsStackabel) {
-          PackingPosition position = FindPackingPositionForNotStackableItem(packingBin, item, useStackingConstraints);
+          PackingPosition position = FindPackingPositionForNotStackableItem(clonedPackingBin, item, useStackingConstraints);
           // if a valid packing position could be found, the current item can be added to the given bin
           if (position != null) {
@@ -126 +128 @@
           }
         } else  {
-          PackingPosition position = FindPackingPositionForItem(packingBin, item, useStackingConstraints);
+          PackingPosition position = FindPackingPositionForItem(clonedPackingBin, item, useStackingConstraints);
           // if a valid packing position could be found, the current item can be added to the given bin
           if (position != null) {
@@ -140 +142 @@
           PackingPosition position = null;
           if (weightSupportedLeft) {
-            position = FindPackingPositionForWeightUnsupportedItem(packingBin, item, useStackingConstraints);
+            position = FindPackingPositionForWeightUnsupportedItem(clonedPackingBin, item, useStackingConstraints);
           } else {
-            position = FindPackingPositionForItem(packingBin, item, useStackingConstraints);
+            position = FindPackingPositionForItem(clonedPackingBin, item, useStackingConstraints);
           }
 

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

@@ -88 +88 @@
       }
 
-      ExtremePointPruningFactory.CreatePruning().PruneExtremePoints(epPruningMethod, packingList);
+      ExtremePointPruningFactory.CreatePruning(epPruningMethod).PruneExtremePoints(packingList);
       return packingList;
     }

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

@@ -45 +45 @@
     }
 
+    public IFixedValueParameter<IntValue> IdParameter {
+      get { return (IFixedValueParameter<IntValue>)Parameters["Id"]; }
+    }
+
     public PackingShape TargetBin {
       get { return TargetBinParameter.Value; }
@@ -58 +62 @@
       get { return LayerParameter.Value.Value; }
       set { LayerParameter.Value.Value = value; }
+    }
+
+    public int Id {
+      get { return IdParameter.Value.Value; }
+      set { IdParameter.Value.Value = value; }
     }
 
@@ -300 +309 @@
       return SupportedWeight >= weigth;
     }
+
+
+
     #endregion
 
@@ -314 +326 @@
       Parameters.Add(new FixedValueParameter<DoubleValue>("Weight"));
       Parameters.Add(new FixedValueParameter<IntValue>("Layer"));
+      Parameters.Add(new FixedValueParameter<IntValue>("Id"));
 
 
@@ -358 +371 @@
       Weight = packingItem.Weight;
       Layer = packingItem.Layer;
+      Id = packingItem.Id;
       Rotated = packingItem.Rotated;
       Tilted = packingItem.Tilted;