Explicit LP Solving Functions

Each explicit LP solving function takes four arguments to represent an LP problem in n variables with m constraints:

1
LHS : m x n matrix, representing the left-hand-side coefficients of the m constraints.
2
relations : m x 1 matrix over the same ring as LHS, representing the relations for each constraint, with a positive entry representing ≥, a zero entry representing =, and a negative entry representing ≤.
3
RHS : m x 1 matrix over the same ring as LHS, representing the right-hand-side values of the m constraints.
4
objective : 1 x n matrix over the same ring as LHS, representing the coefficients of the objective function to be optimised.

Each function returns a vector representing an optimal solution to the problem, and an integer indicating the state of the solution, as described in the introduction.

MaximalSolution(LHS, relations, RHS, objective) : Mtrx, Mtrx, Mtrx, Mtrx -> Mtrx, RngIntElt
The vector maximising the LP problem, with an integer describing the state of the solution.
MinimalSolution(LHS, relations, RHS, objective) : Mtrx, Mtrx, Mtrx, Mtrx -> Mtrx, RngIntElt
The vector minimising the LP problem, with an integer describing the state of the solution.
MaximalIntegerSolution(LHS, relations, RHS, objective) : Mtrx, Mtrx, Mtrx, Mtrx -> Mtrx, RngIntElt
The integer vector maximising the LP problem, with an integer describing the state of the solution.
MinimalIntegerSolution(LHS, relations, RHS, objective) : Mtrx, Mtrx, Mtrx, Mtrx -> Mtrx, RngIntElt
The integer vector minimising the LP problem, with an integer describing the state of the solution.
MaximalZeroOneSolution(LHS, relations, RHS, objective) : Mtrx, Mtrx, Mtrx, Mtrx -> Mtrx, RngIntElt
The vector with each entry either zero or one maximising the LP problem, with an integer describing the state of the solution.
MinimalZeroOneSolution(LHS, relations, RHS, objective) : Mtrx, Mtrx, Mtrx, Mtrx -> Mtrx, RngIntElt
The vector with each entry either zero or one minimising the LP problem, with an integer describing the state of the solution.

Example LP_ExplicitLPSolutionsOne (H169E1)

We solve the LP maximising F(x, y) = 8x + 2y x, y ∈(R) subject to the constraints 10x + 21y ≤156 2x + y ≤22 
> R := RealField( );
> lhs := Matrix(R, 2, 2, [10, 21, 2, 1]);
> rhs := Matrix(R, 2, 1, [156, 22]);
> rel := Matrix(R, 2, 1, [-1, -1]); // negative values - less-or-equal relation
> obj := Matrix(R, 1, 2, [8, 15]);
> MaximalSolution(lhs, rel, rhs, obj);
[9.562500000000000000 2.875000000000000888]
0

Example LP_ExplicitLPSolutionsTwo (H169E2)

We find solutions to the LP maximising F(x1, ..., x7) = 592x1 + 381x2 + 273x3 + 55x4 + 48x5 + 37x6 + 23x7 subject to the constraint 3534x1 + 2356x2 + 2767x3 + 589x4 + 528x5 + 451x6 + 304x7 ≤119567 with (x1, ..., x7) taking real values, integer values, and zero/one values. 
> R := RealField( );
> lhs := Matrix(R, 1, 7, [3534, 2356, 2767, 589, 528, 451, 304]);
> rhs := Matrix(R, 1, 1, [119567]);
> rel := Matrix(R, 1, 1, [-1]);
> obj := Matrix(R, 1, 7, [592, 381, 273, 55, 48, 37, 23]);
> MaximalSolution(lhs, rel, rhs, obj);
[33.83333333333333570 0.E-92 0.E-92 0.E-92 0.E-92 0.E-92 0.E-92]
0
> MaximalIntegerSolution(lhs, rel, rhs, obj);
[33.00000000000000000 1.000000000000000000 0.E-92 1.000000000000000000 0.E-92
    0.E-92 0.E-92]
0
> MaximalZeroOneSolution(lhs, rel, rhs, obj);
[1.000000000000000000 1.000000000000000000 1.000000000000000000
    1.000000000000000000 1.000000000000000000 1.000000000000000000
    1.000000000000000000]
0
V2.28, 13 July 2023