iainnz/rationalsimplex.jl

Julia implementation of the simplex algorithm for rational numbers.

RationalSimplex.jl

Julia implementation of the Simplex algorithm for rational numbers. Intended for educational and experimental purposes only. See code for documentation, or tests for examples.

Last updated on 2018/07/01, tested with Julia 0.7-beta.

rationalsimplex.jl's Issues

Invalid solution if artificial variables are still in basis after phase one

A problem in the current implementation: after phase 1 an artificial variable can still be in the basis (with value 0). Such variables need to be driven out of the basis before starting phase 2, otherwise they might become non-zero in phase 2, which will make the solution invalid.

This is explained here:

Drive artificial variables out of the basis: If l-th basic variable is artifi­cial examine l-th row of B^−1 A. If all elements = 0 ⇒ row redundant. Otherwise pivot with non-0 element.

The following program demonstrates this issue. The returned solution violates the constraints:

A = [
	1//1     1        0        0        0;
	0        0        1        1        0;
	1        0        1        0        0;
	0        1        0        1        1;
	0        0        0        0        1;
];
c = vec([0//1        1        1        0        0]);
b = vec([1//2 1//2 1 1 1 ]);

(status,sol) = simplex(c, A, b); # already in standard form
println(A * sol == b);   # prints false, should be true

Are zeroes in b allowed?

Hi and thanks for this nice module.

Is there a reason why

RationalSimplex.jl/src/RationalSimplex.jl

Line 73 in a7da62c

@assert all(b .> zero(T))

is not .>= zero(T) ?