Trying to implement and solve a Linear Programming problem with in Java using apache-commons-math:
<dependency>
<groupId>org.apache.commons</groupId>
<artifactId>commons-math3</artifactId>
<version>3.6.1</version>
</dependency>
Here is the code:
import org.apache.commons.math3.optim.PointValuePair;
import org.apache.commons.math3.optim.linear.*;
import org.apache.commons.math3.optim.nonlinear.scalar.GoalType;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Main {
public static void simplex() {
double[] supplierCapacities = {200, 100, 50}; // cells G8:G10
double[] consummerCapacities = {150, 75, 50, Arrays.stream(supplierCapacities).sum()}; // cells B12:E12
int numberOfSuppliers = supplierCapacities.length;
int numberOfConsummers = consummerCapacities.length;
double[] prices = {
2, 2, 2, 1,
2, 2, 2, 1,
2, 2, 2, 1
}; // cells B16:E18
LinearObjectiveFunction objectiveFunction = new LinearObjectiveFunction(prices, 0); // cell C4 to maximize
// constraints
List<LinearConstraint> constraintsList = new ArrayList<>();
// the amount of products from supplier N to any consumers must not exceed the supplier capacity
// F8:F10 <= G8:G10
for (int i = 0; i < numberOfSuppliers; ++i) {
double[] coeffs = new double[numberOfConsummers];
Arrays.fill(coeffs, 1.0);
LinearConstraint lessOrEqualToSupplierCapacity = new LinearConstraint(coeffs, Relationship.LEQ, supplierCapacities[i]);
constraintsList.add(lessOrEqualToSupplierCapacity);
}
// the amount of products received by consummer M from any supplier must not exceed the consommer capacity
// B11:E11 <= B12:E12
for (int i = 0; i < numberOfConsummers; ++i) {
double[] coeffs = new double[numberOfSuppliers];
Arrays.fill(coeffs, 1);
LinearConstraint lessOrEqualtToConsommerCapacity = new LinearConstraint(coeffs, Relationship.LEQ, consummerCapacities[i]);
constraintsList.add(lessOrEqualtToConsommerCapacity);
}
// gather up all constraints
LinearConstraintSet linearConstraintSet = new LinearConstraintSet(constraintsList);
// solve
SimplexSolver solver = new SimplexSolver();
PointValuePair solution = solver.optimize(objectiveFunction, linearConstraintSet, GoalType.MAXIMIZE, new NonNegativeConstraint(true));
System.out.println(solution);
}
public static void main(String[] args) {
simplex();
}
}
The code throws an UnboundedSolutionException
Exception in thread "main" org.apache.commons.math3.optim.linear.UnboundedSolutionException: solution non bornée
at org.apache.commons.math3.optim.linear.SimplexSolver.doIteration(SimplexSolver.java:325)
at org.apache.commons.math3.optim.linear.SimplexSolver.doOptimize(SimplexSolver.java:389)
at org.apache.commons.math3.optim.linear.SimplexSolver.doOptimize(SimplexSolver.java:65)
at org.apache.commons.math3.optim.BaseOptimizer.optimize(BaseOptimizer.java:153)
at org.apache.commons.math3.optim.BaseMultivariateOptimizer.optimize(BaseMultivariateOptimizer.java:65)
at org.apache.commons.math3.optim.nonlinear.scalar.MultivariateOptimizer.optimize(MultivariateOptimizer.java:63)
at org.apache.commons.math3.optim.linear.LinearOptimizer.optimize(LinearOptimizer.java:94)
at org.apache.commons.math3.optim.linear.SimplexSolver.optimize(SimplexSolver.java:154)
at Main.simplex(Main.java:53)
at Main.main(Main.java:59)
However I doubt this problem is unbounded. Using Libreoffice Solver, it appears to be working. Here is a screenshot of the spreadsheet, the comments in the java code refers to this spreadsheet.
The problem is to find the quantity to deliver from suppliers to consumers maximizing the profits given prices for each pair or (supplier,consummer) (min-cost max-flow)
