Implement BinPacking problem

[jhelm]

r8737: Initial commit for binPacking branch.

[jhelm]

r9348: First working version of bin-packing problems.

[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);

[jhelm]

r9473:

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

[jhelm]

r9495:

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

[jhelm]

r9563:

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

[jhelm]

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

[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;

[jhelm]

r9598:

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

[jhelm]

r9599:

• Bugfixing
• Refactoring
• Performancetuning

[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?

[gkronber]

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

[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)

[gkronber]

r13022: deleted files that were not referenced by the project

[gkronber]

r13023: fixed build configuration

[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.

[gkronber]

r13028:

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

[gkronber]

r13029: svn:ignore

[gkronber]

r13032:

• removed unused using
• added/updated license headers

[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)

[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

[gkronber]

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

[gkronber]

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

[gkronber]

r13460:

• renamed creatables
• partially fixed bin packing problem instance provider

[gkronber]

r13461:

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

[gkronber]

r13462: PackingPlan is just an Item not a ParameterizedNamedItem

[gkronber]

r13463: removed empty problem classes

[gkronber]

r13464: deleted .resx files

[gkronber]

r13465: general code cleanup ...

[gkronber]

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

[gkronber]

r13468: worked on visualization of packing plans

[gkronber]

r13477: fixed visualization of 2d packing

[gkronber]

r13478: fixed rotation and zooming for 3d packings

[gkronber]

r13497: fixed various problems:

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

[gkronber]

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

[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.

[gkronber]

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

[gkronber]

r13558: finished view for 3d packings

[gkronber]

r13574: changed PackingShapes to ParameterizedItems

[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

[gkronber]

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

[gkronber]

r13577: deleted empty folders

[gkronber]

r13578: implemented view for 2d packings

[gkronber]

r13605:13613 major refactoring

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

[gkronber]

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

[gkronber]

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

[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)

[gkronber]

r14041: formatting

[gkronber]

r14042: moved obsolete files into a separate folder

[gkronber]

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

[gkronber]

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

[gkronber]

r14046: unified namespaces

[gkronber]

r14047: renamed PackingPlan* -> Solution

[gkronber]

r14048: renamed *PackingDimension -> PackingPosition

[gkronber]

r14049: simplified class names

[gkronber]

r14050: renamed evaluators

[gkronber]

r14051:

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

[gkronber]

r14052: deleted dead code

[gkronber]

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

[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

[gkronber]

r14054: renamed *EvaluationAlgorithm -> *DecodingEvaluator

[gkronber]

r14055: simplified parsers

[gkronber]

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

[gkronber]

r14063: implemented random instance generation for 2d BPP instances

[gkronber]

r14064: first refactoring steps to use new Encoding framework

[gkronber]

r14128: refactoring of bin packing implementation

[gkronber]

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

[gkronber]

r14149: refactoring 2d problem

[gkronber]

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

[gkronber]

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

[gkronber]

r14154: refactoring

[gkronber]

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

[abeham]

r16100: renamed branch