In a previous blog on optimization problems, I was exploring the bin packing problem using python's PuLP library and GLPK solver. Today I will play with the same problem, but this time in Java and using OptaPlanner solver with Drools rule engine.
- Docker Community Edition, version 17.03 or newer. Documentation on how to perform the installation.
- Postman API development tool.
The source code for this tutorial can be found here.
Let's start the KIE (Knowledge is Everything) Drools workbench docker container. This includes an IDE for OptaPlanner solver and domain modeling.
docker run -p 8080:8080 -p 8001:8001 -v /path/to/local/folder:/opt/jboss/wildfly/bin/.niogit:Z --name drools-workbench jboss/drools-workbench-showcase:latest
Make sure that
/path/to/local/folder exists on your local machine. All the projects will be saved there.
After a couple of minutes, the environment should be up and running and you should be able to access it at
http://localhost:8080/drools-wb/. In case you get a 404 Not Found message, give it a little bit more time for all the services to come up.
The login credentials are
Menu drop-down, chose
Projects and then create a new project with
Once you named your project, go ahead and select
Data Object from the
Create New Asset drop-down menu.
We need to create three data objects (Bin, Item, PackingSolution) with the relation shown below. You don't have to worry about the constructors, getters and setter, because the IDE will automatically create it. We only need to focus on the domain model, relations and its properties.
1.) Create domain models as POJO (plain old java objects)
Bin, as the name implies represents the bin in which we will insert an item. The bin has an ID, it has a maximum volume (size), above which we cannot insert any items, and an optional weight (cost). We can chose to make some bins more expensive than others.
Item is the object (item) that will be inserted in the bin. The item also has an ID (name) and a size. The item will go into only one bin, hence we need to define a field
bin of type
The last data object that we create is the so called
@PlanningSolution and it will be represented by
PackingSolution class. This is where we are defining the score and type of solution (e.g: hard_soft, simple, bendable etc...). In this case we will chose to define a score of type
HardSoftScore. The other two properties that we define are
listBins of type
listItems of type
listBins will hold all the bins with their properties while
listItems will have a list of all the items with their sizes.
Once you create an asset (in this case a Data Object), in order to create another asset, go back one step in your Spaces path and click on the
Create New Asset drop down menu, as shown below. In this case
Spaces > demos > BinPacking.
NOTE!!! Don't forget to save from time to time your work.
2.) Set relations between objects
Now that we have all three assets (objects), it is time to create the relations between them, as shown in the UML graph above.
2.1.) First we will define the
@PlanningEntity which is the
Item object. Select the
Item.java file and from the right side of the panel chose the optaplanner icon . In the newly opened menu on the right side, select the Planning Entity radio button as shown below.
From the same Model panel, click on the bin Identifier and you will see on the right side the settings for Planning Variable. Tick the box and fill in the text holder with
binReference. The name of this variable should be the same with the one that we will be setting up in the
You can go ahead and check the Source and see that all the constructors, getters, setters and annotations were automatically created by the KIE IDE.
2.2.) Next we will work on the
@PlanningSolution which is the
PackingSolution object. Select
PackingSolution.java file and just as the previous step, from the right side of the menu, click on the optaplanner icon . In the newly opened menu on the right side, select the Planning Solution radio button as shown below.
Automatically a score property of type
HardSoftScore will be created. We will leave the Solution Score Type as Hard soft score.
Also, as a resource, automatically a ScoreHolderGlobal class will be created.
In the same Model panel, select listBins Identifier, tick the Planning Value Range Provider box and fill in the id text holder with the same variable name as in the previous step (in this case
3.) Creating the solver configurations
Again go back one step in your Spaces path, and create a new asset by clicking on
Create New Asset button. From the drop down menu, chose
Solver configuration and perform the settings as shown in the picture below.
Or, select the Source tab and copy/paste the following code:
<solver xStreamId="1"> <scanAnnotatedClasses xStreamId="2"/> <scoreDirectorFactory xStreamId="3"/> <termination xStreamId="4"> <millisecondsSpentLimit>0</millisecondsSpentLimit> <secondsSpentLimit>30</secondsSpentLimit> <minutesSpentLimit>0</minutesSpentLimit> <hoursSpentLimit>0</hoursSpentLimit> <daysSpentLimit>0</daysSpentLimit> </termination> <constructionHeuristic xStreamId="5"> <constructionHeuristicType>FIRST_FIT</constructionHeuristicType> <entitySorterManner>DECREASING_DIFFICULTY_IF_AVAILABLE</entitySorterManner> </constructionHeuristic> <localSearch xStreamId="6"> <localSearchType>LATE_ACCEPTANCE</localSearchType> </localSearch> </solver>
4.) Time for the rules (constraints).
You can implement the constraints in OptaPlanner directly in Java or using Drools. We'll have another post with detailed explanation on how to build complex rules.
In this example we'll be using Drools because it allows us to separate the business logic from the domain objects. It will also be easier to maintain multiple rules in this format, rather than modifying the Java code.
To put it simple, "when conditions are met, then actions are triggered". The format of the rule is something like this:
rule <rule_name> <attribute> <value> when <conditions> then <actions> end
Now go back one step in your Spaces path, and create a new asset by clicking on
Create New Asset button. From the drop down menu, chose
DRL file and copy/paste the following code:
import java.lang.Number; // Hard constraints - these rules CANNOT be broken rule "HardConstraintVolume" /* * The total size of all items in that go in one bin * cannot be bigger than the volume of that specific bin. */ dialect "mvel" when // we have a bin with a certain volume $bin: Bin($volume: volume) // sum up the sizes of each item in the bin Number($totalVolume: intValue() > $volume) from accumulate (Item(bin == $bin, $size: size), sum($size)) then // the sum of all sizes (totalVolume) cannot excede the Bin volume scoreHolder.addHardConstraintMatch(kcontext, -($totalVolume - $volume)); end // Soft constraints - these rules can be broken rule "SoftConstraintCost" /* * Each bin has a certain cost (weight) which needs to be minimized */ dialect "mvel" when // we have a bin with a certain cost (weight) $bin: Bin($weight: weight) // if there is an item in the bin exists (Item(bin == $bin)) then // minimize the cost scoreHolder.addSoftConstraintMatch(kcontext, -$weight); end
From the upper right menu, you could click on the Validate button to make sure that the syntax is correct. If the validation is successful, next we need to check if our project successfully compiles.
5.) Let's compile
Again go back one step in your Spaces path, and from the upper right menu, click on Compile button. If the compilation is successful, we'll move forward to deploying our application.
6.) Build and deploy
We will need an execution environment to run our application and that is provided by KIE server. In order to start the KIE server docker container, run the following command:
docker run -p 8180:8080 --name kie-server --link drools-workbench:kie_wb jboss/kie-server-showcase:latest
Once the server is up, from the top bar Menu drop down, chose
Execution Servers and you should be able to see something like this:
Now go back to your project and from the upper right menu bar, click on
Build & Deploy.
Assuming a successful deployment, your execution environment should look like this:
NOTE!!! Make a note of the IP address of the KIE server container. In this case it is
7.) Finally, solving some bin packing.
The default user/pass for the KIE server is
kieserver/kieserver1!. In order to see if our application works, we will need to use Postman to send GET/PUT/POST requests. Don't forget to setup the Authorization for each request !!!
7.1.) Checking if the server works
In this case
binning_1.0.0 is the name and version of our application. Modify as required.
If you get a
200 OK, this means that our request was successful and the server is running correctly.
7.2.) Create a solver instance
At step 3, we've created a solver configuration. Now we need to PUT into our execution server those settings. First we need to check the path of that configuration file inside our project.
Inside our project, select the file that we've created at step 3 (in this case PackingConfiguration.solver.xml), then chose
Overview tab and inside, the
At the URI field, copy everything that comes after resources path, just as shown in the picture above. Paste the following XML snippet in the Body of your Postman tool.
<solver-instance> <container-id>binning_1.0.0</container-id> <solver-id>binningSolver</solver-id> <solver-config-file>bin/binning/PackingConfiguration.solver.xml</solver-config-file> <status>NOT_SOLVING</status> </solver-instance>
In the Headers add the following settings:
After a few seconds you should see a
201 Created status.
7.3.) Send the problem to be solved.
This is the step where we send the problem to the KIE server to be optimized.
Paste the following XML snippet in the Body of your Postman tool. Modify accordingly the class name and the domain object types.
<planning-problem class="bin.binning.PackingSolution"> <!-- These are the bins and their respective volumes --> <!-- We will be giving equal weight(cost) to all of them --> <listBins> <bin.binning.Bin> <id>1</id> <volume>24</volume> <weight>1</weight> </bin.binning.Bin> <bin.binning.Bin> <id>2</id> <volume>9</volume> <weight>1</weight> </bin.binning.Bin> <bin.binning.Bin> <id>3</id> <volume>15</volume> <weight>1</weight> </bin.binning.Bin> </listBins> <!-- these are the items that need to go inside the bins --> <!-- each item has an ID and a size --> <listItems> <bin.binning.Item> <id>1</id> <size>11</size> </bin.binning.Item> <bin.binning.Item> <id>2</id> <size>1</size> </bin.binning.Item> <bin.binning.Item> <id>3</id> <size>3</size> </bin.binning.Item> <bin.binning.Item> <id>4</id> <size>6</size> </bin.binning.Item> <bin.binning.Item> <id>5</id> <size>3</size> </bin.binning.Item> <bin.binning.Item> <id>6</id> <size>11</size> </bin.binning.Item> <bin.binning.Item> <id>7</id> <size>1</size> </bin.binning.Item> </listItems> </planning-problem>
In the Headers add the following settings:
7.4.) Check the status of the solver
As per our settings, the solver will start to perform the computations for 30 seconds. To check the status of the solver:
You will get a
200 OK back with one of the two solving statuses:
- SOLVING which means that the solver is still working
- NOT_SOLVING which means that the solver return a solution and a score
7.5.) Get the best solution
Once the solver is done computing,
This will return the allocation of the items in the bins, as well as the score. The result will look something like this:
<solver-instance> ... <best-solution class="bin.binning.PackingSolution"> <score>0hard/-2soft</score> <listBins> ... </listBins> <listItems> <bin.binning.Item> <size>11</size> <bin reference="../../../listBins/bin.binning.Bin"/> <id>1</id> </bin.binning.Item> <bin.binning.Item> <size>1</size> <bin reference="../../../listBins/bin.binning.Bin"/> <id>2</id> </bin.binning.Item> <bin.binning.Item> <size>3</size> <bin reference="../../../listBins/bin.binning.Bin"/> <id>3</id> </bin.binning.Item> <bin.binning.Item> <size>6</size> <bin reference="../../../listBins/bin.binning.Bin"/> <id>4</id> </bin.binning.Item> <bin.binning.Item> <size>3</size> <bin reference="../../../listBins/bin.binning.Bin"/> <id>5</id> </bin.binning.Item> <bin.binning.Item> <size>11</size> <bin reference="../../../listBins/bin.binning.Bin"/> <id>6</id> </bin.binning.Item> <bin.binning.Item> <size>1</size> <bin reference="../../../listBins/bin.binning.Bin"/> <id>7</id> </bin.binning.Item> </listItems> </best-solution> </solver-instance>
We had 3 bins (1, 2, 3) and from the above answer we see that only bin 1 (
bin.binning.Bin) and 3 (
bin.binning.Bin) were used. The score is
0hard/-2soft which means that none of the hard constraints were broken.
For detailed documentation on OptaPlanner, check here.
> ==Disclaimer==: This is by no means an original work it is merely meant to serve as a compilation of thoughts, code snippets and teachings from different sources.