Indicator constraints

Topics covered in this section:

• Indicator constraints associate a binary variable b with a linear or nonlinear constraint C.
• An indicator constraint models an implication:
  'if b=1 then C', in symbols: b → C, or
  'if b=0 then C', in symbols: not(b) → C
  (the constraint C is active only if the condition is true)
• Indicator constraints can be used for the composition of logic expressions.

 uses "mmxprs"

 declarations
  R=1..2
  C: array(range) of linctr
  L: array(range) of logctr
  x, b: array(R) of mpvar
 end-declarations

 forall(i in R) b(i) is_binary   ! Variables for indicator constraints

 C(2):= x(2)<=5

! Define 2 indicator constraints
 L(1):= indicator(1, b(1), x(1)+x(2)>=12)    ! b(1)=1 -> x(1)+x(2)>=12
 indicator(-1, b(2), C(2))                   ! b(2)=0 -> x(2)<=5

 C(2):=0                         ! Delete auxiliary constraint definition

 uses "mmxnlp"

 declarations
  R=1..2
  C: array(range) of nlctr
  L: array(range) of logctr
  x, b: array(R) of mpvar
 end-declarations

 forall(i in R) b(i) is_binary   ! Variables for indicator constraints

 C(2):= sin(x(2))>=0.5

! Define 2 indicator constraints
 L(1):= indicator(1, b(1), x(1)*x(2)>=12)    ! b(1)=1 -> x(1)*x(2)=12
 indicator(-1, b(2), C(2))                   ! b(2)=0 -> sin(x(2))>=0.5

 C(2):=0                         ! Delete auxiliary constraint definition

import xpress as xp

N = 2

p = xp.problem()

# Create the decision variables
x = [p.addVariable(name="x_{}".format(i),vartype=xp.continuous) for i in range(N)]
b = [p.addVariable(name="b_{}".format(i),vartype=xp.binary) for i in range(N)]

# b[0] = 1 -> x[0]+x[1] >= 12
p.addIndicator(b[0] == 1, x[0] + x[1] >= 12)
# b[1] = 0 -> x[1] <= 5
p.addIndicator(b[1] == 0, x[1] <= 5)

  XpressProblem prob;

  // Create the decision variables
  auto x = prob.addVariables(N).withType(ColumnType::Continuous).withName("x_%d").toArray();
  auto b = prob.addVariables(N).withType(ColumnType::Binary).withName("b_%d").toArray();

  // Define 2 indicator constraints:
  // b[0] = 1 -> x[0]+x[1] >= 12
  prob.addConstraint(b[0].ifThen(x[0] + x[1] >= 12));
  // b[1] = 0 -> x[1] <= 5
  prob.addConstraint(b[1].ifNotThen(x[1] <= 5));

Inverse implication

b ← a·x ≥ c

• Model as

  not(b) → a·x ≤ c-m

  where m is a sufficiently small value (slightly larger than the feasibility tolerance)

b ← a·x ≤ c

• Model as

  not(b) → a·x ≥ c+m

b ← a·x = c

• Model as

  not(b) → b1 + b2 = 1

  b1 → a·x ≥ c+m

  b2 → a·x ≤ c-m

Logical constructs

Indicator constraints can be used for the formulation of logical constructs composed of linear or nonlinear equality or inequality constraints and the logic functions 'implies', 'not', 'and', 'or', or 'xor' by applying a set of recipes.

In the following we shall be using the following definitions:

C (constraint)

a linear or nonlinear equality or inequality constraint

IC (indicator contraint)

can be either like y → C or not(y) → C

LE (logical expression)

either a C or one of the following functions (of C's or LE's): AND, OR, XOR, NOT, IMPLIES, such as IMPLIES(x(1)>=10, AND(x(1)+x(2)>=12, NOT(x(2)<=5)))

To model logical constructs we associate a binary indicator variable y(e) to each LE e, representing its truth value. For each pair (y(e), e), we may need to enforce either that y(e) → e or y(e) ← e or both, that is, y(e) ↔ e.

We will write

• is(e) (for ImplieS) to refer to the implication y(e) → e, and
• id(e) (for ImplieD) to refer to the implication y(e) ← e which is equivalent to not(y(e)) → not(e).

To model a logical construct, we proceed recursively from the outer LE. Let e be the outer LE, then we can model it as follows:

Rules to model logical constructs

The following set of rules can be applied to model each type of LE (with y being its associated indicator variable).

• C (e.g. a·x≥b)
  • is direction

    model it in the obvious way as an indicator constraint (e.g. y → a·x≥b)

  • id direction

    model it as an inverse implication (e.g. not(y) → a·x≤b-m)

    Here m is a parameter whose default value should be somewhat larger than the feasibility tolerance. When the involved constraints are all integer, m could be set equal to 1.
• AND(e₁, e₂,...,e_n)
  • is direction

    add n contraints: y → y(ei) = 1 ∀ i model is(ei) ∀ i

  • id direction

    add contraint: not(y) → ∑i=1ny(ei) ≤ n- 1 model id(ei) ∀ i

• OR(e₁, e₂,...,e_n)
  • is direction

    add contraint: y → ∑i=1ny(ei) ≥ 1 model is(ei) ∀ i

  • id direction

    add contraint: not(y) → ∑i=1ny(ei) = 0 model id(ei) ∀ i

• XOR(e₁, e₂,...,e_n)
  • is direction

    add constraint: y → ∑i=1ny(ei) = 1 model is(ei) and id(ei) ∀ i

  • id direction

    add two auxiliary variables y' and y" and the constraints y' → ∑i=1ny(ei) = 0 y" → ∑i=1ny(ei) ≥ 2 not(y) → y' + y" = 1 model is(ei) and id(ei) ∀ i

• NOT(e)
  • is direction

    add constraint: y + y(e) = 1 model id(e)

  • id direction

    add constraint: y + y(e) = 1 model is(e)

• IMPLIES(e₁, e₂) (same as: e₁ → e₂)
  • is direction

    add constraint: y → y(e1) ≤ y(e2) model id(e1) and is(e2)

  • id direction

    add constraints: not(y) → y(e1) = 1 not(y) → y(e2) = 0 model is(e1) and id(e2)

Example

By applying the reformulation rules from the previous section to an expression LE that is defined as LE = IMPLIES(x(1)>=10, AND(x(1)+x(2)>=12, NOT(x(2)<=5))) we obtain the following:

start:
  associate y to the outermost expression "LE=IMPLIES(...)"
  add constraint: y = 1
  model is(LE)

model is(LE) yields:
  associate y1 to "e1=x(1)>=10" and y2 to "e2=AND(...)"
  add constraint: y -> y1 = y2
  model id(e1) and is(e2)

model id(e1) yields:
  add constraint: not(y1) -> x(1)=10-m

model is(e2) yields:
  associate y3 to "e3=x(1)+x(2)>=12" and y4 to "e4=NOT(x(2)=5)"
  add constraints:
  y2 -> y3=1
  y2 -> y4=1
  model is(e3) and is(e4)

model is(e3) yields:
  add constraint: y3 -> x(1)+x(2)>=12

model is(e4) yields:
  associate y5 with "e5=x(2)=5"
  add constraint: y4 + y5 = 1
  model id(e5)

model id(e5) yields:
  add constraint: not(y5) -> x(2)>=5+m

In summary, the resulting model formulation is as follows (where the outer fixed indicator constraint can be removed):

 binaries y, y1, y2, y3, y4, y5
 y = 1
 y -> y1 = y2
 not(y1) -> x(1)=10-m
 y2 -> y3=1
 y2 -> y4=1
 y3 -> x(1)+x(2)>=12
 y4 + y5 = 1
 not(y5) -> x(2)>=5+m