2
$\begingroup$

I want to use the sum of two binary decision variables (when their sum equals to one) as the condition of Model.AddGenConstrIndicator https://www.gurobi.com/documentation/current/refman/py_model_agc_indicator.html, however, it seems to be impossible, e.g. for the minimal code below which reflects the relevant part of my real problem trying the following:

import gurobipy as gp

model = gp.Model()

x = model.addVar(vtype=gp.GRB.BINARY, name="x")
y = model.addVar(vtype=gp.GRB.BINARY, name="y")

z = model.addVar(vtype=gp.GRB.CONTINUOUS, name="z")

model.update()
constr = model.addConstr((x + y == 1) >> (z <= 20))

model.setObjective(z, gp.GRB.MAXIMIZE)

# Solve the model
model.optimize()

Will result in the following error:

    constr = model.addConstr((x + y == 1) >> (z <= 20))
  File "src/gurobipy/model.pxi", line 3632, in gurobipy.Model.addConstr
gurobipy.GurobiError: Indicator constraints can only be triggered by a single binary variable at a given value

Is there a workaround for this?

$\endgroup$
1

2 Answers 2

5
$\begingroup$

You want to enforce $x+y=1 \implies z \le 20$. Introduce a new binary variable $w$ and enforce \begin{align} x+y = 1 &\implies w = 1 \tag1\label1\\ w = 1 &\implies z \le 20 \tag2\label2\\ \end{align} Constraint \eqref{2} is already an indicator constraint. The contrapositive of \eqref{1} is $w \not= 1 \implies x+y \not= 1$, which you can rewrite as an indicator constraint $$w = 0 \implies x+y = 2v \tag3\label3,$$ where $v$ is a binary variable.

Alternatively, you can rewrite \eqref{1} in conjunctive normal form to somewhat automatically derive linear constraints: $$ ((x \land \lnot y) \lor (\lnot x \land y)) \implies w \\ \lnot ((x \land \lnot y) \lor (\lnot x \land y)) \lor w \\ (\lnot (x \land \lnot y) \land \lnot (\lnot x \land y)) \lor w \\ ((\lnot x \lor y) \land (x \lor \lnot y)) \lor w \\ (\lnot x \lor y \lor w) \land (x \lor \lnot y \lor w) \\ (1 - x + y + w \ge 1) \land (x + 1 - y + w \ge 1) \\ (w \ge x - y) \land (w \ge y - x) $$

$\endgroup$
3
  • 2
    $\begingroup$ You could also introduce two new variables and one linear constraint. E.g. $x + y = 2 * v + w$. Then $w$ is your indicator for $z <= 20$. $\endgroup$ Mar 5, 2023 at 17:15
  • $\begingroup$ @user1502040 will work if $v$ is nonnegative integer. $\endgroup$ Mar 5, 2023 at 21:27
  • $\begingroup$ @Sutanu yes, I should have said 2 binary variables. $\endgroup$ Mar 5, 2023 at 22:12
0
$\begingroup$

I think what you need in a code is actually something like: (The first constraint actually comes from my last comment)

model = gp.Model()

x = model.addVar(vtype=gp.GRB.BINARY, name="x")
y = model.addVar(vtype=gp.GRB.BINARY, name="y")
w = model.addVar(vtype=gp.GRB.INTEGER, name="w")

z = model.addVar(lb=0, ub=20, vtype=gp.GRB.CONTINUOUS, name="z")

constr = model.addConstr(x + y >= 1 - w)
constr = model.addConstr((w == 1) >> (z <= 20))
model.setObjective(z, gp.GRB.MAXIMIZE)


# Solve the model
model.update()
model.optimize()

Optimize a model with 1 rows, 4 columns and 3 nonzeros
Model fingerprint: 0xcf4a20b1
Model has 1 general constraint
Variable types: 1 continuous, 3 integer (2 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 1e+00]
  Bounds range     [1e+00, 2e+01]
  RHS range        [1e+00, 1e+00]
  GenCon rhs range [2e+01, 2e+01]
  GenCon coe range [1e+00, 1e+00]
Found heuristic solution: objective 20.0000000

Explored 0 nodes (0 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 1 (of 2 available processors)

Solution count 1: 20 

Optimal solution found (tolerance 1.00e-04)
Best objective 2.000000000000e+01, best bound 2.000000000000e+01, gap 0.0000%

Also, as the second attempt I try to use two indicator variables as:

$$ w_{1}=1 \quad \Longleftrightarrow \quad x+y=1$$ $$ w_{2}=1 \quad \Longleftrightarrow \quad z\leq 20$$ $$ w_{1}=1 \implies w_{2}=1$$

The linearization of the constraints would be: $$ w_{1}=1 \implies (x+y=1) $$ $$ \lnot(w_{1}) \lor ((x \land \lnot y) \lor (\lnot x \land y)) $$ $$ ((1-w_{1}) \lor x \lor \lnot y)) \land ((1-w) \lor \lnot x \lor y)) $$ $$ ((1-w_{1}) + x + (1-y) \land ((1-w) + (1-x) + y)) \quad (1) $$ $$ (x+y=1) \implies w_{1}=1 $$ $$ (1 - x + y + w \ge 1) \land (x + 1 - y + w \ge 1) \quad \text{from Rob's answer} \quad (2) $$ $$ w_{2}=1 \Longleftrightarrow z\leq 20$$ $$ z + (UB+\epsilon)w_{2} \geq (UB+\epsilon) \quad (3)$$ $$ w_{1} \leq w_{2} \quad (4)$$

$\endgroup$
13
  • $\begingroup$ The $x+y=w$ constraint is too restrictive because it prevents $(x,y)=(1,1)$. $\endgroup$
    – RobPratt
    Mar 5, 2023 at 14:39
  • $\begingroup$ @RobPratt, thanks. $x+y$ should be equal to one that one of $x$ or $y$ would be one. As the upper bound on the constraint is one I defined a binary variable to that. It also would be by setting $w$ up as a integer number. $\endgroup$
    – A.Omidi
    Mar 5, 2023 at 15:58
  • $\begingroup$ In the original problem, $x+y$ can take three values ($0,1,2$), but your formulation disallows $x+y=2$. $\endgroup$
    – RobPratt
    Mar 5, 2023 at 16:22
  • $\begingroup$ @RobPratt, would you please, say how it takes the value of 2? Is there any constraint except $x+y=1$? $\endgroup$
    – A.Omidi
    Mar 5, 2023 at 16:42
  • 1
    $\begingroup$ Because $x$ and $y$ are binary, there are four possible cases for $(x,y)$. In the two cases where $x+y=1$, the requirement is that $z \le 20$. In the other two cases $(0,0)$ and $(1,1)$, there is no restriction on $z$. $\endgroup$
    – RobPratt
    Mar 5, 2023 at 16:52

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.