3
$\begingroup$

Suppose I have a linear mixed-integer optimization problem of the form

$$MIP: min_{(x,y) \in \mathbb{R}^n \times \mathbb{Z}^m} c^\top x + d^\top y \hspace{0.2cm} \text{s.t.} \hspace{0.1cm} Ax+By \leq b, Cx+Dy =\gamma,$$ with $c\in \mathbb{R}^n$, $d \in \mathbb{R}^m$, $b \in \mathbb{R}^p$, $\gamma \in \mathbb{R}^q$, some $(p,n)$-matrix $A$, $(p,m)$-matrix $B$, $(q,n)$-matrix $C$ and $(q,m)$-matrix $D$.

Would a typical solver like GUROBI/ CPLEX apply some branch-and-cut alrorithm to solve this problem, or is there some "special treatment" for the equality constraints $Cx+Dy =\gamma$? In the literature, I can hardly find equality constraints in the problem formulation of $MIP$. Can someone tell me the reason for this?

$\endgroup$
1
$\begingroup$

This answer was too long for a comment.

It's hard to know what exactly those solvers are doing, but for LP relaxation they use simplex which will on the contrary firstly transform you problem to a standard from where all constraints are equalities (actually depends, but generally that's it). For cuts, it's glhugely depends on the type of cuts. You can print the number of cuts and their types these solvers have done. If those are gomori cuts you just go to any textbook and see how they are done for various constraints and branching strategies.

Also, I want to add that gurobi/cplex often use dual problems and thus treating different type of constraints respectively.

$\endgroup$
0
$\begingroup$

I don't think there is any reason to use a special treatment for those kind of constraints. Any MIP solver can work perfectly fine with both inequality and equality constraints. There is no need to put equality constraints explicitly in text books, since you can replace them by two inequality constraints: $Cx+Dy\leq \gamma$ and $-Cx-Dy\leq -\gamma$.

Thus, a MIP formulation \begin{align}\min_{(x,y)\in\mathbb{R}^n\times\mathbb{Z}^m} &\quad c\cdot x + d\cdot y\\ \text{s.t.} &\quad Ax+By\leq b,\end{align} is general enough to include all kind of constraints.

$\endgroup$

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.