7.5 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
where each \(T_i\) is written as a conjunction
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. 13.8.1 (Linear domains). A disjunctive constraint (DJC) can therefore be succinctly written as
where each \(T_{i,j}\) is an affine condition.
Each \(T_i\) is called a term or clause 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 (clauses) is satisfied. A term (clause) 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.5.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. 12.4.5 (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.5.2 Example DJC1¶
In this tutorial we will consider the following sample demonstration problem:
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 (clauses).
We refer to the basic tutorials 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 clause appearing in a disjunction is created with the method mosekmodel.clause. A clause is specified similarly to the specification of an ordinary constraint in mosekmodel.appendcons, that is in the form
where \(\mathcal{D}\) is some domain or product of domains.
Therefore the first disjunction in our example can be written as
% A disjunction of two clauses
model.appenddisjunction( [ model.clause(F = [1 -2 0 0 ;
0 0 1 0 ;
0 0 0 1], ...
domain=[ mosekdomain("less than", rhs = [-1]), ... % 1st simple term of 1st clause
mosekdomain("equal", dim = 2, rhs = [0 0]') ]), ... % 2nd simple term of 1st clause
model.clause(F = [0 0 1 -3 ;
1 0 0 0 ;
0 1 0 0], ...
domain = [ mosekdomain("less than", rhs = -2), ... % 1st simple term of 2nd clause
mosekdomain("equal", dim = 2, rhs = [0 0]') ]) ], ... % 2nd simple term of 2nd clause
name = "first-djc");
The disjunctive constraint is added to the model with mosekmodel.appenddisjunction. Here we call this method with two clauses, each of which is a conjunction of 2 simple terms (although one could just as well think of each clause as a conjunction of 3 simple terms, one per each row of \(F\); this distinction is purely a mater of convention).
The second disjunctive constraint is created by passing an array of 4 clauses:
% A disjunction of four clauses
model.appenddisjunction([ model.clause(F = [1 0 0 0], domain = mosekdomain("equal", rhs = 2.5)),...
model.clause(F = [0 1 0 0], domain = mosekdomain("equal", rhs = 2.5)),...
model.clause(F = [0 0 1 0], domain = mosekdomain("equal", rhs = 2.5)),...
model.clause(F = [0 0 0 1], domain = mosekdomain("equal", rhs = 2.5)) ],...
name = "second-djc");
The complete code constructing and solving the problem (7.21) is shown below.
model = mosekmodel(name = "djc1", ...
objsense = "minimize", ...
objective = [ 2,1,3,1 ]', ...
numvar = 4);
% A disjunction of two clauses
model.appenddisjunction( [ model.clause(F = [1 -2 0 0 ;
0 0 1 0 ;
0 0 0 1], ...
domain=[ mosekdomain("less than", rhs = [-1]), ... % 1st simple term of 1st clause
mosekdomain("equal", dim = 2, rhs = [0 0]') ]), ... % 2nd simple term of 1st clause
model.clause(F = [0 0 1 -3 ;
1 0 0 0 ;
0 1 0 0], ...
domain = [ mosekdomain("less than", rhs = -2), ... % 1st simple term of 2nd clause
mosekdomain("equal", dim = 2, rhs = [0 0]') ]) ], ... % 2nd simple term of 2nd clause
name = "first-djc");
% A disjunction of four clauses
model.appenddisjunction([ model.clause(F = [1 0 0 0], domain = mosekdomain("equal", rhs = 2.5)),...
model.clause(F = [0 1 0 0], domain = mosekdomain("equal", rhs = 2.5)),...
model.clause(F = [0 0 1 0], domain = mosekdomain("equal", rhs = 2.5)),...
model.clause(F = [0 0 0 1], domain = mosekdomain("equal", rhs = 2.5)) ],...
name = "second-djc");
% The standard liner constraint
model.appendcons(name = "C", F = [1 1 1 1], domain = mosekdomain("greater than", rhs = -10));
model.solve();
if model.hassolution("integer")
[xx,prosta,solsta] = model.getsolution("integer","x");
fprintf("Solution : [%s]\n", sprintf("%g ", xx));
end
