kth.sePublications KTH
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
P-split formulations: a class of intermediate formulations between big-M and convex hull for disjunctive constraints
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Numerical Analysis, Optimization and Systems Theory.ORCID iD: 0000-0003-0299-5745
Department of Computing, Imperial College London, London, UK.
Department of Computing, Imperial College London, London, UK.
2025 (English)In: Mathematical programming, ISSN 0025-5610, E-ISSN 1436-4646Article in journal (Refereed) Epub ahead of print
Abstract [en]

We develop a class of mixed-integer formulations for disjunctive constraints intermediate to the big-M and convex hull formulations in terms of relaxation strength. The main idea is to capture the best of both the big-M and convex hull formulations: a computationally light formulation with a tight relaxation. The “P-split” formulations are based on a lifted transformation that splits convex additively separable constraints into P partitions and forms the convex hull of the linearized and partitioned disjunction. The “P-split” formulations are derived for disjunctive constraints with convex constraints within each disjunct, and we generalize the results for the case with nonconvex constraints within the disjuncts. We analyze the continuous relaxation of the P-split formulations and show that, under certain assumptions, the formulations form a hierarchy starting from a big-M equivalent and converging to the convex hull. We computationally compare the P-split formulations against big-M and convex hull formulations on 344 test instances. The test problems include K-means clustering, semi-supervised clustering, P_ball problems, and optimization over trained ReLU neural networks. The computational results show promising potential of the P-split formulations. For many of the test problems, P-split formulations are solved with a similar number of explored nodes as the convex hull formulation, while reducing the solution time by an order of magnitude and outperforming big-M both in time and number of explored nodes.

Place, publisher, year, edition, pages
Springer Nature , 2025.
Keywords [en]
Convex MINLP, Disjunctive constraints, Disjunctive programming, Mixed-integer formulations, Mixed-integer programming
National Category
Control Engineering Other Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
URN: urn:nbn:se:kth:diva-366570DOI: 10.1007/s10107-025-02232-1ISI: 001504379400001Scopus ID: 2-s2.0-105007912576OAI: oai:DiVA.org:kth-366570DiVA, id: diva2:1983284
Note

QC 20260120

Available from: 2025-07-10 Created: 2025-07-10 Last updated: 2026-01-20Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Kronqvist, Jan

Search in DiVA

By author/editor
Kronqvist, Jan
By organisation
Numerical Analysis, Optimization and Systems Theory
In the same journal
Mathematical programming
Control EngineeringOther Electrical Engineering, Electronic Engineering, Information Engineering

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 55 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf