Bin packing with OptaPlanner and Drools

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.

Prerequisites:

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.

main_menu

The login credentials are admin/admin.
From the Menu drop-down, chose Projects and then create a new project with Add Project.
project

Once you named your project, go ahead and select Data Object from the Create New Asset drop-down menu.

asset

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.

domain

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

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 List<Bin> and listItems of type List<Item>. The listBins will hold all the bins with their properties while listItems will have a list of all the items with their sizes.

add_fields

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.

new_asset

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 domain. In the newly opened menu on the right side, select the Planning Entity radio button as shown below.

Item

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 PackingSolution.java class.

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 domain. 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 binReference).

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.

compile

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:

kie-server
This means that your KIE server is up and running.

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:

deployment

NOTE!!! Make a note of the IP address of the KIE server container. In this case it is 172.17.0.3:8080.

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

GET request

http://172.17.0.3:8080/kie-server/services/rest/server/containers/binning_1.0.0

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 Metadata tab.

URI

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:

KeyValue
Acceptapplication/xml
Content-Typeapplication/xml
X-KIE-ContentTypeXSTREAM

PUT request

http://172.17.0.3:8080/kie-server/services/rest/server/containers/binning_1.0.0/solvers/binningSolver

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:

KeyValue
Acceptapplication/xml
Content-Typeapplication/xml
X-KIE-ContentTypeXSTREAM

POST - request

http://172.17.0.3:8080/kie-server/services/rest/server/containers/binning_1.0.0/solvers/binningSolver/state/solving

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:

GET - request

http://172.17.0.3:8080/kie-server/services/rest/server/containers/binning_1.0.0/solvers/binningSolver

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,

GET - request

http://172.17.0.3:8080/kie-server/services/rest/server/containers/binning_1.0.0/solvers/binningSolver/bestsolution

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[3]"/>
                <id>6</id>
            </bin.binning.Item>
            <bin.binning.Item>
                <size>1</size>
                <bin reference="../../../listBins/bin.binning.Bin[3]"/>
                <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[3]) 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.