Changeset 15454


Ignore:
Timestamp:
11/07/17 08:24:24 (3 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:
13 added
1 deleted
9 edited

Legend:

Unmodified
Added
Removed
  • branches/2817-BinPackingSpeedup/HeuristicLab 3.3.sln

    r15178 r15454  
    22Microsoft Visual Studio Solution File, Format Version 12.00
    33# Visual Studio 15
    4 VisualStudioVersion = 15.0.26430.15
     4VisualStudioVersion = 15.0.26228.9
    55MinimumVisualStudioVersion = 10.0.40219.1
    66Project("{2150E333-8FDC-42A3-9474-1A3956D46DE8}") = "Solution Items", "Solution Items", "{96396439-A764-4022-A8D2-BE021449B8D1}"
     
    462462EndProject
    463463Global
     464  GlobalSection(Performance) = preSolution
     465    HasPerformanceSessions = true
     466  EndGlobalSection
    464467  GlobalSection(SolutionConfigurationPlatforms) = preSolution
    465468    Debug|Any CPU = Debug|Any CPU
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking.Views/3.3/HeuristicLab.Problems.BinPacking.Views-3.3.csproj

    r15233 r15454  
    167167      <Name>HeuristicLab.Problems.BinPacking-3.3</Name>
    168168      <Private>False</Private>
     169    </ProjectReference>
     170    <ProjectReference Include="..\..\HeuristicLab.Problems.Instances.Views\3.3\HeuristicLab.Problems.Instances.Views-3.3.csproj">
     171      <Project>{B1BA398F-953F-4C3A-B07B-1E5E17A27DD9}</Project>
     172      <Name>HeuristicLab.Problems.Instances.Views-3.3</Name>
     173    </ProjectReference>
     174    <ProjectReference Include="..\..\HeuristicLab.Problems.Instances\3.3\HeuristicLab.Problems.Instances-3.3.csproj">
     175      <Project>{3540E29E-4793-49E7-8EE2-FEA7F61C3994}</Project>
     176      <Name>HeuristicLab.Problems.Instances-3.3</Name>
    169177    </ProjectReference>
    170178  </ItemGroup>
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/BinPacking3D.cs

    r15424 r15454  
    2727using HeuristicLab.Common;
    2828using HeuristicLab.Problems.BinPacking;
     29using HeuristicLab.Problems.BinPacking3D.Geometry;
    2930
    3031namespace HeuristicLab.Problems.BinPacking3D {
     
    3839    public BinPacking3D(PackingShape binShape)
    3940      : base(binShape) {
    40       ResidualSpace = new Dictionary<PackingPosition, Tuple<int,int,int>>();
     41      ResidualSpace = new Dictionary<PackingPosition, Tuple<int, int, int>>();
    4142      AddExtremePoint(binShape.Origin);
    4243      InitializeOccupationLayers();
     
    6364      #endregion
    6465    }
     66
     67    #region New methods for bin packer class
     68
     69    public void AddItem(int itemID, PackingItem item, PackingPosition position) {
     70      Items[itemID] = item;
     71      Positions[itemID] = position;
     72      ExtremePoints.Remove(position);
     73      ResidualSpace.Remove(position);
     74    }
     75
     76    public void UpdateExtremePoints(PackingItem item, PackingPosition position, bool stackingConstraints) {
     77      /*if (stackingConstraints) {
     78        AddExtremePoint(new PackingPosition(position.AssignedBin, position.X + item.Width, position.Y, position.Z));
     79        AddExtremePoint(new PackingPosition(position.AssignedBin, position.X, position.Y + item.Height, position.Z));
     80        AddExtremePoint(new PackingPosition(position.AssignedBin, position.X, position.Y, position.Z + item.Depth));
     81      } else {*/
     82      GenerateNewExtremePointsForNewItem(item, position);
     83
     84      // if an item is fit in below, before, or left of another its extreme points have to be regenerated
     85      foreach (var above in GetItemsAbove(position)) {
     86        GenerateNewExtremePointsForNewItem(above.Item2, above.Item1);
     87      }
     88      foreach (var front in GetItemsInfront(position)) {
     89        GenerateNewExtremePointsForNewItem(front.Item2, front.Item1);
     90      }
     91      foreach (var right in GetItemsOnRight(position)) {
     92        GenerateNewExtremePointsForNewItem(right.Item2, right.Item1);
     93      }
     94      //}
     95    }
     96
     97
     98
     99    /// <summary>
     100    /// In this case feasability is defined as following:
     101    /// 1. the item fits into the bin-borders;
     102    /// 2. the point is supported by something;
     103    /// 3. the item does not collide with another already packed item
     104    ///
     105    /// Unfortunatelly this method does not support item rotation
     106    /// </summary>
     107    /// <param name="item"></param>
     108    /// <param name="position"></param>
     109    /// <param name="stackingConstraints"></param>
     110    /// <returns></returns>
     111    public override bool IsPositionFeasible(PackingItem item, PackingPosition position, bool stackingConstraints) {
     112      var b1 = CheckItemDimensions(item);
     113      var b2 = ItemCanBePlaced(item, position);
     114      var b3 = CheckStackingConstraints(item, position, stackingConstraints);
     115
     116      return b1 && b2 && b3;
     117    }
     118
     119    /// <summary>
     120    /// Compares the dimensions of a given item and the current bin.
     121    /// </summary>
     122    /// <param name="item"></param>
     123    /// <returns>Returns true if the dimensions of an given item are less or equal to the bin.</returns>
     124    private bool CheckItemDimensions(PackingItem item) {
     125      return BinShape.Width >= item.Width && BinShape.Height >= item.Height && BinShape.Depth >= item.Depth;
     126    }
     127
     128    /// <summary>
     129    /// Returns true if a given item can be placed in the current bin
     130    /// </summary>
     131    /// <param name="givenItem"></param>
     132    /// <param name="givenItemPosition"></param>
     133    /// <returns></returns>
     134    private bool ItemCanBePlaced(PackingItem givenItem, PackingPosition givenItemPosition) {
     135      // Check if the boundings of the bin would injured
     136      if (givenItemPosition.X + givenItem.Width > BinShape.Width ||
     137          givenItemPosition.Y + givenItem.Height > BinShape.Height ||
     138          givenItemPosition.Z + givenItem.Depth > BinShape.Depth) {
     139        return false;
     140      }
     141
     142      //if the given item collides with any other item, it can not be placed
     143      foreach (var item in Items) {
     144        if (ItemsCollides(new Tuple<PackingPosition, PackingItem>(Positions[item.Key], item.Value),
     145                          new Tuple<PackingPosition, PackingItem>(givenItemPosition, givenItem))) {
     146          return false;
     147        }
     148      }
     149      return true;     
     150    }
     151
     152    /// <summary>
     153    /// Checks if two given items in a space collides
     154    /// </summary>
     155    /// <param name="t1"></param>
     156    /// <param name="t2"></param>
     157    /// <returns></returns>
     158    bool ItemsCollides(Tuple<PackingPosition, PackingItem> t1, Tuple<PackingPosition, PackingItem> t2) {
     159      var position1 = t1.Item1;
     160      var item1 = t1.Item2;
     161      var position2 = t2.Item1;
     162      var item2 = t2.Item2;
     163      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);
     164      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);
     165      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);
     166      return cx && cy && cz;
     167    }
     168
     169    /// <summary>
     170    /// Checks the stacking constraints. This method depends that the given item can be placed at this position
     171    /// </summary>
     172    /// <param name="item"></param>
     173    /// <param name="position"></param>
     174    /// <param name="stackingConstraints"></param>
     175    /// <returns></returns>
     176    private bool CheckStackingConstraints(PackingItem item, PackingPosition position, bool stackingConstraints) {
     177      if (position.Y == 0 || !stackingConstraints && HasOnePointWithAnItemBelow(item, position)) {
     178        return true;
     179      }
     180
     181      return IsStaticStable(item, position) && IsWeightSupported(item, position);
     182    }
     183
     184
     185    /// <summary>
     186    /// Checks if a given item has any point lieing on another item.
     187    /// </summary>
     188    /// <param name="item"></param>
     189    /// <param name="position"></param>
     190    /// <returns></returns>
     191    public bool HasOnePointWithAnItemBelow(PackingItem item, PackingPosition position) {
     192      bool p1, p2, p3, p4;
     193      PointsLiesOnAnItems(item, position, out p1, out p2, out p3, out p4);
     194
     195      return p1 || p2 || p3 || p4;
     196    }
     197
     198    /// <summary>
     199    /// Checks if a given item is static stable.
     200    /// A item is static stable if all edges have an object below.
     201    /// </summary>
     202    /// <param name="item"></param>
     203    /// <param name="position"></param>
     204    /// <returns></returns>
     205    public override bool IsStaticStable(PackingItem item, PackingPosition position) {
     206      bool p1, p2, p3, p4;
     207      PointsLiesOnAnItems(item, position, out p1, out p2, out p3, out p4);
     208      return p1 && p2 && p3 && p4;
     209    }
     210
     211    /// <summary>
     212    /// This method sets the out parameters p1 ... p3 if the point lies on another item.
     213    /// p1 ... p3 represents one point on the bottom side of an given item.
     214    /// +---------+
     215    /// |p1     p2|
     216    /// |         |
     217    /// |p4     p3|
     218    /// +---------+
     219    /// </summary>
     220    /// <param name="item">Given item</param>
     221    /// <param name="position">Given item position</param>
     222    /// <param name="p1"></param>
     223    /// <param name="p2"></param>
     224    /// <param name="p3"></param>
     225    /// <param name="p4"></param>
     226    public void PointsLiesOnAnItems(PackingItem item, PackingPosition position, out bool p1, out bool p2, out bool p3, out bool p4) {
     227      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP1;
     228      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP2;
     229      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP3;
     230      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP4;
     231
     232      GetItemsUnderItemWithContact(item, position, out itemsP1, out itemsP2, out itemsP3, out itemsP4);
     233
     234      p1 = itemsP1.Where(x => position.X < x.Item1.X + x.Item2.Width && position.Z < x.Item1.Z + x.Item2.Depth).Any();
     235      p2 = itemsP2.Where(x => position.X + item.Width > x.Item1.X && position.Z < x.Item1.Z + x.Item2.Depth).Any();
     236      p3 = itemsP3.Where(x => position.X + item.Width > x.Item1.X && position.Z + item.Depth > x.Item1.Z).Any();
     237      p4 = itemsP4.Where(x => position.X < x.Item1.X + x.Item2.Width && position.Z + item.Depth > x.Item1.Z).Any();
     238    }
     239
     240
     241    /// <summary>
     242    ///
     243    /// </summary>
     244    /// <param name="item"></param>
     245    /// <param name="position"></param>
     246    /// <param name="itemsP1"></param>
     247    /// <param name="itemsP2"></param>
     248    /// <param name="itemsP3"></param>
     249    /// <param name="itemsP4"></param>
     250    private void GetItemsUnderItemWithContact(PackingItem item, PackingPosition position,
     251                                   out IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP1,
     252                                   out IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP2,
     253                                   out IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP3,
     254                                   out IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP4) {
     255      itemsP1 = GetItemsBelowForPosition(new PackingPosition(0, position.X, position.Y, position.Z, false));
     256      itemsP2 = GetItemsBelowForPosition(new PackingPosition(0, position.X + item.Width - 1, position.Y, position.Z, false));
     257      itemsP3 = GetItemsBelowForPosition(new PackingPosition(0, position.X, position.Y, position.Z + item.Depth - 1, false));
     258      itemsP4 = GetItemsBelowForPosition(new PackingPosition(0, position.X + item.Width - 1, position.Y, position.Z + item.Depth - 1, false));
     259
     260    }
     261
     262    /// <summary>
     263    /// Returns a collection of items which are below a given point.
     264    /// The top side of every item is at the same level as the Y-coordinate of the given position.
     265    /// </summary>
     266    /// <param name="position"></param>
     267    /// <returns></returns>
     268    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBelowForPosition(PackingPosition position) {
     269      return GetItemsBelow(position).Where(x => (x.Item1.Y + x.Item2.Height) == position.Y);
     270    }
     271
     272
     273    /// <summary>
     274    /// Checks if a given the weight of an given item is supportet by the items below.
     275    /// </summary>
     276    /// <param name="item"></param>
     277    /// <param name="position"></param>
     278    /// <returns></returns>
     279    public bool IsWeightSupported(PackingItem item, PackingPosition position) {
     280      if (position.Y == 0) {
     281        return true;
     282      }
     283      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP1;
     284      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP2;
     285      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP3;
     286      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP4;
     287
     288      GetItemsUnderItemWithContact(item, position, out itemsP1, out itemsP2, out itemsP3, out itemsP4);
     289
     290      return itemsP1.Where(x => x.Item2.SupportsStacking(item)).Any() &&
     291        itemsP2.Where(x => x.Item2.SupportsStacking(item)).Any() &&
     292        itemsP3.Where(x => x.Item2.SupportsStacking(item)).Any() &&
     293        itemsP4.Where(x => x.Item2.SupportsStacking(item)).Any();
     294    }
     295
     296
     297
     298    #endregion
    65299
    66300    public override void PackItem(int itemID, PackingItem item, PackingPosition position) {
     
    83317    }
    84318
     319
     320
    85321    protected override void GenerateNewExtremePointsForNewItem(PackingItem newItem, PackingPosition position) {
    86322      int newWidth = position.Rotated ? newItem.Depth : newItem.Width;
     
    168404    }
    169405
     406
    170407    private bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, Tuple<int, int, int> residualSpace) {
    171408      var eps = ExtremePoints.Where(x => !pos.Equals(x) && pos.IsInside(x, ResidualSpace[x]));
     
    204441
    205442    #region Projections
    206        
     443
    207444    private Vector3D ProjectBackward(Vector3D pos) {
    208445      var line = new Line3D(pos, new Vector3D(0, 0, -1));
     
    268505    #region Get items
    269506
    270    
     507    /// <summary>
     508    ///
     509    /// </summary>
     510    /// <param name="pos"></param>
     511    /// <returns></returns>
    271512    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsAbove(PackingPosition pos) {
    272513      var line = new Line3D(pos, new Vector3D(0, 1, 0));
     
    298539        .Select(x => Tuple.Create(x.Position, x.Item));
    299540    }
     541
     542    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBelow(PackingPosition pos) {
     543      var line = new Line3D(pos, new Vector3D(0, 1, 0));
     544      return Items.Select(x => new {
     545        Item = x.Value,
     546        Position = Positions[x.Key],
     547        Intersection = line.Intersect(new Plane3D(Positions[x.Key], x.Value, Side.Top))
     548      }).Where(x => x.Intersection != null && x.Intersection.Y <= pos.Y)
     549        .Select(x => Tuple.Create(x.Position, x.Item));
     550    }
     551
     552    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBehind(PackingPosition pos) {
     553      var line = new Line3D(pos, new Vector3D(0, 0, 1));
     554      return Items.Select(x => new {
     555        Item = x.Value,
     556        Position = Positions[x.Key],
     557        Intersection = line.Intersect(new Plane3D(Positions[x.Key], x.Value, Side.Front))
     558      }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
     559        .Select(x => Tuple.Create(x.Position, x.Item));
     560    }
     561
     562    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsOnLeft(PackingPosition pos) {
     563      var line = new Line3D(pos, new Vector3D(1, 0, 0));
     564      return Items.Select(x => new {
     565        Item = x.Value,
     566        Position = Positions[x.Key],
     567        Intersection = line.Intersect(new Plane3D(Positions[x.Key], x.Value, Side.Right))
     568      }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
     569        .Select(x => Tuple.Create(x.Position, x.Item));
     570    }
     571
    300572    #endregion
     573
     574
    301575
    302576    public override PackingPosition FindExtremePointForItem(PackingItem item, bool rotated, bool stackingConstraints) {
     
    316590    }
    317591
    318     public override bool IsPositionFeasible(PackingItem item, PackingPosition position, bool stackingConstraints) {
    319       var feasible = base.IsPositionFeasible(item, position, stackingConstraints);
    320       return feasible
    321         && IsSupportedByAtLeastOnePoint(item, position)
    322         && (!stackingConstraints || (IsStaticStable(item, position) && IsWeightSupported(item, position)));
    323     }
     592 
    324593
    325594    #region Sliding based packing   
     
    425694      return shortestSide;
    426695    }
    427     public override bool IsStaticStable(PackingItem item, PackingPosition position) {
    428       //Static stability is given, if item is placed on the ground
    429       if (position.Y == 0)
    430         return true;
    431 
    432       if (IsPointOccupied(new PackingPosition(0, position.X, position.Y - 1, position.Z))
    433         && IsPointOccupied(new PackingPosition(0, position.X + item.Width - 1, position.Y - 1, position.Z))
    434         && IsPointOccupied(new PackingPosition(0, position.X, position.Y - 1, position.Z + item.Depth - 1))
    435         && IsPointOccupied(new PackingPosition(0, position.X + item.Width - 1, position.Y - 1, position.Z + item.Depth - 1)))
    436         return true;
    437 
    438       return false;
    439     }
    440 
    441     public bool IsSupportedByAtLeastOnePoint(PackingItem item, PackingPosition position) {
    442       if (position.Y == 0)
    443         return true;
    444 
    445       int y = position.Y - 1;
    446       for (int x = position.X; x < position.X + item.Width; x++)
    447         for (int z = position.Z; z < position.Z + item.Depth; z++)
    448           if (IsPointOccupied(new PackingPosition(0, x, y, z)))
    449             return true;
    450 
    451       return false;
    452     }
    453     public bool IsWeightSupported(PackingItem item, PackingPosition ep) {
    454       if (ep.Y == 0)
    455         return true;
    456 
    457       if (Items[PointOccupation(new PackingPosition(0, ep.X, ep.Y - 1, ep.Z))].SupportsStacking(item)
    458         && Items[PointOccupation(new PackingPosition(0, ep.X + item.Width - 1, ep.Y - 1, ep.Z))].SupportsStacking(item)
    459         && Items[PointOccupation(new PackingPosition(0, ep.X, ep.Y - 1, ep.Z + item.Depth - 1))].SupportsStacking(item)
    460         && Items[PointOccupation(new PackingPosition(0, ep.X + item.Width - 1, ep.Y - 1, ep.Z + item.Depth - 1))].SupportsStacking(item))
    461         return true;
    462 
    463       return false;
    464     }
     696   
    465697
    466698    protected override void InitializeOccupationLayers() {
     
    488720      return result;
    489721    }
    490    
     722
    491723    public void UpdateResidualSpace(PackingItem item, PackingPosition pos) {
    492724      foreach (var ep in ExtremePoints.ToList()) {
     
    509741          }
    510742        }
    511         if (ep.Z <= pos.Z &&
     743
     744        if (ep.Z <= pos.Z &&
    512745            ep.Y >= pos.Y && ep.Y < pos.Y + item.Height &&
    513746            ep.X >= pos.X && ep.X < pos.X + width) {
     
    517750          changed = true;
    518751        }
     752
    519753        if (changed) {
    520754          if (IsNonZero(rs) && !IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep), rs)) {
     
    529763    }
    530764
    531     #region Helper classes for vector math
    532     private class Vector3D {
    533       public int X;
    534       public int Y;
    535       public int Z;
    536       public Vector3D() { }
    537       public Vector3D(int x, int y, int z) {
    538         X = x;
    539         Y = y;
    540         Z = z;
    541       }
    542       public Vector3D(PackingPosition pos) {
    543         X = pos.X;
    544         Y = pos.Y;
    545         Z = pos.Z;
    546       }
    547       public static Vector3D AlongX(Vector3D pos, PackingItem item) {
    548         return new Vector3D(
    549           pos.X + item.Width,
    550           pos.Y,
    551           pos.Z
    552         );
    553       }
    554       public static Vector3D AlongY(Vector3D pos, PackingItem item) {
    555         return new Vector3D(
    556           pos.X,
    557           pos.Y + item.Height,
    558           pos.Z
    559         );
    560       }
    561       public static Vector3D AlongZ(Vector3D pos, PackingItem item) {
    562         return new Vector3D(
    563           pos.X,
    564           pos.Y,
    565           pos.Z + item.Depth
    566         );
    567       }
    568       public static Vector3D AlongX(PackingPosition pos, PackingItem item) {
    569         return new Vector3D(
    570           pos.X + item.Width,
    571           pos.Y,
    572           pos.Z
    573         );
    574       }
    575       public static Vector3D AlongY(PackingPosition pos, PackingItem item) {
    576         return new Vector3D(
    577           pos.X,
    578           pos.Y + item.Height,
    579           pos.Z
    580         );
    581       }
    582       public static Vector3D AlongZ(PackingPosition pos, PackingItem item) {
    583         return new Vector3D(
    584           pos.X,
    585           pos.Y,
    586           pos.Z + item.Depth
    587         );
    588       }
    589 
    590       public Vector3D Cross(Vector3D b) {
    591         return new Vector3D(
    592           Y * b.Z - Z * b.Y,
    593           -X * b.Z + Z * b.X,
    594           X * b.Y - Y * b.X
    595         );
    596       }
    597 
    598       public bool IsInside(PackingPosition pos, Tuple<int, int, int> rs) {
    599         return X >= pos.X && X < pos.X + rs.Item1
    600           && Y >= pos.Y && Y < pos.Y + rs.Item2
    601           && Z >= pos.Z && Z < pos.Z + rs.Item3;
    602       }
    603 
    604       public static int operator *(Vector3D a, Vector3D b) {
    605         return a.X * b.X + a.Y * b.Y + a.Z * b.Z;
    606       }
    607       public static Vector3D operator *(int a, Vector3D b) {
    608         return new Vector3D(a * b.X, a * b.Y, a * b.Z);
    609       }
    610       public static Vector3D operator *(Vector3D a, int b) {
    611         return new Vector3D(a.X * b, a.Y * b, a.Z * b);
    612       }
    613       public static Vector3D operator +(Vector3D a, Vector3D b) {
    614         return new Vector3D(a.X + b.X, a.Y + b.Y, a.Z + b.Z);
    615       }
    616       public static Vector3D operator -(Vector3D a, Vector3D b) {
    617         return new Vector3D(a.X - b.X, a.Y - b.Y, a.Z - b.Z);
    618       }
    619 
    620       public override bool Equals(object obj) {
    621         var packPos = obj as PackingPosition;
    622         if (packPos != null) {
    623           return X == packPos.X && Y == packPos.Y && Z == packPos.Z;
    624         }
    625         var vec = obj as Vector3D;
    626         if (vec != null) {
    627           return X == vec.X && Y == vec.Y && Z == vec.Z;
    628         }
    629         return false;
    630       }
    631     }
    632 
    633     // A line is given as a point and a directing vector
    634     private class Line3D {
    635       public Vector3D Point;
    636       public Vector3D Direction;
    637 
    638       public Line3D(Vector3D point, Vector3D direction) {
    639         Point = point;
    640         Direction = direction;
    641       }
    642       public Line3D(PackingPosition position, Vector3D direction) {
    643         Point = new Vector3D(position);
    644         Direction = direction;
    645       }
    646 
    647       public bool Intersects(Plane3D plane) {
    648         return plane.Intersects(this);
    649       }
    650 
    651       public Vector3D Intersect(Plane3D plane) {
    652         return plane.Intersect(this);
    653       }
    654     }
    655 
    656     private enum Side { Top, Left, Bottom, Right, Front, Back }
    657     // A plane is given as a point and two directing vectors
    658     private class Plane3D {
    659       public Vector3D Point { get; private set; }
    660       public Vector3D Direction1 { get; private set; }
    661       public Vector3D Direction2 { get; private set; }
    662       public Vector3D Normal { get; private set; }
    663       private int rhs;
    664 
    665       public Plane3D(PackingShape bin, Side side) {
    666         switch (side) {
    667           case Side.Top: // ZX plane
    668             Point = new Vector3D(0, bin.Height, 0);
    669             Direction1 = new Vector3D(0, 0, bin.Depth);
    670             Direction2 = new Vector3D(bin.Width, 0, 0);
    671             break;
    672           case Side.Left: // ZY plane
    673             Point = new Vector3D(0, 0, 0);
    674             Direction1 = new Vector3D(0, 0, bin.Depth);
    675             Direction2 = new Vector3D(0, bin.Height, 0);
    676             break;
    677           case Side.Bottom: // XZ plane
    678             Point = new Vector3D(0, 0, 0);
    679             Direction1 = new Vector3D(bin.Width, 0, 0);
    680             Direction2 = new Vector3D(0, 0, bin.Depth);
    681             break;
    682           case Side.Right: // YZ plane
    683             Point = new Vector3D(bin.Width, 0, 0);
    684             Direction1 = new Vector3D(0, bin.Height, 0);
    685             Direction2 = new Vector3D(0, 0, bin.Depth);
    686             break;
    687           case Side.Front: // XY plane
    688             Point = new Vector3D(0, 0, bin.Depth);
    689             Direction1 = new Vector3D(bin.Width, 0, 0);
    690             Direction2 = new Vector3D(0, bin.Height, 0);
    691             break;
    692           case Side.Back: // YX plane
    693             Point = new Vector3D(0, 0, 0);
    694             Direction1 = new Vector3D(0, bin.Height, 0);
    695             Direction2 = new Vector3D(bin.Width, 0, 0);
    696             break;
    697         }
    698         Normal = Direction1.Cross(Direction2);
    699         rhs = 0;
    700       }
    701 
    702       public Plane3D(PackingPosition pos, PackingItem item, Side side) {
    703         // the directing vectors are chosen such that normal always points outside the packing item
    704         switch (side) {
    705           case Side.Top: // ZX plane
    706             Point = new Vector3D(pos.X, pos.Y + item.Height, pos.Z);
    707             Direction1 = new Vector3D(0, 0, pos.Rotated ? item.Width : item.Depth);
    708             Direction2 = new Vector3D(pos.Rotated ? item.Depth : item.Width, 0, 0);
    709             break;
    710           case Side.Left: // ZY plane
    711             Point = new Vector3D(pos.X, pos.Y, pos.Z);
    712             Direction1 = new Vector3D(0, 0, pos.Rotated ? item.Width : item.Depth);
    713             Direction2 = new Vector3D(0, item.Height, 0);
    714             break;
    715           case Side.Bottom: // XZ plane
    716             Point = new Vector3D(pos.X, pos.Y, pos.Z);
    717             Direction1 = new Vector3D(pos.Rotated ? item.Depth : item.Width, 0, 0);
    718             Direction2 = new Vector3D(0, 0, pos.Rotated ? item.Width : item.Depth);
    719             break;
    720           case Side.Right: // YZ plane
    721             Point = new Vector3D(pos.X + (pos.Rotated ? item.Depth : item.Width), pos.Y, pos.Z);
    722             Direction1 = new Vector3D(0, item.Height, 0);
    723             Direction2 = new Vector3D(0, 0, pos.Rotated ? item.Width : item.Depth);
    724             break;
    725           case Side.Front: // XY plane
    726             Point = new Vector3D(pos.X, pos.Y, pos.Z + (pos.Rotated ? item.Width : item.Depth));
    727             Direction1 = new Vector3D(pos.Rotated ? item.Depth : item.Width, 0, 0);
    728             Direction2 = new Vector3D(0, item.Height, 0);
    729             break;
    730           case Side.Back: // YX plane
    731             Point = new Vector3D(pos.X, pos.Y, pos.Z);
    732             Direction1 = new Vector3D(0, item.Height, 0);
    733             Direction2 = new Vector3D(pos.Rotated ? item.Depth : item.Width, 0, 0);
    734             break;
    735         }
    736         Normal = Direction1.Cross(Direction2);
    737         rhs = Normal.X * Point.X + Normal.Y * Point.Y + Normal.Z * Point.Z;
    738       }
    739 
    740       public bool IsElementOf(Vector3D point) {
    741         return Normal.X * point.X + Normal.Y * point.Y + Normal.Z * point.Z == rhs;
    742       }
    743 
    744       public bool Intersects(Line3D line) {
    745         return Intersect(line) != null;
    746       }
    747 
    748       public Vector3D Intersect(Line3D line) {
    749         var denom = Normal * line.Direction;
    750         if (denom == 0) {
    751           // dir is perpendicular to the normal vector of the plane
    752           // this means they intersect if p1 is element of the plane
    753           // also the plane does not stretch infinitely, but is bound
    754           // to the parallelogram spanned by the point and the two
    755           // directing vectors
    756           if (IsElementOf(line.Point) && IsWithinDirectionalVectors(line.Point))
    757             return line.Point;
    758           else return null;
    759         }
    760         var intersect = line.Point + ((Normal * (Point - line.Point)) / denom) * line.Direction;
    761         if (IsWithinDirectionalVectors(intersect)) return intersect;
    762         return null;
    763       }
    764 
    765       public bool IsWithinDirectionalVectors(Vector3D point) {
    766         return point.X >= Point.X && (Direction1.X + Direction2.X == 0 || (point.X < Point.X + Direction1.X || point.X < Point.X + Direction2.X))
    767             && point.Y >= Point.Y && (Direction1.Y + Direction2.Y == 0 || (point.Y < Point.Y + Direction1.Y || point.Y < Point.Y + Direction2.Y))
    768             && point.Z >= Point.Z && (Direction1.Z + Direction2.Z == 0 || (point.Z < Point.Z + Direction1.Z || point.Z < Point.Z + Direction2.Z));
    769       }
    770     }
    771     #endregion
     765
    772766  }
    773767}
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Instances/RandomInstanceProvider.cs

    r15418 r15454  
    2626using System.IO;
    2727using System.Linq;
     28using System.Reflection;
    2829using HeuristicLab.Common;
    2930using HeuristicLab.Core;
    3031using HeuristicLab.Problems.Instances;
    3132using HeuristicLab.Random;
    32 
    33 namespace HeuristicLab.Problems.BinPacking3D {
     33using HeuristicLab.Problems.BinPacking.Random;
     34
     35namespace HeuristicLab.Problems.BinPacking3D.Instances {
    3436  // make sure that for each class we have a separate entry in the problem instance providers
     37
    3538  public class RandomInstanceClass1Provider : RandomInstanceProvider {
    36     public RandomInstanceClass1Provider() : base() { @class = 1; binWidth = binHeight = binDepth = 100; }
    37   }
     39    public RandomInstanceClass1Provider() : base(new SRand48()) { @class = 1; binWidth = binHeight = binDepth = 100; }
     40
     41  }
     42
    3843  public class RandomInstanceClass2Provider : RandomInstanceProvider {
    39     public RandomInstanceClass2Provider() : base() { @class = 2; binWidth = binHeight = binDepth = 100; }
     44    public RandomInstanceClass2Provider() : base(new SRand48()) { @class = 2; binWidth = binHeight = binDepth = 100; }
     45
    4046  }
    4147  public class RandomInstanceClass3Provider : RandomInstanceProvider {
    42     public RandomInstanceClass3Provider() : base() { @class = 3; binWidth = binHeight = binDepth = 100; }
     48    public RandomInstanceClass3Provider() : base(new SRand48()) { @class = 3; binWidth = binHeight = binDepth = 100; }
     49
    4350  }
    4451  public class RandomInstanceClass4Provider : RandomInstanceProvider {
    45     public RandomInstanceClass4Provider() : base() { @class = 4; binWidth = binHeight = binDepth = 100; }
     52    public RandomInstanceClass4Provider() : base(new SRand48()) { @class = 4; binWidth = binHeight = binDepth = 100; }
     53
    4654  }
    4755  public class RandomInstanceClass5Provider : RandomInstanceProvider {
    48     public RandomInstanceClass5Provider() : base() { @class = 5; binWidth = binHeight = binDepth = 100; }
     56    public RandomInstanceClass5Provider() : base(new SRand48()) { @class = 5; binWidth = binHeight = binDepth = 100; }
     57
    4958  }
    5059
    5160  public class RandomInstanceClass6Provider : RandomInstanceProvider {
    52     public RandomInstanceClass6Provider() : base() {
     61    public RandomInstanceClass6Provider() : base(new SRand48()) {
    5362      @class = 6;
    5463      binWidth = binHeight = binDepth = 10;
    5564    }
    5665    protected override void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
    57       w = rand.Next(1, 11);
    58       h = rand.Next(1, 11);
    59       d = rand.Next(1, 11);
     66      w = rand.Next(1, 10);
     67      h = rand.Next(1, 10);
     68      d = rand.Next(1, 10);
    6069    }
    6170  }
    6271  public class RandomInstanceClass7Provider : RandomInstanceProvider {
    63     public RandomInstanceClass7Provider() : base() {
     72    public RandomInstanceClass7Provider() : base(new SRand48()) {
    6473      @class = 7;
    6574      binWidth = binHeight = binDepth = 40;
    6675    }
    6776    protected override void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
    68       w = rand.Next(1, 36);
    69       h = rand.Next(1, 36);
    70       d = rand.Next(1, 36);
     77      w = rand.Next(1, 35);
     78      h = rand.Next(1, 35);
     79      d = rand.Next(1, 35);
    7180    }
    7281  }
    7382  public class RandomInstanceClass8Provider : RandomInstanceProvider {
    74     public RandomInstanceClass8Provider() : base() {
     83    public RandomInstanceClass8Provider() : base(new SRand48()) {
    7584      @class = 8;
    7685      binWidth = binHeight = binDepth = 100;
    7786    }
    7887    protected override void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
    79       w = rand.Next(1, 101);
    80       h = rand.Next(1, 101);
    81       d = rand.Next(1, 101);
     88      w = rand.Next(1, 100);
     89      h = rand.Next(1, 100);
     90      d = rand.Next(1, 100);
    8291    }
    8392  }
     
    8897  public abstract class RandomInstanceProvider : ProblemInstanceProvider<BPPData>, IProblemInstanceProvider<BPPData> {
    8998
     99    /// <summary>
     100    /// Number of created test items. This items are used for packing them into the bin
     101    /// </summary>
     102    private readonly int[] _numberOfGeneratedTestItems = new int[] { 10, 15, 20, 25, 30, 35, 40, 45, 50, 60, 70, 80, 90, 100, 150, 200 };
     103
     104    /// <summary>
     105    /// Number of instance for which should be created for each instance
     106    /// </summary>
     107    private readonly int _numberOfGeneratedInstances;
     108
     109    /// <summary>
     110    /// Random generator for creating random packing items.
     111    /// </summary>
     112    private readonly IRandom _randomGenerator;
    90113
    91114
     
    93116    protected int binWidth, binHeight, binDepth;
    94117
     118    #region Common information for displaying on the ui
     119
    95120    public override string Name {
    96121      get { return string.Format("Martello, Pisinger, Vigo (class={0})", @class); }
     
    109134    }
    110135
    111     public RandomInstanceProvider() : base() { }
    112 
     136    #endregion
     137
     138
     139    public RandomInstanceProvider(IRandom randomGenerator, int numberOfGeneratedInstances = 10, int[] numberOfGeneratedTestItems = null) : base() {
     140      _numberOfGeneratedInstances = numberOfGeneratedInstances;
     141      if (numberOfGeneratedTestItems != null) {
     142        _numberOfGeneratedTestItems = numberOfGeneratedTestItems;
     143      }
     144      _randomGenerator = randomGenerator;
     145    }
     146
     147
     148    /// <summary>
     149    /// Returns a collection of data descriptors. Each descriptor contains the seed for the random generator.
     150    /// </summary>
     151    /// <returns></returns>
    113152    public override IEnumerable<IDataDescriptor> GetDataDescriptors() {
    114153      // 10 classes
    115       var rand = new MersenneTwister(1234); // fixed seed to makes sure that instances are always the same
    116       foreach (int numItems in new int[] { 10, 15, 20, 25, 30, 35, 40, 45, 50, 60, 70, 80, 90 }) {
    117         // get class parameters
    118         // generate 30 different instances for each class
    119         foreach (int instance in Enumerable.Range(1, 30)) {
     154      foreach (int numItems in _numberOfGeneratedTestItems) {
     155        for (int instance = 1; instance <= _numberOfGeneratedInstances; instance++) {
    120156          string name = string.Format("n={0}-id={1:00} (class={2})", numItems, instance, @class);
    121           var dd = new RandomDataDescriptor(name, name, numItems, @class, seed: rand.Next());
    122           yield return dd;
     157          /* As in the test programm of Silvano Martello, David Pisinger, Daniele Vigo given,
     158           * the seed of the instance provider will be calculated by adding the number of generated items and teh instance number.
     159           * This guarantees that the instances will always be the same
     160           */
     161          yield return new RandomDataDescriptor(name, name, numItems, @class, seed: numItems + instance);
    123162        }
    124163      }
    125164    }
     165
    126166
    127167    public override BPPData LoadData(IDataDescriptor dd) {
    128168      var randDd = dd as RandomDataDescriptor;
    129       if (randDd == null)
     169      if (randDd == null) {
    130170        throw new NotSupportedException("Cannot load data descriptor " + dd);
     171      }
    131172
    132173      var data = new BPPData() {
     
    134175        Items = new PackingItem[randDd.NumItems]
    135176      };
    136       var instanceRand = new MersenneTwister((uint)randDd.Seed);
     177      _randomGenerator.Reset(randDd.Seed);
    137178      for (int i = 0; i < randDd.NumItems; i++) {
    138179        int w, h, d;
    139         SampleItemParameters(instanceRand, out w, out h, out d);
     180        SampleItemParameters(_randomGenerator, out w, out h, out d);
    140181        data.Items[i] = new PackingItem(w, h, d, data.BinShape);
    141182      }
     
    143184    }
    144185
    145     // default implementation for class 1 .. 5
     186
     187    /// <summary>
     188    /// Generates the dimensions for a item by using the given random generator
     189    /// </summary>
     190    /// <param name="rand">Given random generator</param>
     191    /// <param name="w">Calculated width of the item</param>
     192    /// <param name="h">Calculated height of the item</param>
     193    /// <param name="d">Calculated depth of the item</param>
    146194    protected virtual void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
    147       // for classes 1 - 5
    148195      Contract.Assert(@class >= 1 && @class <= 5);
    149       var weights = new double[] { 0.1, 0.1, 0.1, 0.1, 0.1 };
     196      /*var weights = new double[] { 0.1, 0.1, 0.1, 0.1, 0.1 };
    150197      weights[@class - 1] = 0.6;
    151198      var type = Enumerable.Range(1, 5).SampleProportional(rand, 1, weights).First();
    152 
    153       int minW, maxW;
    154       int minH, maxH;
    155       int minD, maxD;
    156       GetItemParameters(type, rand, binWidth, binHeight, binDepth,
    157         out minW, out maxW, out minH, out maxH, out minD, out maxD);
    158 
    159       w = rand.Next(minW, maxW + 1);
    160       h = rand.Next(minH, maxH + 1);
    161       d = rand.Next(minD, maxD + 1);
    162     }
    163 
    164     private void GetItemParameters(int type, IRandom rand,
    165       int w, int h, int d,
    166       out int minW, out int maxW, out int minH, out int maxH, out int minD, out int maxD) {
     199      */
     200
     201      // as by Martello and Vigo
     202      int type = @class;
     203      if (type <= 5) {
     204        var t = rand.Next(1, 10);
     205        if (t <= 5) {
     206          type = t;
     207        }
     208      }
     209
    167210      switch (type) {
    168         case 1: {
    169             minW = 1;
    170             maxW = w / 2; // integer division on purpose (see paper)
    171             minH = h * 2 / 3;
    172             maxH = h;
    173             minD = d * 2 / 3;
    174             maxD = d;
    175             break;
    176           }
    177         case 2: {
    178             minW = w * 2 / 3;
    179             maxW = w;
    180             minH = 1;
    181             maxH = h / 2;
    182             minD = d * 2 / 3;
    183             maxD = d;
    184             break;
    185           }
    186         case 3: {
    187             minW = w * 2 / 3;
    188             maxW = w;
    189             minH = h * 2 / 3;
    190             maxH = h;
    191             minD = 1;
    192             maxD = d / 2;
    193             break;
    194           }
    195         case 4: {
    196             minW = w / 2;
    197             maxW = w;
    198             minH = h / 2;
    199             maxH = h;
    200             minD = d / 2;
    201             maxD = d;
    202             break;
    203           }
    204         case 5: {
    205             minW = 1;
    206             maxW = w / 2;
    207             minH = 1;
    208             maxH = h / 2;
    209             minD = 1;
    210             maxD = d / 2;
    211             break;
    212           }
    213         default: {
    214             throw new InvalidProgramException();
    215           }
    216       }
    217     }
     211        case 1:
     212          CreateInstanceDimensionsType1(rand, out w, out h, out d);
     213          break;
     214        case 2:
     215          CreateInstanceDimensionsType2(rand, out w, out h, out d);
     216          break;
     217        case 3:
     218          CreateInstanceDimensionsType3(rand, out w, out h, out d);
     219          break;
     220        case 4:
     221          CreateInstanceDimensionsType4(rand, out w, out h, out d);
     222          break;
     223        case 5:
     224          CreateInstanceDimensionsType5(rand, out w, out h, out d);
     225          break;
     226        default:
     227          throw new InvalidProgramException();
     228      }
     229    }
     230
     231
     232    #region Instance dimensions generators for type 1 - 5
     233    private void CreateInstanceDimensionsType1(IRandom rand, out int w, out int h, out int d) {
     234      w = rand.Next(1, binWidth / 2);
     235      h = rand.Next((binHeight * 2) / 3, binHeight);
     236      d = rand.Next((binDepth * 2) / 3, binDepth);
     237    }
     238
     239    private void CreateInstanceDimensionsType2(IRandom rand, out int w, out int h, out int d) {
     240      w = rand.Next(((binWidth * 2) / 3), binWidth);
     241      h = rand.Next(1, binHeight / 2);
     242      d = rand.Next(((binDepth * 2) / 3), binDepth);
     243    }
     244
     245    private void CreateInstanceDimensionsType3(IRandom rand, out int w, out int h, out int d) {
     246      w = rand.Next(((binWidth * 2) / 3), binWidth);
     247      h = rand.Next(((binHeight * 2) / 3), binHeight);
     248      d = rand.Next(1, binDepth / 2);
     249    }
     250    private void CreateInstanceDimensionsType4(IRandom rand, out int w, out int h, out int d) {
     251      w = rand.Next(binWidth / 2, binWidth);
     252      h = rand.Next(binHeight / 2, binHeight);
     253      d = rand.Next(binDepth / 2, binDepth);
     254    }
     255    private void CreateInstanceDimensionsType5(IRandom rand, out int w, out int h, out int d) {
     256      w = rand.Next(1, binWidth / 2);
     257      h = rand.Next(1, binHeight / 2);
     258      d = rand.Next(1, binDepth / 2);
     259    }
     260
     261    #endregion
     262
     263
    218264
    219265    public override bool CanImportData {
     
    242288          else
    243289            writer.WriteLine("{0,-5} {1,-5} {2,-5}", instance.Items[i].Width, instance.Items[i].Height, instance.Items[i].Depth);
    244 
    245290        }
    246291        writer.Flush();
    247292      }
    248293    }
    249 
    250294  }
    251295}
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/PackingPosition.cs

    r15304 r15454  
    103103    #region IComparable<PackingPosition> Members
    104104
     105    /// <summary>
     106    /// Compares two packing positions by their coordinates.
     107    /// The order of comparing is z -> x -> y.
     108    /// </summary>
     109    /// <param name="other"></param>
     110    /// <returns></returns>
    105111    public int CompareTo(PackingPosition other) {
    106112      int result = Z.CompareTo(other.Z);
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/Algorithms/3D/ExtremePointAlgorithm.cs

    r15229 r15454  
    3232using HeuristicLab.Parameters;
    3333using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     34using HeuristicLab.Problems.BinPacking3D.Packer;
    3435
    3536namespace HeuristicLab.Problems.BinPacking3D {
    36  
     37
    3738  public enum SortingMethod { All, Given, VolumeHeight, HeightVolume, AreaHeight, HeightArea, ClusteredAreaHeight, ClusteredHeightArea }
    3839  public enum FittingMethod { All, FirstFit, ResidualSpaceBestFit, FreeVolumeBestFit }
     
    8687      Parameters.Add(fittingMethodParameter = new ValueParameter<EnumValue<FittingMethod>>("FittingMethod", "Which method to fit should be used.", new EnumValue<FittingMethod>(FittingMethod.All)));
    8788      Parameters.Add(deltaParameter = new ValueParameter<PercentValue>("Delta", "[1;100]% Clustered sorting methods use a delta parameter to determine the clusters.", new PercentValue(.1)));
    88      
     89
    8990      Problem = new PermutationProblem();
    9091    }
     
    9394      return new ExtremePointAlgorithm(this, cloner);
    9495    }
    95    
     96
    9697    [StorableHook(HookType.AfterDeserialization)]
    9798    private void AfterDeserialization() {
    9899    }
    99100
     101    /// <summary>
     102    /// Runs the extreme point algorithm and adds the results to the property <see cref="Result"/>
     103    /// </summary>
     104    /// <param name="token"></param>
    100105    protected override void Run(CancellationToken token) {
    101106      var items = Problem.Items;
     
    109114        fitting = Enum.GetValues(typeof(FittingMethod)).Cast<FittingMethod>().Where(x => x != FittingMethod.All).ToArray();
    110115      }
     116
     117      //
    111118      var result = GetBest(bin, items, sorting, fitting, token);
    112       if (result == null) throw new InvalidOperationException("No result obtained!");
    113 
    114       Results.Add(new Result("Best Solution",
    115         "The best found solution",
    116         result.Item1));
    117       Results.Add(new Result("Best Solution Quality",
    118         "The quality of the best found solution according to the evaluator",
    119         new DoubleValue(result.Item2)));
     119      if (result == null) {
     120        throw new InvalidOperationException("No result obtained!");
     121      }
     122
     123      Results.Add(new Result("Best Solution", "The best found solution", result.Item1));
     124      Results.Add(new Result("Best Solution Quality", "The quality of the best found solution according to the evaluator", new DoubleValue(result.Item2)));
    120125
    121126      var binUtil = new BinUtilizationEvaluator();
     
    128133        new PercentValue(Math.Round(binUtil.Evaluate(result.Item1), 3))));
    129134
    130       if (result.Item3.HasValue && sorting.Length > 1)
     135      if (result.Item3.HasValue && sorting.Length > 1) {
    131136        Results.Add(new Result("Best Sorting Method",
    132137          "The sorting method that found the best solution",
    133138          new EnumValue<SortingMethod>(result.Item3.Value)));
    134       if (result.Item4.HasValue && fitting.Length > 1)
     139      }
     140
     141      if (result.Item4.HasValue && fitting.Length > 1) {
    135142        Results.Add(new Result("Best Fitting Method",
    136143          "The fitting method that found the best solution",
    137144          new EnumValue<FittingMethod>(result.Item4.Value)));
     145      }
    138146    }
    139147
     
    146154        foreach (var sort in sortings) {
    147155          var result = Optimize(bin, items, sort, fit, DeltaParameter.Value.Value, Problem.UseStackingConstraints, Problem.SolutionEvaluator, token);
    148           if (double.IsNaN(result.Item2) || double.IsInfinity(result.Item2)) continue;
    149           if (double.IsNaN(best)
    150             || Problem.Maximization && result.Item2 > best
    151             || !Problem.Maximization && result.Item2 < best) {
     156          if (double.IsNaN(result.Item2) || double.IsInfinity(result.Item2)) {
     157            continue;
     158          }
     159
     160          if (double.IsNaN(best) || Problem.Maximization && result.Item2 > best || !Problem.Maximization && result.Item2 < best) {
    152161            bestSolution = result.Item1;
    153162            best = result.Item2;
     
    155164            bestFitting = fit;
    156165          }
    157           if (token.IsCancellationRequested) return Tuple.Create(bestSolution, best, bestSorting, bestFitting);
     166          if (token.IsCancellationRequested) {
     167            return Tuple.Create(bestSolution, best, bestSorting, bestFitting);
     168          }
    158169        }
    159170      }
    160       if (double.IsNaN(best)) return null;
     171      if (double.IsNaN(best)) {
     172        return null;
     173      }
    161174      return Tuple.Create(bestSolution, best, bestSorting, bestFitting);
    162175    }
    163176
    164177    private static Tuple<Solution, double> Optimize(PackingShape bin, IList<PackingItem> items, SortingMethod sorting, FittingMethod fitting, double delta, bool stackingConstraints, IEvaluator evaluator, CancellationToken token) {
     178      Permutation sortedItems = SortItemsBySortingMethod(bin, items, sorting, delta);
     179
     180      if (false) {// alt
     181        ExtremePointPermutationDecoderBase decoder = GetDecoderByFittingMethod(fitting);
     182        var sol = decoder.Decode(sortedItems, bin, items, stackingConstraints);
     183        var fit = evaluator.Evaluate(sol);
     184
     185        return Tuple.Create(sol, fit);
     186      } else {
     187        Decoder.ExtremePointPermutationDecoder decoder = new Decoder.ExtremePointPermutationDecoder(GetBinPackerByFittingMethod(fitting, sortedItems, bin, items, stackingConstraints));
     188
     189        var sol = decoder.Decode(sortedItems, bin, items, stackingConstraints);
     190        var fit = evaluator.Evaluate(sol);
     191
     192        return Tuple.Create(sol, fit);
     193      }
     194     
     195
     196     
     197    }
     198
     199
     200
     201    private static BinPacker GetBinPackerByFittingMethod(FittingMethod fittingMethod, Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
     202      BinPacker binPacker = null;
     203      switch (fittingMethod) {
     204        case FittingMethod.FirstFit:
     205          binPacker = new BinPackerFirstFit(sortedItems, binShape, items, useStackingConstraints);
     206          break;
     207        case FittingMethod.FreeVolumeBestFit:
     208          binPacker = new BinPackerFreeVolumeBestFit(sortedItems, binShape, items, useStackingConstraints);
     209          break;
     210        case FittingMethod.ResidualSpaceBestFit:
     211          binPacker = new BinPackerResidualSpaceBestFit(sortedItems, binShape, items, useStackingConstraints);
     212          break;
     213        default:
     214          throw new ArgumentException("Unknown fitting method: " + fittingMethod);
     215      }
     216      return binPacker;
     217    }
     218
     219    /// <summary>
     220    /// Returns a new permutation of the given items depending on the sorting method
     221    /// </summary>
     222    /// <param name="bin"></param>
     223    /// <param name="items"></param>
     224    /// <param name="sortingMethod"></param>
     225    /// <param name="delta"></param>
     226    /// <returns></returns>
     227    private static Permutation SortItemsBySortingMethod(PackingShape bin, IList<PackingItem> items, SortingMethod sortingMethod, double delta) {
    165228      Permutation sorted = null;
    166       switch (sorting) {
     229      switch (sortingMethod) {
    167230        case SortingMethod.Given:
    168231          sorted = new Permutation(PermutationTypes.Absolute, Enumerable.Range(0, items.Count).ToArray());
     
    216279                        .Select(x => x.Index).ToArray());
    217280          break;
    218         default: throw new ArgumentException("Unknown sorting method: " + sorting);
    219       }
    220      
     281        default:
     282          throw new ArgumentException("Unknown sorting method: " + sortingMethod);
     283      }
     284      return sorted;
     285    }
     286
     287    /// <summary>
     288    /// Returns a decoder depending on the given fitting method
     289    /// </summary>
     290    /// <param name="fittingMethod"></param>
     291    /// <returns></returns>
     292    private static ExtremePointPermutationDecoderBase GetDecoderByFittingMethod(FittingMethod fittingMethod) {
    221293      ExtremePointPermutationDecoderBase decoder = null;
    222       switch (fitting) {
     294      switch (fittingMethod) {
    223295        case FittingMethod.FirstFit:
    224296          decoder = new ExtremePointPermutationDecoder();
     
    230302          decoder = new ResidualSpaceBestFitExtremePointPermutationDecoder();
    231303          break;
    232         default: throw new ArgumentException("Unknown fitting method: " + fitting);
    233       }
    234 
    235       var sol = decoder.Decode(sorted, bin, items, stackingConstraints);
    236       var fit = evaluator.Evaluate(sol);
    237 
    238       return Tuple.Create(sol, fit);
     304        default:
     305          throw new ArgumentException("Unknown fitting method: " + fittingMethod);
     306      }
     307      return decoder;
    239308    }
    240309  }
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/BinPacking.cs

    r15304 r15454  
    3737    #region Properties
    3838    [Storable]
     39
     40    //key = item id
    3941    public ObservableDictionary<int, TPos> Positions { get; private set; }
    4042
    4143    [Storable]
     44    //key = item id
    4245    public ObservableDictionary<int, TItem> Items { get; private set; }
    4346
     
    138141      return false;
    139142    }
     143
     144    /// <summary>
     145    ///
     146    /// </summary>
     147    /// <param name="item"></param>
     148    /// <param name="position"></param>
     149    /// <param name="stackingConstraints"></param>
     150    /// <returns></returns>
    140151    public virtual bool IsPositionFeasible(TItem item, TPos position, bool stackingConstraints) {
    141       //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
     152      //In this case feasability is defined as following:
     153      //1. the item fits into the bin-borders;
     154      //2. the point is supported by something;
     155      //3. the item does not collide with another already packed item
    142156      if (!BinShape.Encloses(position, item))
    143157        return false;
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/HeuristicLab.Problems.BinPacking-3.3.csproj

    r15418 r15454  
    103103    <Compile Include="2D\ProblemBase.cs" />
    104104    <Compile Include="2D\Solution.cs" />
     105    <Compile Include="3D\Packer\BinPacker.cs" />
     106    <Compile Include="3D\Packer\BinPackerFirstFit.cs" />
    105107    <Compile Include="3D\BinPacking3D.cs" />
     108    <Compile Include="3D\Decoder\ExtremePointPermutationDecoder.cs" />
    106109    <Compile Include="3D\Evaluators\BinUtilizationEvaluator.cs" />
    107110    <Compile Include="3D\Evaluators\PackingRatioEvaluator.cs" />
    108     <Compile Include="3D\Instances\RandomInstanceProviderWithSRand.cs" />
     111    <Compile Include="3D\Instances\RandomInstanceProvider.cs" />
     112    <Compile Include="3D\Geometry\Line3D.cs" />
     113    <Compile Include="3D\Geometry\Plane3D.cs" />
     114    <Compile Include="3D\Geometry\Vector3D.cs" />
     115    <Compile Include="3D\Packer\BinPackerFreeVolumeBestFit.cs" />
     116    <Compile Include="3D\Packer\BinPackerResidualSpaceBestFit.cs" />
    109117    <Compile Include="Algorithms\3D\ExtremePointAlgorithm.cs" />
    110118    <Compile Include="3D\Instances\ThreeDInstanceDescriptor.cs" />
     
    112120    <Compile Include="3D\Instances\RandomDataDescriptor.cs" />
    113121    <Compile Include="3D\Instances\RealWorldContainerPackingInstanceProvider.cs" />
    114     <Compile Include="3D\Instances\RandomInstanceProvider.cs" />
    115122    <Compile Include="3D\Instances\ThreeDInstanceParser.cs" />
    116123    <Compile Include="3D\IntegerVectorEncoding\BottomLeftIntegerVectorDecoder.cs" />
     
    150157    <Compile Include="Plugin.cs" />
    151158    <Compile Include="Properties\AssemblyInfo.cs" />
     159    <Compile Include="Random\SRand48.cs" />
    152160  </ItemGroup>
    153161  <ItemGroup>
  • branches/2817-BinPackingSpeedup/HeuristicLab.Tests/HeuristicLab.Problems.Bin-Packing-3.3/AlgorithmTest.cs

    r15424 r15454  
    33using Microsoft.VisualStudio.TestTools.UnitTesting;
    44using HeuristicLab.Problems.BinPacking3D;
     5using HeuristicLab.Problems.BinPacking3D.Instances;
    56using System.Collections.Generic;
    67using System.Linq;
     
    3031
    3132      var referenceItemLists = ReadReferenceItemLists();
    32       TestRandomInstanceProviderByClass(new RandomInstanceClass1ProviderWithSRand(), referenceItemLists);
    33       TestRandomInstanceProviderByClass(new RandomInstanceClass2ProviderWithSRand(), referenceItemLists);
    34       TestRandomInstanceProviderByClass(new RandomInstanceClass3ProviderWithSRand(), referenceItemLists);
    35       TestRandomInstanceProviderByClass(new RandomInstanceClass4ProviderWithSRand(), referenceItemLists);
    36       TestRandomInstanceProviderByClass(new RandomInstanceClass5ProviderWithSRand(), referenceItemLists);
    37       TestRandomInstanceProviderByClass(new RandomInstanceClass6ProviderWithSRand(), referenceItemLists);
    38       TestRandomInstanceProviderByClass(new RandomInstanceClass7ProviderWithSRand(), referenceItemLists);
    39       TestRandomInstanceProviderByClass(new RandomInstanceClass8ProviderWithSRand(), referenceItemLists);
     33      TestRandomInstanceProviderByClass(new RandomInstanceClass1Provider(), referenceItemLists);
     34      TestRandomInstanceProviderByClass(new RandomInstanceClass2Provider(), referenceItemLists);
     35      TestRandomInstanceProviderByClass(new RandomInstanceClass3Provider(), referenceItemLists);
     36      TestRandomInstanceProviderByClass(new RandomInstanceClass4Provider(), referenceItemLists);
     37      TestRandomInstanceProviderByClass(new RandomInstanceClass5Provider(), referenceItemLists);
     38      TestRandomInstanceProviderByClass(new RandomInstanceClass6Provider(), referenceItemLists);
     39      TestRandomInstanceProviderByClass(new RandomInstanceClass7Provider(), referenceItemLists);
     40      TestRandomInstanceProviderByClass(new RandomInstanceClass8Provider(), referenceItemLists);
    4041
    4142    }
     
    7980    }
    8081
    81     private void TestRandomInstanceProviderByClass(RandomInstanceProviderWithSRand randomInstanceProvider, IDictionary<string, List<Dimension>> referenceItems) {
     82    private void TestRandomInstanceProviderByClass(RandomInstanceProvider randomInstanceProvider, IDictionary<string, List<Dimension>> referenceItems) {
    8283
    8384      var dataDescriptors = randomInstanceProvider.GetDataDescriptors();
     
    111112    [TestCategory("Problems.BinPacking")]
    112113    public void TestExtremePointAlgorithmClass1() {
    113       TestExtremePointAlgorithm(new RandomInstanceClass1ProviderWithSRand(), 1);
     114      TestExtremePointAlgorithm(new RandomInstanceClass1Provider(), 1);
    114115    }
    115116
     
    117118    [TestCategory("Problems.BinPacking")]
    118119    public void TestExtremePointAlgorithmClass2() {
    119       TestExtremePointAlgorithm(new RandomInstanceClass2ProviderWithSRand(), 2);
     120      TestExtremePointAlgorithm(new RandomInstanceClass2Provider(), 2);
    120121    }
    121122
     
    123124    [TestCategory("Problems.BinPacking")]
    124125    public void TestExtremePointAlgorithmClass3() {
    125       TestExtremePointAlgorithm(new RandomInstanceClass3ProviderWithSRand(), 3);
     126      TestExtremePointAlgorithm(new RandomInstanceClass3Provider(), 3);
    126127    }
    127128
     
    129130    [TestCategory("Problems.BinPacking")]
    130131    public void TestExtremePointAlgorithmClass4() {
    131       TestExtremePointAlgorithm(new RandomInstanceClass4ProviderWithSRand(), 4);
     132      TestExtremePointAlgorithm(new RandomInstanceClass4Provider(), 4);
    132133    }
    133134
     
    135136    [TestCategory("Problems.BinPacking")]
    136137    public void TestExtremePointAlgorithmClass5() {
    137       TestExtremePointAlgorithm(new RandomInstanceClass5ProviderWithSRand(), 5);
     138      TestExtremePointAlgorithm(new RandomInstanceClass5Provider(), 5);
    138139    }
    139140
     
    141142    [TestCategory("Problems.BinPacking")]
    142143    public void TestExtremePointAlgorithmClass6() {
    143       TestExtremePointAlgorithm(new RandomInstanceClass6ProviderWithSRand(), 6);
     144      TestExtremePointAlgorithm(new RandomInstanceClass6Provider(), 6);
    144145    }
    145146
     
    147148    [TestCategory("Problems.BinPacking")]
    148149    public void TestExtremePointAlgorithmClass7() {
    149       TestExtremePointAlgorithm(new RandomInstanceClass7ProviderWithSRand(), 7);
     150      TestExtremePointAlgorithm(new RandomInstanceClass7Provider(), 7);
    150151    }
    151152
     
    153154    [TestCategory("Problems.BinPacking")]
    154155    public void TestExtremePointAlgorithmClass8() {
    155       TestExtremePointAlgorithm(new RandomInstanceClass8ProviderWithSRand(), 8);
    156     }
    157 
    158     private void TestExtremePointAlgorithm(RandomInstanceProviderWithSRand randomInstanceProvider, int @class) {
     156      TestExtremePointAlgorithm(new RandomInstanceClass8Provider(), 8);
     157    }
     158
     159    private void TestExtremePointAlgorithm(RandomInstanceProvider randomInstanceProvider, int @class) {
    159160      foreach (SortingMethod sortingMethod in Enum.GetValues(typeof(SortingMethod))) {
    160161        //foreach (FittingMethod fittingMethod in Enum.GetValues(typeof(FittingMethod))) {
     
    168169
    169170
    170     private void TestExtremePointAlgorithmByParameters(RandomInstanceProviderWithSRand randomInstanceProvider, int @class, SortingMethod sortingMethod, FittingMethod fittingMethod) {
     171    private void TestExtremePointAlgorithmByParameters(RandomInstanceProvider randomInstanceProvider, int @class, SortingMethod sortingMethod, FittingMethod fittingMethod) {
    171172      var dataDescriptors = randomInstanceProvider.GetDataDescriptors();
    172173      var referenceValues = GetReferenceAlgorithmValues();
Note: See TracChangeset for help on using the changeset viewer.