LP formulations for mixed-integer polynomial
optimization problems
Daniel Bienstock and Gonzalo Muñoz, Columbia University

An application: the Optimal Power Flow problem (ACOPF)
Input: an undirected graph G.
• For every vertex i, two variables: ei and fi• For every edge {k, m}, four (specific) quadratics:
PHk,m(ek , fk , em , fm ),P
Hm,k(ek , fk , em , fm ),QHk,m(ek , fk , em , fm )ek fkem fmkm

Q
Hm,k(ek , fk , em , fm )minX

Fk s.t.

XPHk,m(ek , fk , em, fm){k,m}∈δ(k)

kLPk

≤

XPHk,m(ek , fk , em, fm) ≤ UkP∀k{k,m}∈δ(k)LQk≤

XQ(ek , fk , em, fm) ≤ UkQ ∀kHk,m{k,m}∈δ(k)VkL ≤ k(ek , fk )k ≤ VkU∀k.

Function Fk in the objective: convex quadraticComplexity
Theorem (2011) Lavaei and Low: OPF is (weakly) NP-hard on trees.
Theorem (2014) van Hentenryck et al: OPF is NP-hard on trees.
Theorem (2007) B. and Verma (2009): OPF is strongly NP-hard on general graphs.

Complexity
Theorem (2011) Lavaei and Low: OPF is (weakly) NP-hard on trees.
Theorem (2014) van Hentenryck et al: OPF is NP-hard on trees.
Theorem (2007) B. and Verma (2009): OPF is strongly NP-hard on general graphs.
Recent insight: use the SDP relaxation (Lavaei and Low, 2009 + manyothers)
minX

Fk s.t.

XPHk,m(ek , fk , em, fm){k,m}∈δ(k)kLPk

≤XPHk,m(ek , fk , em, fm) ≤ UkP∀k{k,m}∈δ(k)LQk≤

XQHk,m(ek , fk , em, fm) ≤ UkQ ∀k{k,m}∈δ(k)VkL ≤ k(ek , fk )k ≤ VkU∀k.

Complexity
Theorem (2011) Lavaei and Low: OPF is (weakly) NP-hard on trees.
Theorem (2014) van Hentenryck et al: OPF is NP-hard on trees.
Theorem (2007) B. and Verma (2009): OPF is strongly NP-hard on general graphs.
Recent insight: use the SDP relaxation (Lavaei and Low, 2009 + manyothers)
Reformulation of ACOPF:
min F • W
s.t. Ai • W ≤ bi i = 1, 2, . . .
W  0, W of rank 1.

Complexity
Theorem (2011) Lavaei and Low: OPF is (weakly) NP-hard on trees.
Theorem (2014) van Hentenryck et al: OPF is NP-hard on trees.
Theorem (2007) B. and Verma (2009): OPF is strongly NP-hard on general graphs.
Recent insight: use the SDP relaxation (Lavaei and Low, 2009 + manyothers)
SDP Relaxation of OPF:
min F • W
s.t. Ai • W ≤ bi i = 1, 2, . . .
W  0.

Complexity
Theorem (2011) Lavaei and Low: OPF is (weakly) NP-hard on trees.
Theorem (2014) van Hentenryck et al: OPF is NP-hard on trees.
Theorem (2007) B. and Verma (2009): OPF is strongly NP-hard on general graphs.
Recent insight: use the SDP relaxation (Lavaei and Low, 2009 + manyothers)
SDP Relaxation of OPF:min F • Ws.t. Ai • W ≤ bi i = 1, 2, . . .
W  0.
Fact: The SDP relaxation is often good! (“near” rank 1 solution).

But: the SDP relaxation is always slow on large graphs• Real-life grids → > 104 vertices• SDP relaxation of OPF does not terminate
But...

But: the SDP relaxation is always slow on large graphs• Real-life grids → > 104 vertices• SDP relaxation of OPF does not terminate
But...
Fact? Real-life grids have small tree-width
Definition 1: A graph has treewidth ≤ w if it has a chordal supergraphwith clique number ≤ w + 1

But: the SDP relaxation is always slow on large graphs• Real-life grids → > 104 vertices• SDP relaxation of OPF does not terminate
But...
Fact? Real-life grids have small tree-width
Definition 2: A graph has treewidth ≤ w if it is a subgraph of anintersection graph of subtrees of a tree, with ≤ w + 1 subtrees overlappingat any vertex

But: the SDP relaxation is always slow on large graphs• Real-life grids → > 104 vertices• SDP relaxation of OPF does not terminate
But...
Fact? Real-life grids have small tree-width
Definition 2: A graph has treewidth ≤ w if it is a subgraph of an intersection graph of subtrees of a tree, with ≤ w + 1 subtrees overlapping atany vertex(Seymour and Robertson, late 1980s)

Tree-width
Let G be an undirected graph with vertices V (G) and edges E(G).
A tree-decomposition of G is a pair (T, Q) where:• T is a tree. Not a subtree of G, just a tree
• For each vertex t of T , Qt is a subset of V (G). These subsets satisfy
the two properties:(1) For each vertex v of G, the set {t ∈ V (T ) : v ∈ Qt} is a subtreeof T , denoted Tv .
(2) For each edge {u, v} of G, the two subtrees Tu and Tv intersect.
• The width of (T, Q) is maxt∈T |Qt| − 1.
564
132→ two subtrees Tu, Tv may overlap even if {u, v} is not an edge of G

Tree-width
Let G be an undirected graph with vertices V (G) and edges E(G).
A tree-decomposition of G is a pair (T, Q) where:• T is a tree. Not a subtree of G, just a tree
• For each vertex t of T , Qt is a subset of V (G). These subsets satisfy
the two properties:(1) For each vertex v of G, the set {t ∈ V (T ) : v ∈ Qt} is a subtreeof T , denoted Tv .
(2) For each edge {u, v} of G, the two subtrees Tu and Tv intersect.
• The width of (T, Q) is maxt∈T |Qt| − 1.
5width = 3612 344 51 3514 5width = 213 56 56132213

But: the SDP relaxation is always slow on large graphs• Real-life grids → > 104 vertices• SDP relaxation of OPF does not terminate
But...
Fact? Real-life grids have small tree-width
Matrix-completion Theorem
gives fast SDP implementations:
Real-life grids with ≈ 3 × 103 vertices: → 20 minutes runtime

But: the SDP relaxation is always slow on large graphs• Real-life grids → > 104 vertices• SDP relaxation of OPF does not terminate
But...
Fact? Real-life grids have small tree-width
Matrix-completion Theorem
gives fast SDP implementations:
Real-life grids with ≈ 3 × 103 vertices: → 20 minutes runtime→ Perhaps low tree-width yields direct algorithms for ACOPF itself?
That is to say, not for a relaxation?

Much previous work using structured sparsity• Bienstock and Özbay• Wainwright and Jordan• Grimm, Netzer, Schweighofer• Laurent• Lasserre et al• Waki, Kim, Kojima, Muramatsu
older work ...
• Lauritzen (1996): tree-junction theorem• Bertele and Brioschi (1972): nonserial dynamic programming• Bounded tree-width in combinatorial optimization (too many authors)• Fulkerson and Gross (1965): matrices with consecutive ones

ACOPF, again
Input: an undirected graph G.
• For every vertex i, two variables: ei and fi• For every edge {k, m}, four (specific) quadratics:
PHk,m(ek , fk , em , fm ),PHm,k(ek , fk , em , fm ),QHk,m(ek , fk , em , fm )ek fkem fmkm

QHm,k(ek , fk , em , fm )

minXFk s.t.

XPHk,m(ek , fk , em, fm){k,m}∈δ(k)

kLPk



≤

X

P
Hk,m
(ek , fk , em, fm) ≤ UkP∀k{k,m}∈δ(k)

LQk

≤

XQ
(ek , fk , em, fm) ≤ UkQ ∀kHk,m{k,m}∈δ(k)VkL ≤ k(ek , fk )k ≤ VkU∀k.

Function Fk in the objective: convex quadratic

ACOPF, again
Input: an undirected graph G.
• For every vertex i, two variables: ei and fi• For every edge {k, m}, four (specific) quadratics:
PHk,m(ek , fk , em , fm ),P
Hm,k(ek , fk , em , fm ),

minX

Q
Hk,m
(ek , fk , em , fm )ek fkem fmkm

Q
Hm,k(ek , fk , em , fm )

wk

ks.t.

LPk

≤

XP
Hk,m
(ek , fk , em, fm) ≤ UkP∀k{k,m}∈δ(k)LQk≤

XQHk,m(ek , fk , em, fm) ≤ UkQ ∀k{k,m}∈δ(k)UVkL ≤ k(ek , fk )k ≤ Vkwk = F k X{k,m}∈δ(k)∀kPHk,m(ek , fk , em, fm)∀k

Graphical QCQP
Input: an undirected graph G.
• For every vertex k, a set of variables: {xj : j ∈ I(k)}• For every edge e = {k, m}, a quadraticHe(x)=He ( {xj : j ∈ I(k) ∪ I(m)}) .

• For now, the sets I(k) are disjoint
X X
minck,j xjks.t.

j∈I(k)

XHe(x) ≤ bk ∀ke∈δ(k)0 ≤ xj ≤ 1,∀j

→ Easy to solve if graph has small tree-width?

Subset-sum problem
Input: positive integers p1, p2, . . . , pn.
Problem: find a solution to:
nX

n

1X
pj xj =pj
2 j=1
j=1

xj ∈ {0, 1},(weakly) NP-hard (well...)∀j

Subset-sum problem
Input: positive integers p1, p2, . . . , pn.
Problem: find a solution to:
n
X

n

1X
pj xj =pj
2 j=1
j=1

xj (1 − xj ) = 0,∀j(weakly) NP-hard (well...)This is a graphical QCQP on a star – so treewidth 1.
(Perhaps) approximate solutions?
 Pn1{0, 1} solutions with error 2 j=1 pj  in time polynomial in −1?

Graphical QCQP
Input: an undirected graph G.
• For every vertex k, a set of variables: {xj : j ∈ I(k)}• For every edge e = {k, m}, a quadraticHe(x)=He ( {xj : j ∈ I(k) ∪ I(m)}) .

• For now, the sets I(k) are disjoint
min cT x
Xs.t.
He(x) ≤ bk ∀ke∈δ(k)0 ≤ xj ≤ 1,∀j

Graphical PCLP
Input: an undirected graph G.
• For every vertex k, a set of variables: {xj : j ∈ I(k)}• For every edge e = {k, m}, a polynomialPe(x)=Pe ( {xj : j ∈ I(k) ∪ I(m)}) .

min cT x
Xs.t.
Pe(x) ≤ bk ∀ke∈δ(k)0 ≤ xj ≤ 1,∀j

Density of a problem: size of largest set I(k)Density of ACOPF problems: 3

Graphical, mixed-integer PCLP – or GMIPCLP
Input: an undirected graph G.
• For every vertex k, a set of variables: {xj : j ∈ I(k)}• For every edge e = {k, m}, a polynomial
Pe(x)=Pe ( {xj : j ∈ I(k) ∪ I(m)}) .

min cT xXs.t.
Pe(x) ≤ bk ∀ke∈δ(k)xj ∈ {0, 1} ∀j ∈ I,
• Density = size of largest I(k)0 ≤ xj ≤ 1,otherwiseGraphical, mixed-integer PCLP – or GMIPCLP
Input: an undirected graph G.
• For every vertex k, a set of variables: {xj : j ∈ I(k)}• For every edge e = {k, m}, a polynomial
Pe(x)=Pe ( {xj : j ∈ I(k) ∪ I(m)}) .

min cT xXs.t.
Pe(x) ≤ bk ∀ke∈δ(k)xj ∈ {0, 1} ∀j ∈ I,0 ≤ xj ≤ 1,otherwise• Density = size of largest I(k)Theorem 3
For any instance of GMIPCLP on a graph with treewidth w, densityd, max. degree π, and any fixed 0 <  < 1, there is a linear programof size (rows + columns) O ∗(π wd−w n) whose feasibility and optimality
error is O()(abridged).

More general: MIPCLP (Basic polynomially-constrained
mixed-integer LP)
min cT x
s.t. Pi(x) ≤ bi 1 ≤ i ≤ mxj ∈ {0, 1} ∀j ∈ I,Each Pi(x) is a polynomial.

0 ≤ xj ≤ 1,otherwiseMore general: MIPCLP (Basic polynomially-constrainedmixed-integer LP)
min cT xs.t. Pi(x) ≤ bi 1 ≤ i ≤ mxj ∈ {0, 1} ∀j ∈ I,0 ≤ xj ≤ 1,otherwise

Each Pi(x) is a polynomial.
Theorem 2
For any instance of MIPCLP whose intersection graph has treewidth
w, max. degree π, and any fixed 0 <  < 1, there is a linear program of size (rows + columns) O ∗(π w −w−1 n) whose feasibility andoptimality error is O() (abridged).

More general: MIPCLP (Basic polynomially-constrainedmixed-integer LP)
min cT x
s.t. Pi(x) ≤ bi 1 ≤ i ≤ mxj ∈ {0, 1} ∀j ∈ I,0 ≤ xj ≤ 1,otherwise

Each Pi(x) is a polynomial.
Theorem 2
For any instance of MIPCLP whose intersection graph has treewidth
w, max. degree π, and any fixed 0 <  < 1, there is a linear program of size (rows + columns) O ∗(π w −w−1 n) whose feasibility andoptimality error is O() (abridged).
Intersection graph of a constraint system: (Fulkerson? (1962?))• Has a vertex for every variably xj• Has an edge {xi, xj } whenever xi and xj appear in the same constraint

Theorem 2
For any instance of MIPCLP whose intersection graph has treewidthw, max. degree π, and any fixed 0 <  < 1, there is a linear program of size (rows + columns) O ∗(π w −w−1 n) whose feasibility andoptimality error is O() (abridged).
Theorem 3
For any instance of GMIPCLP on a graph G with treewidth w, density d, max. degree π, and any fixed 0 <  < 1, there is a linear
program of size (rows + columns) O ∗(π wd−wd n) whose feasibility andoptimality error is O() (abridged).

Theorem 2
For any instance of MIPCLP whose intersection graph has treewidth
w, max. degree π, and any fixed 0 <  < 1, there is a linear program of size (rows + columns) O ∗(π w −w−1 n) whose feasibility andoptimality error is O() (abridged).
Theorem 3
For any instance of GMIPCLP on a graph G with treewidth w, density d, max. degree π, and any fixed 0 <  < 1, there is a linear
program of size (rows + columns) O ∗(π wd−w n) whose feasibility andoptimality error is O() (abridged).
Two graphs:• G, the graph of the instance• H, the intersection graph of the constraints→ Even if G has small treewidth, H might not
Example: subset sum problem. G is a star, H is a clique.

Theorem 0
Given an instance of graphical mixed-integer PCLP
• On a graph G of treewidth w,• with density d,• For every vertex k, a set of variables: {xj : j ∈ I(k)}, for every edge e = {k, m}, a polynomial
Pe (x)
mins.t.

cT x
X=Pe ( {xj : j ∈ I(k) ∪ I(m)}) .

Pe (x) ≤ bk∀ke∈δ(k)xj ∈ {0, 1},∀j ∈ I,0 ≤ xj ≤ 1,otherwise.

Density of a problem: size of largest set I(k)There is an equivalent
mixed-integer polynomial optimization problem
whose intersection graph has tree-width O(wd).

Theorem 0Given an instance of graphical mixed-integer PCLP• On a graph G of treewidth w,• with density d,There is an equivalent mixed-integer polynomial optimization problem whose intersection
graph has tree-width O(wd).

ACOPF problem on small treewidth graph → (generalize)
Graphical QCQP on small treewidth graph and small density → (generalize)
GMIPCLP on small treewidth graph and small density → (generalize, reduce)
Mixed-integer PCLP with small treewidth intersection graphBasic theorem:
There is a polynomial-time -approximate algorithm for such problems

Main technique: approximation through pure-binary
problems
Glover, 1975 (abridged)
Let x be a variable, with bounds 0 ≤ x ≤ 1. Let 0 < γ < 1. Then wecan approximatex ≈PL−h2yhh=1where each yh is a binary variable. In fact, choosing L = dlog2 −1e,
we havex ≤PL

h=1 2−hyh ≤ x + .

→ Given a mixed-integer polynomially constrained LP (MIPCLP),
apply this technique to each continuous variable xj

Mixed-integer polynomially-constrained LP:(P)min cT xs.t. Pi(x) ≤ bi 1 ≤ i ≤ mxj ∈ {0, 1} ∀j ∈ I, 0 ≤ xj ≤ 1, otherwise
PL−hyh,j , where each yh,j ∈ {0, 1}
substitute: ∀j ∈/ I, xj →h=1 2
L ≈ log2 −1Mixed-integer polynomially-constrained LP:(P)

min cT x
s.t. Pi(x) ≤ bi 1 ≤ i ≤ mxj ∈ {0, 1} ∀j ∈ I, 0 ≤ xj ≤ 1, otherwise
PL−hyh,j , where each yh,j ∈ {0, 1}
substitute: ∀j ∈/ I, xj →h=1 2
L ≈ log2 −1obtain pure binary problem:(Q)

min ĉT z
s.t. P̂i(z) ≤ b̂i 1 ≤ i ≤ mzk ∈ {0, 1} ∀k

If (P) has intersection graph of treewidth w,then (Q) has intersection graph of treewidth Lw.

Mixed-integer polynomially-constrained LP:(P) min cT xs.t. Pi(x) ≤ bi 1 ≤ i ≤ mxj ∈ {0, 1} ∀j ∈ I, 0 ≤ xj ≤ 1, otherwise
PL−hyh,j , where each yh,j ∈ {0, 1}
substitute: ∀j ∈/ I, xj →h=1 2
L ≈ log2 −1obtain pure binary problem:(Q) min ĉT zs.t. P̂i(z) ≤ b̂i 1 ≤ i ≤ mzk ∈ {0, 1} ∀kIf (P) has intersection graph of treewidth w,then (Q) has intersection graph of treewidth Lw.
Theorem
Consider a pure-binary PCLP with n variables.
If the intersection graph has treewidth ≤ W then there is an exact linear
programming formulation withO(2W n) variables and constraints.

Conclusion
Given an ACOPF problem on a graph of treewidth ≤ w and n edges, and0 ≤  ≤ 1 there is an LP formulation with the following properties:• It has O(poly(−1)2O(w)n) variables and constraints• It produces -optimal and -feasible solutions.

Talk on Friday by Gonzalo on the pure-binary problems.