Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
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:
10 edited

Legend:

Unmodified
Added
Removed
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/PointProjectionBasedEPCreator.cs

    r15731 r15820  
    4949        return;
    5050      }
    51 
     51     
    5252      // generate all new extreme points parallel. This speeds up the creator.
    5353      var items = binPacking.Items.OrderBy(x => x.Value.Layer);
     
    5757        GenerateNewExtremePointsForItem(binPacking, it, pos);
    5858      });
    59       ExtremePointPruningFactory.CreatePruning().PruneExtremePoints(ExtremePointPruningMethod.PruneBehind, new List<BinPacking3D>() { binPacking });
    60 
     59     
    6160      Parallel.ForEach(items.Where(x => x.Value.Layer >= item.Layer), i => {
    6261        PackingItem it = i.Value;
     
    6463        GenerateNewExtremePointsForItem(binPacking, it, pos);
    6564      });
    66      
     65
    6766      // remove not needed extreme points.
    6867      foreach (var extremePoint in binPacking.ExtremePoints.ToList()) {
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointPruning/ExtremePointPruning.cs

    r15731 r15820  
    2828namespace HeuristicLab.Problems.BinPacking3D.ExtremePointPruning {
    2929  internal class ExtremePointPruning : IExtremePointPruning {
    30     public void PruneExtremePoints(ExtremePointPruningMethod pruningMethod, PackingShape bin, Dictionary<BinPacking3D, List<KeyValuePair<int, PackingPosition>>> positions) {
    31       if (pruningMethod == ExtremePointPruningMethod.PruneBehind) {
    32         PruneExtremePointsBehind(bin, positions);
    33       }
     30    public void PruneExtremePoints(PackingShape bin, Dictionary<BinPacking3D, List<KeyValuePair<int, PackingPosition>>> positions) {
     31      PruneExtremePointsBehind(bin, positions);
    3432    }
    3533
    36     public void PruneExtremePoints(ExtremePointPruningMethod pruningMethod, IList<BinPacking3D> binPackings) {
     34    public void PruneExtremePoints(IList<BinPacking3D> binPackings) {
    3735      if (binPackings.Count <= 0) {
    3836        return;
     
    4745      }
    4846      PruneExtremePointsBehind(binPackings[0].BinShape, fixedPositions);
     47    }
     48
     49    public void PruneExtremePoints(BinPacking3D binPacking, int layer) {
     50      var pruningPositions = new List<KeyValuePair<int, PackingPosition>>();
     51      var pruning = new Dictionary<BinPacking3D, List<KeyValuePair<int, PackingPosition>>>();
     52      pruning.Add(binPacking, pruningPositions);
     53      foreach (var item in binPacking.Items.Where(x => x.Value.Layer <= layer)) {
     54        pruningPositions.Add(new KeyValuePair<int, PackingPosition>(item.Key, binPacking.Positions[item.Key]));
     55      }
     56
     57      PruneExtremePointsBehind(binPacking.BinShape, pruning);
    4958    }
    5059
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointPruning/ExtremePointPruningFactory.cs

    r15618 r15820  
    2828namespace HeuristicLab.Problems.BinPacking3D.ExtremePointPruning {
    2929  public static class ExtremePointPruningFactory {
    30     public static IExtremePointPruning CreatePruning() {
     30    public static IExtremePointPruning CreatePruning(ExtremePointPruningMethod pruningMethod) {
    3131      return new ExtremePointPruning();
    3232    }
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointPruning/IExtremePointPruning.cs

    r15618 r15820  
    3535    /// <param name="bin"></param>
    3636    /// <param name="positions"></param>
    37     void PruneExtremePoints(ExtremePointPruningMethod pruningMethod, PackingShape bin, Dictionary<BinPacking3D, List<KeyValuePair<int, PackingPosition>>> positions);
     37    void PruneExtremePoints(PackingShape bin, Dictionary<BinPacking3D, List<KeyValuePair<int, PackingPosition>>> positions);
    3838
    3939    /// <summary>
     
    4242    /// <param name="pruningMethod"></param>
    4343    /// <param name="bins"></param>
    44     void PruneExtremePoints(ExtremePointPruningMethod pruningMethod, IList<BinPacking3D> binPackings);
     44    void PruneExtremePoints(IList<BinPacking3D> binPackings);
     45
     46    /// <summary>
     47    /// Prunes the extreme points of the given bins depending on the given pruning method.
     48    /// </summary>
     49    /// <param name="pruningMethod"></param>
     50    /// <param name="binPacking"></param>
     51    /// <param name="layer"
     52    void PruneExtremePoints(BinPacking3D binPacking, int layer);
    4553  }
    4654}
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerFirstFit.cs

    r15652 r15820  
    6363      }
    6464
    65       ExtremePointPruningFactory.CreatePruning().PruneExtremePoints(epPruningMethod, packingList);
     65      ExtremePointPruningFactory.CreatePruning(epPruningMethod).PruneExtremePoints(packingList);
    6666      return packingList;
    6767    }
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerFormClosure.cs

    r15801 r15820  
    4444
    4545
    46       private bool ItemFitsBinShapeWidth(int itemId, PackingItem item, PackingShape binShape) {
     46    private bool ItemFitsBinShapeWidth(int itemId, PackingItem item, PackingShape binShape) {
    4747      item.Rotated = false;
    4848      item.Tilted = false;
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerFreeVolumeBestFit.cs

    r15652 r15820  
    9595        }
    9696      }
    97       ExtremePointPruningFactory.CreatePruning().PruneExtremePoints(epPruningMethod, packingList);
     97      ExtremePointPruningFactory.CreatePruning(epPruningMethod).PruneExtremePoints(packingList);
    9898      return packingList.ToList();
    9999    }
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerMinRSLeft.cs

    r15801 r15820  
    6868      }
    6969
    70       ExtremePointPruningFactory.CreatePruning().PruneExtremePoints(epPruningMethod, packingList);
     70      ExtremePointPruningFactory.CreatePruning(epPruningMethod).PruneExtremePoints(packingList);
    7171
    7272      return packingList;
     
    9292      }
    9393
    94       ExtremePointPruningFactory.CreatePruning().PruneExtremePoints(epPruningMethod, packingList);
     94      ExtremePointPruningFactory.CreatePruning(epPruningMethod).PruneExtremePoints(packingList);
    9595    }
    9696
     
    107107    protected virtual void PackRemainingItems(ref IList<int> remainingIds, ref BinPacking3D packingBin, IList<PackingItem> items, ExtremePointCreationMethod epCreationMethod, bool useStackingConstraints) {
    108108      IExtremePointCreator extremePointCreator = ExtremePointCreatorFactory.CreateExtremePointCreator(epCreationMethod, useStackingConstraints);
    109 
     109     
    110110      var remainingNotWeightSupportedItems = new List<int>();
    111111      foreach (var itemId in new List<int>(remainingIds)) {
    112         var item = items[itemId];       
     112        var item = items[itemId];
     113        var clonedPackingBin = packingBin.Clone() as BinPacking3D;
     114        ExtremePointPruningFactory.CreatePruning(ExtremePointPruningMethod.PruneBehind).PruneExtremePoints(clonedPackingBin, item.Layer - 1);
    113115
    114116        // If an item doesn't support any weight it should have a minimum waste of the residual space.
     
    119121          remainingNotWeightSupportedItems.Add(itemId);
    120122        } else if (!item.IsStackabel) {
    121           PackingPosition position = FindPackingPositionForNotStackableItem(packingBin, item, useStackingConstraints);
     123          PackingPosition position = FindPackingPositionForNotStackableItem(clonedPackingBin, item, useStackingConstraints);
    122124          // if a valid packing position could be found, the current item can be added to the given bin
    123125          if (position != null) {
     
    126128          }
    127129        } else  {
    128           PackingPosition position = FindPackingPositionForItem(packingBin, item, useStackingConstraints);
     130          PackingPosition position = FindPackingPositionForItem(clonedPackingBin, item, useStackingConstraints);
    129131          // if a valid packing position could be found, the current item can be added to the given bin
    130132          if (position != null) {
     
    140142          PackingPosition position = null;
    141143          if (weightSupportedLeft) {
    142             position = FindPackingPositionForWeightUnsupportedItem(packingBin, item, useStackingConstraints);
     144            position = FindPackingPositionForWeightUnsupportedItem(clonedPackingBin, item, useStackingConstraints);
    143145          } else {
    144             position = FindPackingPositionForItem(packingBin, item, useStackingConstraints);
     146            position = FindPackingPositionForItem(clonedPackingBin, item, useStackingConstraints);
    145147          }
    146148
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerResidualSpaceBestFit.cs

    r15652 r15820  
    8888      }
    8989
    90       ExtremePointPruningFactory.CreatePruning().PruneExtremePoints(epPruningMethod, packingList);
     90      ExtremePointPruningFactory.CreatePruning(epPruningMethod).PruneExtremePoints(packingList);
    9191      return packingList;
    9292    }
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/PackingItem.cs

    r15770 r15820  
    4545    }
    4646
     47    public IFixedValueParameter<IntValue> IdParameter {
     48      get { return (IFixedValueParameter<IntValue>)Parameters["Id"]; }
     49    }
     50
    4751    public PackingShape TargetBin {
    4852      get { return TargetBinParameter.Value; }
     
    5862      get { return LayerParameter.Value.Value; }
    5963      set { LayerParameter.Value.Value = value; }
     64    }
     65
     66    public int Id {
     67      get { return IdParameter.Value.Value; }
     68      set { IdParameter.Value.Value = value; }
    6069    }
    6170
     
    300309      return SupportedWeight >= weigth;
    301310    }
     311
     312
     313
    302314    #endregion
    303315
     
    314326      Parameters.Add(new FixedValueParameter<DoubleValue>("Weight"));
    315327      Parameters.Add(new FixedValueParameter<IntValue>("Layer"));
     328      Parameters.Add(new FixedValueParameter<IntValue>("Id"));
    316329
    317330
     
    358371      Weight = packingItem.Weight;
    359372      Layer = packingItem.Layer;
     373      Id = packingItem.Id;
    360374      Rotated = packingItem.Rotated;
    361375      Tilted = packingItem.Tilted;
Note: See TracChangeset for help on using the changeset viewer.