# DisjunctiveProgramming.jl

Generalized Disjunctive Programming (GDP) extension to JuMP, based on the GDP modeling paradigm described in Perez and Grossmann, 2023.

## Installation

```
using Pkg
Pkg.add("DisjunctiveProgramming")
```

## Model

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 Big-M, 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

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)`

## Logical Constraints

Two types of logical constraints are supported:

`Selector`

or cardinality constraints: A subset of Logical variables is passed and`Exactly`

,`AtMost`

, or`AtLeast`

`n`

of these is allowed to be`true`

. These constraints are specified with the`func`

$\in$`set`

notation in`MathOptInterface`

in a`@constraint`

JuMP macro. It is not assumed that disjunctions have an`Exactly(1)`

constraint enforced on their disjuncts upon creation. This constraint must be explicitly specified.`julia @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:`∨`

or`logical_or`

or`||`

(OR, typed with`\vee + tab`

).`∧`

or`logical_and`

or`&&`

(AND, typed with`\wedge + tab`

).`¬`

or`logical_not`

(NOT, typed with`\neg + tab`

).`⟹`

of`implies`

(Implication, typed with`\Longrightarrow + tab`

).`⇔`

or`iff`

or`==`

(double implication or equivalence, typed with`\Leftrightarrow + tab`

).

The `@constraint`

JuMP macro is used to create these constraints with `:=`

:

`@constraint(model, Y[1] ⟹ Y[2] := true)`

*Note*: The parenthesis in the example above around the implication clause are only required when the parent logical operator is `⟹`

or `⇔`

to avoid parsing errors.

Logical propositions can be reformulated to IP constraints by automatic reformulation to Conjunctive Normal Form.

## Disjunctions

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.

## MIP Reformulations

The following reformulation methods are currently supported:

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. This is invoked with

`Indicator`

.

## Release Notes

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.

## Example

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 M-tightening
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
```

## Contributing

`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.