Pseudo basic steps: bound improvement guarantees from Lagrangian decomposition in convex disjunctive programming

Dimitri J. Papageorgiou () and Francisco Trespalacios ()
Additional contact information
Dimitri J. Papageorgiou: ExxonMobil Research and Engineering Company
Francisco Trespalacios: ExxonMobil Research and Engineering Company

EURO Journal on Computational Optimization, 2018, vol. 6, issue 1, No 3, 55-83

Abstract: Abstract An elementary, but fundamental, operation in disjunctive programming is a basic step, which is the intersection of two disjunctions to form a new disjunction. Basic steps bring a disjunctive set in regular form closer to its disjunctive normal form and, in turn, produce relaxations that are at least as tight. An open question is: What are guaranteed bounds on the improvement from a basic step? In this paper, using properties of a convex disjunctive program’s hull reformulation and multipliers from Lagrangian decomposition, we introduce an operation called a pseudo basic step and use it to provide provable bounds on this improvement along with techniques to exploit this information when solving a disjunctive program as a convex MINLP. Numerical examples illustrate the practical benefits of these bounds. In particular, on a set of K-means clustering instances, we make significant bound improvements relative to state-of-the-art commercial mixed-integer programming solvers.

Keywords: Basic step; Disjunctive programming; K-means clustering; Lagrangian decomposition; Mixed-integer conic quadratic optimization; 90C11; Mixed; integer; programming (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s13675-017-0088-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:eurjco:v:6:y:2018:i:1:d:10.1007_s13675-017-0088-0

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/13675

DOI: 10.1007/s13675-017-0088-0

Access Statistics for this article

EURO Journal on Computational Optimization is currently edited by Martine C. Labbé

More articles in EURO Journal on Computational Optimization from Springer, EURO - The Association of European Operational Research Societies
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().