6.9 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. 15.10.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 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.
6.9.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.
6.9.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 begin by expressing problem (6.34) in the format where all simple terms are of the form \(D_{ij}x+d_{ij}\in\D_{ij}\), that is of the form a sequence of affine expressions belongs to a linear domain:
where \(0^n\) denotes the \(n\)-dimensional zero domain and \(\real^n_{\leq 0}\) denotes the \(n\)-dimensional nonpositive orthant, as in Sec. 15.10 (Supported domains).
Now we show how to add the two DJCs from (6.35). This involves three steps:
storing the affine expressions which appear in the DJCs,
creating the required domains, and
combining the two into the description of the DJCs.
Readers familiar with Sec. 6.2 (From Linear to Conic Optimization) will find that the process is completely analogous to the process of adding affine conic constraints (ACCs). In fact we would recommend Sec. 6.2 (From Linear to Conic Optimization) as a means of familiarizing with the structures used here at a slightly lower level of complexity.
6.9.3 Step 1: add affine expressions¶
In the first step we need to store all affine expressions appearing in the problem, that is the rows of the expressions \(D_{ij}x+d_{ij}\). In problem (6.35) the disjunctive constraints contain altogether the following affine expressions:
To store affine expressions (AFE for short) MOSEK provides a matrix \(\afef\) and a vector \(\afeg\) with the understanding that every row of
defines one affine expression. The API functions with infix afe are used to operate on \(\afef\) and \(\afeg\), add rows, add columns, set individual elements, set blocks etc. similarly to the methods for operating on the \(A\) matrix of linear constraints. The storage matrix \(\afef\) is a sparse matrix, therefore only nonzero elements have to be explicitly added.
Remark: the storage \(\afef,\afeg\) may, but does not have to be, kept in the same order in which the expressions enter DJCs. In fact in (6.36) we have chosen to list the linear expressions in a different, convenient order. It is also possible to store some expressions only once if they appear multiple times in DJCs.
Given the list (6.36), we initialize the AFE storage as (only nonzeros are listed and for convenience we list the content of (6.36) alongside in the leftmost column):
Initially \(\afef\) and \(\afeg\) are empty (have 0 rows). We construct them as follows. First, we append a number of empty rows:
numafe = 10;
r = MSK_appendafes(task, numafe);
We now have \(\afef\) and \(\afeg\) with 10 rows of zeros and we fill them up to obtain (6.37).
const MSKint64t fafeidx[] = {0, 0, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9};
const MSKint32t fvaridx[] = {0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3};
const MSKrealt fval[] = {1.0, -2.0, 1.0, -3.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0};
const MSKrealt g[] = {1.0, 2.0, 0.0, 0.0, 0.0, 0.0, -2.5, -2.5, -2.5, -2.5};
r = MSK_putafefentrylist(task, 12, fafeidx, fvaridx, fval);
if (r == MSK_RES_OK)
r = MSK_putafegslice(task, 0, numafe, g);
We have now created the matrices from (6.37). Note that at this point we have not defined any DJCs yet. All we did was define some affine expressions and place them in a generic AFE storage facility to be used later.
6.9.4 Step 2: create domains¶
Next, we create all the domains \(\D_{ij}\) appearing in all the simple terms of all DJCs. Domains are created with functions with infix domain. In the case of (6.35) there are three different domains appearing:
We create them with the corresponding functions:
MSK_appendrzerodomain(task, 1, &zero1);
MSK_appendrzerodomain(task, 2, &zero2);
MSK_appendrminusdomain(task, 1, &rminus1);
The function returns a domain index, which is just the position in the list of all domains (potentially) created for the problem. At this point the domains are just stored in the list of domains, but not yet used for anything.
6.9.5 Step 3: create the actual disjunctive constraints¶
We are now in position to create the disjunctive constraints. DJCs are created with functions with infix djc. The function MSK_appenddjcs will append a number of initially empty DJCs to the task:
numdjc = 2;
r = MSK_appenddjcs(task, numdjc);
We can then define each disjunction with the method MSK_putdjc. It will require the following data:
the list
termsizelistof the sizes of all terms of the DJC,the list
afeidxlistof indices of AFEs to be used in the constraint. These are the row numbers in \(\afef,\afeg\) which contain the required affine expressions.the list
domidxlistof the domains for all the simple terms.
For example, consider the first DJC of (6.35). Below we format this DJC by replacing each affine expression with the index of that expression in (6.37) and each domain with its index we obtained in Step 2:
It implies that the DJC will be represented by the following data:
termsizelist = [2, 2],afeidxlist = [0, 4, 5, 1, 2, 3],domidxlist = [rminus1, zero2, rminus1, zero2].
The code adding this DJC will therefore look as follows:
const MSKint64t domidxlist[] = {rminus1, zero2, rminus1, zero2};
const MSKint64t afeidxlist[] = {0, 4, 5, 1, 2, 3};
const MSKint64t termsizelist[] = {2, 2};
r = MSK_putdjc(task,
0, // DJC index
4, domidxlist,
6, afeidxlist,
NULL, // Unused
2, termsizelist);
Note that number of AFEs used in afeidxlist must match the sum of dimensions of all the domains (here: \(6 == 1+2+1+2\)) and the number of domains must match the sum of all term sizes (here: \(4 == 2+2\)).
For similar reasons the second DJC of problem (6.35) will have the description:
termsizelist = [1, 1, 1, 1],afeidxlist = [6, 7, 8, 9],domidxlist = [zero1, zero1, zero1, zero1].
const MSKint64t domidxlist[] = {zero1, zero1, zero1, zero1};
const MSKint64t afeidxlist[] = {6, 7, 8, 9};
const MSKint64t termsizelist[] = {1, 1, 1, 1};
r = MSK_putdjc(task,
1, // DJC index
4, domidxlist,
4, afeidxlist,
NULL, // Unused
4, termsizelist);
This completes the setup of the disjunctive constraints.
6.9.6 Example DJC1 full code¶
We refer to Sec. 6.1 (Linear Optimization) for instructions how to initialize a MOSEK session, add variables and set up the objective and linear constraints. All else that remains is to call the solver with MSK_optimize and retrieve the solution with MSK_getxx. Since our problem contains a DJC, and thus is solved by the mixed-integer optimizer, we fetch the integer solution. The full code solving problem (6.34) is shown below.
#include <stdio.h>
#include "mosek.h"
/* This function prints log output from MOSEK to the terminal. */
static void MSKAPI printstr(void *handle,
const char str[])
{
printf("%s", str);
} /* printstr */
int main(int argc, const char *argv[])
{
MSKenv_t env = NULL;
MSKtask_t task = NULL;
MSKrescodee r = MSK_RES_OK;
MSKint32t i, j, numvar;
MSKint64t k, l, numafe, numdjc;
MSKint64t zero1, zero2, rminus1; // Domain indices
/* Create the mosek environment. */
r = MSK_makeenv(&env, NULL);
if (r == MSK_RES_OK)
{
/* Create the optimization task. */
r = MSK_maketask(env, 0, 0, &task);
if (r == MSK_RES_OK)
{
// Append free variables
numvar = 4;
r = MSK_appendvars(task, numvar);
if (r == MSK_RES_OK)
MSK_putvarboundsliceconst(task, 0, numvar, MSK_BK_FR, -MSK_INFINITY, MSK_INFINITY);
}
if (r == MSK_RES_OK)
{
// The linear part: the linear constraint
const MSKint32t idx[] = {0, 1, 2, 3};
const MSKrealt val[] = {1, 1, 1, 1};
r = MSK_appendcons(task, 1);
if (r == MSK_RES_OK) MSK_putarow(task, 0, 4, idx, val);
if (r == MSK_RES_OK) MSK_putconbound(task, 0, MSK_BK_LO, -10.0, -10.0);
}
if (r == MSK_RES_OK)
{
// The linear part: objective
const MSKint32t idx[] = {0, 1, 2, 3};
const MSKrealt val[] = {2, 1, 3, 1};
r = MSK_putobjsense(task, MSK_OBJECTIVE_SENSE_MINIMIZE);
if (r == MSK_RES_OK) MSK_putclist(task, 4, idx, val);
}
// Fill in the affine expression storage F, g
if (r == MSK_RES_OK)
{
numafe = 10;
r = MSK_appendafes(task, numafe);
}
if (r == MSK_RES_OK)
{
const MSKint64t fafeidx[] = {0, 0, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9};
const MSKint32t fvaridx[] = {0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3};
const MSKrealt fval[] = {1.0, -2.0, 1.0, -3.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0};
const MSKrealt g[] = {1.0, 2.0, 0.0, 0.0, 0.0, 0.0, -2.5, -2.5, -2.5, -2.5};
r = MSK_putafefentrylist(task, 12, fafeidx, fvaridx, fval);
if (r == MSK_RES_OK)
r = MSK_putafegslice(task, 0, numafe, g);
}
if (r == MSK_RES_OK)
{
// Create domains
MSK_appendrzerodomain(task, 1, &zero1);
MSK_appendrzerodomain(task, 2, &zero2);
MSK_appendrminusdomain(task, 1, &rminus1);
}
if (r == MSK_RES_OK)
{
// Append disjunctive constraints
numdjc = 2;
r = MSK_appenddjcs(task, numdjc);
}
if (r == MSK_RES_OK)
{
// First disjunctive constraint
const MSKint64t domidxlist[] = {rminus1, zero2, rminus1, zero2};
const MSKint64t afeidxlist[] = {0, 4, 5, 1, 2, 3};
const MSKint64t termsizelist[] = {2, 2};
r = MSK_putdjc(task,
0, // DJC index
4, domidxlist,
6, afeidxlist,
NULL, // Unused
2, termsizelist);
}
if (r == MSK_RES_OK)
{
// Second disjunctive constraint
const MSKint64t domidxlist[] = {zero1, zero1, zero1, zero1};
const MSKint64t afeidxlist[] = {6, 7, 8, 9};
const MSKint64t termsizelist[] = {1, 1, 1, 1};
r = MSK_putdjc(task,
1, // DJC index
4, domidxlist,
4, afeidxlist,
NULL, // Unused
4, termsizelist);
}
// Useful for debugging
if (r == MSK_RES_OK)
{
// Write a human-readable file
r = MSK_writedata(task, "djc.ptf");
// Directs the log task stream to the 'printstr' function.
if (r == MSK_RES_OK)
r = MSK_linkfunctotaskstream(task, MSK_STREAM_LOG, NULL, printstr);
}
// Solve the problem
if (r == MSK_RES_OK)
{
MSKrescodee trmcode;
r = MSK_optimizetrm(task, &trmcode);
/* Print a summary containing information
about the solution for debugging purposes. */
MSK_solutionsummary(task, MSK_STREAM_LOG);
if (r == MSK_RES_OK)
{
MSKsolstae solsta;
if (r == MSK_RES_OK)
r = MSK_getsolsta(task,
MSK_SOL_ITG,
&solsta);
switch (solsta)
{
case MSK_SOL_STA_INTEGER_OPTIMAL:
{
double *xx = (double*) calloc(numvar, sizeof(double));
if (xx)
{
MSK_getxx(task,
MSK_SOL_ITG,
xx);
printf("Optimal primal solution\n");
for (j = 0; j < numvar; ++j)
printf("x[%d]: %e\n", j, xx[j]);
free(xx);
}
else
r = MSK_RES_ERR_SPACE;
break;
}
default:
printf("Another solution status.\n");
break;
}
}
}
if (r != MSK_RES_OK)
{
/* In case of an error print error code and description. */
char symname[MSK_MAX_STR_LEN];
char desc[MSK_MAX_STR_LEN];
printf("An error occurred while optimizing.\n");
MSK_getcodedesc(r,
symname,
desc);
printf("Error %s - '%s'\n", symname, desc);
}
/* Delete the task and the associated data. */
MSK_deletetask(&task);
}
/* Delete the environment and the associated data. */
MSK_deleteenv(&env);
return r;
}
The answer is
[0, 0, -12.5, 2.5]
6.9.7 Summary and extensions¶
In this section we presented the most basic usage of the affine expression storage \(\afef,\afeg\) to input affine expressions used together with domains to create disjunctive constraints (DJC). Now we briefly point out additional features of his interface which can be useful in some situations for more demanding users. They will be demonstrated in various examples in other tutorials and case studies in this manual.
It is important to remember that \(\afef,\afeg\) has only a storage function and during the DJC construction we can pick an arbitrary list of row indices and place them in a domain. It means for example that:
It is not necessary to store the AFEs in the same order they will appear in DJCs.
The same AFE index can appear more than once in one and/or more conic constraints (this can be used to reduce storage if the same affine expression is used in multiple DJCs).
The \(\afef,\afeg\) storage can even include rows that are not presently used in any DJC.
Domains can be reused: multiple DJCs can use the same domain. On the other hand the same type of domain can appear under many
domidxpositions. In this sense the list of created domains also plays only a storage role: the domains are only used when they enter a DJC.The same affine expression storage \(\afef,\afeg\) is shared between disjunctive constraints and affine conic constraints (ACCs, see Sec. 6.2 (From Linear to Conic Optimization)).
When defining an DJC an additional constant vector \(b\) can be provided to modify the constant terms coming from \(\afeg\) but only for this particular DJC. This could be useful to reduce \(\afef\) storage space if, for example, many expressions \(D^Tx-b_i\) with the same linear part \(D^Tx\), but varying constant terms \(b_i\), are to be used throughout DJCs.
