Opened 3 weeks ago

Last modified 2 weeks ago

#2817 accepted enhancement

Improve speed of bin packing

Reported by: abeham Owned by: abeham
Priority: medium Milestone: HeuristicLab 3.3.16
Component: Problems.BinPacking Version: 3.3.14
Keywords: Cc:


The GenerateNewExtremePointsForNewItem method uses a rather primitive way to generate new points. Intersection between vector and plane should be used to calculate the extreme points.

Change History (7)

comment:1 Changed 3 weeks ago by abeham

  • Status changed from new to accepted

comment:2 Changed 3 weeks ago by abeham

r15303: created branch

comment:3 Changed 2 weeks ago by abeham


  • Improved speed of GenerateNewExtremePointsForNewItem
  • GenerateNewExtremePointsForNewItem previously generated too many extreme points and the points were generated for each item anew each time an item was packed.
  • Some bugs are still present (generation of unnecessary extreme points, e.g. with a residual space that is a sub-space of the residual space of another extreme point)

comment:4 Changed 2 weeks ago by abeham


  • Avoided generating unnecessary extreme points
  • Added vector calculation code for line/plane intersection

comment:5 Changed 2 weeks ago by abeham


  • Drawing extreme points in the visualization (will add a checkbox to the view to enable/disable this)
  • Fixing some bugs:
    • Updating residual space of extreme points before generating new extreme points
    • Fixed calculation of residual space for new extreme points by calculating intersections
    • Fixed bug in UpdateResidualSpace regarding > and >=

comment:6 Changed 2 weeks ago by abeham


  • Added checkbox to control showing extreme points in visualization
    • Automatically determine size of extreme point cubes
  • Fixed some bugs in extreme point generation

comment:7 Changed 2 weeks ago by abeham


  • fixed remaining bugs
Note: See TracTickets for help on using tickets.