Ignore:
Timestamp:
07/21/17 11:29:08 (3 years ago)
Author:
abeham
Message:

#2762, #2739: merged revisions 14708, 14709, 14971, 14978, 14979, 15167, 15230, 15233, 15240, 15241, 15276 to stable

Location:
stable
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • stable

  • stable/HeuristicLab.Problems.BinPacking

    • Property svn:mergeinfo set to (toggle deleted branches)
      /trunk/sources/HeuristicLab.Problems.BinPackingmergedeligible
      /branches/1721-RandomForestPersistence/HeuristicLab.Problems.BinPacking10321-10322
      /branches/Algorithms.GradientDescent/HeuristicLab.Problems.BinPacking5516-5520
      /branches/Benchmarking/sources/HeuristicLab.Problems.BinPacking6917-7005
      /branches/BinPackingExtension/HeuristicLab.Problems.BinPacking14835-15229
      /branches/CloningRefactoring/HeuristicLab.Problems.BinPacking4656-4721
      /branches/CodeEditor/HeuristicLab.Problems.BinPacking11700-11806
      /branches/DataAnalysis Refactoring/HeuristicLab.Problems.BinPacking5471-5808
      /branches/DataAnalysis SolutionEnsembles/HeuristicLab.Problems.BinPacking5815-6180
      /branches/DataAnalysis/HeuristicLab.Problems.BinPacking4458-4459,​4462,​4464
      /branches/DataPreprocessing/HeuristicLab.Problems.BinPacking10085-11101
      /branches/GP.Grammar.Editor/HeuristicLab.Problems.BinPacking6284-6795
      /branches/GP.Symbols (TimeLag, Diff, Integral)/HeuristicLab.Problems.BinPacking5060
      /branches/HLScript/HeuristicLab.Problems.BinPacking10331-10358
      /branches/HeuristicLab.DatasetRefactor/sources/HeuristicLab.Problems.BinPacking11570-12508
      /branches/HeuristicLab.Problems.DataAnalysis.Trading/HeuristicLab.Problems.BinPacking6123-9799
      /branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.BinPacking11130-12721
      /branches/HiveStatistics/sources/HeuristicLab.Problems.BinPacking12440-12877
      /branches/LogResidualEvaluator/HeuristicLab.Problems.BinPacking10202-10483
      /branches/NET40/sources/HeuristicLab.Problems.BinPacking5138-5162
      /branches/NSGA-II Changes/HeuristicLab.Problems.BinPacking12033-12122
      /branches/ParallelEngine/HeuristicLab.Problems.BinPacking5175-5192
      /branches/ProblemInstancesRegressionAndClassification/HeuristicLab.Problems.BinPacking7568-7810
      /branches/QAPAlgorithms/HeuristicLab.Problems.BinPacking6350-6627
      /branches/Restructure trunk solution/HeuristicLab.Problems.BinPacking6828
      /branches/RuntimeOptimizer/HeuristicLab.Problems.BinPacking8943-9078
      /branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.BinPacking7787-8333
      /branches/SlaveShutdown/HeuristicLab.Problems.BinPacking8944-8956
      /branches/SpectralKernelForGaussianProcesses/HeuristicLab.Problems.BinPacking10204-10479
      /branches/SuccessProgressAnalysis/HeuristicLab.Problems.BinPacking5370-5682
      /branches/Trunk/HeuristicLab.Problems.BinPacking6829-6865
      /branches/UnloadJobs/HeuristicLab.Problems.BinPacking9168-9215
      /branches/VNS/HeuristicLab.Problems.BinPacking5594-5752
      /branches/crossvalidation-2434/HeuristicLab.Problems.BinPacking12948-12950
      /branches/histogram/HeuristicLab.Problems.BinPacking5959-6341
      /branches/symbreg-factors-2650/HeuristicLab.Problems.BinPacking14232-14825
      /trunk/sources/HeuristicLab.Problems.TestFunctions.MultiObjective/HeuristicLab.Problems.BinPacking14175
  • stable/HeuristicLab.Problems.BinPacking/3.3/3D/BinPacking3D.cs

    r14966 r15278  
    2020#endregion
    2121
     22using System;
    2223using System.Collections.Generic;
    2324using System.Linq;
     
    3233  public class BinPacking3D : BinPacking<PackingPosition, PackingShape, PackingItem> {
    3334
     35    [Storable]
     36    public Dictionary<PackingPosition, Tuple<int, int, int>> ResidualSpace { get; protected set; }
     37
    3438    public BinPacking3D(PackingShape binShape)
    3539      : base(binShape) {
    36       ExtremePoints = new SortedSet<PackingPosition>();
    37       ExtremePoints.Add(binShape.Origin);
     40      ResidualSpace = new Dictionary<PackingPosition, Tuple<int,int,int>>();
     41      AddExtremePoint(binShape.Origin);
    3842      InitializeOccupationLayers();
    3943    }
     
    4246    protected BinPacking3D(BinPacking3D original, Cloner cloner)
    4347      : base(original, cloner) {
    44       this.ExtremePoints = new SortedSet<PackingPosition>(original.ExtremePoints.Select(p => cloner.Clone(p)));
     48      this.ResidualSpace = new Dictionary<PackingPosition, Tuple<int, int, int>>();
     49      foreach (var o in original.ResidualSpace)
     50        this.ResidualSpace.Add(cloner.Clone(o.Key), Tuple.Create(o.Value.Item1, o.Value.Item2, o.Value.Item3));
    4551    }
    4652    public override IDeepCloneable Clone(Cloner cloner) {
    4753      return new BinPacking3D(this, cloner);
     54    }
     55
     56
     57    [StorableHook(HookType.AfterDeserialization)]
     58    private void AfterDeserialization() {
     59      // BackwardsCompatibility3.3
     60      #region Backwards compatible code, remove with 3.4
     61      if (ResidualSpace == null)
     62        ResidualSpace = new Dictionary<PackingPosition, Tuple<int, int, int>>();
     63      #endregion
     64    }
     65
     66    public override void PackItem(int itemID, PackingItem item, PackingPosition position) {
     67      ResidualSpace.Remove(position);
     68      base.PackItem(itemID, item, position);
    4869    }
    4970
     
    6081          current = PackingPosition.MoveDown(current);
    6182        }
    62         ExtremePoints.Add((PackingPosition)current.Clone());
     83        AddExtremePoint((PackingPosition)current.Clone());
    6384        while (current.X > 0 && !IsPointOccupied(PackingPosition.MoveLeft(current))) {
    6485          current = PackingPosition.MoveLeft(current);
    6586        }
    66         ExtremePoints.Add(current);
     87        AddExtremePoint(current);
    6788
    6889        //Traversing down the z-axis
     
    7192          current = PackingPosition.MoveBack(current);
    7293        }
    73         ExtremePoints.Add((PackingPosition)current.Clone());
    74         while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {
    75           current = PackingPosition.MoveDown(current);
    76         }
    77         ExtremePoints.Add(current);
     94        AddExtremePoint((PackingPosition)current.Clone());
     95        while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {
     96          current = PackingPosition.MoveDown(current);
     97        }
     98        AddExtremePoint(current);
    7899      }
    79100
     
    86107          current = PackingPosition.MoveLeft(current);
    87108        }
    88         ExtremePoints.Add((PackingPosition)current.Clone());
    89         while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {
    90           current = PackingPosition.MoveDown(current);
    91         }
    92         ExtremePoints.Add(current);
     109        AddExtremePoint((PackingPosition)current.Clone());
     110        while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {
     111          current = PackingPosition.MoveDown(current);
     112        }
     113        AddExtremePoint(current);
    93114
    94115        //Traversing down the z-axis
     
    97118          current = PackingPosition.MoveBack(current);
    98119        }
    99         ExtremePoints.Add((PackingPosition)current.Clone());
    100         while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {
    101           current = PackingPosition.MoveDown(current);
    102         }
    103         ExtremePoints.Add(current);
     120        AddExtremePoint((PackingPosition)current.Clone());
     121        while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {
     122          current = PackingPosition.MoveDown(current);
     123        }
     124        AddExtremePoint(current);
    104125      }
    105126
     
    112133          current = PackingPosition.MoveLeft(current);
    113134        }
    114         ExtremePoints.Add((PackingPosition)current.Clone());
    115         while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {
    116           current = PackingPosition.MoveDown(current);
    117         }
    118         ExtremePoints.Add(current);
     135        AddExtremePoint((PackingPosition)current.Clone());
     136        while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {
     137          current = PackingPosition.MoveDown(current);
     138        }
     139        AddExtremePoint(current);
    119140
    120141        //Traversing down the y-axis
     
    123144          current = PackingPosition.MoveDown(current);
    124145        }
    125         ExtremePoints.Add((PackingPosition)current.Clone());
     146        AddExtremePoint((PackingPosition)current.Clone());
    126147        while (current.X > 0 && !IsPointOccupied(PackingPosition.MoveLeft(current))) {
    127148          current = PackingPosition.MoveLeft(current);
    128149        }
    129         ExtremePoints.Add(current);
     150        AddExtremePoint(current);
     151      }
     152    }
     153
     154    private void AddExtremePoint(PackingPosition current) {
     155      if (ExtremePoints.Add(current)) {
     156        var tuple = Tuple.Create(BinShape.Width - current.X, BinShape.Height - current.Y, BinShape.Depth - current.Z);
     157        ResidualSpace.Add(current, tuple);
    130158      }
    131159    }
    132160
    133161    public override PackingPosition FindExtremePointForItem(PackingItem item, bool rotated, bool stackingConstraints) {
    134 
    135162      PackingItem newItem = new PackingItem(
    136163        rotated ? item.Depth : item.Width,
     
    139166        item.TargetBin, item.Weight, item.Material);
    140167
    141       int epIndex = 0;
    142       while (epIndex < ExtremePoints.Count && (
    143         !IsPositionFeasible(newItem, ExtremePoints.ElementAt(epIndex))
    144         || !IsSupportedByAtLeastOnePoint(newItem, ExtremePoints.ElementAt(epIndex))
    145         || (stackingConstraints && !IsStaticStable(newItem, ExtremePoints.ElementAt(epIndex)))
    146         || (stackingConstraints && !IsWeightSupported(newItem, ExtremePoints.ElementAt(epIndex)))
    147       )) { epIndex++; }
    148 
    149       if (epIndex < ExtremePoints.Count) {
    150         var origPoint = ExtremePoints.ElementAt(epIndex);
    151         var result = new PackingPosition(origPoint.AssignedBin, origPoint.X, origPoint.Y, origPoint.Z, rotated);
     168      var ep = ExtremePoints.Where(x => IsPositionFeasible(newItem, x, stackingConstraints)).FirstOrDefault();
     169      if (ep != null) {
     170        var result = new PackingPosition(ep.AssignedBin, ep.X, ep.Y, ep.Z, rotated);
    152171        return result;
    153172      }
     
    155174    }
    156175
    157     public override PackingPosition FindPositionBySliding(PackingItem item, bool rotated) {
    158       //TODO: does not support stacking constraints yet
     176    public override bool IsPositionFeasible(PackingItem item, PackingPosition position, bool stackingConstraints) {
     177      var feasible = base.IsPositionFeasible(item, position, stackingConstraints);
     178      return feasible
     179        && IsSupportedByAtLeastOnePoint(item, position)
     180        && (!stackingConstraints || (IsStaticStable(item, position) && IsWeightSupported(item, position)));
     181    }
     182
     183    public override PackingPosition FindPositionBySliding(PackingItem item, bool rotated, bool stackingConstraints) {
    159184      //Starting-position at upper right corner (=left bottom point of item-rectangle is at position item.width,item.height)
    160185      PackingPosition currentPosition = new PackingPosition(0,
     
    163188        BinShape.Depth - (rotated ? item.Width : item.Depth), rotated);
    164189      //Slide the item as far as possible to the bottom
    165       while (IsPositionFeasible(item, PackingPosition.MoveDown(currentPosition))
    166         || IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition))
    167         || IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition))) {
     190      while (IsPositionFeasible(item, PackingPosition.MoveDown(currentPosition), stackingConstraints)
     191        || IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition), stackingConstraints)
     192        || IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition), stackingConstraints)) {
    168193        //Slide the item as far as possible to the left
    169         while (IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition))
    170       || IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition))) {
     194        while (IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition), stackingConstraints)
     195      || IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition), stackingConstraints)) {
    171196          //Slide the item as far as possible to the back
    172           while (IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition))) {
     197          while (IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition), stackingConstraints)) {
    173198            currentPosition = PackingPosition.MoveBack(currentPosition);
    174199          }
    175           if (IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition)))
     200          if (IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition), stackingConstraints))
    176201            currentPosition = PackingPosition.MoveLeft(currentPosition);
    177202        }
    178         if (IsPositionFeasible(item, PackingPosition.MoveDown(currentPosition)))
     203        if (IsPositionFeasible(item, PackingPosition.MoveDown(currentPosition), stackingConstraints))
    179204          currentPosition = PackingPosition.MoveDown(currentPosition);
    180205      }
    181206
    182       return IsPositionFeasible(item, currentPosition) ? currentPosition : null;
    183     }
    184 
    185     public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items) {
     207      return IsPositionFeasible(item, currentPosition, stackingConstraints) ? currentPosition : null;
     208    }
     209
     210    public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints) {
    186211      var temp = new List<int>(sequence);
    187212      for (int i = 0; i < temp.Count; i++) {
    188213        var item = items[temp[i]];
    189         var position = FindPositionBySliding(item, false);
     214        var position = FindPositionBySliding(item, false, stackingConstraints);
    190215        if (position != null) {
    191216          PackItem(temp[i], item, position);
     
    194219      }
    195220    }
    196     public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items, Dictionary<int, bool> rotationArray) {
     221    public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items, Dictionary<int, bool> rotationArray, bool stackingConstraints) {
    197222      var temp = new List<int>(sequence);
    198223      for (int i = 0; i < temp.Count; i++) {
    199224        var item = items[temp[i]];
    200         var position = FindPositionBySliding(item, rotationArray[i]);
     225        var position = FindPositionBySliding(item, rotationArray[i], stackingConstraints);
    201226        if (position != null) {
    202227          PackItem(temp[i], item, position);
     
    212237        if (positionFound != null) {
    213238          PackItem(itemID, item, positionFound);
     239          if (Items.Count > 1)
     240            UpdateResidualSpace(item, positionFound);
    214241          sequence.Remove(itemID);
    215242        }
     
    227254      }
    228255    }
    229 
    230256    public override int ShortestPossibleSideFromPoint(PackingPosition position) {
    231257
     
    297323    }
    298324
    299 
    300325    protected override void InitializeOccupationLayers() {
    301326      for (int i = 0; i * 10 <= BinShape.Depth; i += 1) {
     
    320345      for (int i = z1; i <= z2; i++)
    321346        result.AddRange(OccupationLayers[i]);
    322 
    323347      return result;
    324348    }
     349   
     350    public void UpdateResidualSpace(PackingItem item, PackingPosition pos) {
     351      foreach (var ep in ExtremePoints) {
     352        if (ep.Z >= pos.Z && ep.Z <= pos.Z + item.Depth) {
     353          if (ep.X <= pos.X && ep.Y > pos.Y && ep.Y < pos.Y + item.Height) {
     354            var diff = pos.X - ep.X;
     355            var newRSX = ResidualSpace[ep].Item1 < diff ? ResidualSpace[ep].Item1 : diff;
     356            ResidualSpace[ep] = Tuple.Create(newRSX, ResidualSpace[ep].Item2, ResidualSpace[ep].Item3);
     357          }
     358          if (ep.Y <= pos.Y && ep.X > pos.X && ep.X < pos.X + item.Width) {
     359            var diff = pos.Y - ep.Y;
     360            var newRSY = ResidualSpace[ep].Item2 < diff ? ResidualSpace[ep].Item2 : diff;
     361            ResidualSpace[ep] = Tuple.Create(ResidualSpace[ep].Item1, newRSY, ResidualSpace[ep].Item3);
     362          }
     363        }
     364        if (ep.Z <= pos.Z &&
     365          ep.Y > pos.Y && ep.Y < pos.Y + item.Height &&
     366          ep.X > pos.X && ep.X < pos.X + item.Width) {
     367            var diff = pos.Z - ep.Z;
     368            var newRSZ = ResidualSpace[ep].Item3 < diff ? ResidualSpace[ep].Item3 : diff;
     369            ResidualSpace[ep] = Tuple.Create(ResidualSpace[ep].Item1, ResidualSpace[ep].Item2, newRSZ);
     370        }
     371      }
     372      return;
     373    }
    325374  }
    326 
    327375}
Note: See TracChangeset for help on using the changeset viewer.