# Mixed-integer (Linear) Programming (MILP) standard/canonical form

Is there a standard or canonical form for mixed-integer (linear) programming problems? For linear programms the standard form is sometimes given by: $$\max_{\boldsymbol x} \boldsymbol c^T \boldsymbol x\\ \text{s.t.} \boldsymbol{Ax} = \boldsymbol b\\ \boldsymbol x \geq \boldsymbol 0$$ or$$\max_{\boldsymbol x} \boldsymbol c^T \boldsymbol x\\ \text{s.t.} \boldsymbol{Ax} \leq \boldsymbol b\\ \boldsymbol x \geq \boldsymbol 0$$ Mostly, the MILP problems are just explained by "require some variables to be integer" (e.g. Wikipedia). So I was wondering: Is there a standard form for MILPs or the more general MIPs?

## 1 Answer

Yes. For a pure integer linear program you can write it as an LP but specifying that your variables are integers. For a MILP you can write:

\begin{align}\max_{\boldsymbol x,\boldsymbol y} \boldsymbol c^T \boldsymbol x + \boldsymbol h^T \boldsymbol y\\ \text{ s.t. } \boldsymbol{Ax} + \boldsymbol{Gy} \le \boldsymbol b\\ \boldsymbol x \geq \boldsymbol 0 \\ \boldsymbol y \geq \boldsymbol 0& \text{ integral}\end{align}

• Thank you for your answer. But is this also called "standard" form as for linear problems? I haven't found a reference for this, can you maybe provide one? – mjd Sep 29 '16 at 16:44
• It comes from the textbook Integer Programming (Conforti et. al). Note that the canonical or standard LP is important for theorems in duality theory and so on. I am not aware of theorems in integer programming where following a certain format to express the problem is important. So that is why you do not hear people talking about the canonical ILP or MILP formulation. – Septimus G Sep 29 '16 at 22:11