7.8 Disjunctive constraints

A disjunctive constraint (DJC) involves of a number of affine conditions combined with the logical operators \(\OR\) (\(\vee\)) and optionally \(\AND\) (\(\wedge\)) into a formula in disjunctive normal form, that is a disjunction of conjunctions. Specifically, a disjunctive constraint has the form of a disjunction

(7.21)\[T_1\ \OR\ T_2\ \OR \cdots\ \OR\ T_t\]

where each \(T_i\) is written as a conjunction

(7.22)\[T_i = T_{i,1}\ \AND\ T_{i,2}\ \AND \cdots\ \AND\ T_{i,s_i}\]

and each \(T_{i,j}\) is an affine condition (affine equation or affine inequality) of the form \(D_{ij}x+d_{ij}\in\D_{ij}\) with \(\D_{ij}\) being one of the affine domains from Sec. 14.8.1 (Affine domains). A disjunctive constraint (DJC) can therefore be succinctly written as

(7.23)\[ \bigvee_{i=1}^t \bigwedge_{j=1}^{s_i} T_{i,j}\]

where each \(T_{i,j}\) is an affine condition.

Each \(T_i\) is called a term of the disjunctive constraint and \(t\) is the number of terms. Each condition \(T_{i,j}\) is called a simple term and \(s_i\) is called the size of the \(i\)-th term.

A disjunctive constraint is satisfied if at least one of its terms is satisfied. A term is satisfied if all of its constituent simple terms are satisfied. A problem containing DJCs will be solved by the mixed-integer optimizer.

Note that nonlinear cones are not allowed as one of the domains \(\D_{ij}\) inside a DJC.

7.8.1 Applications

Disjunctive constraints are a convenient and expressive syntactical tool. Then can be used to phrase many constructions appearing especially in mixed-integer modelling. Here are some examples.

• Complementarity. The condition \(xy=0\), where \(x,y\) are scalar variables, is equivalent to

  \[x=0\ \OR\ y=0.\]

  It is a DJC with two terms, each of size 1.

• Semicontinuous variable. A semicontinuous variable is a scalar variable which takes values in \(\{0\} \cup [a,+\infty]\). This can be expressed as

  \[x=0\ \OR\ x\geq a.\]

  It is again a DJC with two terms, each of size 1.

• Exact absolute value. The constraint \(t=|x|\) is not convex, but can be written as

  \[(x\geq 0\ \AND\ t=x)\ \OR\ (x\leq 0\ \AND\ t=-x)\]

  It is a DJC with two terms, each of size 2.

• Indicator. Suppose \(z\) is a Boolean variable. Then we can write the indicator constraint \(z=1 \implies a^Tx\leq b\) as

  \[(z=1\ \AND\ a^Tx\leq b)\ \OR\ (z=0)\]

  which is a DJC with two terms, of sizes, respectively, 2 and 1.

• Piecewise linear functions. Suppose \(a_1\leq\cdots\leq a_{k+1}\) and \(f:[a_1,a_{k+1}]\to\real\) is a piecewise linear function, given on the \(i\)-th of \(k\) intervals \([a_i,a_{i+1}]\) by a different affine expression \(f_i(x)\). Then we can write the constraint \(y=f(x)\) as

  \[\bigvee_{i=1}^k\left(a_i\leq y\ \AND\ y\leq a_{i+1}\ \AND\ y-f_i(x)=0 \right)\]

  making it a DJC with \(k\) terms, each of size 3.

On the other hand most DJCs are equivalent to a mixed-integer linear program through a big-M reformulation. In some cases, when a suitable big-M is known to the user, writing such a formulation directly may be more efficient than formulating the problem as a DJC. See Sec. 13.4.6 (Disjunctive constraints) for a discussion of this topic.

Disjunctive constraints can be added to any problem which includes linear constraints, affine conic constraints (without semidefinite domains) or integer variables.

7.8.2 Example DJC1

In this tutorial we will consider the following sample demonstration problem:

(7.24)\[\begin{split}\begin{array}{ll} \minimize & 2x_0+x_1+3x_2+x_3 \\ \st & x_0+x_1+x_2+x_3\geq -10, \\ & \left(\begin{array}{c}x_0-2x_1\leq -1\\ \AND\\ x_2=x_3=0\end{array}\right)\ \OR\ \left(\begin{array}{c}x_2-3x_3\leq -2\\ \AND\\ x_0=x_1=0\end{array}\right),\ \\ & x_i=2.5\ \textrm{for at least one}\ i\in\{0,1,2,3\}. \end{array}\end{split}\]

The problem has two DJCs: the first one has 2 terms. The second one, which we can write as \(\bigvee_{i=0}^3(x_i=2.5)\), has 4 terms.

We refer to Sec. 7.1 (Linear Optimization) for the details of constructing a model and setting up variables and linear constraints. In this tutorial we focus on the two disjunctive constraints. Each of the simple terms appearing in disjunctions is constructed using DJC.term in the form known from ordinary constraints, that is

Expression belongs to a Domain.

Therefore the first disjunction in our example can be written as

    M.disjunction( (x[0]-2*x[1]<=-1) & (x[2:4]==0) 
                  | 
                   (x[2]-3*x[3]<=-2) & (x[0:2]==0))

The disjunctive constraint is added to them model with Model.disjunction (|). Here we call this method with two terms, each of which is a conjunction (DJC.AND (&)) of simple terms.

The second disjunctive constraint is created by passing an array of 4 terms:

    # Array of terms reading x_i = 2.5 for i = 0,1,2,3
    M.disjunction( [ x[i] == 2.5 for i in range(4) ])

The complete code constructing and solving the problem (7.24) is shown below.

Listing 7.16 Source code solving problem (7.24). Click here to download.

from mosek.fusion import *
import mosek.fusion.pythonic
import sys

with Model('djc1') as M:
    # Create a variable of length 4
    x = M.variable('x', 4)

    # First disjunctive constraint
    M.disjunction( (x[0]-2*x[1]<=-1) & (x[2:4]==0) 
                  | 
                   (x[2]-3*x[3]<=-2) & (x[0:2]==0))
    
    # Second disjunctive constraint
    # Array of terms reading x_i = 2.5 for i = 0,1,2,3
    M.disjunction( [ x[i] == 2.5 for i in range(4) ])

    # The linear constraint
    M.constraint(Expr.sum(x) >= -10)

    # Objective
    M.objective(ObjectiveSense.Minimize, Expr.dot([2,1,3,1], x))

    # Useful for debugging
    M.writeTask("djc.ptf")          # Save to a readable file
    M.setLogHandler(sys.stdout)     # Enable log output

    # Solve 
    M.solve()

    if M.getPrimalSolutionStatus() == SolutionStatus.Optimal:
        print(f"Solution ={x.level()}")
    else:
        print("Another solution status")