search

heal-research / HeuristicLab

HeuristicLab - An environment for heuristic and evolutionary optimization
https://dev.heuristiclab.com
GNU General Public License v3.0
38 stars 16 forks source link

Improve speed of bin packing #2817

Open HeuristicLab-Trac-Bot opened 7 years ago

HeuristicLab-Trac-Bot commented 7 years ago

Issue migrated from trac ticket # 2817

milestone: HeuristicLab 3.3.17 | component: Problems.BinPacking | priority: medium

2017-08-02 16:50:14: @abeham created the issue

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.

HeuristicLab-Trac-Bot commented 7 years ago

2017-08-02 22:51:22: @abeham changed status from new to accepted

HeuristicLab-Trac-Bot commented 7 years ago

2017-08-02 22:52:39: @abeham commented

r15303: created branch

HeuristicLab-Trac-Bot commented 7 years ago

2017-08-03 12:18:36: @abeham commented

r15304:

  • 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)
HeuristicLab-Trac-Bot commented 7 years ago

2017-08-04 12:37:27: @abeham commented

r15305:

  • Avoided generating unnecessary extreme points
  • Added vector calculation code for line/plane intersection
HeuristicLab-Trac-Bot commented 7 years ago

2017-08-04 17:00:45: @abeham commented

r15306:

  • 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 >=
HeuristicLab-Trac-Bot commented 7 years ago

2017-08-04 23:45:22: @abeham commented

r15307:

  • Added checkbox to control showing extreme points in visualization
    • Automatically determine size of extreme point cubes
  • Fixed some bugs in extreme point generation
HeuristicLab-Trac-Bot commented 7 years ago

2017-08-06 23:04:53: @abeham commented

r15308:

  • fixed remaining bugs
HeuristicLab-Trac-Bot commented 7 years ago

2017-10-11 15:40:26: rhanghof changed status from accepted to assigned

HeuristicLab-Trac-Bot commented 7 years ago

2017-10-11 15:40:26: rhanghof changed owner from @abeham to rhanghof

HeuristicLab-Trac-Bot commented 7 years ago

2017-10-11 15:40:33: rhanghof changed status from assigned to accepted

HeuristicLab-Trac-Bot commented 7 years ago

2017-10-11 16:18:03: rhanghof commented

r15418:

  • 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
HeuristicLab-Trac-Bot commented 7 years ago

2017-10-17 13:55:58: rhanghof commented

r15423:

  • 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.
HeuristicLab-Trac-Bot commented 7 years ago

2017-10-18 10:55:18: rhanghof commented

r15424:

  • 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
HeuristicLab-Trac-Bot commented 7 years ago

2017-11-07 08:24:55: rhanghof commented

r15454:

  • 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
HeuristicLab-Trac-Bot commented 7 years ago

2017-11-14 15:31:48: rhanghof commented

r15471:

  • Added some unit tests
  • Enhanced the documentation
HeuristicLab-Trac-Bot commented 7 years ago

2017-11-15 12:30:36: rhanghof commented

r15473:

  • Added unit tests
  • Refactoring of bp 3D
HeuristicLab-Trac-Bot commented 7 years ago

2017-11-28 16:10:53: rhanghof commented

r15488:

  • Added line projection based bin packing
  • Added residual spaces to the view
HeuristicLab-Trac-Bot commented 6 years ago

2017-12-13 09:48:07: rhanghof commented

r15520:

  • Changed the calculation algorithm for creating extreme points by using line based projection
  • Changed the calculation of the residual spaces for line based projection
HeuristicLab-Trac-Bot commented 6 years ago

2017-12-20 16:18:43: rhanghof commented

r15554:

  • Unittests
  • Bugfixes on the line projection based extreme point creation method.
HeuristicLab-Trac-Bot commented 6 years ago

2018-01-09 15:47:18: rhanghof commented

r15585:

  • Bugfixes for the line projection based extreme point creation
  • Bugfixes for the tests
HeuristicLab-Trac-Bot commented 6 years ago

2018-01-16 15:41:49: rhanghof commented

r15617:

  • The items can be rotated and tilted now.
  • Added pruning of extreme points in packed bins.
  • Added new packer which packs items by positioning them on the point with the minimum of wasted space. He uses rotating and tilting of items.
  • Added classes for sorting given items.
HeuristicLab-Trac-Bot commented 6 years ago

2018-01-16 15:43:59: rhanghof commented

r15618:

  • The items can be rotated and tilted now.
  • Added pruning of extreme points in packed bins.
  • Added new packer which packs items by positioning them on the point with the minimum of wasted space. It uses rotating and tilting of items.
  • Added classes for sorting given items.
HeuristicLab-Trac-Bot commented 6 years ago

2018-01-24 13:17:22: rhanghof commented

r15646:

  • Dealing with stackable items
  • Enhanced the Evaluator
  • Added parameters some paramters to the packing items
HeuristicLab-Trac-Bot commented 6 years ago

2018-01-24 17:15:38: rhanghof commented

r15652:

  • Little changes on the packer
HeuristicLab-Trac-Bot commented 6 years ago

2018-02-01 12:21:53: rhanghof commented

r15705:

  • Former material is now the layer.
  • Added material enumeration
  • Modification at the minimum residual space left bin packer
HeuristicLab-Trac-Bot commented 6 years ago

2018-02-07 14:54:56: rhanghof commented

r15731:

  • Added a new packer.
  • Enhanced the material types.
  • Added extreme point pruning for layer support in the extrem point creators.
  • BinPacking3D: Added a graph for calculating weigth distribution of the items.
HeuristicLab-Trac-Bot commented 6 years ago

2018-02-13 16:45:20: rhanghof commented

r15770:

  • Added a graph to the BinPacking3D for calculating the weight distribution.
  • Added some materials.
HeuristicLab-Trac-Bot commented 6 years ago

2018-02-21 16:33:06: rhanghof commented

r15801:

  • Little changes on the packer
HeuristicLab-Trac-Bot commented 6 years ago

2018-02-28 14:05:41: rhanghof commented

r15820:

  • Fixes for pruning
HeuristicLab-Trac-Bot commented 6 years ago

2018-02-28 15:33:58: rhanghof commented

r15822:

  • Added the property SequenceGroup to the PackingItem
  • Fixed a bug related to the sequence group
HeuristicLab-Trac-Bot commented 6 years ago

2018-03-12 14:19:23: rhanghof commented

r15838:

  • Fixed a bug at creating the extreme points with the point projection based method.
HeuristicLab-Trac-Bot commented 6 years ago

2018-03-16 13:09:34: rhanghof commented

r15844:

  • Some bug fixes at the placing algorithm
HeuristicLab-Trac-Bot commented 6 years ago

2018-06-13 15:33:01: rhanghof commented

r15959:

  • Refactoring BinPackerFormClosure.cs -> BinPackerWidthBestFit.cs
  • Changes on the unit tests
HeuristicLab-Trac-Bot commented 6 years ago

2018-07-09 13:00:00: rhanghof commented

r15989:

  • Adjusted the unit tests
  • Refactoring of the sorter
  • Bugfix on the BinPackerResidualSpaceBestFit packer
HeuristicLab-Trac-Bot commented 6 years ago

2018-09-14 11:47:45: @abeham commented

r16140: updated to trunk r15680

r16141: updated to trunk r16140

HeuristicLab-Trac-Bot commented 5 years ago

2019-04-19 10:58:44: @abeham changed milestone from HeuristicLab 3.3.16 to HeuristicLab 3.3.17