Solving Nonlinear Problems via Disjunctions
Daniel Bienstock
Columbia University

October 2019

Bienstock (Columbia)

Disjunctions

October 20191 / 16

Some of my papers that were influenced by Egon’s work
and which relate to today’s talk
Subset Algebra Lift Operators for 0-1 Integer Programming, with M.
Zuckerberg (2004).
Tree-width and the Sherali-Adams operator, with N. Özbay (2004)
Strong formulations for convex functions over nonconvex sets, with A.
Michalka (2014).
LP formulations for polynomial optimization problems, with G. Muñoz(2015).
Outer-Product-Free Sets for Polynomial Optimization andOracle-Based Cuts, with C. Chen and G. Muñoz (2018).
Principled Deep Neural Network Training through Linear
Programming, with G. Muñoz and S. Pokutta (2019).

Bienstock (Columbia)

Disjunctions

October 20192 / 16

Some of my papers that were influenced by Egon’s work
and which relate to today’s talk
Subset Algebra Lift Operators for 0-1 Integer Programming, with M.
Zuckerberg (2004).
Tree-width and the Sherali-Adams operator, with N. Özbay (2004)
Strong formulations for convex functions over nonconvex sets, with A.
Michalka (2014).
LP formulations for polynomial optimization problems, with G.
Muñoz (2015).
Outer-Product-Free Sets for Polynomial Optimization andOracle-Based Cuts, with C. Chen and G. Muñoz (2018).
Principled Deep Neural Network Training through Linear
Programming, with G. Muñoz and S. Pokutta (2019).

Bienstock (Columbia)

Disjunctions

October 20193 / 16

We wanteed to talk about ongoing computational work

But it is not ready

So we will settle for some theory

Bienstock (Columbia)

Disjunctions

October 20194 / 16

Approximate optimization of well-behaved functions
Prototype problem:
min c T x
s.t. fi (x) ≤ 0,i = 1, . . . , mnx ∈ [0, 1] , xj ∈ {0, 1}, j ∈ J
Each fi is “well-behaved”: Lipschitz constant LiNote: it appears redundant to say that some variables are binary
Toolset:Intersection graph
A vertex for each variable and an edge whenever two variables appear
in the same fi
Tree-width Min clique number (minus one) over all chordal
supergraphs of G

Bienstock (Columbia)

Disjunctions

October 20195 / 16

Prototype problem:
min c T x
s.t. fi (x) ≤ 0,i = 1, . . . , mnx ∈ [0, 1] , xj ∈ {0, 1}, j ∈ J
An extension of work in B. and Muñoz 2015, SIOPT 2018.
Suppose:the intersection graph has tree-width ω and fi has Lipschitz constantLi ≤ L.
If problem is feasible, for every 0 <  < 1 there is an LP relaxation withO (L/)ω+1 (n + m) log(L/) variables and constraints, andoptimality and feasibility errors O()Bienstock (Columbia)

Disjunctions

October 20196 / 16

Main technique: approximation through pure-binary problems
Glover, 1975 (extended)
Let x be a variable, with bounds 0 ≤ x ≤ 1. Let 0 < γ < 1. Then wecan approximatex ≈PK−h yhh=1 2

where each yh is a binary variable. In fact, choosing K = dlog2 γ −1 e,
we havex ≤PK−h yh
h=1 2≤ x + γ.

→ Given a mixed-integer well-behaved problem
apply this technique to each continuous variable xj
Bienstock (Columbia)

Disjunctions

October 20197 / 16

The main result.
c ∗ = min c T xs.t. fi (x) ≤ 0,i = 1, . . . , mnx ∈ [0, 1] , xj ∈ {0, 1}, j ∈ JIntersection graph with tree-width ω,
Each fi has Lipschitz constant Li ≤ L.
For 0 <  < 1, an LP relaxation of size O (1/)ω+1 (n + m) log(1/)yields x̂ ∈ [0, 1]n , x̂J ∈ {0, 1}J withc T x̂ ≤ c ∗ + O(kck1 )fi (x̂) ≤ O(Li ),
Bienstock (Columbia)

i = 1, . . . , m
Disjunctions

October 20198 / 16

How is it done?

Lifting hierarchies in 0-1 linear integer programming
Balas, Lovász-Schrijver, Sherali-Adams, Balas-Ceria-Cornuéjols
Specific version: zeta-function idea of Lovász-Schrijver[n]x ∈ {0, 1}n → X ∈ {0, 1}2

Bienstock (Columbia)

Disjunctions

October 20199 / 16

Applications
Fixed-charge network flow problems, on networks with small treewidth

ACOPF problem, on networks with small treewidth
In both cases, LP of size O (1/)ω+1 n log(1/)ω = treewidth of network≤ treewidth of intersection graph of formulation
A famous scientist: “lifting hierarchies do not work”

Bienstock (Columbia)

Disjunctions

October 201910 / 16

Another “application”
Positivestellensätze for semi-algebraic systems
Given a system of polynomial inequalities pi (x) ≤ 0,i ∈I

A positivstellensatz is a proof of infeasibility of the system
Under assumptions (e.g. compactness) such statements exist (richliterature)(2017) Amir-Ali Ahmadi, Georgina Hall ⇒ a new positivstellensatz,
under compactness (containment in a known ball)Bienstock (Columbia)

Disjunctions

October 201911 / 16

The lifted LP relaxation hierarchy gives a similar result
We are given a systemfi (x) ≤ 0,i ∈I(1a)nx ∈ [0, 1] , xj ∈ {0, 1}, j ∈ J.

(1b)where each fi is a function with Lipschitz constant L.
→ If the system is infeasible, is there a short proof thereof? Yes:
1

Given , our LP = LP(), if feasible, yields x̂ = x̂() withfi (x̂) ≤ O(L) ∀i ∈ I , x̂ ∈ [0, 1]n , x̂j ∈ {0, 1}, j ∈ J

2Let  → 0: x̂ has accumulation point x ∗3

But system (1a), (1b) is infeasible, so x ∗ cannot be feasible!

4

Conclusion: LP() is not feasible for some  small enough5

But LP() is a relaxation for (1a), (1b)Bienstock (Columbia)

Disjunctions

October 201912 / 16

A bad QCQP

→ Gurobi, SCIP, other codes: value ≈ 1.4142
Wrong, actual value ≈ 1.22
Bienstock (Columbia)

Disjunctions

October 201913 / 16

What’s going on?

maxs.t.

x2(x1 − 1)2 + x22≥ 32≥ 3x22(x1 + 1) +x12+ x22
10(0,≤ 22 )(0, − 2 )But this is NOT the problem being solved ..
Bienstock (Columbia)

Disjunctions

October 201914 / 16

The bad QCQP

→ Gurobi, SCIP, other codes: value ≈ 1.4142
Wrong, actual value ≈ 1.22
Bienstock (Columbia)

Disjunctions

October 201915 / 16

Actually THIS is the problem being solved:

maxs.t.

x22(x1 − 1) + x22≥ 3+φ(x1 + 1)2 + x22
x12+ x2210≥ 3(0,(φ > 0)

≤ 22 )(0, − 2 )Fri.Oct.25.162243.2019@littleboy

Bienstock (Columbia)

Disjunctions

October 201916 / 16