PaperlayerView exact revision on arXiv

Source-linked AI summary

Solution Methods for Infinite-Dimensional Generalized Disjunctive Programming

Daniel Nguyen, Joshua L. Pulsipher

arXiv:2608.27707v1math.OCeess.SY

TL;DR

InfiniteGDP previously lacked generalized intermediate GDP solution methods beyond big-M and hull. The paper extends MBM, P-split, CP, and LOA to infinite-dimensional optimization, introduces MBM-GP, and benchmarks them in dynamic and stochastic case studies. The results show intermediate methods can outperform the endpoints, while MBM-GP preserves MBM tightness with lower reformulation cost.

  • Problem

    InfiniteGDP had generalized only the big-M and hull endpoints, leaving intermediate methods unavailable for infinite-dimensional mixed discrete-continuous optimization.

  • Method

    The paper generalizes MBM, P-split, CP, and LOA, introduces MBM-GP to learn big-M functions from a subset of support subproblems, and implements the methods in Julia.

  • Results

    Across three case studies, generalized methods outperform big-M and hull in challenging settings; on F1, MBM solves in 102 s and MBM-GP in 194 s with an 8-fold reduced pre-solve time.

  • Takeaways & Limitations

    MBM-GP retains multiple big-M tightness at a fraction of its reformulation cost, expanding the practical InfiniteGDP method library.

  • Takeaways & Limitations

    CP is sound only for convex GDP, while LOA has no global guarantee under mild nonconvexity and degrades sharply outside its targeted convex regime.

Abstract

from arXiv · show

Generalized disjunctive programming (GDP) expresses mixed discrete-continuous decisions through Boolean indicators and disjunctions, and can be systematically solved via a library of methods proposed in the literature. The recent InfiniteGDP abstraction lifts this modeling layer to continuous domains such as time, space, and uncertainty, but only the big-M and hull reformulations, the two endpoints of the relaxation spectrum, have been generalized to the infinite setting. This work closes this gap by generalizing four other GDP solution methods to infinite-dimensional optimization: the multiple big-M reformulation, P-split reformulation, cutting plane reformulation, and the logic-based outer approximation algorithm. It further proposes MBM-GP, a novel Gaussian-process variant of multiple big-M that learns the big-M function over the infinite domain from a small subset of the subproblem solves. Moreover, these approaches are implemented in the Julia package InfiniteDisjunctiveProgramming.jl. The methods are benchmarked on case studies arising in dynamic and stochastic optimization. The results demonstrate how the generalized solution methods can outperform big-M and hull, with MBM-GP retaining the tightness of multiple big-M at a fraction of its reformulation cost.

1 Introduction

InfiniteGDP extends InfiniteOpt modeling to mixed discrete-continuous decisions, but previously generalized only the big-M and hull endpoints. This work fills the intermediate-method gap and adds MBM-GP, with implementations and benchmarks across dynamic and stochastic case studies.

  • InfiniteOpt supports variables, objectives, and constraints indexed over continuous domains including time, space, and uncertainty.
  • Existing InfiniteOpt transcription automates discretization but leaves domain-varying discrete decisions for modelers to encode as mixed-integer programs.
  • GDP represents discrete structure with Boolean indicators, disjunction-specific constraints, and logical propositions, while automatic reformulations convert models into MIPs.
  • InfiniteGDP generalized big-M and hull, but intermediate methods including MBM, P-split, and CP remained unavailable in the infinite setting.
  • The paper generalizes MBM, P-split, CP, and LOA, and introduces MBM-GP, which learns big-M functions from a small subset of per-support subproblems.
  • The methods are implemented and benchmarked through three case studies, with the paper organized around background, methods, benchmarks, and conclusions.

2 Background and Notation

The background defines GDP and InfiniteOpt abstractions, then positions big-M, hull, P-split, MBM, CP, and LOA by their reformulation structure, relaxation tightness, cost, and algorithmic requirements.

  • GDP and InfiniteGDP: GDP models discrete structure with Boolean indicators and disjunctions whose active constraints are selected by logical propositions.
  • Solution strategies: A reformulation maps GDP to one finite MIP, whereas LOA solves the original problem through a sequence of subproblems without forming one equivalent program.
  • Big-M: Big-M produces a structure-preserving linear MIP when disjunct constraints are linear, but loose constants yield a weak continuous relaxation.
  • Hull: Hull disaggregates decision variables and provides the tightest convex relaxation per disjunction, at the cost of duplicated variables and typically nonlinear perspective constraints.
  • P-split: P-split partitions disjunct expressions into P groups, interpolating between big-M at P = 1 and hull at P = n_z while trading model size for tightness.
  • Multiple big-M: MBM uses pairwise M constants computed from subproblems, producing a linear relaxation strictly between big-M and hull when the disjuncts are linear.
  • Cutting planes: CP alternates a relaxed big-M master with a hull-based separation problem, adding cuts toward hull tightness without variable doubling, but requires convexity for soundness.
  • Logic-based outer approximation: LOA alternates fixed-assignment NLP subproblems with an outer-approximation master, using convergent upper and lower bounds for convex GDPs.

3 Solution Methods for InfiniteGDPs

This section generalizes GDP solution methods to InfiniteGDP through lift-then-transcribe reformulations and iterative algorithms, including MBM-GP for reducing multiple-big-M construction cost. The methods span different relaxation and reformulation-cost trade-offs, with specialized cutting-plane behavior when support points are uncoupled.

  • Overview: The section generalizes MBM, P-split, cutting planes, and LOA to InfiniteGDP, while MBM-GP avoids solving every multiple-big-M subproblem.Each method recovers its finite form when no infinite parameters are present; reformulations lift finite rules to symbolic infinite models before transcription.
  • Multiple Big-M: Multiple big-M replaces scalar parameters with continuous per-pair functions Mii1(d), obtained from support-wise subproblem solves when constraints vary over the infinite domain.If a subproblem is independent of the infinite parameter, one solve produces a scalar instead.
  • Gaussian Process Multiple Big-M: MBM-GP solves only a subset of supports, fits a Gaussian process, and uses its inflated upper bound to preserve a valid big-M function at unsolved supports.A larger confidence factor reduces undershoot risk but adds slack; adaptive sampling targets supports with high predictive variance.
  • Gaussian Process Multiple Big-M: 40 supports with 10 exact solves illustrate MBM-GP; the GP upper bound lies above pointwise M values throughout, while case studies solve roughly a quarter of supports with κ = 2.5.The case-study configuration uses adaptive support selection and reports objectives comparable to grid MBM at a small fraction of reformulation cost.
  • Cutting Planes: Without cross-support coupling, each support projection supplies a valid pointwise cut, yielding a strictly stronger family than the summed cut; coupling requires the summed fallback.The pointwise family contributes |K| cuts per separation solve and has no finite-GDP counterpart.
  • Method Selection: Method choice balances reformulation time against solver time: MBM tightens big-M at greater up-front cost, whereas big-M is cheapest but has the loosest relaxation.MBM’s computed functions can be reused across repeated solves, amortizing reformulation cost while retaining tighter relaxations.
  • Cutting Planes: Cutting planes recover hull-like tightness without variable doubling by alternating a big-M master with a hull-based separation problem, but validity requires convex disjunct constraints.The method can generate cuts that remove feasible points on nonconvex models, and finite termination at the optimum is not guaranteed.

4 Case studies

The paper benchmarks generalized InfiniteGDP solution methods on nonconvex dynamic and convex stochastic case studies. MBM methods perform especially well on nonconvex problems, while all methods reach the same optimum on the convex powergrid study.

  • Case studies: Three case studies cover nonconvex F1 lap-time control, nonconvex biodiesel scheduling, and convex IEEE 14-bus capacity design.The problems use N = 100, 300, and 200 support points, respectively, with a 5% relative MIP gap target.
  • 4.1 Minimum lap-time control: The F1 problem uses spatially varying powertrain mode selection and three bilinear couplings, making it a nonconvex MIQCP.Modes may switch at individual support points along the 5.807 km Suzuka circuit.
  • 4.1 Minimum lap-time control: Only MBM and MBM-GP solve the F1 instance within 1200 s; MBM reaches 0.95 at ≈102 s, while MBM-GP follows at ≈194 s after a 2.7 s build.Big-M and hull have no incumbent, P-split ends with a 16.9% gap, and CP produces no valid incumbent.
  • 4.2 Biodiesel scheduling: On biodiesel scheduling, all five reformulations meet the gap target; MBM takes 17 s, versus 100 s for big-M and 496 s for hull.The temperature–COP coupling creates nonconvexity and a power amplification factor of ≈2.7 across the reboiler-temperature range.
  • 4.2 Biodiesel scheduling: MBM-GP matches MBM’s biodiesel objective of ´213397 while reducing reformulation time from 122 to 6.3 s, a 19× reduction.The Gaussian-process fit preserves most of MBM’s tightness while avoiding per-support computation of every M value.
  • 4.2 Biodiesel scheduling: CP is sound only for convex GDP; on the nonconvex biodiesel problem, its generated cuts violated a verified optimum and the method returned no recoverable solution at N = 300.The reported cut violations were ´3.1×107, ´8.6×104, and ´6.2×104.
  • 4.3 IEEE 14-bus capacity design: On the convex IEEE 14-bus study, all methods, including MBM-GP, CP, and LOA, reach the same global optimum of 36.71.P-split is slowest because its lifted transcription carries 8× big-M’s rows.
  • 4.4 Summary: Across the studies, MBM methods solve fastest, while big-M suffers from loose relaxations, hull from model size, and P-split from oversized lifts.LOA performs reliably in the convex regime but degrades sharply on the nonconvex F1 and biodiesel problems.

5 Conclusions and Future Work

The work extends four GDP solution methods to infinite-dimensional optimization, adds MBM-GP, and implements the approaches for benchmarking. The results indicate that InfiniteGDP MBM can provide competitive solution times through a tight continuous relaxation.

  • Four GDP methods are generalized to infinite-dimensional optimization: multiple big-M, P-split, cutting plane, and logic-based outer approximation.
  • These reformulations fill the relaxation spectrum between the previously extended big-M and hull endpoints.
  • Logic-based outer approximation provides an iterative alternative that never forms a single mixed-integer program.
  • MBM-GP introduces a Gaussian-process variant of multiple big-M for learning the big-M function over the infinite domain from a subset of subproblem solves.
  • The methods are implemented in DisjunctiveProgramming.jl, InfiniteDisjunctiveProgramming.jl, and DisjunctiveAlgorithms.jl, and benchmark studies report competitive InfiniteGDP MBM solution times.
Loading 2608.27707v1…