Every so often inside our simulation models, we might need to make use of some optimization tool, whether it is to solve a simple linear problem or some advanced vehicle routing problem with time windows and capacity constraints. In this post, we explore the use of an open-source, free-to-use software package created by Google, called OR-Tools, to solve a linear problem (LP).
Although we will be looking at using the LP solving capabilities of OR-Tools, it has many other optimization capabilities, and since it is Java-based, it fits in nicely within the AnyLogic framework. In a future post, we will cover using Google OR tools to solve a Vehicle Routing Problem (VRP).
Ready to use OR tools in AnyLogic?
The LP Problem
Maximize 3x + 4y subject to the following constraints:
x + 2y≤14
3x – y≥0
x – y≤2
The objective function, 3x + 4y, and the constraints are given by linear expressions, making this a linear problem.
The constraints define the feasible region, which is the triangle shown below, including its interior.
Setting up Google OR-Tools
The setup process for Google OR-Tools can be a bit daunting at first, with a few places to get lost, especially since the setup is in no way created for AnyLogic users but more for pure Java programmers. Luckily with these handy step-by-step instructions, you should be able to get it up and running in no time.
FYI: This process has changed in the last two years since I originally used it for a project back in 2020, see here, and it is likely to change again in the future... Google OR-Tools is an active project with various additions, improvements and enhancements happening on a regular basis. Please contact us if this process has changed so significantly that this post is outdated.
Download the required files and libraries.
Here you have two options
1) Follow the step-by-step instructions on the Google OR tools website as described here
2) Download the 4 (+1 if you are using Windows) jar files as I described below
If you try step 1, it will consume about an hour of your time, and when you are done, you will still have a few missing libraries that are required to use Google OR-tools inside AnyLogic, so I would not advise it.
If you go for option 2 you will need the following libraries.
ortools-darwin - download here
ortools-java - download here
jna - download here
protobuf-java - download here
Additional for Windows: ortools-win32 - download here
OR you can just download the example at the end of this post.
FYI: For advanced users, check out Guilherme Coelho post about using Maven here, and you can automate this download process.
Solving the LP using Google OR tools inside AnyLogic
The steps as provided in the Google OR Tools tutorial are as follows.
Import the linear solver wrapper,
declare the LP solver,
define the variables,
define the constraints,
define the objective,
call the LP solver; and
display the solution
Steps 2-7 can all be done in a single function.
Step 1) Import all the libraries to your AnyLogic model
The first step is to import the libraries to your Anylogic model by adding them as per the screenshot below or check the AnyLogic help file here for more details
2) Declare the LP solver
MPSolver solver = MPSolver.createSolver("GLOP");MPsolver is a wrapper for several different solvers, including Glop. The code below declares the GLOP solver.
Note: Substitute PDLP for GLOP to use an alternative LP solver. For more details on choosing solvers, see advanced LP solving, and for installation of third-party solvers, see the installation guide.
3) Define the variables
First, create variables x and y whose values are in the range from 0 to infinity.
double infinity = java.lang.Double.POSITIVE_INFINITY;
// x and y are continuous non-negative variables.
MPVariable x = solver.makeNumVar(0.0, infinity, "x");
MPVariable y = solver.makeNumVar(0.0, infinity, "y");
System.out.println("Number of variables = " + solver.numVariables());4) Define the constraints
Next, define the constraints on the variables. Give each constraint a unique name (such as constraint0), and then define the coefficients for the constraint.
// x + 2*y <= 14.
MPConstraint c0 = solver.makeConstraint(-infinity, 14.0, "c0");
c0.setCoefficient(x, 1);
c0.setCoefficient(y, 2);
// 3*x - y >= 0.
MPConstraint c1 = solver.makeConstraint(0.0, infinity, "c1");
c1.setCoefficient(x, 3);
c1.setCoefficient(y, -1);
// x - y <= 2.
MPConstraint c2 = solver.makeConstraint(-infinity, 2.0, "c2");
c2.setCoefficient(x, 1);
c2.setCoefficient(y, -1);
System.out.println("Number of constraints = " + solver.numConstraints());5) Define the objective
The following code defines the objective function, 3x + 4y, and specifies that this is a maximization problem.
// Maximize 3 * x + 4 * y.
MPObjective objective = solver.objective();
objective.setCoefficient(x, 3);
objective.setCoefficient(y, 4);
objective.setMaximization();6) Call the LP solver
final MPSolver.ResultStatus resultStatus = solver.solve();7) Display the solution
if (resultStatus == MPSolver.ResultStatus.OPTIMAL) {
System.out.println("Solution:");
System.out.println("Objective value = " + objective.value());
System.out.println("x = " + x.solutionValue());
System.out.println("y = " + y.solutionValue());
} else {
System.err.println("The problem does not have an optimal solution!");
}
System.out.println("\nAdvanced usage:");
System.out.println("Problem solved in " + solver.wallTime() + " milliseconds");
System.out.println("Problem solved in " + solver.iterations() + " iterations");Simply put all of this code into a function or button in your AnyLogic model and you can execute and get the result almost instantly!
Summary
Google OR-Tools is a super useful, flexible, lightweight tool used to solve several operations research-type problems. Having a Java wrapper makes it a perfect fit for AnyLogic models.
Visit the Google-OR tools website for more details or contact us if you have a custom implementation and require assistance.
Download the example model below or from the AnyLogic cloud here
P.S. Watch this space for a future post where I will be doing an example of a vehicle routing problem!
What next?
If you liked this post, you are welcome to read more posts by following the links above to similar posts. Remember to subscribe, so that you can get notifications via email or you can also join the mobile app here! Or follow us on any of the social media accounts for future updates. The links are in the Menu bar at the top or the footer at the bottom.
If you want to contact us for some advice, maybe a potential partnership or project or just to say "Hi!", feel free to get in touch here and we will get back to you soon!
댓글