2
$\begingroup$

I am wondering about the characteristics and performance of some constraints with only binary variables. I assume that solving (integer) linear programs is faster than quadratic ones.
At first: $$ a,b,c \in \{0,1\} \\ a\cdot b = c \tag{1} $$ Is it a quadratic constraint because of the multiplication with two variables.
I try to model the logical equation $ a \land b = c $ and wonder about the performance of equation 1 or 2 (linearization of AND-Constraint, Chapter 2.5). \begin{align} c &\le a \\ c &\le b \\ c &\ge a+b-1 \tag{2} \end{align} Which one should I use and why (please considering performance)?

Second:
What is the difference between equation 3 and 4 for the logical equation $ a = 1 \rightarrow b = c$ with $ a \in \{0,1\}; b,c \in \mathbb{N}$? From a logical/mathematical point of view, I do not see anyone. $$ a \cdot b = a\cdot c \tag{3} $$

\begin{align} b-a\cdot M &= c-a\cdot M \tag{4} \end{align}

Summary of the questions:

  1. Is there a performance issue between $(1)$ and $(2)$?
  2. Which equation ($(3)$ or $(4)$) should I use and why?

If you know a good resource that explains these basics, please let me know.

$\endgroup$
3
  • 2
    $\begingroup$ Constraint (4) makes no sense to me. Are there perhaps typos in it? $\endgroup$
    – prubin
    Jun 24 at 15:35
  • $\begingroup$ Thanks for the hint. I modified it, does it make sense now or are there better ways to model it? $\endgroup$
    – Mike
    Jun 24 at 19:08
  • $\begingroup$ If $a=0,$ constraint (4) becomes $b=c$. If $a=1,$ constraint (4) becomes $b-M=c-M$, which reduces to $b=c.$ $\endgroup$
    – prubin
    Jun 24 at 21:38

2 Answers 2

4
$\begingroup$

Instead of deciding between linear and nonlinear (quadratic) constraints, I think one should rather decide in terms of convexity as a rule of thumb. For integer problems, one should decide in terms of the convexity of the continuous relaxations. Convex problems are much easier to solve than non-convex problems since (for a convex minimization problem) each local minimizer is guaranteed to be a global one.

Note that you obtain the continuous relaxation of a problem by replacing all discrete sets with contiguous sets. For instance, in your case, you'd replace the discrete set $\{0,1$} with the contiguous set $[0, 1]$. Note also that a MIP solver always solves multiple instances of continuous relaxations during a Branch&Bound algorithm, so it's highly recommended to preserve a nice mathematical structure of the continuous relaxations if possible. Last but not least, a quadratic equality constraint is always non-convex and a linear constraint is convex, regardless of whether it is an inequality or an equality constraint.

To answer your questions:

  1. The continuous relaxation of constraint (2) is convex, while (1) is not. So I'd pick constraint (2).

  2. The continuous relaxation of constraint (4) is convex, while (3) is not. So I'd pick constraint (4).

$\endgroup$
3
  • $\begingroup$ Thank you for your explanation. As I understand, it's about local and global extremes points of the equations. Since a linear (which is a convex (?)) equation, there is just a one global minimal or maximal point. However, a quadratic equation can keep multiple local min. or max. points. $\endgroup$
    – Mike
    Jun 24 at 12:57
  • $\begingroup$ Solving a model by a solver can be faster, if the relaxation is as much continous as possible. Variables should be continous (and not integer) even the constraints using this variable lead to a integer (or even binary) solution. Is this correct? $\endgroup$
    – Mike
    Jun 24 at 13:01
  • $\begingroup$ I agree with the importance of convexity, but a nominally nonconvex model may be fine because the presolver may "convexify" it. $\endgroup$
    – prubin
    Jun 24 at 18:16
4
$\begingroup$

The answers to the questions may be solver dependent, because many solvers (including I think all the commercial ones) will either linearize the products of variables or perhaps bake them into the branching scheme.

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