Linear and Integer programming are essential tools in mathematical optimizations. They can be used to provide an educated answer to a wide range of problems. Although they are not in the mainstream software development, there are some excellent libraries out there. In this post, I’ll cover how to run LP and IP computations from Java with ojAlgo.
This section detailed how to add an extra repository as ojAlgo was missing from Maven Central. Fortunately, it is not true any more, and this part is now obsolete.
Simply add a new dependency to your project:
The sample problems
First, we need a problem to solve. I’ve searched a bit and found this, the problem is based on the one described in the 8th slide.
The LP problem
Let’s say there are 4 investment funds: The first one is expected to pay $9 for every $6 investment, the second to pay $5 for every $4, the third is to pay $6 for every $5, and the last to pay $4 for every $2. The maximum allowed amount to be bought is capped at $6M, $3M, $5M and $2M, respectively. We have $10M, how much we should buy from each fund?
The problem can be summarized in a table:
And we have $10M to invest.
Formalizing the LP problem
So, we have x1, x2, x3 and x4, these represents the results we are looking for. And we have the following constraints:
And we have an objective function:
Solving the LP problem in Java
First, we need the four variables with a weight. The weights are the coefficients in the objective function.
Note: I’m using Guava too, as it makes working with collection much more fun.
And we store them in the variables variable.
Then, we need to construct an ExpressionBasedModel then add the variables:
Next, we add the constraints. First, the upper constraint:
Then that each variable is between 0 and 1 inclusively:
Update: As a shorthand, we can set the constraints directly to the Variable:
Last part is to solve and use the results:
We can get the individual variables with result.get(..), and the result amount (our sum revenue) with result.getValue()
If we run out program, we get the output:
The IP problem
Let’s rephrase the problem to an IP one! Imagine we have 4 places to build factories. If we build on the first spot, it would cost $6M, but it is expected to produce $9M, the second spot would cost $3M with an expected revenue of $5M, and so on, just like the last example. We have $10M capital, which factories should we build?
Our formalization is exactly the same as for the LP problem, we only have one additional requirement: All the result are integers (in fact they are binary, as we either build the factory or we don’t).
In out Java program, making the change is easy, as we just set the variables to be integers with a simple call:
Update: For binary variables, there is a shortcut we can use:
This is exactly the same as setting the upper and lower bounds to 1 and 0 respectively along with setting the integer property.
When we run the program, we get the output:
As Optimatika pointed out some best practices when using the API, I’ve updated the relevant parts. Thanks!
As luke777 pointed out, the API changed with v43. I’ve updated the code samples and the GitHub project. Thanks!