A Generalized Disjunctive Programming (GDP) extension to JuMP.
using Pkg
Pkg.add("DisjunctiveProgramming")
The theory behind the GDP modeling paradigm is described in the following references:
 JuliaCon 2022 Proceedings
 Perez and Grossmann (2023)
 Generalized Disjunctive Programming
 Disjunctive Inequalities
If you use DisjunctiveProgramming.jl in your research, we would greatly appreciate your citing it.
@article{Perez2023,
title = {DisjunctiveProgramming.jl: Generalized Disjunctive Programming Models and Algorithms for JuMP},
author = {Hector D. Perez and Shivank Joshi and Ignacio E. Grossmann},
journal = {Proceedings of the JuliaCon Conferences},
year = {2023},
publisher = {The Open Journal},
volume = {1},
number = {1},
pages = {117}
}
A generalized disjunctive programming (GDP) model is created using GDPModel()
, where the optimizer can be passed at model creation, along with other keyword arguments supported by JuMP Models.
using DisjunctiveProgramming
using HiGHS
model = GDPModel(HiGHS.Optimizer)
A GDPModel
is a JuMP Model
with a GDPData
field in the model's .ext
dictionary, which stores the following:
Logical Variables
: Indicator variables used for the various disjuncts involved in the model's disjunctions.Logical Constraints
: Selector (cardinality) or proposition (Boolean) constraints describing the relationships between the logical variables.Disjunct Constraints
: Constraints associated with each disjunct in the model.Disjunctions
: Disjunction constraints.Solution Method
: The reformulation technique or solution method. Currently supported methods include BigM, Hull, and Indicator Constraints.Reformulation Variables
: List of JuMP variables created when reformulating a GDP model into a MIP model.Reformulation Constraints
: List of constraints created when reformulating a GDP model into a MIP model.Ready to Optimize
: Flag indicating if the model can be optimized.
Additionally, the following mapping dictionaries are stored in GDPData
:
Indicator to Binary
: Maps the Logical variables to their respective reformulated Binary variables.Indicator to Constraints
: Maps the Logical variables to the disjunct constraints associated with them.
A GDP Model's GDPData
can be accessed via:
data = gdp_data(model)
Logical variables are JuMP AbstractVariable
s with two fields: fix_value
and start_value
. These can be optionally specified at variable creation. Logical variables are created with the @variable
JuMP macro by adding the tag Logical
as the last keyword argument. As with the regular @variable
macro, variables can be named and indexed:
@variable(model, Y[1:3], Logical)
Two types of logical constraints are supported:

Selector
or cardinality constraints: A subset of Logical variables is passed andExactly
,AtMost
, orAtLeast
n
of these is allowed to betrue
. These constraints are specified with thefunc
$\in$ set
notation inMathOptInterface
in a@constraint
JuMP macro. It is not assumed that disjunctions have anExactly(1)
constraint enforced on their disjuncts upon creation. This constraint must be explicitly specified.@constraint(model, [Y[1], Y[2]] in Exactly(1))

Proposition
or Boolean constraints: These describe the relationships between Logical variables via Boolean algebra. Supported logical operators include:
∨
orlogical_or
or
(OR, typed with\vee + tab
). 
∧
orlogical_and
or&&
(AND, typed with\wedge + tab
). 
¬
orlogical_not
(NOT, typed with\neg + tab
). 
⟹
orimplies
(Implication, typed with\Longrightarrow + tab
). 
⇔
oriff
or==
(double implication or equivalence, typed with\Leftrightarrow + tab
).
The
@constraint
JuMP macro is used to create these constraints using:=
:@constraint(model, Y[1] ⟹ Y[2] := true)
DisjunctiveProgramming.jl will automatically reformulate Logical propositions to integer programming constraints by converting these expressions to Conjunctive Normal Form, and then to algebraic constraints.
Variable splatting is supported in the logical operator functions
logical_or
,logical_and
,logical_not
,implies
, andiff
such that@constraint(model, logical_and(Y...) := true)
is equivalent to
@constraint(model, Y[1] ∧ Y[2] := true)

Disjunctions are built by first defining the constraints associated with each disjunct. This is done via the @constraint
JuMP macro with the extra Disjunct
tag specifying the Logical variable associated with the constraint:
@variable(model, x)
@constraint(model, x ≤ 100, Disjunct(Y[1]))
@constraint(model, x ≥ 200, Disjunct(Y[2]))
After all disjunct constraints associated with a disjunction have been defined, the disjunction is created with the @disjunction
macro, where the disjunction is defined as a Vector
of Logical variables associated with each disjunct:
@disjunction(model, [Y[1], Y[2]])
Disjunctions can be nested by passing an additional Disjunct
tag. The Logical variable in the Disjunct
tag specifies which disjunct, the nested disjunction belongs to:
@disjunction(model, Y[1:2], Disjunct(Y[3]))
Empty disjuncts are supported in GDP models. When used, the only constraints enforced on the model when the empty disjunct is selected are the global constraints and any other disjunction constraints defined.
For convenience, the Exactly(1)
selector constraint is added by default when adding a disjunction to the model. In other words, @disjunction(model, Y)
will add the disjunction and automatically add the logical constraint Y in Exactly(1)
. For nested disjunctions, the appropriate Exactly
constraint is added (e.g., @constraint(model, Y[1:2] in Exactly(Y[3]))
) to indicate that Exactly 1
logical variable in Y[1:2]
is set to true
when Y[3]
is true
, and both variables in Y[1:2]
are set to false
when Y[3]
is false
, meaning the parent disjunct is not selected. Adding the Exactly
selector constraint by default can be disabled by setting the keyword argument exactly1
to false
in the @disjunction
macro.
The following reformulation methods are currently supported:

BigM: The
BigM
struct is created with the following optional arguments:value
: BigM value to use. Default:1e9
. BigM values are currently global to the model. Constraint specific BigM values can be supported in future releases.tighten
: Boolean indicating if tightening the BigM value should be attempted (currently supported only for linear disjunct constraints when variable bounds have been set or specified in thevariable_bounds
field). Default:true
.

Hull: The
Hull
struct is created with the following optional arguments:value
:ϵ
value to use when reformulating quadratic or nonlinear constraints via the perspective function proposed by Furman, et al. [2020]. Default:1e6
.ϵ
values are currently global to the model. Constraint specific tolerances can be supported in future releases.

Indicator: This method reformulates each disjunct constraint into an indicator constraint with the Boolean reformulation counterpart of the Logical variable used to define the disjunct constraint.
Prior to v0.4.0
, the package did not leverage the JuMP extension capabilities and was not as robust. For these earlier releases, refer to Perez, Joshi, and Grossmann, 2023 and the following JuliaCon 2022 Talk.
The example below is from the Cornell University Computational Optimization Open Textbook.
using DisjunctiveProgramming
using HiGHS
m = GDPModel(HiGHS.Optimizer)
@variable(m, 0 ≤ x[1:2] ≤ 20)
@variable(m, Y[1:2], Logical)
@constraint(m, [i = 1:2], [2,5][i] ≤ x[i] ≤ [6,9][i], Disjunct(Y[1]))
@constraint(m, [i = 1:2], [8,10][i] ≤ x[i] ≤ [11,15][i], Disjunct(Y[2]))
@disjunction(m, Y)
@objective(m, Max, sum(x))
print(m)
# Max x[1] + x[2]
# Subject to
# x[1] ≥ 0
# x[2] ≥ 0
# x[1] ≤ 20
# x[2] ≤ 20
##
optimize!(m, gdp_method = BigM(100, false)) #specify M value and disable Mtightening
print(m)
# Max x[1] + x[2]
# Subject to
# Y[1] + Y[2] = 1
# x[1]  100 Y[1] ≥ 98
# x[2]  100 Y[1] ≥ 95
# x[1]  100 Y[2] ≥ 92
# x[2]  100 Y[2] ≥ 90
# x[1] + 100 Y[1] ≤ 106
# x[2] + 100 Y[1] ≤ 109
# x[1] + 100 Y[2] ≤ 111
# x[2] + 100 Y[2] ≤ 115
# x[1] ≥ 0
# x[2] ≥ 0
# x[1] ≤ 20
# x[2] ≤ 20
# Y[1] binary
# Y[2] binary
##
optimize!(m, gdp_method = Hull())
print(m)
# Max x[1] + x[2]
# Subject to
# x[2] + x[2]_Y[1] + x[2]_Y[2] = 0
# x[1] + x[1]_Y[1] + x[1]_Y[2] = 0
# Y[1] + Y[2] = 1
# 2 Y[1] + x[1]_Y[1] ≥ 0
# 5 Y[1] + x[2]_Y[1] ≥ 0
# 8 Y[2] + x[1]_Y[2] ≥ 0
# 10 Y[2] + x[2]_Y[2] ≥ 0
# x[2]_Y[1]_lower_bound : x[2]_Y[1] ≤ 0
# x[2]_Y[1]_upper_bound : 20 Y[1] + x[2]_Y[1] ≤ 0
# x[1]_Y[1]_lower_bound : x[1]_Y[1] ≤ 0
# x[1]_Y[1]_upper_bound : 20 Y[1] + x[1]_Y[1] ≤ 0
# x[2]_Y[2]_lower_bound : x[2]_Y[2] ≤ 0
# x[2]_Y[2]_upper_bound : 20 Y[2] + x[2]_Y[2] ≤ 0
# x[1]_Y[2]_lower_bound : x[1]_Y[2] ≤ 0
# x[1]_Y[2]_upper_bound : 20 Y[2] + x[1]_Y[2] ≤ 0
# 6 Y[1] + x[1]_Y[1] ≤ 0
# 9 Y[1] + x[2]_Y[1] ≤ 0
# 11 Y[2] + x[1]_Y[2] ≤ 0
# 15 Y[2] + x[2]_Y[2] ≤ 0
# x[1] ≥ 0
# x[2] ≥ 0
# x[2]_Y[1] ≥ 0
# x[1]_Y[1] ≥ 0
# x[2]_Y[2] ≥ 0
# x[1]_Y[2] ≥ 0
# x[1] ≤ 20
# x[2] ≤ 20
# x[2]_Y[1] ≤ 20
# x[1]_Y[1] ≤ 20
# x[2]_Y[2] ≤ 20
# x[1]_Y[2] ≤ 20
# Y[1] binary
# Y[2] binary
DisjunctiveProgramming
is being actively developed and suggestions or other forms of contribution are encouraged.
There are many ways to contribute to this package. Feel free to create an issue to address questions or provide feedback.