# 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 \times n$ matrix, representing the left-hand-side coefficients of the $m$ constraints.

**2**
`relations` : $m \times 1$ matrix over the same ring as `LHS`, representing the relations for each constraint, with a positive entry representing $\ge$, a zero entry representing $=$, and a negative entry representing $\le$.

**3**
`RHS` : $m \times 1$ matrix over the same ring as `LHS`, representing the right-hand-side values of the $m$ constraints.

**4**
`objective` : $1 \times 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: Explicit LP Solutions One (ex-807d41)`

We solve the LP maximising $F(x, y) = 8x + 15y \quad x, y \in {\bf R}$ subject to the constraints $10x + 21y \le 156$ $2x + y \le 22$

```magma
> 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: Explicit LP Solutions Two (ex-33e772)`

We find solutions to the LP maximising $F(x_1, \cdots, x_7) = 592x_1 + 381x_2 + 273x_3 + 55x_4 + 48x_5 + 37x_6 + 23x_7$ subject to the constraint $3534x_1 + 2356x_2 + 2767x_3 + 589x_4 + 528x_5 + 451x_6 + 304x_7 \le 119567$ with $(x_1, \cdots, x_7)$ taking real values, integer values, and zero/one values.

```magma
> 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

```