Using indicator constraint with two variables

Question

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?

Answer 1

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

Answer 2

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