On a concept of a generic intersection cutcallback
Liding Xu
OptimiX, LIX, École Polytechnique

November 4, 2022

1 / 29

Table of Contents

Introduction to Intersection Cuts
ExamplesLattice
Nonlinear functions
Polynomials
Signomials

Generic Intersection Cut Callback
Discussions

2 / 29Intersection cuts

The goal of intersection cuts: convexify hard non-convex sets.
▶ Given a complex set S, we want to tighten a polyhedral outerapproximation P of S;▶ The polyhedral outer approximation (an LP relaxation) should
be constructed a priori.
▶ Useful for LP-based solvers.

3 / 29

History and recent development

History:▶ Concave programs (Hoang 1964): S is the epigraph of aconcave function;▶ Integer programs (Balas 1971): S is a lattice:▶ Linear complementary programs (Ibaraki 1973): S is acomplementary condition xi xj = 0.

4 / 29

History and recent development

Recent development (in non-convex MINLPs):▶ Bilevel programs (Fischetti 2018);▶ Factorable Programs (Serrano 2019): S is a sublevel set of adifference of concave functions;

5 / 29

History and recent development

Recent development (in non-convex MINLPs):▶ Bilevel programs (Fischetti 2018);▶ Factorable Programs (Serrano 2019): S is a sublevel set of adifference of concave functions;▶ Extended formulation of quadratic/polynomial programs(Bienstock 2020): S is an outer product set (set of rank-1matrices):▶ Projected formulation of quadratic programs (Muñoz 2022): S
is a sublevel set of a quadratic function (quadratic constraint).

5 / 29

Cut construction methods: phase 1

Preparation phase:▶ Assumption: a point z ′ ∈/ S, and a corner polyhedron(simplicial cone) R pointed at z ′ .

6 / 29

Cut construction methods: phase 1

Preparation phase:▶ Assumption: a point z ′ ∈/ S, and a corner polyhedron(simplicial cone) R pointed at z ′ .
▶ How to obtain?
▶ optimizing a relaxation problem over the polyhedral outerapproximation P.
▶ z ′ is the optimal solution at a vertex of P.
▶ find edges of P adjacent to z ′ , these edges’ convex hull is R.

6 / 29Visualization of preparation phase

7 / 29

Cut construction methods: phase 2

Set construction phase:

Definition
Given S ∈ Rp , a closed set C is called S-free, if the following
conditions are satisfied:
1. C is convex;
2. inter(C) ∩ S = ∅.
Find an S-free set C containing z ′ .

8 / 29Visualization of set construction phase

9 / 29

Cut construction methods: phase 3

Separation phase:▶ Intersect the corner polyhedron R with the set C.
▶ Intersection points support a separating hyperplane (anintersection cut).

10 / 29

Visualization of separation phase

11 / 29

Separation problem reduction▶ Phase 1 and 3 are standard procedures.
▶ The only non-standard (non-trivial) procedure is Phase 2.

12 / 29

Separation problem reduction▶ Phase 1 and 3 are standard procedures.
▶ The only non-standard (non-trivial) procedure is Phase 2.
▶ Larger S-fee set gives rise to stronger cuts, so maximal S-freeset is good.
▶ We next review methods to construct S-free sets in Phase 2.

12 / 29

Lattice sets

▶ Integer Programming: S is a lattice (the set of integer points).
▶ Maximal lattice-free sets in R2 :▶ Splits;▶ Triangles;▶ Quadrilaterals;▶ Gomory’s Mixed Integer Cuts are split intersection cuts.

13 / 29

Visualization of lattice-free sets

14 / 29

Sublevel set of difference of concave (convex) forms
Theorem (Khamisov 1999,Serrano 2019)
Assume S := {z ∈ Rp : f1 (z) − f2 (z) ≤ 0}, where f1 , f2 are concave
functions. Then, for z ′ ∈ dom(f2 ),Cz ′ := {z ∈ Rp : f1 (z) − f2 (z ′ ) − ∇f2 (z ′ )⊤ (z − z ′ ) ≥ 0} is a S-freeset.

15 / 29

Sublevel set of difference of concave (convex) forms
Theorem (Khamisov 1999,Serrano 2019)
Assume S := {z ∈ Rp : f1 (z) − f2 (z) ≤ 0}, where f1 , f2 are concave
functions. Then, for z ′ ∈ dom(f2 ),Cz ′ := {z ∈ Rp : f1 (z) − f2 (z ′ ) − ∇f2 (z ′ )⊤ (z − z ′ ) ≥ 0} is a S-freeset.

Theorem (Serrano 2021)
Assume S := {z ∈ Rp : f1 (z) − f2 (z) ≤ 0}, where f1 , f2 are concave
functions and positive-homogeneous of degree-1. Then, forz ′ ∈ dom(f2 ),Cz ′ := {z ∈ Rp : f1 (z) − f2 (z ′ ) − ∇f2 (z ′ )⊤ (z − z ′ ) ≥ 0} is amaximal S-free set.
Remark: for some case, positive-homogeneity of one concave
function can be relaxed.
15 / 29

Visualization of a sublevel-free set

16 / 29

Polynomial/signomial programmingmax

Xaikk∈K0∀i ∈ [m]Xk∈KiY

αxj kj

(1a)

j∈[n]

aik

Y

αxj kj ≤ 0(1b)

j∈[n]

where
Q K αis the index set for the whole monomial terms{ j∈[n] xj kj }k∈K , K0 and Ki are its subsets.
▶ Polynomial programming: αkj ∈ Z+ (nonegative integer);▶ Signomial programming: αkj ∈ R (real);

17 / 29

Examples: extended formulation of polynomial
programming

Dense lifting: a polynomial program can be lifted to an LP +rank-1 condition on a matrix X (Bienstock 2020).
▶ Xij represents a product of two monomial terms.
▶ Theorem: if X is rank one, then the determinants of its 2-by-2
minors are zeros;▶ Example of a principle minor: Xii Xjj − Xij2 = 0.

18 / 29

Examples: extended formulation of polynomial
programming

Dense lifting: a polynomial program can be lifted to an LP +rank-1 condition on a matrix X (Bienstock 2020).
▶ Xij represents a product of two monomial terms.
▶ Theorem: if X is rank one, then the determinants of its 2-by-2
minors are zeros;▶ Example of a principle minor: Xii Xjj − Xij2 = 0.
▶ Reformulation: (Xii + Xjj )2 − (Xii − Xjj )2 = 4Xij2 ;▶ DCC equivalence: (Xii + Xjj )2 − (Xii − Xjj )2 − 4Xij2 ≤ 0 and(Xii + Xjj )2 − (Xii − Xjj )2 − 4Xij2 ≥ 0;

18 / 29

Examples: extended formulation of signomial programmingSparse lifting: a signomial program can be lifted to an LP +condition y = x α (our working paper).
▶ Signomial-term-set S = {(x, y ) ∈ Rn+ × R+ : y ≤ x α }, where
α is an exponent vector with negative and/or positive entries;

19 / 29

Examples: extended formulation of signomial programmingSparse lifting: a signomial program can be lifted to an LP +condition y = x α (our working paper).
▶ Signomial-term-set S = {(x, y ) ∈ Rn+ × R+ : y ≤ x α }, where
α is an exponent vector with negative and/or positive entries;▶ After some transformation,
S = {(u, v ) ∈ Rh+ × Rl+ : u β − v γ ≤ 0}, wheremax(∥β∥1 , ∥γ∥1 ) = 1 and β, γ ≥ 0.

19 / 29

Examples: extended formulation of signomial programmingSparse lifting: a signomial program can be lifted to an LP +condition y = x α (our working paper).
▶ Signomial-term-set S = {(x, y ) ∈ Rn+ × R+ : y ≤ x α }, where
α is an exponent vector with negative and/or positive entries;▶ After some transformation,
S = {(u, v ) ∈ Rh+ × Rl+ : u β − v γ ≤ 0}, wheremax(∥β∥1 , ∥γ∥1 ) = 1 and β, γ ≥ 0.
▶ Intersection cuts: u β , v γ are power functions (whosehypograph are power cone representable) and concave, S now
is in the difference of concave form;

19 / 29

Examples: extended formulation of signomial programming▶ Factorable programming: u β is concave, so it
under-estimators can be constructed by factorization. Forinstance, u10.5 u20.3 u30.2 ≤ t is reverse convex.
▶ (conventional) multilinear factorization:
u10.5 ≤ t1 , u20.3 ≤ t2 , u30.2 ≤ t3 , t1 t2 t3 ≤ t.
▶ (new) power factorization: u20.6 u30.4 ≤ t1 , u10.5 t10.5 ≤ t. We cangive convex envelopes of u20.6 u30.4 , u10.5 t10.5 .

20 / 29

Supporting intersection cuts

▶ In the future, we will find more families of S-free sets.
▶ Users want to quickly know the performance of cuts fromtheir S-free sets in a real solver, rather than manuallyconstructing polyhedral outer approximation.
▶ A callback-based solution.

21 / 29

Pipeline of intersection cuts

▶ Phase 1 deals with simplex tableau and construct corner
polyhedron (standard).
▶ Phase 3 finds intersection points (standard).
▶ Non-standard: phase 2, defining an S-free set.

22 / 29

Defining S-free set

An S-free set is C := {z ∈ D : g (z) ≥ 0}, D is a domain, andg (z ′ ) ≥ 0.
▶ g is concave over D.
▶ A sublevel-free set C := {z ∈ D : g (z) ≥ 0}.
(1, z ∈ D ∩ C▶ Arbitrary set C (like lattice-free): g (z) =−∞, otherwise.
is an indicator function.
Interface: the user needs to register the defining-variables of C anddomain D.

23 / 29

Oracle access and separation

Defining C is equivalent to defining 0th-order (function value)
access to g (z), optional: 1th-order (gradient value) oracle accessto g (z).
▶ The separation problem: find intersection point of ray z ′ + tr(t ≥ 0) with C, where r is an extreme ray of the corner
polyhedron R;▶ Equivalently, find root of the 1d function g (z ′ + tr );24 / 29

Oracle access and separation

Defining C is equivalent to defining 0th-order (function value)
access to g (z), optional: 1th-order (gradient value) oracle accessto g (z).
▶ The separation problem: find intersection point of ray z ′ + tr(t ≥ 0) with C, where r is an extreme ray of the corner
polyhedron R;▶ Equivalently, find root of the 1d function g (z ′ + tr );▶ Bisection root finding: 0th-order oracle access.
▶ Newton root finding: 0th-order and 1th-order oracle access.
Interface: user provides 0th-order and 1th-order oracle access.

24 / 29

Root finding

25 / 29

Abstract functions of the callback

Setting:▶ BisectionOrNewtion: TRUE or FALSE.
Minimal interface functions▶ Register(): register variables and domain for an S-free set.
▶ ZeroOrderOracle(): 0th-order access.
▶ FirstOrderOracle(): 1st-order access.
The callback automatically extracts corner polyhedron, finds roots,and checks numerical stability.

26 / 29

Limitations

Intersection cuts can be dense and thus numerically dangerous.

27 / 29Strengthenning methods

We can at best approximate conv(C c ∩ R), and R is a loose
relaxation of P. Balas’s original (generalized) intersection cuts
definition: R is P.
▶ Consider variables’ bounds: Chielma 2022.
▶ Consider bounded simplex paths from a relaxation point, moreedges of P are considered: Balas 2022.

28 / 29Comparing lift-and-project

When C is a polyhedron,▶ Intersection cuts for (conv(C c ∩ R)) is weaker than lift-projectcuts (conv(C c ∩ P)).
▶ Assume P = R, intersection cuts are then equivalent tolift-and-project cuts
When C is not polyhedron▶ Only Intersection cuts works.

29 / 29