Indicator constraints

Indicator constraints

• associate a binary variable b with a linear constraint C
• model an implication:
  'if b=1 then C', in symbols: b → C, or
  'if b=0 then C', in symbols: b^- → C
  (the constraint C is active only if the condition is true)
• use indicator constraints for the composition of logic expressions

Indicator constraints in Mosel: for the definition of indicator constraints (function indicator of module mmxprs) you need a binary variable (type mpvar) and a linear inequality constraint (type linctr). You also have to specify the type of the implication (1 for b → C and -1 for b^- → C). The subroutine indicator returns a new constraint of type logctr that can be used in the composition of other logic expressions (see Section Logic constructs below).

 uses "mmxprs"

 declarations
  R=1..10
  C: array(range) of linctr
  L: array(range) of logctr
  x: array(R) of mpvar
  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

Indicator constraints in BCL: an indicator constraint is defined by associating a binary decision variable (XPRBvar) and an integer flag (1 for b → C and -1 for b^- → C) with a linear inequality or range constraint (XPRBctr). By defining an indicator constraint (function XPRBsetindicator or method XPRBctr.setIndicator() depending on the host language) the type of the constraint itself gets changed; it can be reset to 'standard constraint' by calling the setIndicator function with flag value 0.

 XPRBprob prob("testind");
 XPRBvar x[N], b[N];
 XPRBctr IndCtr[N];
 int i;

// Create the decision variables
 for(i=0;i<N;i++) x[i] = prob.newVar("x", XPRB_PL);  // Continuous variables
 for(i=0;i<N;i++) b[i] = prob.newVar("b", XPRB_BV);  // Indicator variables

// Define 2 linear inequality constraints
 IndCtr[0] = prob.newCtr("L1", x[0]+x[1]>=12);
 IndCtr[1] = prob.newCtr("L2", x[1]<=5);

// Turn the 2 constraints into indicator constraints
 IndCtr[0].setIndicator(1, b[0]);              // b(0)=1 -> x(0)+x(1)>=12
 IndCtr[1].setIndicator(-1, b[1]);             // b(1)=0 -> x(1)<=5

Inverse implication

b ← ax ≥ c

• Model as

  b- → ax ≤ c-m

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

b ← ax ≤ c

• Model as

  b- → ax ≥ c+m

b ← ax = c

• Model as

  b- → b1 + b2 = 1

  b1 → ax ≥ c+m

  b2 → ax ≤ c-m

Logic constructs

Mosel provides the type logctr for defining and working with logic constraints in MIP models. The implementation of these constraints is based on indicator constraints. Logic constraints are composed with linear constraints using the operations and, or, xor, implies, and not as shown in the following example. Mosel models using logic constraints must include the package advmod instead of the Xpress Optimizer library mmxprs.

 uses "advmod"

! **** 'implies', 'not', and 'and' ****
 declarations
  R = 1..3
  C: array(range) of linctr
  x: array(R) of mpvar
 end-declarations

 C(1):= x(1)>=10
 C(2):= x(2)<=5
 C(3):= x(1)+x(2)>=12

 implies(C(1), C(3) and not C(2))
 forall(j in 1..3) C(j):=0              ! Delete the auxiliary constraints

! Same as:
 implies(x(1)>=10, x(1)+x(2)>=12 and not x(2)<=5)

! **** 'or' and 'xor' ****
 declarations
  p: array(1..6) of mpvar
 end-declarations

 forall(i in 1..6) p(i) is_binary

! Choose at least one of projects 1,2,3 (option A)
! or at least two of projects 2,4,5,6 (option B)
  p(1) + p(2) + x(3) >= 1 or p(2) + p(4) + p(5) + p(6) >= 2

! Choose either option A or option B, but not both
  xor(p(1) + p(2) + p(3) >= 1, x(2) + p(4) + p(5) + p(6) >= 2)

These logic constructs, particularly the logic or, can be used for the formulation of minimum or maximum values of a set of variables and also for absolute values:

• Minimum values: y = min{x₁, x₂, ..., x_n} for continuous variables x₁, ..., x_n
  • Logic formulation:

    y ≤ xi ∀ i=1,...,n

    y ≥ x1 or ... or y ≥ xn

• Maximum values: y = max{x₁, x₂, ..., x_n} for continuous variables x₁, ..., x_n
  • Logic formulation:

    y ≥ xi   ∀ i=1,...,n

    y ≤ x1 or ... or y ≤ xn

• Absolute values: y = | x₁ - x₂| for two variables x₁, x₂
  • Modeling y = | x₁ - x₂| is equivalent to y = max{ x₁ - x₂, x₂ - x₁ }
  • Logic formulation:

    y ≥ x1 - x2

    y ≥ x2 - x1

    y ≤ x1 - x2 or y ≤ x2 - x1

• Example implementation with Mosel:

 declarations
  x: array(1..2) of mpvar
  y, u, v: mpvar
  C1, C2: linctr
  C3: logctr
 end-declarations

! Formulation of y = min{x(1), x(2)}
 C1:= y <= x(1)
 C2:= y <= x(2)
 C3:= y >= x(1) or y >= x(2)

! Formulation of u = max{x(1), x(2)}
 C1:= u >= x(1)
 C2:= u >= x(2)
 C3:= u <= x(1) or u <= x(2)

! Formulation of v = |x(1) - x(2)|
 C1:= v >= x(1) - x(2)
 C2:= v >= x(2) - x(1)
 C3:= v <= x(1) - x(2) or v <= x(2) - x(1)