DisjunctiveProgramming.jl
Generalized Disjunctive Programming extension to JuMP
Installation
using Pkg
Pkg.add("DisjunctiveProgramming")
Disjunctions
After defining a JuMP model, disjunctions can be added to the model by using the @disjunction
macro. This macro is called by @disjunction(m, disjuncts...; kwargs...), where
disjuncts...` is a list of at least two expressions of the form:
- A valid expression accepted by JuMP.@constraint. Names for the constraints or containers of constraints cannot be passed (use option 2).
- A valid expression accepted by JuMP.@constraints (using `begin...end)
- A valid expression accepted by JuMP.@NLconstraint. Containers of constraints cannot be passed (use option 4). Naming of non-linear constraints is not currently supported.
- A valid expression accepted by JuMP.@NLconstraints (using `begin...end)
Tuple
of expressions accepted by options 1 and/or 3.
NOTES:
- Vectorized constraints (using
.
notation) are not currently supported. The current workarround is to first create the constraint with the@constraint
macro and then use theadd_disjunction!
, instead of the@disjunction
macro. Theadd_disjunction!
function receives the same arguments as the@disjunction
macro, with the exception that instead of creating the constraints in the disjunctions, references to previously created constraints are used for the disjuncts. - Any constraints that are of
EqualTo
type are split into two constraints (e.g.,f(x) == 0
->0 <= f(x) <= 0
). This is necessary only for the Big-M reformulation of equality constraints, but is currently applied regardless of the reformulation technique. - Any constraints that are of
Interval
type are split into two constraints (one for each bound). - It is assumed that the disjuncts belonging to a disjunction are proper disjunctions (mutually exclussive) and only one of them will be selected (
XOR
).
The valid key-word arguments for the @disjunction
macro are:
reformulation::Symbol
::big_m
for Big-M Reformulation,:hull
for Hull ReformulationM
: Big-M value used whenreformulation = :big_m
.ϵ
: epsilon tolerance for the perspective function proposed by Furman, et al. [2020]. Only used whenreformulation = :hull
.name::Symbol
: Name for the disjunction (also name for indicator variable used on that disjunction). If not passed (name = missing
), a symbolic name will be generated with the prefixdisj
. The mutual exclussion constraint on the binary indicator variables can be accessed withmodel[Symbol("XOR(disj_$name)")]
.
When a disjunction is defined using the @disjunction
macro, the disjunctions are reformulated to algebraic constraints via either Big-M or Hull reformulations. For the Hull reformulation, disaggregated variables are generated by adding the suffix _$name$i
to the original variables, where i
is the index of the disjunct in that disjunction. Bounding constraints are applied to the disaggregated variables and can be accessed with model[Symbol("$<original var>_$name$i_lb")]
and model[Symbol("$<original var>_$name$i_ub")]
for the lower bound and upper bound constraints, respectively. The aggregation constraint can be accessed with model[Symbol("$<original var>_aggregation")]
. For Big-M reformulations, the user may provide an M
object that represents the BigM value(s). The M
object can be a Number
that is applied to all constraints in the disjuncts, or a Vector
/Tuple
of values that are used for each of the disjuncts. For Hull reformulations, the user may provide an ϵ
value for the perspective function (default is ϵ = 1e-6
). The ϵ
object can be a Number
that is applied to all perspective functions, or a Vector
/Tuple
of values that are used for each of the disjuncts.
For empty disjuncts, use nothing
for their positional argument (e.g., @disjunction(m, x <= 1, nothing, reformulation = :big_m)
).
NOTE: :object_dict
is used in the extension dictionary to store the object dictionary of models using DisjunctiveProgramming.jl.
Logical Propositions
Boolean logic can be included in the model by using the @proposition
macro. This macro will take an expression that uses only binary variables from the model (typically a subset of the indicator variables used in the disjunctions) and one or more of the following Boolean operators:
∨
(or, typed with\vee + tab
)∧
(and, typed with\wedge + tab
)¬
(negation, typed with\neg + tab
)⇒
(implication, typed with\Rightarrow + tab
)⇔
(double implication or equivalence, typed with\Leftrightarrow + tab
) The logical proposition is then internally reformulated to an algebraic constraint that is added to the model. This constrait can be accessed withmodel[Symbol("<logical proposition expression>")]
.
Example
The example below is from the Northwestern University Process Optimization Open Textbook.
To perform the Big-M reformulation, :big_m
is passed to the reformulation
keyword argument. If nothing is passed to the keyword argument M
, tight Big-M values will be inferred from the variable bounds using IntervalArithmetic.jl. If x
is not bounded, Big-M values must be provided for either the whole system (e.g., M = 10
) or for each of the constraint arrays in the example (e.g., M = (10,10)
).
To perform the Hull reformulation, reformulation = :hull
. Variables must have bounds for the reformulation to work.
using JuMP
using DisjunctiveProgramming
m = Model()
@variable(m, -5 ≤ x ≤ 10)
@disjunction(
m,
0 ≤ x ≤ 3,
5 ≤ x ≤ 9,
reformulation=:big_m,
name=:y
)
@proposition(m, y[1] ∨ y[2]) #this is a redundant proposition
print(m)
┌ Warning: disj_y[1] : x in [0.0, 3.0] uses the `MOI.Interval` set. Each instance of the interval set has been split into two constraints, one for each bound.
┌ Warning: disj_y[2] : x in [5.0, 9.0] uses the `MOI.Interval` set. Each instance of the interval set has been split into two constraints, one for each bound.
Feasibility
Subject to
XOR(disj_y) : y[1] + y[2] == 1.0 <- XOR constraint
y[1] ∨ y[2] : y[1] + y[2] >= 1.0 <- reformulated logical proposition (name is the proposition)
disj_y[1][lb] : -x + 5 y[1] <= 5.0 <- left-side of constraint in 1st disjunct (name is assigned to disj_y[1][lb])
disj_y[1][ub] : x + 7 y[1] <= 10.0 <- right-side of constraint in 1st disjunct (name is assigned to disj_y[1][ub])
disj_y[2][lb] : -x + 10 y[2] <= 5.0 <- left-side of constraint in 2nd disjunct (name is assigned to disj_y[2][lb])
disj_y[2][ub] : x + y[2] <= 10.0 <- right-side of constraint in 2nd disjunct (name is assigned to disj_y[2][ub])
x >= -5.0 <- variable lower bound
x <= 10.0 <- variable upper bound
y[1] binary <- indicator variable (1st disjunct) is binary
y[2] binary <- indicator variable (2nd disjunct) is binary