Free cookie consent management tool by TermsFeed Policy Generator

Changeset 15585


Ignore:
Timestamp:
01/09/18 15:46:53 (7 years ago)
Author:
rhanghof
Message:

#2817:

  • Bugfixes for the line projection based extreme point creation
  • Bugfixes for the tests
Location:
branches/2817-BinPackingSpeedup
Files:
6 edited

Legend:

Unmodified
Added
Removed

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

    r15488 r15585  
    205205                  SortingMethod[] sortings,
    206206                  FittingMethod[] fittings,
    207                   ExtremePointCreationMethod[] ePGeneration,
     207                  ExtremePointCreationMethod[] epCreationMethods,
    208208                  CancellationToken token) {
    209209      SortingMethod? bestSorting = null;
    … …  
    214214      foreach (var fit in fittings) {
    215215        foreach (var sort in sortings) {
    216           foreach (var epCreation in ePGeneration) {
     216          foreach (var epCreation in epCreationMethods) {
    217217            IDecoder<Permutation> decoder = new ExtremePointPermutationDecoder() {
    218218              FittingMethod = fit,

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

    r15554 r15585  
    2020
    2121    /// <summary>
    22     /// Updates the residual space for a given bin packing
     22    /// Updates the residual space for a given bin packing.
    2323    /// </summary>
    2424    /// <param name="binPacking"></param>
    … …  
    2626    /// <param name="position"></param>
    2727    protected abstract void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position);
     28
     29    /// <summary>
     30    /// Adds an extreme point to the bin packing.
     31    /// </summary>
     32    /// <param name="binPacking"></param>
     33    /// <param name="position"></param>
     34    /// <returns></returns>
    2835    protected abstract bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position);
    2936
    … …  
    214221
    215222    /// <summary>
    216     /// Returns true, if the given poisition and the related residual space is within the residual space of the given extreme point
    217     /// </summary>
    218     /// <param name="pos"></param>
     223    /// Returns true, if the given poisition (pos) and the related residual space is within any residual space of the given extreme point (ep).
     224    /// </summary>
     225    /// <param name="pos">Given poisition</param>
    219226    /// <param name="rsPos"></param>
    220     /// <param name="ep"></param>
     227    /// <param name="ep">Given extreme point</param>
    221228    /// <param name="rsEp"></param>
    222229    /// <returns></returns>
    … …  
    226233
    227234    /// <summary>
    228     /// Returns true, if the given poisition and the related residual space is within the residual space of the given extreme point
    229     /// </summary>
    230     /// <param name="pos"></param>
     235    /// Returns true, if the given poisition (pos) and the related residual space is within the residual space of the given extreme point (ep).
     236    /// </summary>
     237    /// <param name="pos">Given poisition</param>
    231238    /// <param name="rsPos"></param>
    232     /// <param name="ep"></param>
     239    /// <param name="ep">Given extreme point</param>
    233240    /// <param name="rsEp"></param>
    234241    /// <returns></returns>
    235242    protected virtual bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, ResidualSpace rsPos, PackingPosition ep, ResidualSpace rsEp) {
     243      /*old implementation
    236244      return rsEp.Width >= pos.X - ep.X + rsPos.Width
    237245          && rsEp.Height >= pos.Y - ep.Y + rsPos.Height
    238           && rsEp.Depth >= pos.Z - ep.Z + rsPos.Depth;
     246          && rsEp.Depth >= pos.Z - ep.Z + rsPos.Depth;*/
     247
     248      var x = pos.X >= ep.X && pos.X + rsPos.Width <= ep.X + rsEp.Width;
     249      var y = pos.Y >= ep.Y && pos.Y + rsPos.Height <= ep.Y + rsEp.Height;
     250      var z = pos.Z >= ep.Z && pos.Z + rsPos.Depth <= ep.Z + rsEp.Depth;
     251
     252      return x && y && z;
    239253    }
    240254

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

    r15554 r15585  
    2323        GenerateNewExtremePointsForItem(binPacking, it, p);
    2424      }
    25     }
    26 
    27     /// <summary>
    28     /// Adds a new extreme point an the related residual spaces to a given bin packing.
    29     /// - The given position has to be valid.
    30     /// - The extreme point does not exist in the bin packing.
    31     /// - There must be at minimum one valid residual space. A residual space is invalid if the space is zero.
    32     /// </summary>
    33     /// <param name="binPacking"></param>
    34     /// <param name="position"></param>
    35     /// <returns>True = the given point and its related residual spaces were successfully added to the bin packing</returns>
    36     protected override bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position) {
    37       if (position == null) {
    38         return false;
    39       }
    40 
    41       if (PointIsInAnyItem(binPacking, new Vector3D(position))) {
    42         return false;
    43       }
    44 
    45       if (binPacking.ExtremePoints.ContainsKey(position)) {
    46         return false;
    47       }
    48 
    49       var rs = CalculateResidualSpace(binPacking, new Vector3D(position));
    50 
    51       if (rs.Count() <= 0) {
    52         return false;
    53       }
    54 
    55       // todo
    56       /*
    57        ist der extrempunkt im residual space eines anderen muss ueberprueft werden:
    58           - ist der andere ep in der luft, kann auch dieser hinzugefuegt werden.
    59           - hat der andere ep ein item unterhalb, darf dieser nicht hinzugefuegt werden.
    60        -> neu methode basierend auf IsWithinResidualSpaceOfAnotherExtremePoint, die den ep oder rs zurueck gibt, der einen anderen rs einschließt.
    61           eventuell gehoert diese logik in den ResidualSpaceCreator.
    62       if (LiesOnAnyItem(binPacking, position)) {
    63         return false;
    64       }*/
    65 
    66       binPacking.ExtremePoints.Add(position, rs);
    67       return true;
    68     }
    69 
     25     
     26      // remove not needed extreme points.
     27      foreach (var extremePoint in binPacking.ExtremePoints.ToList()) {
     28        // check if a residual space can be removed
     29        foreach (var rs in extremePoint.Value.ToList()) {
     30          if (ResidualSpaceCanBeRemoved(binPacking, extremePoint.Key, rs)) {
     31            ((IList<ResidualSpace>)extremePoint.Value).Remove(rs);
     32          }
     33        }
     34        // if the current extreme point has no more residual spaces, it can be removed.
     35        if (((IList<ResidualSpace>)extremePoint.Value).Count <= 0) {
     36          binPacking.ExtremePoints.Remove(extremePoint);
     37        }
     38      }
     39    }
     40   
     41    /// <summary>
     42    /// Returns true if a given residual space can be removed.
     43    /// The given residual space can be removed if it is within another residual space and
     44    /// - neither the position of the other residual space and the current extreme point have an item below or
     45    /// - the current extreme point has an item below.
     46    /// </summary>
     47    /// <param name="binPacking"></param>
     48    /// <param name="position"></param>
     49    /// <param name="rs"></param>
     50    /// <returns></returns>
     51    private bool ResidualSpaceCanBeRemoved(BinPacking3D binPacking, PackingPosition position, ResidualSpace rs) {
     52      foreach (var extremePoint in binPacking.ExtremePoints) {
     53        if (position.Equals(extremePoint.Key)) {
     54          continue;
     55        }
     56        if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(position), rs, extremePoint.Key, extremePoint.Value)) {
     57          var itemBelowEp = LiesOnAnyItem(binPacking, extremePoint.Key);
     58          var itemBelowPos = LiesOnAnyItem(binPacking, position);
     59
     60          if (itemBelowEp || !itemBelowEp && !itemBelowPos) {
     61            return true;
     62          }         
     63        }
     64      }
     65      return false;
     66    }
     67   
     68    /// <summary>
     69    /// Returns true if the given position lies on an item or an the ground.
     70    /// </summary>
     71    /// <param name="binPacking"></param>
     72    /// <param name="position"></param>
     73    /// <returns></returns>
    7074    private bool LiesOnAnyItem(BinPacking3D binPacking, PackingPosition position) {
    7175      if (position.Y == 0) {
    … …  
    8589
    8690      return items.Count() > 0;
     91    }
     92
     93
     94    /// <summary>
     95    /// Adds a new extreme point an the related residual spaces to a given bin packing.
     96    /// - The given position has to be valid.
     97    /// - The extreme point does not exist in the bin packing.
     98    /// - There must be at minimum one valid residual space. A residual space is invalid if the space is zero.
     99    /// </summary>
     100    /// <param name="binPacking"></param>
     101    /// <param name="position"></param>
     102    /// <returns>True = the given point and its related residual spaces were successfully added to the bin packing</returns>
     103    protected override bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position) {
     104      if (position == null) {
     105        return false;
     106      }
     107
     108      if (PointIsInAnyItem(binPacking, new Vector3D(position))) {
     109        return false;
     110      }
     111
     112      if (binPacking.ExtremePoints.ContainsKey(position)) {
     113        return false;
     114      }
     115
     116      var rs = CalculateResidualSpace(binPacking, new Vector3D(position));
     117
     118      if (rs.Count() <= 0) {
     119        return false;
     120      }
     121
     122      binPacking.ExtremePoints.Add(position, rs);
     123      return true;
    87124    }
    88125

  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ResidualSpaceCalculation/ResidualSpaceCalculator.cs

    r15554 r15585  
    1919      if (!rs1.IsZero()) {
    2020        residualSpaces.Add(rs1);
    21       }     
    22 
     21      }
    2322
    2423      if (!rs2.IsZero() && !residualSpaces.Any(rs => rs.Equals(rs2))) {
    … …  
    3130    }
    3231
     32    /// <summary>
     33    /// Calculates a resiual space by expanding to the limits of the axis in the following order:
     34    /// 1. x
     35    /// 2. z
     36    /// 3. y
     37    /// </summary>
     38    /// <param name="binPacking"></param>
     39    /// <param name="point"></param>
     40    /// <returns></returns>
    3341    private ResidualSpace CalculateXZY(BinPacking3D binPacking, Vector3D point) {
    3442      ResidualSpace rs = new ResidualSpace(binPacking, point);
    … …  
    4048    }
    4149
     50    /// <summary>
     51    /// Calculates a resiual space by expanding to the limits of the axis in the following order:
     52    /// 1. z
     53    /// 2. y
     54    /// 3. x
     55    /// </summary>
     56    /// <param name="binPacking"></param>
     57    /// <param name="point"></param>
     58    /// <returns></returns>
    4259    private ResidualSpace CalculateZYX(BinPacking3D binPacking, Vector3D point) {
    4360      ResidualSpace rs = new ResidualSpace(binPacking, point);
    … …  
    4966    }
    5067
     68    /// <summary>
     69    /// Calculates a resiual space by expanding to the limits of the axis in the following order:
     70    /// 1. y
     71    /// 2. x
     72    /// 3. z
     73    /// </summary>
     74    /// <param name="binPacking"></param>
     75    /// <param name="point"></param>
     76    /// <returns></returns>
    5177    private ResidualSpace CalculateYXZ(BinPacking3D binPacking, Vector3D point) {
    5278      ResidualSpace rs = new ResidualSpace(binPacking, point);
    … …  
    114140
    115141    private bool OverlapsOnRight(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
    116       // if point.x >= position.x, the residual space would be located on the left side!
     142      // if point.x >= position.x => the residual space is being located on the left side!
    117143      if (point.X >= position.X) {
    118144        return false;
    … …  
    133159    }
    134160
     161
    135162    private bool OverlapsAbove(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item ) {
    136163      if (point.Y >= position.Y) {
    … …  
    142169      return x && z;
    143170    }
    144    
     171
     172    /// <summary>
     173    /// Recalculates the width of a given residual space.
     174    /// The new width is being limited by any item right of the residual space or the dimension of the bin shape.
     175    /// If the new width is zero, the whole residual space is being set to zero.
     176    /// </summary>
     177    /// <param name="binPacking"></param>
     178    /// <param name="point"></param>
     179    /// <param name="residualSpace"></param>
    145180    private void LimitResidualSpaceOnRight(BinPacking3D binPacking, Vector3D point, ResidualSpace residualSpace) {
    146181      if (residualSpace.IsZero()) {
    … …  
    163198    }
    164199
     200    /// <summary>
     201    /// Recalculates the depth of a given residual space.
     202    /// The new depth is being limited by any item in front of the residual space or the dimension of the bin shape.
     203    /// If the new depth is zero, the whole residual space is being set to zero.
     204    /// </summary>
     205    /// <param name="binPacking"></param>
     206    /// <param name="point"></param>
     207    /// <param name="residualSpace"></param>
    165208    private void LimitResidualSpaceInFront(BinPacking3D binPacking, Vector3D point, ResidualSpace residualSpace) {
    166209      if (residualSpace.IsZero()) {
    … …  
    183226    }
    184227
     228    /// <summary>
     229    /// Recalculates the height of a given residual space.
     230    /// The new height is being limited by any item above the residual space or the dimension of the bin shape.
     231    /// If the new height is zero, the whole residual space is being set to zero.
     232    /// </summary>
     233    /// <param name="binPacking"></param>
     234    /// <param name="point"></param>
     235    /// <param name="residualSpace"></param>
    185236    private void LimitResidualSpaceAbove(BinPacking3D binPacking, Vector3D point, ResidualSpace residualSpace) {
    186237      if (residualSpace.IsZero()) {

  • branches/2817-BinPackingSpeedup/HeuristicLab.Tests/HeuristicLab.Problems.Bin-Packing-3.3/3D/Algorithms/ExtremePointAlgorithmTest.cs

    r15554 r15585  
    7474      };
    7575
    76       object[] parameters = new object[] { _packingShape3, _items, new SortingMethod[] { SortingMethod.Given }, new FittingMethod[] { FittingMethod.FirstFit }, new CancellationToken() };
     76      object[] parameters = new object[] { _packingShape3,
     77                                           _items,
     78                                           new SortingMethod[] { SortingMethod.Given },
     79                                           new FittingMethod[] { FittingMethod.FirstFit },
     80                                           new ExtremePointCreationMethod[] { ExtremePointCreationMethod.PointProjection},
     81                                           new CancellationToken() };
    7782      _extremPointAlgorithm.SortingMethodParameter.Value.Value = SortingMethod.Given;
    7883      _extremPointAlgorithm.FittingMethodParameter.Value.Value = FittingMethod.FirstFit;
    7984      _extremPointAlgorithm.ExtremePointCreationMethodParameter.Value.Value = ExtremePointCreationMethod.PointProjection;
    8085      _extremPointAlgorithm.SortByMaterialParameter.Value.Value = false;
    81       var result = TestUtils.InvokeMethod(typeof(ExtremePointAlgorithm), _extremPointAlgorithm, "GetBest", parameters) as Tuple<Solution, double, SortingMethod?, FittingMethod?>;
     86      var result = TestUtils.InvokeMethod(typeof(ExtremePointAlgorithm), _extremPointAlgorithm, "GetBest", parameters) as Tuple<Solution, double, SortingMethod?, FittingMethod?, ExtremePointCreationMethod?>;
    8287
    8388      int i = 0;

  • branches/2817-BinPackingSpeedup/HeuristicLab.Tests/HeuristicLab.Problems.Bin-Packing-3.3/3D/Instances/RandomInstanceProviderTest.cs

    r15554 r15585  
    170170        //foreach (FittingMethod fittingMethod in Enum.GetValues(typeof(FittingMethod))) {
    171171        FittingMethod fittingMethod = FittingMethod.FirstFit;
    172         TestExtremePointAlgorithmByParameters(randomInstanceProvider, @class, sortingMethod, fittingMethod);
     172        foreach (ExtremePointCreationMethod epCreationMethod in Enum.GetValues(typeof(ExtremePointCreationMethod))) {
     173          TestExtremePointAlgorithmByParameters(randomInstanceProvider, @class, sortingMethod, fittingMethod, epCreationMethod);
     174        }
     175       
    173176        //}
    174177      }
    175178    }
    176179
    177     private void TestExtremePointAlgorithmByParameters(RandomInstanceProvider randomInstanceProvider, int @class, SortingMethod sortingMethod, FittingMethod fittingMethod) {
     180    private void TestExtremePointAlgorithmByParameters(RandomInstanceProvider randomInstanceProvider, int @class, SortingMethod sortingMethod, FittingMethod fittingMethod, ExtremePointCreationMethod epCreationMethod) {
    178181      var dataDescriptors = randomInstanceProvider.GetDataDescriptors();
    179182      var referenceValues = GetReferenceAlgorithmValues();
    … …  
    189192          algorithm.SortingMethodParameter.Value.Value = sortingMethod;
    190193          algorithm.FittingMethodParameter.Value.Value = fittingMethod;
     194          algorithm.ExtremePointCreationMethodParameter.Value.Value = epCreationMethod;
    191195          algorithm.Problem.Load(packingData);
    192196
    … …  
    207211
    208212        if (referenceValues.TryGetValue(new Tuple<int, int, SortingMethod>(@class, numItems, sortingMethod), out referenceValue)) {
    209           Console.WriteLine($"{numItems}-{@class}-{sortingMethod}: \tReference: {referenceValue} \tImplementation: {(double)sumNumberOfBins / (double)NUMBER_OF_TEST_INSTANCES} \t{(referenceValue - ((double)sumNumberOfBins / (double)NUMBER_OF_TEST_INSTANCES)):F2}");
     213          Console.WriteLine($"{numItems}-{@class}-{sortingMethod}-{epCreationMethod}: \tReference: {referenceValue} \tImplementation: {(double)sumNumberOfBins / (double)NUMBER_OF_TEST_INSTANCES} \t{(referenceValue - ((double)sumNumberOfBins / (double)NUMBER_OF_TEST_INSTANCES)):F2}");
    210214          Assert.AreEqual(referenceValue, (double)sumNumberOfBins / (double)NUMBER_OF_TEST_INSTANCES, 20.0);
    211215        }
Note: See TracChangeset for help on using the changeset viewer.