2
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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$$

$\endgroup$
9
  • $\begingroup$ Hmm.. How about for $d_{n+1}x_{n+1} +\dots +d_{2n}x_{2n}$, we set them as $=0$ (each of the $d_jx_j=0$ for $j=n+1, \dots, 2n$) in the constraint matrix? That way we are able to have a single matrix for the constraints. $\endgroup$ – Stoner Nov 5 '17 at 16:20
  • $\begingroup$ @Stoner If $d_jx_j=0 \ \forall \ j=n+1, \ldots , 2n$ then this would be the constraint. In matrix notation it would be $$\begin{pmatrix}{}d_{n+1} & d_{n+2} & \ldots & d_{2n-1} & d_{2n} \end{pmatrix}\cdot \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}=\begin{pmatrix}{}0 & 0 & \ldots & 0 \end{pmatrix}$$ Again I don´t see how to summarize this two equations into one. $\endgroup$ – callculus Nov 5 '17 at 17:16
  • $\begingroup$ I will picture it as $\begin{bmatrix} a_{11} & \cdots & a_{1n} & -1 & 0 & \cdots & 0 \\ \vdots & \ddots & \vdots & \vdots & \vdots & \ddots \vdots \\ a_{n1} & \cdots & a_{nn} & 0 & 0 & \cdots & -1\\ d_1 & \cdots & d_n & 0 & 0 & \cdots & 0 \end{bmatrix} $ $\endgroup$ – Stoner Nov 5 '17 at 19:18
  • $\begingroup$ @Stoner But in my option the problem is to write both equations in one matrix equation. Also doesn´t $d_j$ start with the index $n+1$ ? But if you have an idea how to write in one matrix equation please post it. Personal note: I go to bed in one hour. $\endgroup$ – callculus Nov 5 '17 at 19:58
  • 1
    $\begingroup$ @Stoner No problem. A late reply is much better that no reply. $\endgroup$ – callculus Nov 13 '17 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.