toStandardForm A
toStandardForm(A, c)
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.
|
|
|
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.