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
View LP formulations for mixed-integer polynomial optimization problems