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
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. 14.8.1 (Affine 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 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:
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
|
Therefore the first disjunction in our example can be written as
M->disjunction( DJC::AND( DJC::term(Expr::dot(dblarray({1,-2,0,0}), x), Domain::lessThan(-1)), // x0 - 2x1 <= -1
DJC::term(x->slice(2, 4), Domain::equalsTo(0)) ), // x2 = x3 = 0
DJC::AND( DJC::term(Expr::dot(dblarray({0,0,1,-3}), x), Domain::lessThan(-2)), // x2 - 3x3 <= -2
DJC::term(x->slice(0, 2), Domain::equalsTo(0)) ) ); // x0 = x1 = 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:
// Disjunctive constraint from an array of terms reading x_i = 2.5 for i = 0,1,2,3
M->disjunction(std::make_shared<ndarray<Term::t,1>>(shape(4), [x](int i) { return DJC::term(x->index(i), Domain::equalsTo(2.5)); }));
The complete code constructing and solving the problem (7.24) is shown below.
#include <iostream>
#include "fusion.h"
using namespace mosek::fusion;
using namespace monty;
std::shared_ptr<ndarray<double,1>> dblarray(std::initializer_list<double> x) {
return new_array_ptr<double,1>(x);
}
int main(int argc, char ** argv)
{
Model::t M = new Model("djc1"); auto _M = finally([&]() { M->dispose(); });
// Create variable 'x' of length 4
Variable::t x = M->variable("x", 4);
// First disjunctive constraint
M->disjunction( DJC::AND( DJC::term(Expr::dot(dblarray({1,-2,0,0}), x), Domain::lessThan(-1)), // x0 - 2x1 <= -1
DJC::term(x->slice(2, 4), Domain::equalsTo(0)) ), // x2 = x3 = 0
DJC::AND( DJC::term(Expr::dot(dblarray({0,0,1,-3}), x), Domain::lessThan(-2)), // x2 - 3x3 <= -2
DJC::term(x->slice(0, 2), Domain::equalsTo(0)) ) ); // x0 = x1 = 0
// Second disjunctive constraint
// Disjunctive constraint from an array of terms reading x_i = 2.5 for i = 0,1,2,3
M->disjunction(std::make_shared<ndarray<Term::t,1>>(shape(4), [x](int i) { return DJC::term(x->index(i), Domain::equalsTo(2.5)); }));
// The linear constraint
M->constraint(Expr::sum(x), Domain::greaterThan(-10));
// Objective
M->objective(ObjectiveSense::Minimize, Expr::dot(dblarray({2,1,3,1}), x));
// Useful for debugging
M->writeTask("djc1.ptf");
M->setLogHandler([ = ](const std::string & msg) { std::cout << msg << std::flush; } );
// Solve the problem
M->solve();
// Get the solution values
if (M->getPrimalSolutionStatus() == SolutionStatus::Optimal) {
auto sol = x->level();
std::cout << "[x0,x1,x2,x3] = " << (*sol) << std::endl;
}
else {
std::cout << "Another solution status" << std::endl;
}
}
