7.8 Disjunctive constraints¶
A disjunctive constraint (DJC) involves of a number of affine conditions combined with the logical operators
where each
and each
where each
Each
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
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
, where are scalar variables, is equivalent toIt is a DJC with two terms, each of size 1.
Semicontinuous variable. A semicontinuous variable is a scalar variable which takes values in
. This can be expressed asIt is again a DJC with two terms, each of size 1.
Exact absolute value. The constraint
is not convex, but can be written asIt is a DJC with two terms, each of size 2.
Indicator. Suppose
is a Boolean variable. Then we can write the indicator constraint aswhich is a DJC with two terms, of sizes, respectively, 2 and 1.
Piecewise linear functions. Suppose
and is a piecewise linear function, given on the -th of intervals by a different affine expression . Then we can write the constraint asmaking it a DJC with
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.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.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
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(new double[]{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(new double[]{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:
// Array of terms reading x_i = 2.5 for i = 0,1,2,3
Term[] terms = new Term[4];
for(int i = 0; i < 4; i++)
terms[i] = DJC.term(x.index(i), Domain.equalsTo(2.5));
// The disjunctive constraint from the array of terms
M.disjunction(terms);
The complete code constructing and solving the problem (7.24) is shown below.
package com.mosek.fusion.examples;
import mosek.fusion.*;
public class djc1 {
public static void main(String[] args)
throws SolutionError {
try(Model M = new Model("djc1"))
{
// Create variable 'x' of length 4
Variable x = M.variable("x", 4);
// First disjunctive constraint
M.disjunction( DJC.AND( DJC.term(Expr.dot(new double[]{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(new double[]{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
// Array of terms reading x_i = 2.5 for i = 0,1,2,3
Term[] terms = new Term[4];
for(int i = 0; i < 4; i++)
terms[i] = DJC.term(x.index(i), Domain.equalsTo(2.5));
// The disjunctive constraint from the array of terms
M.disjunction(terms);
// The linear constraint
M.constraint(Expr.sum(x), Domain.greaterThan(-10));
// Objective
M.objective(ObjectiveSense.Minimize, Expr.dot(new double[]{2,1,3,1}, x));
// Useful for debugging
M.writeTask("djc.ptf"); // Save to a readable file
M.setLogHandler(new java.io.PrintWriter(System.out)); // Enable log output
// Solve the problem
M.solve();
if (M.getPrimalSolutionStatus() == SolutionStatus.Optimal) {
double[] sol = x.level();
System.out.printf("[x0,x1,x2,x3] = [%e, %e, %e, %e]\n", sol[0], sol[1], sol[2], sol[3]);
}
else {
System.out.printf("Anoter solution status");
}
}
}
}