Optimization Online


LP formulations for mixed-integer polynomial optimization problems

Daniel Bienstock (dano***at***columbia.edu)
Gonzalo Munoz (gonzalo***at***ieor.columbia.edu)

Abstract: We present polynomial-time algorithms for constrained optimization problems overwhere the intersection graph of the constraint set has bounded tree-width. In the case of binary variables we obtain exact, polynomial-size linear programming formulations for the problem. In the mixed-integer case with bounded variables we obtain polynomial-size linear programming representations that attain guaranteed optimality and feasibility bounds. As a consequence, we obtain approximation algorithms based on linear programming, with guaranteed bounds, for the AC-OPF problem on graphs with bounded tree-width.

Keywords: mixed-integer nonlinear programming

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

Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Citation: Columbia University, 2014

Download: [PDF]

Entry Submitted: 01/19/2015
Entry Accepted: 01/19/2015
Entry Last Modified: 03/20/2015

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