Intersection cuts meet submodularity
Liding Xu
Joint with Leo Liberti
OptimiX, LIX, École Polytechnique

March 1, 2023

1 / 21Intersection cuts

The goal of intersection cuts: convexify a hard non-convex set S.
Useful for LP-based global optimization solvers.

2 / 21History

The history in discrete and continuous optimization:▶ Continuous programs (Hoang 1964): S is the hypograph of aconvex function (maximization of a convex function!);▶ Integer programs (Balas 1971): S is a lattice.

3 / 21

Submodular functions

Submodular functions: discrete convex functions defined onBoolean hypercube.
▶ Let f : {0, 1}n → R be a submodular function, define
S := {(x, t) ∈ {0, 1}n × R : f (x) ≥ t} the hypograph of f ;▶ Maximization problem (N P-hard):
maxx∈{0,1}n f (x) = max(x,t)∈conv(S) t.

4 / 21

Outline of this talk

▶ Construction of S-free sets and their maximality;▶ Separation of intersection cuts;▶ Generalization and Boolean multilinear (quadratic)
constraints;▶ Applications and testing;▶ Open problems and future direction.

5 / 21

S-free sets

▶ S-free set: a convex set C such that inter(C) ∩ S = ∅.

6 / 21

S-free sets: construction 1Lifting.

Theorem
Let H be a maximal {0, 1}n -free set, then H × R is a maximal
S-free set.
Remarks:▶ Proof similar to mixed-lattice set;
▶ Examples: H = {x ∈ Rn : 0 ≤ x ≤ 1} defined by a split.

7 / 21

S-free sets: construction 2

Construct the Lovász extension of f on [0, 1]n , and further extend
it to a continuous function f¯ on Rn .

Lemma
For all x ∈ {0, 1}n , f¯(x) = f (x) and f¯ : Rn → R is a (continuous)
polyhedral convex function.

8 / 21

S-free sets: construction 2 (cont.)

Facts: Linear components of f¯ ≡ facets of epi(f¯) ≡ permutations
on {1, · · · , n} ≡ chains in {0, 1}n .

Theoremconv(epi(f )) = epi(f¯) ∩ ([0, 1]n × R).
Remarks:▶ Proof based on polymatroid [Atamtürk et al. 2022].
▶ Separation of epi(f¯): Strongly polynomial time.

9 / 21

S-free sets: construction 2 (cont.)

Theorem
The epigraph epi(f¯) of f¯ is a (non-maximal) S-free set.

10 / 21

Why not maximal?

Theorem
Let C include epi(f¯), C is a maximal S-free set if the following twoconditions are satsified:▶ each of its facets contains a point (x, f (x)) (x ∈ {0, 1}n ) in
its relative interior;▶ The boundary of S contains all points (x, f (x)) (x ∈ {0, 1}n ).
Remark: Proof similar to lattice set.

11 / 21

A counter example
n = 3, 6 = 3! permutations/chains/facets, and 8 = 23 points of(x, f (x)).

Figure: {0, 1}33 facets (each facet supported by 4 points) are enough:( (0, 0, 0), (0, 0, 1), (0, 1, 1), (1, 1, 1) ) ,( (0, 0, 0), (0, 1, 0), (1, 1, 0), (1, 1, 1) ) ,( (0, 0, 0), (1, 0, 0), (1, 0, 1), (1, 1, 1) ) .
Dropping remaining facets from epi(f¯) = enlarging epi(f¯).
12 / 21

Cut separation▶ Reduction 1: The computation of one coefficient ofintersection cut is reduced to a line search problem: from aninterior point of epi(f¯), find the intersection point along a ray
to the border of the polyhedron;▶ Reduction 2: Equivalent to finding the zero point of a
univariate piece-wise linear convex function.

(a) Line search(b) 1-D zero finding
13 / 21

Zero finding▶ Previous results [Chmiela et al. 2022, Xu et al. 2022] arebased on binary search.
▶ New discrete Newton algorithm similar to [Iwata et al. 2008].
▶ Newton algorithm requires gradient information.
▶ Separation of epi(f¯) in a polynomial time implies thatgradients can be computed in a polynomial time.

14 / 21

Generalization to submodular-supermodular functions

Consider S := {(x, t) ∈ {0, 1}n × R : f1 (x) − f2 (x) ≥ ℓt}, withℓ ∈ {0, 1}, f1 , f2 being submodular.

Theorem
Let f¯1 , f¯2 be the continuous extensions of f1 , f2 on Rn , then{(x, t) ∈ Rn × R : f¯1 (x) − f¯2 (x ′ ) − ∇f¯2 (x ′ )(x − x ′ ) ≤ ℓt} is S-free.
Key idea: Construct the ‘best’ submodular over-estimator of thesubmodular-supermodular function.

15 / 21

Boolean multilinear constraintTheorem
Given a P
Boolean multilinear
function f : {0, 1}n → R defined asQf (x) := k∈[K ] ak j∈Ak xj (for index sets Ak ⊆ {1,P· · · , n})Qwith
K multilinear terms, let f = f1 − f2 where f1 (x) :=akxj
k∈[K ]
ak <0and f2 (x) := −{0, 1}n .

Pk∈[K ]
ak >0akQj∈Akxj . Then f1 , f2 are submodular onj∈Ak

Remark: Apply the previous theorem to the Boolean multilinear
constraint f (x) ≥ ℓt.

16 / 21

Implementation and test

More insights come from coding and experiments:▶ Implementation in SCIP 8.0.
▶ Result 1: Maximal S-free sets does not imply practically goodcuts;▶ Result 2: Performance difference between problems withnatural MILP and MINLP formulations, monotone andnon-monotone.

17 / 21

Problem zoo

Monotone submodular maximization usually has a cardinality or
knapsack constraint.
▶ Max cut with positive weights: non-monotone submodularmaximization, natural MILP formulation.
▶ Exponential utility function maximization: monotone
submodular maximization, natural convex MINLP formulation(too easy for SCIP).
▶ D-optimal design: submodular maximization, natural convex
MISDP/MICP formulation (not useful).
▶ MUBO: submodular-supermodular maximization.

18 / 21

Max cut

30 “g05” and 30 “pw” instances with nonnegative weights fromBiq Mac.

Configuration
standalone
embeddedDefault
closed
time
0.04
5.13
0.22 12.62

closed0.16
0.27

Submodular cut
relativetime
cuts
4.40
85.40 207.59
1.22
104.0270.68

closed0.12
0.27

Split cutrelative time
2.93
17.92
1.22
34.62

cuts
92.53
45.15

Table: Summary of max cut results

19 / 21

Multilinear unconstrained Boolean optimization

44 “autocorr bern” MUBO instances from MINLPLib.

Configuration
standalone
embeddedDefault
closed
time
0.01
9.49
0.105 22.52

closed0.05
0.11

Submodular cut
relative time
cuts
4.81
43.54 43.17
1.13
49.61 13.80

closed0.03
0.106

Split cutrelative time
2.31
14.64
1.01
25.58

cuts
20.94
28.21

Table: Summary of pseudo boolean maximization results

20 / 21

Open problems and future▶ Enlarging S-free set;
▶ Is the discrete Newton algorithm strongly polynomial time?
(unbounded test) [Goemans et al, 2017];▶ Natural extension to submodular functions over integer lattice(integer quadratic/multilinear constraint);▶ Monoid strengthening of intersection cuts similar for
quadratic-constraint [Chmiela et al. 2022].
▶ Using the submodular overestimator for thesubmodular-supermodular function: better approximation
algorithm? DC programming?

21 / 21