Table of Contents
Disjunctive programming is an alternative modeling approach to mixed integer programming. Both mathematical programs model optimization problems that involve discrete and continuous variables. The advantage of disjunctive programming is that it retains and exploits the inherent logic structure of problems and thus reduces the combinatorics and improves the relaxations by using Boolean variables and disjunction definitions for modeling discrete choices.
Disjunctive programs have many applications, including ordering of tasks in a production process, organizing complex projects in a time saving manner and choosing the optimal route in a circuit.
In this section we first present the mathematical formulation of Generalized Disjunctive Programs (GDPs) and then demonstrate how disjunctive programs are implemented with GAMS EMP using two simple examples. Note that both examples are adapted from the LogMIP 2.0 User's Manual. At the end of the section we introduce and discuss the syntax for EMP annotations for disjunctive programs.
For information on the development of disjunctive programming in GAMS EMP and its connection to the solver LogMIP, see the respective section in the solver manual of the solver JAMS.
Generalized Disjunctive Programs (GDPs)
A GDP has Boolean and continuous variables, algebraic constraints that need to be satisfied regardless of the discrete choices, disjunctions that represent the discrete choices, and logic propositions that contain the logic relationships between the Boolean variables. Mathematically, the general structure of a GDP may be expressed as follows:
\begin{equation*} \tag {28} \begin{array}{llr} \textrm{Min} & f(x) & \textrm{Objective Function} \\ \textrm{s.t.} & g(x) \, \leq \, 0 & \textrm{Algebraic Constraints} \\ & \bigvee_{i \in D_k} \begin{bmatrix} Y_{ik} \\ r_{ik}(x) \leq 0 \end{bmatrix}, \, k \in K & \textrm{Disjunctions} \\ & \Omega (Y) = \textrm{True} & \textrm{Logic Propositions} \\ & L \leq x \leq U, \, x \in \mathbb R^n, & \textrm{Continuous Variables} \\ & Y_{ik} \in \{\textrm{True, False} \} & \textrm{Boolean Variables} \end{array} \end{equation*}
where:
- \( f : \mathbb R^n \rightarrow \mathbb R \) is a function, \( x \) is a vector of continuous variables with bounds \(L\) and \(U\).
- \( g : \mathbb R^n \rightarrow \mathbb R^l \) represents the set of global constraints.
- Each disjunction \(k \in K\) is composed of a number of terms \(i \in D_k\) that are connected by the Boolean operator
OR( \(\bigvee\)). - Each term \( i \in D_k\) consists of a Boolean variable \(Y_{ik}\) and a set of inequalities \(r_{ik}(x) \leq 0 \), \(r_{ik} : \mathbb R^n \rightarrow \mathbb R^j\). If \(Y_{ik}\) is true, then \(r_{ik}(x) \leq 0 \) is enforced, otherwise these constraints are ignored.
- \( \Omega (Y) = \textrm{True}\) are logic propositions for the Boolean variables \(Y_{ik}\) expressed in the Conjunctive Normal Form \( \Omega (Y) = \bigwedge_{t=1,2, \dots, T} [\bigvee_{Y_{jk} \in R_t} (Y_{jk}) \bigvee_{Y_{jk} \in Q_t} (\neg Y_{jk})] \), where for each clause \(t \in {1, \dots, T}\), \(R_t\) is the subset of Boolean variables that are non-negated and \(Q_t\) is the subset of Boolean variables that are negated.
N.B.: we assume that each disjunction is an exclusive-or, so that for each \(k\) exactly one variable \(Y_{ik}\) is true. Put another way, we assume the logic constraints \( \underline{\bigvee}_{i \in D_k} Y_{ik} \) are contained in \( \Omega (Y) = \textrm{True} \).
There are three cases of disjunctive programs: the functions \(f\), \(g\) and \(r\) are linear, some of them are nonlinear, but convex, and some of them are nonlinear and nonconvex. Note that currently GAMS EMP facilitates modeling only the first two cases.
Disjunctive Programming with EMP: Example with No Algebraic Constraints
Consider the following simple example, that has no algebraic constraints which must be satisfied regardless of the disjunctive choices:
\begin{equation*} \tag {29} \begin{array}{llr} \textrm{Minimize} & c + 2x_1 + x_2 & \textrm{Objective Function} \\ \textrm{subject to} & & \\ & \begin{bmatrix} Y_{1} \\ -x_1 + x_2 + 2 \leq 0 \\ c \leq 5 \end{bmatrix} \, \vee \begin{bmatrix} Y_{2} \\ 2 - x_2 \leq 0 \\ c \leq 7 \end{bmatrix} & \textrm{Disjunctions} \\ \\ & \begin{bmatrix} Y_3 \\ x_1 - x_2 \leq 0 \end{bmatrix} \, \vee \begin{bmatrix} \neg Y_3 \\ x_1 \leq 1 \end{bmatrix} & \\ \\ & Y_1 \land \neg Y_2 \Rightarrow \neg Y_3 & \textrm{Logic Propositions} \\ & Y_2 \Rightarrow \neg Y_3 & \\ & Y_3 \Rightarrow \neg Y_2 & \\ \\ & 0 \leq x_1 \leq 5 & \textrm{Continuous Variables} \\ & 0 \leq x_2 \leq 5 & \\ & c \geq 0 & \\ \\ & Y_j \in \{\textrm{True, False}\}, \, j=1,2,3 & \textrm{Boolean Variables} \end{array} \end{equation*}
Observe that there are two disjunctions, each with two terms. In the first disjunction, each term is governed by a different Boolean variable: the first term is active if \(Y_1\) is true and the second term is active if \(Y_2\) is true. In the second disjunction, both terms are governed by the Boolean variable \(Y_3\): the first term applies if \(Y_3\) is true and the second term applies if \(Y_3\) is false.
Note that the logic propositions imply that if \(Y_1\) is true and \(Y_2\) is false , then \(Y_3\) must be false, and that \(Y_2\) and \(Y_3\) cannot both be true.
This example can be implemented in GAMS EMP as follows:
Set i / 1*2 /
j / 1*3 /;
Positive Variables x(i), c;
Variable z;
Binary Variables y(j);
x.up(i) = 5;
c.up = 7;
Equations Obj, Eq1, Eq2, Eq3, Eq4, Eq5, Eq6;
Obj.. z =e= c + 2*x('1') + x('2');
* Equations for Disjunctions
Eq1.. x('2') - x('1') =l= - 2;
Eq2.. c =l= 5;
Eq3.. x('2') =g= 2;
Eq4.. c =l= 7;
Eq5.. x('1') - x('2') =l= 1 ;
Eq6.. x('1') =l= 1;
* Equations for Logic Propositions
Logic Equations LEq1, LEq2, LEq3;
LEq1.. y('1') and not y('2') -> not y('3');
LEq2.. y('2') -> not y('3');
LEq3.. y('3') -> not y('2');
Model small1 / all /;
File emp / '%emp.info%' /;
put emp;
$onput
disjunction y('1') Eq1 Eq2 elseif y('2') Eq3 Eq4
disjunction y('3') Eq5 else Eq6
$offput
putclose;
Option optcr = 0.0;
solve small1 using EMP minimize z;
Note that in this model the Boolean variables \(Y_j\) are implemented as GAMS binary variables, the inequalities in the terms of the disjunctions are formulated as GAMS equations, and the logic propositions are expressed as GAMS logic equations. The disjunctive structure of the model is specified in the EMP annotations file emp.info. This file contains two lines (one per disjunction), each starting with the EMP keyword disjunction and specifying the structure and content of its disjunction. In the first line or disjunction, the binary variable y('1') that governs the first term is followed by the two equations contained in this term. The EMP keyword elseif denotes the start of a new term, here governed by the binary variable y('2') listed next and containing the two equations Eq3 and Eq4. Similarly, in the second line, the binary variable y('3') that governs the first term of the second disjunction is followed by the equation Eq5 contained in that term. As the binary variable governing the second term is just the negation of y('3'), the keyword else is enough to specify this and is followed by the equation Eq6 of the second term.
- Note
- Much more complex logical constructs for disjunctions are possible. For details, see section EMP Syntax for Disjunctive Programming below.
Finally, note that the model type in the solve statement is EMP.
Given the annotations in the file emp.info, the solver JAMS reformulates the model as a MIP (Mixed Integer Programming) model and passes it to a subsolver. By default, the convex hull relaxation is used for the reformulation, but users may choose reformulations that use big M or indicator constraints: see section EMP Syntax for Disjunctive Programming for details.
Observe that the listing file will contain some additional information if the model type EMP is used. The EMP Summary and the Disjunction Summary may be particularly useful. The respective listings for our example model follow:
--- EMP Summary
Logical Constraints = 3
Disjunctions = 2
...
...
--- Disjunction Summary
Disjunction 1 Term 2 is active
Disjunction 2 Term 2 is active
Note that the EMP summary lists the number of logic constraints and disjunctions and the disjunction summary reports which terms of the disjunctions are active in the optimal solution.
Disjunctive Programming with EMP: Example with No Logic Propositions
Consider the following simple example:
\begin{equation*} \tag {30} \begin{array}{llr} \textrm{Min} & t & \textrm{Objective Function} \\ \textrm{s.t.} & t \geq x_A + 8 & \textrm{Algebraic Constraints} \\ & t \geq x_B + 5 & \\ & t \geq x_C + 6 & \\ \\ & \begin{bmatrix} Y_{1} \\ x_A - x_C + 5 \leq 0 \end{bmatrix} \, \vee \begin{bmatrix} \neg Y_{1} \\ x_C - x_A + 2 \leq 0 \end{bmatrix} & \textrm{Disjunctions} \\ \\ & \begin{bmatrix} Y_2 \\ x_B - x_C + 1 \leq 0 \end{bmatrix} \, \vee \begin{bmatrix} \neg Y_2 \\ x_C - x_B + 6 \leq 0 \end{bmatrix} & \\ \\ & \begin{bmatrix} Y_3 \\ x_A - x_B + 5 \leq 0 \end{bmatrix} \, \vee \begin{bmatrix} \neg Y_3 \\ x_B - x_A \leq 0 \end{bmatrix} & \\ \\ & t, x_A, x_B, x_C \geq 0 & \textrm{Continuous Variables} \\ \\ & Y_j \in \{\textrm{True, False} \}, \, j=1,2,3 & \textrm{Boolean Variables} \end{array} \end{equation*}
As this example has no logic propositions, the binary variables would not appear in any equations of a GAMS formulation like the one above. As a result, the binary variables would not be part of the model and any EMP annotations file that mentions these variables would be rejected by the EMP solver. To avoid this problem, we can introduce a dummy equation and include it in the EMP model: this ensures that the binary variables will be part of the GAMS model. The respective code follows:
set i / A, B, C /
j / 1*3 /
;
positive variables x(i), t;
binary variables y(j);
variable z;
equations obj, alg1, alg2, alg3,
d1t1, d1t2, d2t1, d2t2, d3t1, d3t2
dummy;
obj.. z =e= t;
* common algebraic equations
alg1.. t =g= x('A') + 8;
alg2.. t =g= x('B') + 5;
alg3.. t =g= x('C') + 6;
* equations for disjunctions
d1t1.. x('A') - x('C') + 5 =l= 0;
d1t2.. x('C') - x('A') + 2 =l= 0;
d2t1.. x('B') - x('C') + 1 =l= 0;
d2t2.. x('C') - x('B') + 6 =l= 0;
d3t1.. x('A') - x('C') + 5 =l= 0;
d3t2.. x('B') - x('C') =l= 0;
* dummy equation
dummy.. sum(j, y(j)) =g= 0;
model small2 / all /;
file emp / '%emp.info%' /;
putclose emp
"disjunction y('1') d1t1 else d1t2" /
"disjunction y('2') d2t1 else d2t2" /
"disjunction y('3') d3t1 else d3t2" /
;
option optcr = 0.0;
solve small2 using EMP minimize z;
Apart from the dummy equation, this formulation is very similar to the formulation in the first example above.
EMP also supports an alternative formulation for models that have no logic equations, a formulation using implicit default binary variables. These variables are denoted in the EMP annonations with the star symbol '*', which is internally replaced by a default binary variable. Note that this alternative model does not contain any explicit binary variables Y(j) and hence the dummy equation may be omitted, as in the following GAMS code which can be added to the model above:
model small3 'no dummy equation needed' / small2 - dummy /;
putclose emp
"disjunction * d1t1 else d1t2" /
"disjunction * d2t1 else d2t2" /
"disjunction * d3t1 else d3t2" /
;
solve small3 using EMP minimize z;
EMP Syntax for Disjunctive Programming
The general syntax that EMP provides to write disjunctions to the EMP annotations file emp.info is as follows:
Disjunction [chull [chull eps] | bigM [big M value] | indic]
[NOT] var|* [NOT] {equ} {ELSEIF [NOT] var|* [NOT] {equ}} [ELSE [NOT] {equ}]
The EMP keyword Disjunction is mandatory, it indicates that what follows is a disjunction. The three constructs that follow are optional and relate to the three possible reformulations: convex hull (chull), big M method (bigM) or indicator constraints (indic). Note that in the the sequencing model [SEQUENCE] all three options are implemented. Note further, that currently, indicator constraints can only be handled by the solvers CPLEX, SCIP and XPRESS.
- Note
- By default, the convex hull reformulation method is used.
- A different reformulation method may be used for each disjunction.
Observe that for the convex hull reformulation, the value of the parameter epsilon may optionally be specified. This parameter is an upper bound to check for constraint satisfaction, the default value is 0.0001.
Note that for the big M method, the value of M may optionally be specified. The value of M should be large enough to relax the constraint, but it should not be too large, to avoid infeasible solutions. The default value is 10000.
Following the EMP keyword disjunction, the first mandatory entry is a specification of the variable that governs the disjunction: [NOT] var|*. This may be either a binary variable, a negated binary variable or the symbol '*', that is internally replaced by default binary variables. For an example and more details on the symbol '*' in this context, see section Disjunctive Programming with EMP: Example with No Logic Propositions. Further, {equ} denotes a set of GAMS equation names that must be satisfied if the first disjunction term is selected. The remainder of the syntax is self-explanatory.
Alternatively, the following syntax may be used:
Default [chull [chull eps] | bigM [big M value] | indic]
Disjunction [NOT] var|* [NOT] {equ} {ELSEIF [NOT] var|* [NOT] {equ}} [ELSE [NOT] {equ}]
Note that the first line is optional and serves to specify the reformulation method. The second line is identical to the first formulation of the general syntax where the specification of the reformulation method is omitted. Some users find this alternative syntax clearer, since the specification of the reformulation method and the disjunction are separated.
In addition to the sequencing model [SEQUENCE] that was already mentioned, the GAMS EMP Library has two other models for disjunctive programming: the manufacturing problem [FOODEMP] and the job scheduling problem [MAKESPAN]