Using Google OR-Tools to solve an LP problem in AnyLogic

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?


gif

The LP Problem


Maximize 3x + 4y subject to the following constraints:

x + 2y≤14

3xy≥0

xy≤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.


Source: https://developers.google.com/optimization/lp/lp_example



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.

  1. Import the linear solver wrapper,

  2. declare the LP solver,

  3. define the variables,

  4. define the constraints,

  5. define the objective,

  6. call the LP solver; and

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