Opened 3 months ago

Last modified 3 days ago

#2817 accepted enhancement

Improve speed of bin packing

Reported by: abeham Owned by: rhanghof
Priority: medium Milestone: HeuristicLab 3.3.16
Component: Problems.BinPacking Version: branch
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 (13)

comment:1 Changed 3 months ago by abeham

  • Status changed from new to accepted

comment:2 Changed 3 months ago by abeham

r15303: created branch

comment:3 Changed 3 months 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 3 months ago by abeham


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

comment:5 Changed 3 months 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 3 months 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 3 months ago by abeham


  • fixed remaining bugs

comment:8 Changed 6 weeks ago by abeham

  • Version changed from 3.3.14 to branch

comment:9 Changed 9 days ago by rhanghof

  • Owner changed from abeham to rhanghof
  • Status changed from accepted to assigned

comment:10 Changed 9 days ago by rhanghof

  • Status changed from assigned to accepted

comment:11 Changed 9 days ago by rhanghof


  • New RandomInstanceProvider added for testing the EP-algorithm with the same instances as Silvano Martello, David Pisinger, Daniele Vigo in their paper.
  • Added some Unit Tests for the BinPacking-3D EP-algorithm

comment:12 Changed 4 days ago by rhanghof


  • Now the new RandomInstanceProvider creates the same instances as in the specification given by Martello, Pisinger and Vigo.
  • Now the unit tests are testing the new RandomInstanceProvider.

comment:13 Changed 3 days ago by rhanghof


  • Added some comments and regions to the source code
  • Added reference instance files created by the test algoritm of S. Martello, D. Pisinger, D. Vigo
Note: See TracTickets for help on using tickets.