Apache common SimplexSolver ObjectiveFunction for maximizing the sum of values in a matrix

Question

I am trying to solve the following linear problem by using the Simplex solver from apache-commons: org.apache.commons.math3.optim.linear.SimplexSolver.

n is the number of rows
m is the number of columns
L is a global limit for the sum value of each row

This is what I have so far:

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

double[][] A = calculateAValues();
// m = count of columns
// constraint 1: the sum of values in all column must be <= 1
for(int i = 0; i < m; i++) {
    double[] v = new double[n];
    for(int j=0; j < n; j++) {
        v[j] = 1;
    }
    constraints.add(new LinearConstraint(v, Relationship.LEQ, 1));
}
// n = count of rows
// constraint 2: sum of a_i,j in all row must be <= L (Limit)
for(int i = 0; i < n; i++) {
    double[] v = new double[m];
    for(int j=0; j < m; j++) {
        v[j] =  A[i][j];
    }
    constraints.add(new LinearConstraint(v, Relationship.LEQ, L));
}

double[] objectiveCoefficients = new double[n * m];
for(int i = 0; i < n * m; ++i) {
    objectiveCoefficients[i] = 1;
}

LinearObjectiveFunction objective = new LinearObjectiveFunction(objectiveCoefficients, 0);
LinearConstraintSet constraintSet = new LinearConstraintSet(constraints);

SimplexSolver solver = new SimplexSolver();
PointValuePair solution = solver.optimize(objective, constraintSet, GoalType.MAXIMIZE);
return solution.getValue();

I have trouble getting the objective function right, and also it might be some other things missing. My every attempt so far resulted in UnboundedSolutionException.

Lungan

Answer 1

The error seems to be in the coefficient arrays of the linear constraints.

You have n*m variables therefore the coefficient arrays for the constraints and the objective functions must have length n*m. Unfortunately the SimplexSolver silently expands the constraints array if they are shorter than the array of the objective function. So your code did not specify the correct constraints leading to an unbounded solution.

Constraint 1: the sum of values in all column must be <= 1

for(int j=0; j<m; j++)
{
    double[] v = new double[n*m];
    for(int i=0; i<n; i++)
        v[i*n + j] = 1;
    constraints.add(new LinearConstraint(v, Relationship.LEQ, 1));
}

Constraint 2: sum of a_i,j in all row must be <= L (Limit)

// n = count of rows
for(int i=0; i<n; i++)
{
    double[] v = new double[n*m];
    for(int j=0; j<m; j++)
        v[i*n + j] = A[i][j];
    constraints.add(new LinearConstraint(v, Relationship.LEQ, L));
}

Objective coffecifients:

double[] objectiveCoefficients = new double[n * m];
Arrays.fill(objectiveCoefficients, 1.0);
LinearObjectiveFunction objective = LinearObjectiveFunction(objectiveCoefficients, 0);

The constraint x_ij <= 1 is already fulfilled because of constraint 2. Maybe it makes things more clear to also explicitly specify a constraint for 0 <= x_ij using a NonNegativeConstraint:

SimplexSolver solver = new SimplexSolver();
PointValuePair solution = solver.optimize(objective, constraintSet,
     GoalType.MAXIMIZE, new NonNegativeConstraint(true));

Capricorn