LP formulations for mixed-integer polynomial optimization problems

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.

Citation

Columbia University, 2014

Article

Download

View LP formulations for mixed-integer polynomial optimization problems