Applying Optaplanner to everyday problems

If you work anywhere in Devops, you probably have had a few (or more) times when you find something you have to do in your everyday life that’s either hard, complex, or probably just going to take you some time you’d rather use to anything else. And then the thought comes to mind: “I probably can build a script to do this for me” or “If I wanted I could write a program that would save me some time doing this” or something of the sort. Today I had one of those moments where I decided to go ahead and code a solution to save me some time, and I woud like to share it to you.

I have recently moved into a house with a lot of roof. So I decided to make a small garden on top of it. I took some measures, did some research, and came up with this idea for my very own roof garden:

A garden idea

I designed some flat pots, measured how much space they will take, and when I found a size I would be confortable with for the far boxes, I decided to go ahead and find somewhere to buy wood to build them. I found a place where wood was cheap, but they delived preestablished sizes and I just wasn’t sure which length of wood beams would be best for all the measures I wanted to use.

I remembered this was a mathematical issue, but math is not always my best buddy. I just couldn’t remember the right mathematical approach to solving this, but I did know that if I had a set of options to choose from, I would be able to do so easily: just pick the one with the least scrap. And then it hit me: I could try and solve this as a np-complete problem

 What is a np-complete problem?

A np-complete problem is a non-deterministic polynomial complete problem. That’s quite clear, right? Of course not, it’s just the longest name I remember regarding anything mathematical and I like to flaunt it as much as I can (it’s great to leave mouths open in job interviews).

A planning problem is a soemthing you can’t express mathematically; So if you try to write a formula to explain the problem in its whole and try to find it’s optimal solutions, you wouldn’t be able to do so (yet). But, if you came through some way to a couple possible solutions of the problem, you would be able to write a scoring formula to see which of the solutions is better than the other.

This fits to our case because I didn’t remember how to write my problem in a mathematical way to see how to avoid buying extra wood. I did remember something about using integrals, but just couldn’t put my finger on it. But I could write quite easily a formula to see, given a set of cuts I needed, and the amount and size of the beams, which solution fitted better (i.e. the one that used the least wood)

If I had to write this from scratch, I would have probably investigated the mathematical option a little better. But I knew I had access to a lot of planning problems example provided by Optaplanner. Optaplanner is a lightweight, embeddable planning engine, which comes with a lot of benchmarks and possible solutions to planning problems. To use it for my case, I followed these steps:

Step 1: Investigate existing solutions

Optaplanner comes with a lot of examples you can investigate and run, to see how to solve similar issues. If you download and run the optaplanner example application following these instructions you will find a lot of examples of planning problems, with different ways of being solved:

Step 2: Find your best fit

From all the different types of problems they present to you in this UI, you can go shopping for your goldielocks problem. Not too complex, not too simple, and basically a similar search of what you want, but with different names. In my case, I took the cloud balancing problem as basis for finding my own solution. This is because they were both similar problems. You had specific elements that should fit inside some bags, without exceeding their capacity. In the cloud balancing problem, this was defined as processes and computers. In my mundane case, the same problem was defined with wood cuts and wood beams.

Step 3: Refactor to fit your needs

Once you find the one you prefer, you get to refactor all the components. In my case, I refactored the CloudComputer into a WoodBeam. Where I used to have cpu power, bandwidth and memory as fixed parameters, now I had the length of the beam in millimeters. The CloudProcess went a similar path, becoming WoodMeasure. The CloudBalance class was changed into WoodAssignment, and the generator classes that populated a WoodAssignment were now based on the measures I had for each type of box I wanted to build.

I loaded the measures I took from my 3D model to build loading methods for all the WoodMeasure objects needed for a small box (50cm x 50cm) and a big box (1m x 1m). Then I let the planning problem try to solve it through the WoodProblemHelloWorld class (previously called CloudBalancingHelloWorld)

Step 4: Cut out all the fat

The optaplanner examples is great for investigation. It lets you find quickly which way is the best to run your solution. But it has a lot of extra content that you might find confusing or distracting. In my case, I just wanted a small script to run from command line. I didn’t need all the Swing UI components, so I started removing a lot of that.

Also, I had a lot of other examples in the application that weren’t necessary for my case. So I started removing all of the ones I wasn’t using. Nurse rostering, traveling salesman, course scheduling, all great examples depending on what you want to do, just not fit for my particular case.

Step 5: Run and analyze

After WoodProblemHelloWorld was ready, I started running it to see the different outcomes. The solver strategy was implemented in the solveForBeamsOfSize, which takes the SolverFactory (used to load algorithms strategies to run the np-complete problem) and the size of the beam to generate all measures and a maximum number of beams. The best solution is found when you

  • Don’t try and use more length on a beam than available (hard constraint, cannot be broken or the solution is phisicaly impossible)
  • You use the least amount of beams (soft constraint, it is desirable to not break this constraint but not required by the physics of the problem)

The algorithm used was best fit decreasing, which indicates we try to fit the biggest measure on the beams and fit the smaller ones later. It eventually improves on measures until it finds one that breaks no hard constraints.

The code of the solveForBeamsOfSize method can be seen here, and as you can see, it’s pretty small:


Solver solver = solverFactory.buildSolver();
// Load 8 small boxes and 1 large box
WoodAssignment unsolvedWoodAssignment = new WoodProblemGenerator().createWoodProblem(8, 1, beamsLength);
WoodAssignment solvedWoodAssignment = null;
// Solve the problem
solver.solve(unsolvedWoodAssignment);
solvedWoodAssignment = (WoodAssignment) solver.getBestSolution();
//store how many beams we're using
int beamsAmount = solvedWoodAssignment.getUsedBeams().size();
// Display the result
System.out.println("\nSolved woodProblem with 8 small boxes, 1 big one, and "
+ beamsAmount + " beams of " + beamsLength + "mm:\n"
+ toDisplayString(solvedWoodAssignment));

The output find out the following results:

  • using 2.44m beams: 25 beams were necessary
  • using 3.05m beams: 19 beams were necessary
  • using 3.66m beams: 16 beams were necessary
  • using 4.27m beams: 14 beams were necessary

The beams were 10 cm wide, and charged by squared meters used. Since the first result was using 6.1 squared meters while the other three used about 5.9 squared meters all last three options were cheaper. Also, since the smaller beams would be easier to handle, I opted to use the 3.05m beams. Condensing the solution printed out, this is the cuts I’ll use:

  1. 3 cuts of 1000mm each, and 1 cut of 50mm (leftover: nothing)
  2. 3 cuts of 1000mm each, and 1 cut of 50mm (leftover: nothing)
  3. 3 cuts of 1000mm each, and 1 cut of 50mm (leftover: nothing)
  4. 1 cut of 1000mm, 2 cuts of 973mm, and 2 cuts of 50mm (leftover: 4mm)
  5. 3 cuts of 973mm, and 2 cuts of 50mm (leftover: 31mm)
  6. 3 cuts of 973mm, and 2 cuts of 50mm (leftover: 31mm)
  7. 6 cuts of 500mm each, and 1 cut of 50mm (leftover: nothing)
  8. 6 cuts of 500mm each, and 1 cut of 50mm (leftover: nothing)
  9. 6 cuts of 500mm each, and 1 cut of 50mm (leftover: nothing)
  10. 6 cuts of 500mm each, and 1 cut of 50mm (leftover: nothing)
  11. 6 cuts of 500mm each, and 1 cut of 50mm (leftover: nothing)
  12. 6 cuts of 500mm each, and 1 cut of 50mm (leftover: nothing)
  13. 4 cuts of 500mm each, 2 cuts of 473mm, and 2 cuts of  50mm (leftover: 4mm)
  14. 6 cuts of 473mm each, and 4 cuts of 50mm each (leftover: 12mm)
  15. 6 cuts of 473mm each, and 4 cuts of 50mm each (leftover: 12mm)
  16. 6 cuts of 473mm each, and 4 cuts of 50mm each (leftover: 12mm)
  17. 6 cuts of 473mm each, and 4 cuts of 50mm each (leftover: 12mm)
  18. 6 cuts of 473mm each, and 4 cuts of 50mm each (leftover: 12mm)
  19. 39 cuts of 50mm each (leftover:1100mm)

Try it yourself!

You can find the resulting code of the Wood Problem here. Feel free to send any queries, comments or pull requests on it. We’ll be glad to see this being helpful to you. So let us know, what problems in your everyday life you see software like this would help you get through faster?

Keep in touch!

Posted in drools, optaplanner, planning.

Leave a Reply

Your email address will not be published. Required fields are marked *