Free cookie consent management tool by TermsFeed Policy Generator

Opened 11 years ago

Last modified 6 years 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 (83)

comment:1 Changed 11 years ago by jhelm

  • Status changed from new to accepted

comment:2 Changed 11 years ago by jhelm

r8737: Initial commit for binPacking branch.

comment:3 Changed 11 years ago by jhelm

r9348: First working version of bin-packing problems.

comment:4 Changed 11 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 11 years ago by jhelm

r9473:

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

comment:6 Changed 11 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 11 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 11 years ago by jhelm

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

comment:9 Changed 11 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 11 years ago by jhelm

r9598:

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

comment:11 Changed 11 years ago by jhelm

r9599:

  • Bugfixing
  • Refactoring
  • Performancetuning

comment:12 Changed 10 years ago by gkronber

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

comment:13 Changed 10 years ago by gkronber

  • Owner changed from architects to gkronber

comment:14 Changed 10 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 10 years ago by gkronber

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

comment:16 Changed 9 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 8 years 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 8 years 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 8 years ago by gkronber

r13022: deleted files that were not referenced by the project

comment:20 Changed 8 years ago by gkronber

r13023: fixed build configuration

comment:21 Changed 8 years 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 8 years ago by gkronber (previous) (diff)

comment:22 Changed 8 years 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 8 years ago by gkronber

r13029: svn:ignore

comment:24 Changed 8 years ago by gkronber

r13032:

  • removed unused using
  • added/updated license headers

comment:25 Changed 8 years 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 8 years 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 8 years 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 8 years 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 8 years ago by gkronber

  • Milestone changed from HeuristicLab 4.0 to HeuristicLab 3.3.14

comment:30 Changed 8 years ago by gkronber

r13460:

  • renamed creatables
  • partially fixed bin packing problem instance provider

comment:31 Changed 8 years 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 8 years ago by gkronber

r13462: PackingPlan is just an Item not a ParameterizedNamedItem

comment:33 Changed 8 years ago by gkronber

r13463: removed empty problem classes

comment:34 Changed 8 years ago by gkronber

r13464: deleted .resx files

comment:35 Changed 8 years ago by gkronber

r13465: general code cleanup ...

comment:36 Changed 8 years ago by gkronber

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

comment:37 Changed 8 years ago by gkronber

r13468: worked on visualization of packing plans

comment:38 Changed 8 years ago by gkronber

r13477: fixed visualization of 2d packing

comment:39 Changed 8 years ago by gkronber

r13478: fixed rotation and zooming for 3d packings

comment:40 Changed 8 years 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 8 years ago by gkronber

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

comment:42 Changed 8 years 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 8 years ago by gkronber

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

comment:44 Changed 8 years ago by gkronber

r13558: finished view for 3d packings

comment:45 Changed 8 years ago by gkronber

r13574: changed PackingShapes to ParameterizedItems

comment:46 Changed 8 years 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 8 years ago by gkronber

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

comment:48 Changed 8 years ago by gkronber

r13577: deleted empty folders

comment:49 Changed 8 years ago by gkronber

r13578: implemented view for 2d packings

comment:50 Changed 8 years ago by gkronber

r13605:13613 major refactoring

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

comment:51 Changed 8 years 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 8 years ago by gkronber

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

comment:53 Changed 8 years 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 8 years ago by gkronber

r14041: formatting

comment:55 Changed 8 years ago by gkronber

r14042: moved obsolete files into a separate folder

comment:56 Changed 8 years ago by gkronber

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

Last edited 8 years ago by gkronber (previous) (diff)

comment:57 Changed 8 years ago by gkronber

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

Last edited 8 years ago by gkronber (previous) (diff)

comment:58 Changed 8 years ago by gkronber

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

r14046: unified namespaces

comment:59 Changed 8 years ago by gkronber

r14047: renamed PackingPlan* -> Solution

comment:60 Changed 8 years ago by gkronber

r14048: renamed *PackingDimension -> PackingPosition

comment:61 Changed 8 years ago by gkronber

r14049: simplified class names

comment:62 Changed 8 years ago by gkronber

r14050: renamed evaluators

comment:63 Changed 8 years ago by gkronber

r14051:

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

comment:64 Changed 8 years ago by gkronber

r14052: deleted dead code

comment:65 Changed 8 years ago by gkronber

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

comment:66 Changed 8 years 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 8 years ago by gkronber (previous) (diff)

comment:67 Changed 8 years ago by gkronber

r14054: renamed *EvaluationAlgorithm -> *DecodingEvaluator

comment:68 Changed 8 years ago by gkronber

r14055: simplified parsers

comment:69 Changed 8 years 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 8 years ago by gkronber

r14063: implemented random instance generation for 2d BPP instances

comment:71 Changed 8 years ago by gkronber

r14064: first refactoring steps to use new Encoding framework

comment:72 Changed 8 years ago by gkronber

r14128: refactoring of bin packing implementation

comment:73 Changed 8 years ago by swagner

  • Milestone changed from HeuristicLab 3.3.14 to HeuristicLab 3.3.15

comment:74 Changed 8 years 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 8 years 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 8 years ago by gkronber

r14149: refactoring 2d problem

comment:77 Changed 8 years 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 8 years ago by gkronber

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

comment:79 Changed 8 years ago by gkronber

r14154: refactoring

comment:80 Changed 8 years 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 8 years ago by gkronber (previous) (diff)

comment:81 Changed 7 years ago by gkronber

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

comment:82 Changed 7 years ago by abeham

  • Owner changed from gkronber to dsouravl
  • Status changed from accepted to assigned

comment:83 Changed 6 years ago by abeham

r16100: renamed branch

Note: See TracTickets for help on using tickets.