Optimization Online


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

Dimitri Papageorgiou (dimitri.j.papageorgiou***at***exxonmobil.com)
Francisco Trespalacios (francisco.trespalacios***at***exxonmobil.com)

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 note, using properties of a 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

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Citation: To appear in EURO Journal on Computational Optimization (EJCO). [Original citation:Technical Report, Corporate Strategic Research, ExxonMobil Research and Engineering, 9/2016]

Download: [PDF]

Entry Submitted: 09/13/2016
Entry Accepted: 09/13/2016
Entry Last Modified: 06/22/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society