Macaulay2 » Documentation
Packages » IntegerProgramming » toStandardForm
next | previous | forward | backward | up | index | toc

toStandardForm -- converts an LP to standard form

Description

The standard form of an integer linear program is $$\text{minimize } c^T x \quad\text{subject to } Ax = b \text{ and } x \in \mathbb Z_{\ge 0}^n.$$ An integer linear program with constraints $Bx \le b$ is equivalent to one in standard form in the following way: One constraint $B_{j,1}x_1 + \cdots + B_{j,r}x_r \le d_j$ in this system is equivalent to the pair of constraints $B_{j,1}x_1 + \cdots + B_{j, r}x_r + y_j = d_j$ and $y_j \ge 0$.

Hence we rewrite the constrains $Bx \le b$ as $Ax = b$ by introducing slack variables $y_j$ and concatenating a copy of the identity matrix A = B|I of the appropriate size. (Note that we abuse notation here and write $x$ for both the vector of the given program and the vector that includes the slack variables $y_j$.)

This equivalence does not change the objective function; we pad $c$ with a zero for each slack variable introduced.

i1 : A = matrix{{1, 2}, {3, 4}}

o1 = | 1 2 |
     | 3 4 |

              2       2
o1 : Matrix ZZ  <-- ZZ
i2 : c = matrix{{5}, {6}}

o2 = | 5 |
     | 6 |

              2       1
o2 : Matrix ZZ  <-- ZZ
i3 : toStandardForm(A, c)

o3 = (| 1 2 1 0 |, | 5 |)
      | 3 4 0 1 |  | 6 |
                   | 0 |
                   | 0 |

o3 : Sequence

See also

Ways to use toStandardForm:

  • toStandardForm(Matrix)
  • toStandardForm(Matrix,List)
  • toStandardForm(Matrix,Matrix)

For the programmer

The object toStandardForm is a method function.


The source of this document is in /build/reproducible-path/macaulay2-1.25.06+ds/M2/Macaulay2/packages/IntegerProgramming.m2:506:0.