Opened 5 years ago

Last modified 4 months ago

#1966 assigned feature request

Implement BinPacking problem

Reported by: jhelm Owned by: dsouravl
Priority: medium Milestone: HeuristicLab 3.3.x Backlog
Component: Problems.BinPacking Version: branch
Keywords: Cc:

Description


Change History (82)

comment:1 Changed 5 years ago by jhelm

  • Status changed from new to accepted

comment:2 Changed 5 years ago by jhelm

r8737: Initial commit for binPacking branch.

comment:3 Changed 4 years ago by jhelm

r9348: First working version of bin-packing problems.

comment:4 Changed 4 years ago by jhelm

r9440:

  • Implemented new encoding (MultiComponentVector/MCV);
  • Implemented move-operators for MCV and GV encodings;
  • Implemented new decoding-methods for PS, GV and MCV encodings (ExtremePoint-based packing);

comment:5 Changed 4 years ago by jhelm

r9473:

  • Fixed some problems in MCV-move operators;
  • Added parts of potvin-encoding implementation;

comment:6 Changed 4 years ago by jhelm

r9495:

  • Did some major refactoring in Decoder-classes;
  • Added MoveEvaluator classes for different encodings and dimensions;
  • Added new crossover-class for MCV encoding;

comment:7 Changed 4 years ago by jhelm

r9563:

  • Implemented additional Operator-Wrappers for PackingSequence and GroupingVector;
  • Implemented additional problem-class for Rosenbauer-Problemstatement;
  • Added marker-interfaces for decoder-types;

comment:8 Changed 4 years ago by jhelm

r9593: Applied some heavy refactoring on the decoder-classes and cleaned up the code a bit;

comment:9 Changed 4 years ago by jhelm

r9596:

  • Added more sophisticated structures for packing-plan and bin-packing representation;
  • Transferred parts of the decoding-algorithms to these structures;
  • Did some more refactoring and cleanup;

comment:10 Changed 4 years ago by jhelm

r9598:

  • Fixed a bug which caused the stacking-constraint to be wrongly enforced;
  • Did some cleanup;

comment:11 Changed 4 years ago by jhelm

r9599:

  • Bugfixing
  • Refactoring
  • Performancetuning

comment:12 Changed 3 years ago by gkronber

  • Owner changed from jhelm to architects
  • Status changed from accepted to assigned

comment:13 Changed 3 years ago by gkronber

  • Owner changed from architects to gkronber

comment:14 Changed 3 years ago by gkronber

There is an external reference to a project called PackingPlanVisualizations (which presumably uses SharpDX for visualization). Is it possible to add all the source code for this project to this branch?

comment:15 Changed 3 years ago by gkronber

  • Cc joseph.n.helm@gmail.com added

comment:16 Changed 2 years ago by gkronber

  • Milestone changed from HeuristicLab 3.3.x Backlog to HeuristicLab 3.3.13
  • Status changed from assigned to accepted

comment:17 Changed 22 months ago by gkronber

r13020 increased framework version to 4.5, deleted files that should not be committed to the repository and set svn:ignore properties

comment:18 Changed 22 months ago by gkronber

r13021:

  • deleted old files that were not referenced by the project
  • set svn:ignore properties
  • temporarily excluded the BPPInstanceProvider as it does not work currently (the used resources are not available in the repository, instead a .rar file can be found in the data folder)

comment:19 Changed 22 months ago by gkronber

r13022: deleted files that were not referenced by the project

comment:20 Changed 22 months ago by gkronber

r13023: fixed build configuration

comment:21 Changed 22 months ago by gkronber

TODO:

  • reintegrate visualizations for packing (pending answer from Joseph concerning external library)
  • Set names for named itmes (e.g. RectangularPackingShape)
  • Exception in ISOContainerDecoder
  • No view for MultiComponentVector
  • Check binaries of SharpDX (official binaries?)
  • Extract SharpDX into ExtLibs
  • separate 2d and 3d problem instances
  • test exporting 2d and 3d problem instances
  • test persistence
  • "View for rectangular shapes" looks strange
  • "View for rectangular packed item" looks strange
  • PackingPlan is a ParameterizedNamedItem (but doesn't have parameters)
  • mouse interaction in view for CuboidPackingBin doesn't work correctly anymore
  • CuboidPackingBinView doesn't release focus (not possible to change to another view anymore).
  • What's the difference between *PackingShape and *PackingItem? (the shape represents the container, the item represents an item in the container which might also have a weight and a material.)
  • Review all code
  • rename preperations file
  • Info link is a 404
  • Create a sample
  • seemingly an analyzer changes the packing and the corresponding view is not notified.
Last edited 12 months ago by gkronber (previous) (diff)

comment:22 Changed 22 months ago by gkronber

r13028:

  • added PackingPlanVisualizations plugin received from jhelm.
  • this project also contains necessary binaries of SharpDX
  • visualization in HL works now

comment:23 Changed 22 months ago by gkronber

r13029: svn:ignore

comment:24 Changed 21 months ago by gkronber

r13032:

  • removed unused using
  • added/updated license headers

comment:25 Changed 21 months ago by gkronber

r13161:

  • removed SharpDX binaries since these are available through a transport plugin now (see #2504) and
  • also made some changes to make the code work with the latest stable release of SharpDX (TODO: test mouse interaction)

comment:26 Changed 21 months ago by ascheibe

I just tried out this plugin. When I open a GA, select the ISOContainerBinPackingProblem and click run I get an exception. The other 2 problems work. Here's the exception:

HeuristicLab version: 3.3.12.12927
OperatorExecutionException: An exception was thrown by the operator "ISO container decoder for the MultiComponentVector encoding." [C:\dev\trunk\sources\bin\HeuristicLab.Problems.BinPacking-3.3.dll: 3.3.7.13032]: The given key was not present in the dictionary.
   at HeuristicLab.SequentialEngine.SequentialEngine.Run(CancellationToken cancellationToken) in C:\dev\trunk\sources\HeuristicLab.SequentialEngine\3.3\SequentialEngine.cs:line 65
   at HeuristicLab.Core.Engine.Run(Object state) in C:\dev\trunk\sources\HeuristicLab.Core\3.3\Engine.cs:line 153
   at System.Threading.Tasks.Task.Execute()
-----
KeyNotFoundException: The given key was not present in the dictionary.
   at System.Collections.Generic.Dictionary`2.get_Item(TKey key)
   at HeuristicLab.Encodings.PackingEncoding.PackingPlan.BinPacking3D.GetLayerItemIDs(CuboidPackingItem measures, ThreeDimensionalPacking position) in C:\dev\branches\HeuristicLab.BinPacking\HeuristicLab.Problems.BinPacking\3.3\Encodings\PackingPlans\BinPacking3D.cs:line 366
   at HeuristicLab.Encodings.PackingEncoding.PackingPlan.BinPacking`3.IsPositionFeasible(I measures, D position) in C:\dev\branches\HeuristicLab.BinPacking\HeuristicLab.Problems.BinPacking\3.3\Encodings\PackingPlans\BinPacking.cs:line 143
   at HeuristicLab.Encodings.PackingEncoding.PackingPlan.BinPacking3D.FindExtremePointForItem(CuboidPackingItem measures, Boolean rotated, Boolean stackingConstraints) in C:\dev\branches\HeuristicLab.BinPacking\HeuristicLab.Problems.BinPacking\3.3\Encodings\PackingPlans\BinPacking3D.cs:line 160
   at HeuristicLab.Encodings.PackingEncoding.PackingPlan.BinPacking3D.ExtremePointBasedPacking(List`1& sequence, ItemList`1 itemMeasures, Boolean stackingConstraints, Dictionary`2 rotationArray) in C:\dev\branches\HeuristicLab.BinPacking\HeuristicLab.Problems.BinPacking\3.3\Encodings\PackingPlans\BinPacking3D.cs:line 239
   at HeuristicLab.Problems.BinPacking.Decoders.ISOContainerMultiComponentVectorDecoder3D.Decode(MultiComponentVectorEncoding solution, CuboidPackingBin binMeasures, ItemList`1 itemMeasures) in C:\dev\branches\HeuristicLab.BinPacking\HeuristicLab.Problems.BinPacking\3.3\Decoders\3D\EP\ISOContainerMultiComponentVectorDecoder3D.cs:line 72
   at HeuristicLab.Problems.BinPacking.Decoders.ISOContainerMultiComponentVectorDecoder3D.CreatePackingPlanFromEncoding(IItem encodedSolution, CuboidPackingBin binMeasures, ItemList`1 itemMeasures) in C:\dev\branches\HeuristicLab.BinPacking\HeuristicLab.Problems.BinPacking\3.3\Decoders\3D\EP\ISOContainerMultiComponentVectorDecoder3D.cs:line 113
   at HeuristicLab.Problems.BinPacking.Decoders.PackingSolutionDecoder`3.Apply() in C:\dev\branches\HeuristicLab.BinPacking\HeuristicLab.Problems.BinPacking\3.3\Decoders\PackingSolutionDecoder.cs:line 80
   at HeuristicLab.Operators.Operator.Execute(IExecutionContext context, CancellationToken cancellationToken) in C:\dev\trunk\sources\HeuristicLab.Operators\3.3\Operator.cs:line 124
   at HeuristicLab.SequentialEngine.SequentialEngine.Run(CancellationToken cancellationToken) in C:\dev\trunk\sources\HeuristicLab.SequentialEngine\3.3\SequentialEngine.cs:line 60

comment:27 Changed 21 months ago by gkronber

Thanks, I also observed this exception an a few other problems... I'll try to fix those before I merge this to trunk.

comment:28 Changed 20 months ago by gkronber

  • Milestone changed from HeuristicLab 3.3.13 to HeuristicLab 4.0

Review of code and bugfixing is not done yet. Unfortunately, we have to postpone the release of the bin-packing problem again.

comment:29 Changed 20 months ago by gkronber

  • Milestone changed from HeuristicLab 4.0 to HeuristicLab 3.3.14

comment:30 Changed 20 months ago by gkronber

r13460:

  • renamed creatables
  • partially fixed bin packing problem instance provider

comment:31 Changed 20 months ago by gkronber

r13461:

  • used Items instead of NamedItems and adapted views (Names/Descriptions) were not set anyway
  • fixed problems identified by Essential unit tests

comment:32 Changed 20 months ago by gkronber

r13462: PackingPlan is just an Item not a ParameterizedNamedItem

comment:33 Changed 20 months ago by gkronber

r13463: removed empty problem classes

comment:34 Changed 20 months ago by gkronber

r13464: deleted .resx files

comment:35 Changed 20 months ago by gkronber

r13465: general code cleanup ...

comment:36 Changed 20 months ago by gkronber

r13466: docking of controls in (Cuboid|Rectangular)(PackingShape|PackingItem)View

comment:37 Changed 20 months ago by gkronber

r13468: worked on visualization of packing plans

comment:38 Changed 20 months ago by gkronber

r13477: fixed visualization of 2d packing

comment:39 Changed 20 months ago by gkronber

r13478: fixed rotation and zooming for 3d packings

comment:40 Changed 19 months ago by gkronber

r13497: fixed various problems:

  • bugs in cloning,
  • bugs in persistence,
  • method names,
  • various minor improvements of source code for readability.

comment:41 Changed 18 months ago by gkronber

r13530: final commit of changes to game before deleting the whole visualization plugin

comment:42 Changed 18 months ago by gkronber

r13531: deleted PackingPlanVisualizations which uses SharpDX to display 3d packings

Reasoning:

  • there were problems with lost click events when a 3d view was shown. I couldn't fix this even though I invested a lot of time. The game class from SharpDX toolkit implements it's own message loop (dispatching windows events) when it is running. ListView from the .NET framework also implements it's own message loop. Because of incompatibility it was not possible to select an item in a ListView via a mouse click when a game is running.
  • Implementing the 3D visualization as a DirectX game is not necessary because we don't have any kind of animation or interaction with objects in the 'game'.
  • external dependency to a huge library (SharpDX)
  • WPF also provides a simple way to display and animate 3d objects.

comment:43 Changed 18 months ago by gkronber

r13532: added WPF control to visualize packings (work in progress)

comment:44 Changed 18 months ago by gkronber

r13558: finished view for 3d packings

comment:45 Changed 18 months ago by gkronber

r13574: changed PackingShapes to ParameterizedItems

comment:46 Changed 18 months ago by gkronber

r13575: removed *PackingShapeView and *PackingItemView (because they only showed one packing shape and this is not really helpful). Instead we are using the ParameterizedItemView now which shows all details and also allows that the shapes are manipulated through the GUI

comment:47 Changed 18 months ago by gkronber

r13576: folder reorganization (only 4 classes left in .Views plugin)

comment:48 Changed 18 months ago by gkronber

r13577: deleted empty folders

comment:49 Changed 18 months ago by gkronber

r13578: implemented view for 2d packings

comment:50 Changed 18 months ago by gkronber

r13605:13613 major refactoring

  • split 2d and 3d implementations
  • start work on encodings

comment:51 Changed 13 months ago by gkronber

r14038: fixed compile errors and reverted some changes from the last commit which prepared for refactoring to use new Encoding framework

comment:52 Changed 13 months ago by gkronber

r14039: restored functionality after splitting into 2d and 3d problems

comment:53 Changed 13 months ago by gkronber

r14040:

  • removed separation of general bin packing problems and 'regular' (=rectangular or cuboid) bin packing problems (=> all our bin packing problems are regular)
  • removed ISOContainer BinPacking problem (seems to be just a minor variant for generic 3d bin packing)

comment:54 Changed 13 months ago by gkronber

r14041: formatting

comment:55 Changed 13 months ago by gkronber

r14042: moved obsolete files into a separate folder

comment:56 Changed 13 months ago by gkronber

r14043: removed interface IRegularPackingShape (=> all our packing shapes are regular)

Last edited 13 months ago by gkronber (previous) (diff)

comment:57 Changed 13 months ago by gkronber

r14045: removed types for *PackingBin because PackingBins and PackingShapes have the same capabilities

Last edited 13 months ago by gkronber (previous) (diff)

comment:58 Changed 13 months ago by gkronber

  • Cc joseph.n.helm@gmail.com removed

r14046: unified namespaces

comment:59 Changed 13 months ago by gkronber

r14047: renamed PackingPlan* -> Solution

comment:60 Changed 13 months ago by gkronber

r14048: renamed *PackingDimension -> PackingPosition

comment:61 Changed 13 months ago by gkronber

r14049: simplified class names

comment:62 Changed 13 months ago by gkronber

r14050: renamed evaluators

comment:63 Changed 13 months ago by gkronber

r14051:

  • renamed files to match class names
  • deleted RegularSimpleRotationIdenticalBinPackingPlanEvaluator because it has been merged with EvaluatorBase

comment:64 Changed 13 months ago by gkronber

r14052: deleted dead code

comment:65 Changed 13 months ago by gkronber

r14053: separated 2d and 3d problem instances using two different providers

comment:66 Changed 13 months ago by gkronber

TODO:

  • improve code in parsers
  • it seems there are much more problem instances but the parser only returns the first one of each class
  • create separate problem classes for different encodings
Last edited 12 months ago by gkronber (previous) (diff)

comment:67 Changed 13 months ago by gkronber

r14054: renamed *EvaluationAlgorithm -> *DecodingEvaluator

comment:68 Changed 13 months ago by gkronber

r14055: simplified parsers

comment:69 Changed 13 months ago by gkronber

r14062: reimplemented problem instance generation from paper Silvano Martello, David Pisinger Daniele Vigo, "The Three-Dimensional Bin Packing Problem"

comment:70 Changed 13 months ago by gkronber

r14063: implemented random instance generation for 2d BPP instances

comment:71 Changed 13 months ago by gkronber

r14064: first refactoring steps to use new Encoding framework

comment:72 Changed 12 months ago by gkronber

r14128: refactoring of bin packing implementation

comment:73 Changed 12 months ago by swagner

  • Milestone changed from HeuristicLab 3.3.14 to HeuristicLab 3.3.15

comment:74 Changed 12 months ago by swagner

  • Component changed from General to Problems.BinPacking
  • Milestone changed from HeuristicLab 3.3.15 to HeuristicLab 3.3.14

comment:75 Changed 12 months ago by gkronber

  • r14146: new implementation for 2d bin packing problem with permutation encoding
  • r14147: finished implementation of 2d bin packing problem using permutation
  • r14148: restructuring

comment:76 Changed 12 months ago by gkronber

r14149: refactoring 2d problem

comment:77 Changed 12 months ago by gkronber

r14151: added abstract problem and move evaluator classes and implemented 2d bin packing problem based on integer vector encoding

comment:78 Changed 12 months ago by gkronber

r14153: implemented 3d bin packing problems (using permutation and integer vector encoding) based on the 2d implementations

comment:79 Changed 12 months ago by gkronber

r14154: refactoring

comment:80 Changed 12 months ago by gkronber

  • Milestone changed from HeuristicLab 3.3.14 to HeuristicLab 3.3.15

The bin packing implementation has been partially merged to trunk for release 3.3.14 with #2641. Not yet merged:

  • 'MultiVectorEncoding'
  • Moves for 'GroupingEncoding' (IntegerVectorEncoding)

Not yet tested:

  • Stacking constraints (material / weight)

TODO:

  • re-add unit test class to create / run BPP sample
Last edited 12 months ago by gkronber (previous) (diff)

comment:81 Changed 5 months ago by gkronber

  • Milestone changed from HeuristicLab 3.3.15 to HeuristicLab 3.3.x Backlog

comment:82 Changed 4 months ago by abeham

  • Owner changed from gkronber to dsouravl
  • Status changed from accepted to assigned
Note: See TracTickets for help on using tickets.