Hector D. Perez

We present a Julia package (DisjunctiveProgramming.jl) that extends the functionality in JuMP to allow modeling problems via logical propositions and disjunctive constraints. Logical propositions are converted into algebraic expressions by converting the Boolean expressions to Conjunctive Normal Form and then to algebraic inequalities. The package allows the user to specify the technique to reformulate the disjunctions (Big-M or Convex-Hull reformulation) into mixed-integer constraints.

Modeling systems with discrete-continuous decisions is commonly done in algebraic form with mixed-integer programming models, which can be linear or nonlinear in the continuous variables. A more systematic approach to modeling such systems is to use Generalized Disjunctive Programming (GDP) (Chen & Grossmann, 2019; Grossmann & Trespalacios, 2013), which generalizes the Disjunctive Programming paradigm proposed by Balas (2018). GDP allows modeling systems from a logic-based level of abstraction that captures the fundamental rules governing such systems via algebraic constraints and logic. The models obtained via GDP can then be reformulated into the pure algebraic form best suited for the application of interest. The two main reformulation strategies are the Big-M reformulation (Nemhauser & Wolsey, 1999; Trespalacios & Grossmann, 2015) and the Convex-Hull reformulation (Lee & Grossmann, 2000), the latter of which yields tighter models than those typically used in standard mixed-integer programming (Grossmann & Lee, 2003).

DisjunctiveProgramming.jl supports reformulations for disjunctions containing linear, quadratic, and/or nonlinear constraints. When using the Big-M reformulation, the user can specify the Big-M value to be used, which can either be general to the disjunction or specific to each constraint expression in the disjunction. Alternately, the user can allow the package to determine the tightest Big-M value based on the variable bounds and constraint functions using interval arithmetic (IntervalArithmetic.jl [Sanders, et al., 2022]). When the Convex-Hull reformulation is selected, the perspective function approximation from Furman, et al. (2020) is used for nonlinear constraints with a specified ϵ tolerance value. This is done by relying on manipulation of symbolic expressions via Symbolics.jl (Gowda, et al., 2022).

Hector D. Perez

Talks:

Generalized Disjunctive Programming via DisjunctiveProgramming

Platinum sponsors

Gold sponsors

Silver sponsors

Media partners

Community partners

Fiscal Sponsor