3
$\begingroup$

I'm new to Gurobi in Python and I am wondering if there is way to express/code "or" in the following constraint, where $x_i$ are binary variables:

$x_i-x_i*x_{i-1} =0$

OR

$x_i*x_{i+1} =1.$

Question:

Is there a way to express "Or" between the above two constraints?

My Approch:

I tried the following model.addConstr((x[i]-x[i]*x[i-1]) * (x[i]*x[i+1] -1 )==0) however this leads to an error:

gurobipy.GurobiError: Invalid argument to QuadExpr multiplication

I think that addConstr can take at max three multiplications.

$\endgroup$
7
  • $\begingroup$ 1) Take a look at these two links from gurobi: or_ function and indicator constraints. 2) There are other questions on this site about formulating "OR" constraints. Make sure to search for it $\endgroup$
    – EhsanK
    Nov 14, 2022 at 14:06
  • $\begingroup$ @EhsanK In fact, or_function doesn't work in this case, indicator constraints could work, but I do not see how. I already searched for the other questions about "OR" constraints, didn't find something suitable. $\endgroup$
    – M.Badaoui
    Nov 14, 2022 at 14:27
  • 4
    $\begingroup$ Hi @M.Badaoui May you could expand a bit on what you want to achieve. Maybe there is a better way to formulate the logic you want to enforce? The first constraint says that "if $x_i=1$ then $x_{i-1}$ must equal 1 as well" the second say "both $x_i$ and $x_{i+1}$ must be one". Note that you can formulate both of these constraints linearly: $x_i\leq x_{i-1}$ and $x_i+x_{i+1}=2$ $\endgroup$
    – Sune
    Nov 14, 2022 at 14:43
  • 1
    $\begingroup$ Boolean type constraints are more familiar to Constraint Programming type of problems. It is almost always possible to write them in MIP with a little more difficulty. OR-Tools has boolean operators for its CP-SAT module developers.google.com/optimization/reference/python/sat/python/… Btw, it seems what you are trying is nonlinear, which may be another problem depending on the solver type. $\endgroup$
    – berkorbay
    Nov 15, 2022 at 7:15
  • 1
    $\begingroup$ @M.Badaoui I might have missed something but I think I have an answer for you for your specific case. $\endgroup$
    – berkorbay
    Nov 15, 2022 at 11:37

3 Answers 3

7
$\begingroup$

Since $x_i$'s are binary: $$ \begin{align*} &(x_i(1 - x_{i-1}) = 0) \vee (x_ix_{i+1}=1)\\ \Leftrightarrow&(\neg x_i \vee x_{i-1})\vee(x_i \wedge x_{i+1})\\ \Leftrightarrow&\neg x_i \vee x_{i-1}\vee(x_i \wedge x_{i+1})\\ \Leftrightarrow&(\neg x_i \vee x_{i-1}\vee x_i) \wedge (\neg x_i \vee x_{i-1}\vee x_{i+1})\\ \Leftrightarrow& 1 \wedge (\neg x_i \vee x_{i-1} \vee x_{i+1})\\ \Leftrightarrow& \neg x_i \vee x_{i-1} \vee x_{i+1}\\ \Leftrightarrow& (1-x_i) + x_{i-1} + x_{i+1} \geq 1\\ \Leftrightarrow& x_{i-1} - x_i + x_{i+1} \geq 0 \end{align*} $$

$\endgroup$
2
  • $\begingroup$ Thank you! Using the last inequality we can formulate the constraint in gurobi. I was hopping for something similar to CPLEX in this question (to express OR constraint directly): stackoverflow.com/questions/56710025/… Seems that there no direct way in Gurobi like Cplex. $\endgroup$
    – M.Badaoui
    Nov 15, 2022 at 10:54
  • $\begingroup$ See addGenConstrOr and addGenConstrIndicator @M.Badaoui $\endgroup$
    – xd y
    Nov 16, 2022 at 4:03
4
$\begingroup$

Edit: This is actually the "English" version of @xd y's accepted answer.

In your specific case I think adding just $x_{i+1} \ge x_i-x_{i-1}$ works. Let's enumerate

If $x_i = 0$ then your OR constraint is satisfied since LHS will be 0 for both constraints. Other variables are free.

If $x_i = 1$ and $x_{i+1} = 1$ then the second constraint is satisfied. $x_{i-1}$ is free.

If $x_i = 1$ and $x_{i+1} = 0$ then $x_{i-1}$ should be 1.

So if you add $x_{i+1} \ge x_i-x_{i-1}$, you ensure that if $x_{i} = 1$ and $x_{i-1} = 0$ you will get $x_{i+1} = 1$. Otherwise, $x_{i+1}$ is free.

$\endgroup$
1
$\begingroup$

$x_i*(1-x_{i-1} = 0\ or \ x_i*x_{i+1}=1$ implies
Cons(1): $x_i*(1-x_{i-1}) >=0$;
Cons(2): $x_i*x_{i+1} <=1$;
Cons(3): $x_i*(1-x_{i-1} + x_{i+1}) =1$
So if you are looking for 0 or 1 for cons(1) & cons(2) & not either way then constraints are:
$x_i = 1$
$x_{i+1} >= x_{i-1}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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