0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – mjd Sep 29 '16 at 16:44
  • $\begingroup$ 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. $\endgroup$ – Septimus G Sep 29 '16 at 22:11

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.