solve(SimplexTable table)

timfargo2000Participant 2012-02-06 at 8:23 am

Hi,

I was using the solve(SimplexTable table) method of GeneralLPSolver.java to solve a linear programming table for

min cx s.t. Ax = b x>=0

In the result of my code(see attachment), the solve() method returns solution with negative variable, which is wrong.

Does Suanshu assume the non-basic variables in the simplex table to be non-negative? If not, do I need to manually augment the table to add non-negative constraints, or any other shortcuts?

Thanks.
RyuParticipant 2012-02-06 at 12:17 pm

Could you attach also your code please?

In general, if you don’t have any box constraints, SuanShu assumes all variables are non-negative.
timfargo2000Participant 2012-02-06 at 1:38 pm

The optimal solution returned by GeneralLPSolver is negative, which is unreasonable. If Suanshu assumes variables non-negative, infeasible exception should be thrown in this case.

Please also take note that columns labeled “equality” in the solution table seem to duplicate with other columns in the table. How so?

Thanks!
timfargo2000Participant 2012-02-06 at 1:58 pm

Another problem regarding Suanshu – how do I check if the label type of a column in the SimplexTable equals Equality type? Although the following code

table.getColLabel(j).type.equals(SimplexTable.LabelType.EQUALITY)

passed through the compiler, runtime error was thrown.

Exception in thread “main” java.lang.ClassCastException: java.lang.String cannot be cast to com.numericalmethod.suanshu.optimization.constrained.linearprogramming.simplex.SimplexTable$Label

Thanks!
RyuParticipant 2012-02-06 at 2:43 pm

As said, please attach your source code for investigation.

timfargo2000Participant 2012-02-06 at 2:51 pm

Hi ryu,

sure, here you go.

import com.numericalmethod.suanshu.matrix.doubles.matrixtype.dense.DenseMatrix;
import com.numericalmethod.suanshu.optimization.constrained.constraint.linear.LinearLessThanConstraints;
import com.numericalmethod.suanshu.optimization.constrained.linearprogramming.exception.LPInfeasible;
import com.numericalmethod.suanshu.optimization.constrained.linearprogramming.problem.GeneralLPProblem;
import com.numericalmethod.suanshu.optimization.constrained.linearprogramming.simplex.SimplexTable;
import com.numericalmethod.suanshu.optimization.constrained.linearprogramming.simplex.SimplexTable.LabelType;
import com.numericalmethod.suanshu.optimization.constrained.linearprogramming.simplex.solver.GeneralLPSolver;
import com.numericalmethod.suanshu.optimization.constrained.linearprogramming.simplex.solver.LPBoundedSolution;
import com.numericalmethod.suanshu.optimization.constrained.linearprogramming.simplex.solver.Phase2ByFerrisMangasarianWright;
import com.numericalmethod.suanshu.vector.doubles.dense.DenseVector;

/* * testing modifying SimplexTable.Label */ public class testing{

public static void main(String[] args) throws LPInfeasible{ GeneralLPProblem problem = new GeneralLPProblem( new DenseVector(new double[]{-1,-1}), null, new LinearLessThanConstraints(new DenseMatrix(new double[][]{ {7,1}, {-1,1} }), new DenseVector( new double[]{15,1})), null,null); System.out.println(“The root IP problem is: “+problem); //testing

GeneralLPSolver instance = new GeneralLPSolver();
LPBoundedSolution solution = (LPBoundedSolution) instance.solve(problem);
SimplexTable table =  solution.getResultantTableau();
table.renameCol(1, new SimplexTable.Label(LabelType.NON_BASIC, 3));
table.renameCol(2, new SimplexTable.Label(LabelType.NON_BASIC, 4));
table.renameRow(1, new SimplexTable.Label(LabelType.EQUALITY, 1));
table.renameRow(2, new SimplexTable.Label(LabelType.EQUALITY, 2));
table.addColAt(1, new SimplexTable.Label(LabelType.NON_BASIC, 1));
table.addColAt(2, new SimplexTable.Label(LabelType.NON_BASIC, 2));
table.set(1, 1, 1);
table.set(2, 2, 1);
table.addRowAt(3, new SimplexTable.Label(LabelType.EQUALITY, 3));
table.set(3, 3, -1./8);
table.set(3, 4, -7./8);
table.set(3, 5, 3./4);
table.addColAt(5, new SimplexTable.Label(LabelType.NON_BASIC, 5));
table.set(3, 5, 1);

System.out.println(“Linear Programming problem tableau: “+table);
solution = (LPBoundedSolution) instance.solve(table);

System.out.println(“Solution Table: “+solution.getResultantTableau());
System.out.println(“Solution: t:”+solution.minimizer());
}
}

RyuParticipant 2012-02-07 at 3:04 pm

I do not see any problem with GeneralLPSolver. I ran your LP problem and it gives positive outputs.

<br />
    @Test<br />
    public void test_reported() throws LPInfeasible, LPUnbounded {<br />
        GeneralLPProblem problem = new GeneralLPProblem(<br />
                new DenseVector(new double[]{-1, -1}),<br />
                null,<br />
                new LinearLessThanConstraints(new DenseMatrix(new double[][]{<br />
                    {7, 1},<br />
                    {-1, 1}<br />
                }), new DenseVector(new double[]{15, 1})),<br />
                null, null);<br />
<br />
        GeneralLPSolver solver = new GeneralLPSolver();<br />
        LPBoundedSolution soln = (LPBoundedSolution) solver.solve(problem);<br />
        System.out.println(soln.minimizer());<br />
    }<br />

[1.750000, 2.750000]

Your negative results may be due to you modifying the internal simplex table manually and got it wrong (constraints broken, inconsistent representation, etc.).