Linear Programming in Java: Solving the Assignment Problem

1. Overview

Linear Programming is an optimization algorithm to minimize or maximize an objective function subject to a set of linear constraints.

In this tutorial, we’ll explore how to solve an assignment problem using Java. We’ll primarily focus on pure Java-based numerical libraries, including ojAlgo and Apache Commons Math, and demonstrate how each could be used to solve the problem.

2. Assignment Problem

An assignment problem is a classic optimization problem that involves assigning a set of persons to a set of tasks exclusively. Now, let’s elaborate on the problem using the following scenario.

We have three volunteers and three working locations. The goal is to assign each volunteer to a location and minimize the volunteers’ total travel time. This problem is subject to two constraints:

1. Each volunteer can be assigned to only one location, and
2. One location only needs one volunteer.

The travel times between each volunteer and each location are known and fixed. We can represent these travel times as a cost matrix. Let’s define an example to demonstrate how to solve it in the latter section:

3. Mathematical Definitions

Before we dive into the implementation, let’s first define this assignment problem mathematically. This will help us clarify the objective function and constraints that we will adopt in our implementation later.

3.1. Objective Function

Based on this formulation, we define our objective function as follows:

The goal is to minimize the total travel time between volunteers and locations, where i denotes a volunteer and j denotes a location.

t_ij represents the travel time between volunteer i and location j, as specified by the travel time cost matrix defined in Section 2. Lastly, x_ij indicates whether the volunteer i is assigned to location j.

3.2. Constraints

Given the constraints we depicted in Section 2,  we define the first constraint as:

For a single volunteer i, by summing up the assignment x_ij over all possible location j. Confining the summation to one ensures each volunteer is assigned to one and only one location.

The second constraint is similar to the first one:

This confines each location to one and only one volunteer.

Finally, we need an additional constraint. Since each assignment x_ij is a discrete event where we either assign or do not assign a volunteer to a location, we confine the assignment variables to be binary:

where one indicates that volunteer i is assigned to location j, and zero indicates no assignment is made. This constraint guarantees a volunteer cannot be assigned to a location partially.

4. Solving with ojAlgo

After defining the mathematical formulation of the assignment problem, let us move on to the practical part, where we’ll put the function and constraints together using ojAlgo programmatically.

ojAlgo is an open-source Java library for numerical optimization and supports various optimization algorithms, including linear programming. This makes it a perfect library to solve this classical problem.

To get started with ojAlgo, let’s add the following Maven dependency to our pom.xml:

<dependency>
    <groupId>org.ojalgo</groupId>
    <artifactId>ojalgo</artifactId>
    <version>56.2.0</version>
</dependency>

4.1. Model Creation

We start by populating a cost matrix introduced earlier as a two-dimensional array. Each row represents a volunteer, and each column represents a location. Hence, the value of t[i][j] corresponds to the travel time between volunteer i and location j that was represented as t_ij in the previous section:

double[][] t = {
    {27, 6, 21},
    {18, 12, 9},
    {15, 24, 3}
};

Next, we create an optimization model using ExpressionsBasedModel, and a two-dimensional Variable array x to store the assignment variables. Each assignment variable represents whether a volunteer i is assigned to location j, which corresponds to x_ij in the previous section:

int volunteers = t.length;
int locations = t[0].length;
ExpressionsBasedModel model = new ExpressionsBasedModel();
Variable[][] x = new Variable[volunteers][locations];

4.2. Objective Function

We now initialize each variable as binary via binary(), which enforces the assignment x_ij to be either zero or one. By doing so, ojAlgo will run the model as an integer linear program.

We associate each assignment variable x_ij with the corresponding travel cost t_ij using the weight(t[i][j]). Collectively, the assignment variables and the weights define the objective function:

for (int i = 0; i < volunteers; i++) {
    for (int j = 0; j < locations; j++) {
        x[i][j] = model
          .newVariable("Assignment_" + i + "_" + j)
          .binary()
          .weight(t[i][j]);
    }
}

It’s worth noting that we only define the objective function in this stage, but do not specify whether we minimize or maximize it yet.

4.3. Constraints

When we defined our objective function, we had already defined one of our constraints, which states that the assignment must be binary. Let’s define the rest of the two constraints:

for (int i = 0; i < volunteers; i++) {
    Expression volunteerConstraint = model.addExpression("Volunteer_" + i).level(1);
    for (int j = 0; j < locations; j++) {
        volunteerConstraint.set(x[i][j], 1);
    }
}

This code fragment defines the volunteer constraint. For each volunteer, it creates a linear expression whose value is equal to one via .level(1).

The inner loop adds all assignment variables for the volunteer, meaning this constraint assigns each volunteer to one and only one location.

Likewise, each location can have only one volunteer. We’ll similarly define the location constraint:

for (int j = 0; j < locations; j++) {
    Expression locationConstraint = model.addExpression("Location_" + j).level(1);
    for (int i = 0; i < volunteers; i++) {
        locationConstraint.set(x[i][j], 1);
    }
}

These two constraints ensure a one-to-one mapping between volunteers and locations.

4.4. Model Solving

With the objective function and constraints defined, we could finally optimize the model by calling .minimize(), which instructs ojAlgo to find the assignment that minimizes the total travel time:

var result = model.minimise();

If we check the values stored in the Variable array x, we can see that the final assignments are equal to:

new double[][] {
    {0, 1, 0}, 
    {1, 0, 0}, 
    {0, 0, 1}
}

The following table shows the cost matrix with the selected assignments highlighted:

The total travel time is 27 by summing up each assigned travel time, which is the optimal solution of this assignment example. From the solved model, we could also get the minimized travel time by:

double totalCost = result.getValue();

5. Solving with Apache Commons Math

Besides ojAlgo, we could also solve this assignment problem using Apache Commons Math. It is an open-source Maths library that includes mathematics and statistics components.

We need the following Maven dependency in our pom.xml to get started with:

<dependency>
    <groupId>org.apache.commons</groupId>
    <artifactId>commons-math3</artifactId>
    <version>3.6.1</version>
</dependency>

5.1. Helper Function

We start by creating a helper function. Commons Math will define the objective as a one-dimensional array. We’ll need a function to map our two-dimensional assignment variables (volunteer, location) into a one-dimensional index:

private int index(int i, int j, int locationsAvailable) {
    return i * locations + j;
}

5.2. Objective Function

Similar to what we did in ojAlgo, we create the objective function using our travel time cost matrix t. We’ll use the helper function to convert the cost matrix into a one-dimensional array that Commons Math requires:

int volunteers = t.length;
int locations = t[0].length;
int vars = volunteers * locations;

double[] x = new double[vars];
for (int i = 0; i < volunteers; i++) {
    for (int j = 0; j < locations; j++) {
        x[index(i, j, locations)] = t[i][j];
    }
}

LinearObjectiveFunction objective = new LinearObjectiveFunction(x, 0);

The second argument of LinearObjectiveFunction is a constant term. However, we don’t need it to solve the assignment problem, since our coefficient is only t_ij · x_ij without any fixed offset.

5.3. Constraints

Next, we define our linear constraints of the assignment problem. Commons Math represents each constraint as a LinearConstraint instance. We’ll put our constraints into a Collection:

Collection<LinearConstraint> constraints = new ArrayList<>();

The first constraint confines each volunteer to one and only one location:

for (int i = 0; i < volunteers; i++) {
    double[] x_i = new double[vars];
    for (int j = 0; j < locations; j++) {
        x_i[index(i, j, locations)] = 1.0;
    }
    constraints.add(new LinearConstraint(x_i, Relationship.EQ, 1.0));
}

and the second constraint confines each location to have only one volunteer:

for (int j = 0; j < locations; j++) {
    double[] x_j = new double[vars];
    for (int i = 0; i < volunteers; i++) {
        x_j[index(i, j, locations)] = 1.0;
    }
    constraints.add(new LinearConstraint(x_j, Relationship.EQ, 1.0));
}

Even though we use a different Java implementation this time, the constraint definitions are pretty much the same by confining the summation of assignment variables to one.

5.4. Model Solving

We have the objective function and constraints ready, and we could solve the linear program using the SimplexSolver. Since we are minimizing the total travel time, we specify GoalType.MINIMIZE as our optimization goal:

SimplexSolver solver = new SimplexSolver();
PointValuePair solution = solver.optimize(
  objective,
  new LinearConstraintSet(constraints),
  GoalType.MINIMIZE,
  new NonNegativeConstraint(true)
);

The last argument confines the assignment variable x_ij be a non-negative number.

We could get the optimized cost and the final assignments after optimization by calling:

double totalCost = solution.getValue();
double[] point = solution.getPoint();

If we transform the solution point array back into a two-dimensional representation, we find out the assignment is identical to the ojAlgo with totalCost equal to 27.

6. Conclusion

In this article, we presented a classical assignment problem that could be solved by linear programming.

We also demonstrated how to apply the ojAlgo and Apache Commons Math libraries to solve this problem programmatically. These libraries prove to be powerful tools for solving numerical optimization problems.

As usual, our complete code examples are available over on GitHub.