--- title: "Handbook of Magma Functions, Part XXII: Optimization" version: "2.30-1" canonical: "https://docs.magma-maths.org/Optimization/index-optimization.html" --- # Optimization - [Linear Programming](https://docs.magma-maths.org/Optimization/LinearProgramming/index-linear-programming.md): Linear programming problem construction and solution. ## Linear Programming - [Introduction](https://docs.magma-maths.org/Optimization/LinearProgramming/introduction.md) - [Explicit LP Solving Functions](https://docs.magma-maths.org/Optimization/LinearProgramming/instant-lp.md) - [`MaximalSolution(LHS, relations, RHS, objective): Mtrx, Mtrx, Mtrx, Mtrx → Mtrx, RngIntElt`](https://docs.magma-maths.org/Optimization/LinearProgramming/instant-lp.md#function-maximalsolution-mtrx-mtrx-mtrx-mtrx) - [`MinimalSolution(LHS, relations, RHS, objective): Mtrx, Mtrx, Mtrx, Mtrx → Mtrx, RngIntElt`](https://docs.magma-maths.org/Optimization/LinearProgramming/instant-lp.md#function-minimalsolution-mtrx-mtrx-mtrx-mtrx) - [`MaximalIntegerSolution(LHS, relations, RHS, objective): Mtrx, Mtrx, Mtrx, Mtrx → Mtrx, RngIntElt`](https://docs.magma-maths.org/Optimization/LinearProgramming/instant-lp.md#function-maximalintegersolution-mtrx-mtrx-mtrx-mtrx) - [`MinimalIntegerSolution(LHS, relations, RHS, objective): Mtrx, Mtrx, Mtrx, Mtrx → Mtrx, RngIntElt`](https://docs.magma-maths.org/Optimization/LinearProgramming/instant-lp.md#function-minimalintegersolution-mtrx-mtrx-mtrx-mtrx) - [`MaximalZeroOneSolution(LHS, relations, RHS, objective): Mtrx, Mtrx, Mtrx, Mtrx → Mtrx, RngIntElt`](https://docs.magma-maths.org/Optimization/LinearProgramming/instant-lp.md#function-maximalzeroonesolution-mtrx-mtrx-mtrx-mtrx) - [`MinimalZeroOneSolution(LHS, relations, RHS, objective): Mtrx, Mtrx, Mtrx, Mtrx → Mtrx, RngIntElt`](https://docs.magma-maths.org/Optimization/LinearProgramming/instant-lp.md#function-minimalzeroonesolution-mtrx-mtrx-mtrx-mtrx) - [Example: Linear Program in Two Variables](https://docs.magma-maths.org/Optimization/LinearProgramming/instant-lp.md#example-ex-807d41) - [Example: Linear Program in Seven Variables](https://docs.magma-maths.org/Optimization/LinearProgramming/instant-lp.md#example-ex-33e772) - [Creation of LP objects](https://docs.magma-maths.org/Optimization/LinearProgramming/creation.md) - [`LPProcess(R, n): Rng, RngIntElt → LP`](https://docs.magma-maths.org/Optimization/LinearProgramming/creation.md#function-lpprocess-rng-rngintelt) - [Example: Creating an LP Object](https://docs.magma-maths.org/Optimization/LinearProgramming/creation.md#example-ex-a6b954) - [Operations on LP objects](https://docs.magma-maths.org/Optimization/LinearProgramming/operations.md) - [`AddConstraints(L, lhs, rhs): LP, Mtrx, Mtrx`](https://docs.magma-maths.org/Optimization/LinearProgramming/operations.md#procedure-addconstraints-lp-mtrx-mtrx) - [`NumberOfConstraints(L): LP → RngIntElt`](https://docs.magma-maths.org/Optimization/LinearProgramming/operations.md#function-numberofconstraints-lp) - [`NumberOfVariables(L): LP → RngIntElt`](https://docs.magma-maths.org/Optimization/LinearProgramming/operations.md#function-numberofvariables-lp) - [`EvaluateAt(L, p): LP, Mtrx → RngIntElt`](https://docs.magma-maths.org/Optimization/LinearProgramming/operations.md#function-evaluateat-lp-mtrx) - [`Constraint(L, n): LP, RngIntElt → Mtrx, Mtrx, RngIntElt`](https://docs.magma-maths.org/Optimization/LinearProgramming/operations.md#function-constraint-lp-rngintelt) - [`IntegerSolutionVariables(L): LP → SeqEnum`](https://docs.magma-maths.org/Optimization/LinearProgramming/operations.md#function-integersolutionvariables-lp) - [`ObjectiveFunction(L): LP → Mtrx`](https://docs.magma-maths.org/Optimization/LinearProgramming/operations.md#function-objectivefunction-lp) - [`IsMaximisingFunction(L): LP → BoolElt`](https://docs.magma-maths.org/Optimization/LinearProgramming/operations.md#function-ismaximisingfunction-lp) - [`RemoveConstraint(L, n): LP, RngIntElt`](https://docs.magma-maths.org/Optimization/LinearProgramming/operations.md#procedure-removeconstraint-lp-rngintelt) - [`SetIntegerSolutionVariables(L, I, m): LP, SeqEnum[RngIntElt], BoolElt`](https://docs.magma-maths.org/Optimization/LinearProgramming/operations.md#procedure-setintegersolutionvariables-lp-seqenum-rngintelt-boolelt) - [`SetLowerBound(L, n, b): LP, RngIntElt, RngElt`](https://docs.magma-maths.org/Optimization/LinearProgramming/operations.md#procedure-setlowerbound-lp-rngintelt-rngelt) - [`SetMaximiseFunction(L, m): LP, BoolElt`](https://docs.magma-maths.org/Optimization/LinearProgramming/operations.md#procedure-setmaximisefunction-lp-boolelt) - [`SetObjectiveFunction(L, F): LP, Mtrx`](https://docs.magma-maths.org/Optimization/LinearProgramming/operations.md#procedure-setobjectivefunction-lp-mtrx) - [`SetUpperBound(L, n, b): LP, RngIntElt, RngElt`](https://docs.magma-maths.org/Optimization/LinearProgramming/operations.md#procedure-setupperbound-lp-rngintelt-rngelt) - [`Solution(L): LP → Mtrx, RngIntElt`](https://docs.magma-maths.org/Optimization/LinearProgramming/operations.md#function-solution-lp) - [`UnsetBounds(L): LP`](https://docs.magma-maths.org/Optimization/LinearProgramming/operations.md#procedure-unsetbounds-lp) - [Example: Filling and Solving an LP Object](https://docs.magma-maths.org/Optimization/LinearProgramming/operations.md#example-ex-b5bf57) - [Bibliography](https://docs.magma-maths.org/Optimization/LinearProgramming/bibliography.md) ### Introduction A Linear Program in $n$ variables $x_1, \cdots, x_n$ with $m$ constraints of the form $\sum_{j=1}^n a_jx_j~\le~c$ (the relations in any of the constraints may also be $=$ or $\ge$) may be represented in matrix form as: $$ \begin{pmatrix}a_{11} & \cdots & a_{1n}\\ \vdots & \ddots & \vdots\\ a_{m1} & \cdots & a_{mn}\end{pmatrix}\;. \begin{pmatrix}x_1\\ \vdots\\ x_n\end{pmatrix}\; \quad \begin{pmatrix}REL\end{pmatrix} \quad \begin{pmatrix}c_1\\ \vdots\\ c_n\end{pmatrix}\; $$ where $\begin{pmatrix}REL\end{pmatrix}$ represents a componentwise relation between vectors, with each element $=$, $\le$, or $\ge$. Note that there is an additional implicit constraint, wherein all variables are assumed to be nonnegative. We wish to find a solution $\begin{pmatrix}x_i\end{pmatrix}\;$ that maximises (or minimises) the objective function: $\sum_{i = 1}^n o_i x_i$ Magma provides two methods for solving LP problems. The first is to set up suitable constraint matrices and then use an explicit LP solving function to solve the problem. The second involves creating an instance of the `LP` process, which is of category `LP`. Constraints are added and options set before calling `Solution` to get a solution to the problem. All functions that actually solve an LP problem return a solution vector together with an integer code representing the state of the solution, provided by the lp_solve library. The codes are: **0** Optimal Solution **1** Failure **2** Infeasible problem **3** Unbounded problem **4** Failure Magma supports LP problems over Integer, Rational, and Real rings. For Integer and Real problems, the solutions will be provided as Integer and Real vectors respectively. For LP problems provided in Rationals, the solution is a Real vector. Linear programming in Magma is implemented using the lp_solve library written by Michel Berkelaar ([michel@ics.ele.tue.nl](mailto:michel@ics.ele.tue.nl)). The library source may be found at `ftp://ftp.ics.ele.tue.nl/pub/lp_solve/`. For further reference see [[Naz87](https://docs.magma-maths.org/references.md#cite-naz87)], [[Chv83](https://docs.magma-maths.org/references.md#cite-chv83)], [[OH68](https://docs.magma-maths.org/references.md#cite-oh68)], and [[NW88](https://docs.magma-maths.org/references.md#cite-nem88)]. ### 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: Linear Program in Two Variables (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: Linear Program in Seven Variables (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 ``` ### Creation of LP objects #### `LPProcess(R, n): Rng, RngIntElt -> LP` A Linear Program over the ring $R$ in $n$ variables. #### `Example: Creating an LP Object (ex-a6b954)` We create an LP representing a problem in 2 real variables: ```magma > R := RealField( ); > L := LPProcess(R, 2); > L; LP Minimising objective function: [0 0] Subject to constraints: Variables bounded above by: [ ] Variables bounded below by: [ ] Solving in integers for variables [ ] ``` ### Operations on LP objects #### `AddConstraints(L, lhs, rhs): LP, Mtrx, Mtrx` ```magma Rel: MonStgElt Default: "eq" ``` Add some constraints to the LP problem $L$. All constraints will have the same relation, given by `Rel`, which may be set to `"eq"` for strict equality (the default), `"le"` for less-or-equal constraints, or `"ge"` for greater-or-equal constraints. Constraints are of the form $$ \sum_{j = 1}^{n}\hbox{\tt lhs}_{ij}\quad \hbox{\tt Rel}\quad \hbox{\tt rhs}_{i1} $$ where $lhs$ and $rhs$ are described in Section [Explicit LP Solving Functions](https://docs.magma-maths.org/Optimization/LinearProgramming/instant-lp.md#lp-explicit). #### `NumberOfConstraints(L): LP -> RngIntElt` The number of constraints in the LP problem $L$. #### `NumberOfVariables(L): LP -> RngIntElt` The number of variables in the LP problem $L$. #### `EvaluateAt(L, p): LP, Mtrx -> RngIntElt` Evaluate the objective function of the LP problem $L$ at the point $p$ given by a matrix. #### `Constraint(L, n): LP, RngIntElt -> Mtrx, Mtrx, RngIntElt` The LHS, RHS, and relation ($-1$ for $\le$, $0$ for $=$, $1$ for $\ge$) of the $n$-th constraint of the LP problem $L$. #### `IntegerSolutionVariables(L): LP -> SeqEnum` Sequence of indices of the variables in the LP problem $L$ to be solved in integers. #### `ObjectiveFunction(L): LP -> Mtrx` The objective function of the LP problem $L$. #### `IsMaximisingFunction(L): LP -> BoolElt` Returns `true` if the LP problem $L$ is set to maximise its objective function, `false` if set to minimise. #### `RemoveConstraint(L, n): LP, RngIntElt` Remove the $n$-th constraint from the LP problem $L$. #### `SetIntegerSolutionVariables(L, I, m): LP, SeqEnum[RngIntElt], BoolElt` Set the variables of the LP problem $L$ indexed by elements of the sequence $I$ to be solved in integers if $m$ is `true`, or in the usual ring if `false`. #### `SetLowerBound(L, n, b): LP, RngIntElt, RngElt` Set the lower bound on the $n$-th variable in the LP problem $L$ to $b$. Note that for all LP problems in Magma there is an implicit constraint that all variables are $\geq 0$. This constraint is overridden if a lower bound is specified by using this function (e.g., specifying a lower bound of $-5$ works as expected), but the lower bound can currently not be completely removed. #### `SetMaximiseFunction(L, m): LP, BoolElt` Set the LP problem $L$ to maximise its objective function if $m$ is `true`, or to minimise the objective function if $m$ is false. #### `SetObjectiveFunction(L, F): LP, Mtrx` Set the objective function of the LP problem $L$ to the matrix $F$. #### `SetUpperBound(L, n, b): LP, RngIntElt, RngElt` Set the upper bound on the $n$-th variable in the LP problem $L$ to $b$. #### `Solution(L): LP -> Mtrx, RngIntElt` Solve the LP problem $L$; returns a point representing an optimal solution, and an integer representing the state of the solution. #### `UnsetBounds(L): LP` Remove any bounds on all variables in the LP problem $L$. Note that this reactivates the implicit constraint that all variables are $\geq 0$. #### `Example: Filling and Solving an LP Object (ex-b5bf57)` We use an LP object to solve the LP maximising $F(x,y) = 3x + 13y$ subject to constraints $2x + 9y <= 40$ $11x -8y <= 82$ ```magma > R := RealField( ); > L := LPProcess(R, 2); > SetObjectiveFunction(L, Matrix(R, 1, 2, [3,13])); > lhs := Matrix(R, 2, 2, [2, 9, 11, -8]); > rhs := Matrix(R, 2, 1, [40, 82]); > AddConstraints(L, lhs, rhs : Rel := "le"); > SetMaximiseFunction(L, true); > L; LP Maximising objective function: [ 3 13] Subject to constraints: 1 : [2 9] <= [40] 2 : [11 -8] <= [82] Variables bounded above by: [ ] Variables bounded below by: [ ] Solving in integers for variables [ ] > Solution(L); [9.199999999999999289 2.400000000000000355] 0 ``` Now, we place some bounds on y: ```magma > SetUpperBound(L, 2, R!2); > SetLowerBound(L, 2, R!1); > Solution(L); [8.909090909090908283 2.000000000000000000] 0 ``` And find integer solutions: ```magma > SetIntegerSolutionVariables(L, [1,2], true); > Solution(L); [8.000000000000000000 2.000000000000000000] 0 ``` Now, removing the 2nd constraint: ```magma > RemoveConstraint(L, 2); > L; LP Maximising objective function: [ 3 13] Subject to constraints: 1 : [2 9] <= [40] Variables bounded above by: [ 2:2 ] Variables bounded below by: [ 2:1 ] Solving in integers for variables [ 1, 2 ] > Solution(L); [11.00000000000000000 2.000000000000000000] 0 ``` And removing the restriction to Integer values for y, ```magma > SetIntegerSolutionVariables(L, [2], false); > Solution(L); [15.00000000000000000 1.111111111111111160] 0 ```