Logical Modeling and Generalized Disjunctive Programs

Prepared by: Prof. Alexander Dowling (adowling@nd.edu), Hailey Lynch (hlynch@nd.edu, 2023)

Introduction and Learning Objectives¶

Translate logical statements into binary constraints, model continuous alternatives with Pyomo.GDP, and compare Big-M and hull reformulations. The separator and parts examples develop the logic; the reactor example shows how bounds affect the reformulation. Full derivations and reproducible diagnostics supplement the lecture activities.

Import Modules¶

Motivating Example: Separation¶

The following excerpts are from Section 15.7 in Biegler, Grossmann, and Westerberg (1997).

Black circles mark the common binary vertices; squares mark the two extra aggregate vertices. The slice exposes the printed fractional witness.

If the absorber is selected or the membrane is selected, do not use cryogenic separation. Let $y_A,y_M,y_{CS}\in\{0,1\}$ indicate these selections. The OR is inclusive: selecting both absorber and membrane is permitted.

Translate each way the antecedent can be true first:

Adding the two rows gives the aggregate:

The pair implies the aggregate even for fractional variables. Conversely, for binary variables the aggregate enforces both rows: if $y_{CS}=1$, it forces $y_A=y_M=0$; if $y_{CS}=0$, it imposes no further restriction. Thus both formulations describe the same binary choices.

They differ on the unit cube $[0,1]^3$. At $(y_A,y_M,y_{CS})=(1,0,1/2)$, the aggregate holds with equality, but the first pairwise row reads $3/2\le1$ and fails. The pair therefore has a strictly tighter LP relaxation. The all-zero choice remains feasible: the implication does not require installing a separator.

Source: Biegler, Grossmann, and Westerberg (1997), §15.7, pp. 514–517, Example 15.4.

Logical Modeling¶

An atomic statement can represent a selection, such as “use the absorber.” Logical connectives combine these statements. Conjunctive normal form separates the resulting formula into disjunctive clauses, each of which becomes one linear inequality.

Symbolic Logic Notation¶

Vocabulary¶

An atom $P_i$ has no logical connective inside it. Associate the binary variable $y_i=1$ with a true atom and $y_i=0$ with a false atom. A literal is an atom $P_i$ or its negation $\neg P_i$; their numerical truth values are $y_i$ and $1-y_i$.

A disjunctive clause is an OR of finitely many literals. It is true when at least one literal is true. A conjunctive clause is an AND of literals; all must be true. Conjunctive normal form (CNF) is an AND of disjunctive clauses, not an arbitrary sequence of clauses.

For example,

is CNF and translates to

More generally, if a clause has positive-literal indices $J^+$ and negative-literal indices $J^-$, its row is

Each literal is 0 or 1, so this sum is at least one exactly when the clause is true. Retain binary domains: this equivalence concerns truth assignments, not fractional truth values.

Logical Statements and Conjunctive Normal Form¶

The following excerpts are from Section 15.7 in Biegler, Grossmann, and Westerberg (1997).

The three step procedure below shows how to convert logical statements into conjunctive normal form:

Step 1: Replace the implication by its equivalent disjunction. Example:

Step 2: Distribute the negation by applying DeMorgan’s Theorem. Examples:

Step 3: Recursively distribute the $\textbf{OR}$ over the $\textbf{AND}$ by using the following equivalence. Example:

Once in conjunctive normal form, translate each clause separately. The following dictionary also handles common direct relations.

A chain of ordinary two-input XORs is a parity test: for three true inputs, $(P_1\veebar P_2)\veebar P_3$ is true. It is not the exactly-one relation for three or more inputs. In GDP below, “exclusive selection” means exactly one selected indicator, as in Pyomo’s default disjunction semantics.

Source: BGW, Table 15.1, p. 515, and Eqs. (15.18)–(15.21), pp. 515–516. The exactly-one row above states the intended cardinality directly rather than interpreting a repeated XOR as cardinality.

Derived AND- and OR-implication rows¶

For $(P_1\land P_2)\Rightarrow P_3$, implication removal and De Morgan give $\neg P_1\lor\neg P_2\lor P_3$. Its single clause is $(1-y_1)+(1-y_2)+y_3\ge1$, or $y_1+y_2-y_3\le1$.

For $(P_1\lor P_2)\Rightarrow P_3$, the same first steps give $(\neg P_1\land\neg P_2)\lor P_3$. Distributing yields $(\neg P_1\lor P_3)\land(\neg P_2\lor P_3)$. The two rows are $(1-y_1)+y_3\ge1$ and $(1-y_2)+y_3\ge1$, equivalently $y_1\le y_3$ and $y_2\le y_3$. Adding them gives the weaker aggregate $y_1+y_2\le2y_3$ on fractional variables. The separator example substitutes the consequence $\neg P_{CS}$ and thus $y_3=1-y_{CS}$.

Example: Separation Sequence¶

Let’s revisit the example from the top of the notebook. Reformulate:

Step 1:

Step 2:

Step 3:

Now substituting:

$\neg P_A \rightarrow 1 - y_A, \quad \neg P_{CS} \rightarrow 1 - y_{CS}$

$\neg P_M \rightarrow 1 - y_M, \quad \neg P_{CS} \rightarrow 1 - y_{CS}$

We get:

$(1 - y_A) + (1 - y_{CS}) \geq 1$

$(1 - y_M) + (1 - y_{CS}) \geq 1$

Rearrange:

$y_A + y_{CS} \leq 1$

$y_M + y_{CS} \leq 1$

Example: Assembling Components¶

If (parts 1 and 2) or part 3 is used, then parts 4 or 5 must also be used. Here $P_i$ means “use part $i$,” and both ORs are inclusive.

Step 1: replace the implication. Apply $A\Rightarrow B\Leftrightarrow\neg A\lor B$ with the whole antecedent $A=((P_1\land P_2)\lor P_3)$ and $B=(P_4\lor P_5)$:

Step 2: move the negations inward. De Morgan’s laws first negate the outer OR and then the inner AND:

Step 3: distribute OR over AND. With $C=(P_4\lor P_5)$, distribute $(A\land B)\lor C$ into $(A\lor C)\land(B\lor C)$:

Translate the two clauses separately:

Equivalently,

The first row has $y_4$, not $y_3$, in its negative terms. For example, parts 1 and 2 without 4 or 5 must be rejected even when part 3 is absent. Source: BGW, Example 15.5, Eqs. (15.28)–(15.33), pp. 516–517.

Modeling Disjunctions¶

When modeling disjunctions, we will have to represent logical constraints that involve continuous variables.

General Notation¶

A generalized disjunctive program combines an objective, global algebraic constraints, disjunctions, and logical constraints. One common form is

Here $K$ indexes disjunctions and $D_k$ indexes the alternatives in disjunction $k$. The cost variable $c_k$ is assigned the given cost $\gamma_{ik}$ when term $i$ is selected. Each selected term enforces all its constraints together. Global rows hold regardless of the choice. The Boolean indicators $Y_{ik}$ are distinct from their algebraic binary representatives $y_{ik}$.

The displayed $\bigvee$ denotes inclusive OR. Our reactor and packing models additionally impose exactly one selected indicator per disjunction, which is Pyomo’s default. A false indicator removes that term’s requirements; it does not assert the negation of every inequality in the term. Thus more than one alternative’s algebraic inequalities can happen to hold even though only one indicator is selected.

Sources: Bynum et al. (2021), §11.1, Eqs. (11.13)–(11.17), p. 173; Pyomo’s modeling documentation. Pyomo exposes indicator_var as Boolean and binary_indicator_var as its associated binary. Use BooleanVar for logic and a Var(domain=Binary) for numeric binary algebra.

Example: The Reactor Problem¶

The following excerpts are from Section 15.8 in Biegler, Grossmann, and Westerberg (1997).

This modeling disjunctions example involves selecting between two reactors:

• If reactor 1 is selected, then pressure $P$ must be between 5 and 10 atmospheres.

• If reactor 2 is selected, then pressure $P$ must be between 20 and 30 atmospheres.

A bounded linear disjunction has term sets

Selecting a term enforces all of its rows. With exactly-one selection, eliminating the indicators leaves the union $\bigcup_{i\in D}S_i$. The same continuous union can also be represented by inclusive selection; overlapping terms can then have several true indicators.

Applied to the reactor problem:

The continuous feasible set is $[5,10]\cup[20,30]$ atm. We minimize $P$ to obtain a simple test objective. The analytic Big-M illustration below uses the declared common box $0\le P\le30$. The canonical Pyomo builder uses the stronger valid bound $5\le P\le30$. This difference affects automatic Big-M values and LP bounds; it does not change the original disjunctive feasible set.

Define Model in Pyomo with GDP¶

First we will define the model (including disjunctions) for the Reactor Problem in Pyomo.

Pyomo creates the Boolean and associated binary indicators when the disjuncts are declared, as the pre-transformation model printout shows. Reformulation then supplies the algebraic selection and constraint rows.

Transform and Solve with Big-M Relaxation¶

The following excerpts are from Section 15.8 in Biegler, Grossmann, and Westerberg (1997).

Use “Big-M” constraints to convert linear disjunctions into mixed-integer constraints to represent logic with continuous variables.

Big-M Relaxation Approach¶

For each row $a_{ij}^{\mathsf T}\mathbf{x}\le b_{ij}$ in term $i$, choose a nonnegative constant $M_{ij}$ large enough that the row imposes no restriction on the relevant off-state domain:

When $y_i=1$, the original row is enforced. When $y_i=0$, a valid $M_{ij}$ deactivates it. A conservative choice is

A common constant for all rows of a term can be the maximum of their row constants. Bounds or constraints known to hold in the other selected terms may yield smaller valid constants. State which off-state domain was used.

For the reactor, common constants give

Over the entire box $[0,30]$, maximum row violations are $20,5,0,20$, so $M_1=M_2=20$ deactivates every row over that box. These are the smallest common per-term constants for that deactivation policy. They are not the smallest constants that can preserve this particular union: when term 2 is off, term 1 supplies $P\ge5$, so $M_2=15$ already suffices.

A too-small constant may remove feasible points. For example, $M_1=10$ wrongly caps $P\le20$ when reactor 2 is selected, cutting out its valid pressures above 20. An unnecessarily large constant can weaken the LP relaxation and worsen scaling; it does not guarantee a particular iteration count. Neither problem size alone nor a blanket preference selects the better reformulation.

Source: BGW, §15.8, Eqs. (15.43)–(15.44), pp. 519–520. The two printing errors in (15.44) are corrected above: the fourth row starts with -20, and the selection row is $y_1+y_2=1$.

Big-M Implementation in Pyomo¶

First we will create and print the model.

Next, let’s transform using Big-M and print the model again.

Finally, we’ll solve the model and examine the solution.

Transform and Solve with Convex Hull Relaxation¶

The following excerpts are from Section 15.8 in Biegler, Grossmann, and Westerberg (1997).

The linear hull construction disaggregates each continuous variable into one scaled copy per term. The copies express a convex combination of feasible points, giving the convex hull of one bounded linear disjunction when the indicators are relaxed. This avoids choosing Big-M constants, at the cost of additional variables and rows.

Convex Hull Relaxation Approach¶

This analytic illustration uses the manual box-wide constants, not the automatic transformation of the builder with P bounded below by 5. The hatched difference is entirely at the lower boundary.

For the nonempty bounded linear term sets $S_i$ defined above, introduce $\mathbf{z}_i$ and impose

The bounds are signed: $\mathbf{L}$ need not be zero. For example, a valid selected value $x=-1$ would be lost if $0\le z_i$ were incorrectly imposed. At $y_i=0$, the scaled bounds force $\mathbf{z}_i=\mathbf{0}$. The row $\mathbf{A}_i\mathbf{z}_i\le\mathbf{0}$ alone need not do so; $-z_i\le0$ allows any nonnegative $z_i$.

Why the relaxed formulation gives the hull. Replace binary domains by $y_i\ge0$. For any positive weight $y_i$, divide by that weight to obtain $\mathbf{z}_i/y_i\in S_i$. The zero-weight copies vanish by the scaled bounds. Hence $\mathbf{x}=\sum_{i:y_i>0}y_i(\mathbf{z}_i/y_i)$ is a convex combination of points in the union. Conversely, combine any convex combination’s contributions from the same term, which is convex; assigning its total weight to $y_i$ and its weighted point to $\mathbf{z}_i$ satisfies every row. This proves both inclusions.

With binary weights, exactly one copy remains and equals $\mathbf{x}$, proving exactness for the original union. The bounded linear assumptions matter: nonlinear hull reformulation needs additional theory. Also, intersecting separately convexified disjunctions with global constraints need not give the convex hull of the entire GDP feasible set.

Reactor hull:

Here each term already bounds its copy on both sides, forcing an off-copy to zero. With $t=y_1$, $y_2=1-t$, the relaxed pressure interval is

Every value in this interval is a sum of points in $[5t,10t]$ and $[20(1-t),30(1-t)]$. Thus these projected bounds are necessary and sufficient. Minimizing $P$ gives 5.

For the manual $[0,30]$, $M_1=M_2=20$ model, the corresponding lower bound is $\max\{20t-15,20-20t\}$ and the upper bound is $30-20t$. The lower lines meet at $t=7/8$, $P=5/2$, whereas the hull’s lower bound there is $55/8$. At $t=1/2$, the respective intervals are $[10,20]$ and $[12.5,20]$. The upper boundaries agree; the lower boundaries explain the gap.

Sources: BGW, Eqs. (15.45)–(15.46), pp. 520–521; Balas (1985). Pyomo’s hull transformation requires finite lower and upper bounds on the variables appearing in disjuncts, including when automatic Big-M estimation could instead be replaced by supplied valid constants.

Convex Hull Implementation in Pyomo¶

We will repeat the procedure above but using Convex Hull now.

Discussion Questions¶

1. Why does CNF allow one linear row per clause?

2. Does the separator implication require selecting any separator?

3. What changes when an indicator is zero in Big-M? Does it assert the opposite inequality?

4. Is hull always strictly stronger than a valid Big-M formulation?

5. Under what conditions can the zero-term hull be simplified?

Check the model and its relaxations¶

The following calculation constructs fresh copies of the same builder used above, inspects Pyomo’s signed lower/upper M values, and solves their MIP and LP versions. It also checks a pressure cap of 19: the correct model must return 10, not 19. Fixing $P=15$ must be infeasible. Both checks detect an error that the minimum $P=5$ would miss.

For this builder’s box $[5,30]$, automatic row magnitudes are $20,0,0,15$. Substitution yields $20-15t\le P\le30-20t$, the same projection as the hull. A zero M means the bound is already globally implied. This example therefore illustrates equality, rather than a strict automatic-Big-M/hull gap. The manual $M=20$ illustration deliberately uses a different deactivation policy.

A test that rejects the toothless indexed model¶

The incorrect formulation below creates two independent exactly-one choices between overlapping half-lines. At $P=15$, each pair has a satisfied alternative. Even exclusive indicator selection cannot repair a wrongly grouped model: the unselected half-line is deactivated, rather than negated.

Reproduce the manual LP bounds¶

The following LPs use the same four reactor rows with explicit nonnegative row constants. Their continuous variables are $(P,t)$, with $y_1=t$ and $y_2=1-t$. Keeping the box and constant policy in the output makes the comparison reproducible.

For $[0,30]$, row-specific box maxima $(20,5,0,20)$ improve the LP bound from 2.5 to 4. Using the other branch to justify common constants $(M_1,M_2)=(20,15)$ gives the hull projection and bound 5. The canonical $[5,30]$ automatic constants $(20,0,0,15)$ also give 5. These choices are all valid for integer selections; their fractional behavior differs.

Formulation size and choice¶

For one disjunction with $d$ terms, $n$ continuous components, and $r_i$ inequalities in term $i$, count the algebraic core as follows. These are numbers of declared components, not a Jacobian rank or degrees-of-freedom calculation.

This table excludes domain bounds and scaled-copy bound rows. The explicit general hull also has $2nd$ scaled bound inequalities, although some can be redundant or subsumed by term rows. Global constraints add to both formulations. Pyomo can eliminate or reuse components, so compare the actual counts printed above under a stated convention rather than asserting they must equal the simplified table.

Tighter relaxations can improve lower bounds for minimization, while larger models cost more per node. Bounds, formulation structure, presolve, objective, and solver all matter. Compare actual relaxations and solve evidence; “Big-M for small problems, hull for large problems” is not a valid selection rule. This notebook reports optimality and mathematical bounds rather than treating an iteration count as a universal performance result.

Source: BGW, §15.8, p. 521. Nonlinear convex hull theory is treated by Grossmann & Lee (2003); it does not follow from the bounded linear proof above.

A two-term on/off simplification¶

Consider $[Y;\ \mathbf{A}\mathbf{x}\le\mathbf{b},\ \mathbf{L}\le\mathbf{x}\le\mathbf{U}]$ or $[\neg Y;\ \mathbf{x}=\mathbf{0}]$. The hull copies satisfy $\mathbf{x}=\mathbf{z}_{on}+\mathbf{z}_{off}$ and $\mathbf{z}_{off}=\mathbf{0}$, so eliminate both copies to obtain

At $y=1$ these are the original on-term rows; at $y=0$ the scaled bounds force zero. Relaxing $y$ represents convex combinations with the zero point by the same proof as above. The signed bounds are essential in general. Merely having two alternatives, without an explicit zero off-term, does not justify this elimination. Source: BGW, Eqs. (15.47)–(15.48), p. 521.

Cost assignment and logical scope¶

When exactly one indicator is selected, the disjunctive assignments $c=\gamma_i$ are equivalently expressed by $c=\sum_i\gamma_i y_i$. The equality takes the selected alternative’s cost. With several selected alternatives this expression instead adds their costs, so it must not be substituted into an inclusive-cost model without checking the intended semantics.

A separate complementarity warning concerns NLP solution methods. Biegler (2010), §11.3, p. 337, Eq. (11.18), gives $0\le x\perp(1-x)\ge0$: the product condition $x(1-x)=0$ and the nonnegativity bounds leave only $x=0$ or $x=1$. The book warns that this disconnected feasible set can cause convergence difficulties and advises against using such MPCC constructions for exclusive choices. This is a warning about formulation and solution behavior, not a proof that complementarity cannot represent those two points. Inclusive alternatives can sometimes be modeled successfully with MPCCs, but the construction and its assumptions are problem dependent. The present lecture uses explicit binary/GDP selection instead. See MINLP Algorithms for the later discrete-continuous algorithm material.

Further reading and applications¶

The CNF procedure here follows BGW §15.7, pp. 515–516. BGW attribute its formalization to Clocksin & Mellish (1981). Raman & Grossmann (1991) connect logical inference with MILP process-synthesis modeling; the 1993 paper by Raman & Grossmann (1993) develops symbolic integration of logic, including CNF/DNF representations, in mixed-integer methods. These historical notes explain the relationship between the logic and algebraic models; they do not add another conversion algorithm to learn.

Start with Balas (1985) for disjunctive relaxations, Raman & Grossmann (1994) for the logic-based GDP framework, and Grossmann & Ruiz (2012) for formulations and alternative MINLP algorithms. Grossmann (2002) and Trespalacios & Grossmann (2014) are broader reviews; Kronqvist et al. (2026) give a historical overview. Grossmann & Trespalacios (2013) explain systematic discrete-continuous modeling, and Chen & Grossmann (2019) discuss model variants and hierarchy. Perez & Grossmann (2024) extend GDP to hierarchical structures and first-order logic. These are extension readings, not prerequisites for the bounded linear hull proof.

Representative applications include power/desalination superstructures (Mussati et al. (2008)), thermally linked distillation (Caballero & Grossmann (2001)), production scheduling (Castro & Grossmann (2012)), maintenance scheduling (Castro et al. (2014)), solvent-mixture design (Jonuzaj et al. (2016)), modular process synthesis (Chen & Grossmann (2019)), and discrete-continuous energy-system model predictive control (Bhattacharya et al. (2021)).

Nonlinear solution methods are developed by Lee & Grossmann (2005); Türkay & Grossmann (1996) treat discontinuous investment costs and multiple size regions. The current Pyomo modeling ecosystem is described by Chen et al. (2022).

Textbooks and software¶

Biegler, Grossmann, and Westerberg (1997), Systematic Methods of Chemical Process Design, Chapter 15, §§15.7–15.8, pp. 514–521. Bynum et al. (2021), Pyomo—Optimization Modeling in Python, 3rd ed., Chapter 11, pp. 173–179, DOI. Biegler (2010), Nonlinear Programming: Concepts, Algorithms, and Applications, §11.3, p. 337 (complementarity warning). Postek et al. (2025), Hands-On Mathematical Optimization with Python, §3.4: Production model using disjunctions. Current Pyomo.GDP modeling and reformulation documentation supplement the book’s syntax; diagnostics above ran with Pyomo 6.10.1.