SimplexSolver returns unfeasible solution
-----------------------------------------
Key: MATH-434
URL: https://issues.apache.org/jira/browse/MATH-434
Project: Commons Math
Issue Type: Bug
Affects Versions: 2.1
Reporter: Wayne Witzel
The SimplexSolver is returning an unfeasible solution:
import java.util.ArrayList;
import java.text.DecimalFormat;
import org.apache.commons.math.linear.ArrayRealVector;
import org.apache.commons.math.optimization.GoalType;
import org.apache.commons.math.optimization.OptimizationException;
import org.apache.commons.math.optimization.linear.*;
public class SimplexSolverBug {
public static void main(String[] args) throws OptimizationException {
LinearObjectiveFunction c = new LinearObjectiveFunction(new
double[]{0.0d, 1.0d, 1.0d, 0.0d, 0.0d, 0.0d, 0.0d}, 0.0d);
ArrayList<LinearConstraint> cnsts = new ArrayList<LinearConstraint>(5);
LinearConstraint cnst;
cnst = new LinearConstraint(new double[] {1.0d, -0.1d, 0.0d, 0.0d,
0.0d, 0.0d, 0.0d}, Relationship.EQ, -0.1d);
cnsts.add(cnst);
cnst = new LinearConstraint(new double[] {1.0d, 0.0d, 0.0d, 0.0d, 0.0d,
0.0d, 0.0d}, Relationship.GEQ, -1e-18d);
cnsts.add(cnst);
cnst = new LinearConstraint(new double[] {0.0d, 1.0d, 0.0d, 0.0d, 0.0d,
0.0d, 0.0d}, Relationship.GEQ, 0.0d);
cnsts.add(cnst);
cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 0.0d, 1.0d, 0.0d,
-0.0128588d, 1e-5d}, Relationship.EQ, 0.0d);
cnsts.add(cnst);
cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 0.0d, 0.0d, 1.0d,
1e-5d, -0.0128586d}, Relationship.EQ, 1e-10d);
cnsts.add(cnst);
cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, -1.0d,
0.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
cnsts.add(cnst);
cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, 1.0d, 0.0d,
0.0d, 0.0d}, Relationship.GEQ, 0.0d);
cnsts.add(cnst);
cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, 0.0d,
-1.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
cnsts.add(cnst);
cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, 0.0d, 1.0d,
0.0d, 0.0d}, Relationship.GEQ, 0.0d);
cnsts.add(cnst);
DecimalFormat df = new java.text.DecimalFormat("0.#####E0");
System.out.println("Constraints:");
for(LinearConstraint con : cnsts) {
for (int i = 0; i < con.getCoefficients().getDimension(); ++i)
System.out.print(df.format(con.getCoefficients().getData()[i])
+ " ");
System.out.println(con.getRelationship() + " " + con.getValue());
}
SimplexSolver simplex = new SimplexSolver(1e-7);
double[] sol = simplex.optimize(c, cnsts, GoalType.MINIMIZE,
false).getPointRef();
System.out.println("Solution:\n" + new ArrayRealVector(sol));
System.out.println("Second constraint is violated!");
}
}
It's an odd problem, but something I ran across. I tracked the problem to the
getPivotRow routine in SimplexSolver. It was choosing a pivot that resulted in
a negative right-hand-side. I recommend a fix by replacing
...
final double ratio = rhs / entry;
if (MathUtils.equals(ratio, minRatio, epsilon)) {
minRatioPositions.add(i);
} else {
...
with
...
if (MathUtils.equals(rhs, minRatio*entry, epsilon)) {
minRatioPositions.add(i);
} else {
final double ratio = rhs / entry;
...
I believe this would be more appropriate (and at least resolves this particular
problem).
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
