Apache common SimplexSolver ObjectiveFunction to maximize the sum of values ​​in a matrix

Question

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

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

This is what I still have:

 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 problems with the correct objective function, and also maybe some other things are missing. My every attempt so far has led to an UnboundedSolutionException .

Answer 1

There seems to be an error in the linear constraint coefficient arrays.

You have n*m variables, so the arrays of coefficients for constraints and the objective functions must be n*m long. Unfortunately, SimplexSolver quietly extends the array of constraints if they are shorter than the array of the objective function. Thus, your code did not indicate the correct restrictions leading to an unlimited solution.

Limit 1: the sum of the values ​​in all columns 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: the sum of a_i, j in all lines 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 Coefficients:

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

The restriction x_ij <= 1 has already been implemented due to restriction 2. Perhaps this makes it more clear and explicitly specify the restriction for 0 <= x_ij using NonNegativeConstraint :

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