Suppose we have an integer linear program of the form:
$\begin{equation*}
\begin{aligned}
& \text{minimize}
& & \sum\limits_{i=1}^n \sum\limits_{j=1}^n c_{ij}x_{ij}\\
& \text{s.t.}
& & \mathbf{A}\mathbf{x}\geq \mathbf{b} \\
&&&\mathbf{dx}=\mathbf{g} \\
&&& x_{ij}\geq 0, x_{ij} \text{ integer}
\end{aligned}
\end{equation*}
$
How can we formulate the constraint matrix for this problem? My thoughts will be to convert all constraints to equality constraints by adding slack variables, and then take the coefficients of each $x_{ij}$ (e.g. $a_{ij}$, $d_{ij}$) and put it into the matrix, which looks like:
$\begin{bmatrix}
a_{11} \ \ \ \ \ \ \ \ a_{12} \ \dots \ \ \ a_{1n}\\
\vdots \\
a_{n1} \ \ \ \ \ \ \ a_{n2} \ \dots \ \ \ a_{nn}\\
d_{n+1, 1} \ d_{n+1,2} \ \dots \ d_{n+1,n}
\end{bmatrix}
$
Am I right on this? Some clarification will be great!
Best Answer
To intodruce slack variables ($s_i$) is a good idea. Then the two constraints can be written with two matrix equalities. I assume $d$ is a $1\times n$ vector.
$$\underbrace{\begin{pmatrix}{} a_{11}&a_{12}&\ldots & a_{1n} & -s_{1} & 0 & \ldots & 0 \\ \vdots & \vdots &\vdots &\vdots & \vdots &\vdots &\vdots &\vdots \\ a_{n1}&a_{n2}&\ldots & a_{1n} & 0 & 0 & \ldots & -s_{n} \end{pmatrix}}_{n\times 2n=\color{blue}A}\cdot \underbrace{\begin{pmatrix}{} x_1\\ x_2\\\vdots \\ x_n \\1 \\1 \\ \vdots \\ 1\end{pmatrix}}_{2n \times 1=\color{blue}B}=\begin{pmatrix}{} b_1\\ b_2\\\vdots \\ b_n\end{pmatrix} $$
$$\begin{pmatrix}{}d_{n+1} & d_{n+2} & \ldots & d_{2n-1} & d_{2n} \end{pmatrix}=\color{blue}C $$ $$\begin{pmatrix}{}x_{n+1} & 0 &\ldots& 0 \\ 0&x_{n+1} &\ldots& 0 \\ \vdots & \vdots & \vdots & \vdots \\ 0 & 0& \ldots & x_{2n}\end{pmatrix}=\color{blue}D$$
$x_{i}, s_{i} \in \mathbb N_0$
Maybe a block matrix would do the job. I use the blue letters A,B,C and D from above. $O$ are Null vectors or Null matrices. The right hand side is
$$\begin{pmatrix} A0\\0C \end{pmatrix}\cdot \begin{pmatrix} B0\\0D \end{pmatrix}=\ldots$$