Transcript How Good Are Sparse Cutting-Planes?

How Good Are Sparse Cutting
Planes?
Santanu Dey, Marco Molinaro, Qianyi Wang
Georgia Tech
Cutting planes
In theory
• 𝑎𝑥 ≤ 𝑏
• Give convex hull of solutions
• Many families of cuts, large literature, since 60’s
Cutting planes
In practice
• Only want to use sparse cutting planes
𝑎
.𝑥 ≤ 𝑏
• Most commercial
solvers
use sparsity
to filter cuts
at most
𝒌 non-zero
entries
• Very limited theoretical investigation [Andersen, Weismantel 10]
• Do not give convex hull of solutions
How good are sparse cutting planes?
Geometric problem
• 𝑃 - polytope in 0,1 𝑛
• 𝑃𝑘 - intersection of all 𝑘-sparse cuts
• 𝑑 𝑃, 𝑃𝑘 = max𝑘 𝑑(𝑥, 𝑃)
𝑥∈𝑃
– Well defined for every polytope
– Upper bound on depth-of-cut
– At most 𝑛
Geometric problem
• 𝑃 - polytope in 0,1 𝑛
• 𝑃𝑘 - intersection of all 𝑘-sparse cuts
• 𝑑 𝑃, 𝑃𝑘 = max𝑘 𝑑(𝑥, 𝑃)
𝑥∈𝑃
– Well defined for every polytope
– Upper bound on depth-of-cut 𝑘
How does 𝑑(𝑃, 𝑃 ) behave?
– At most 𝑛
Ex 1: 𝑃 =
𝑖 𝑥𝑖
≤ 1, 𝑥 ≥ 0 ; 𝑃𝑘 = {𝑥𝐼 ≤ 1, k-subset 𝐼 of 𝑛 ; 𝑥 ≥ 0}
𝑑 𝑃, 𝑃𝑘
≈
1
𝑖 𝑥𝑖
≤
good
5
𝑘 (density)
5 𝑛
Ex 2: 𝑃 =
𝒏
𝒌
𝑛
,𝑥
2
𝑘
≥ 0 ; 𝑃 = {𝑥𝐼 ≤
𝑛
,
2
k-subset 𝐼 of 𝑛 ; 𝑥 ≥ 0}
𝒏 𝒏
≈
𝟐 𝒌
bad
𝑛/2
Ex 3: 𝑃 - set of 𝑡 random 0/1 points
∝
𝟏
𝒌
medium
𝟏
∝
𝒌
Our
Ourresults
results
• Upper bounds on 𝑑(𝑃, 𝑃𝑘 ) for polytopes in 0,1 𝑛
• Matching lower bound: a random 0/1 polytope, with prob ¼
• Hard packing IPs: sparse cuts are bad
≈
𝑑 𝑃, 𝑃𝑘
𝒏
𝒌
𝐥𝐨𝐠(𝒏. #𝐯𝐞𝐫𝐭 𝑷 )
𝟐 𝒏
𝑘 (density)
𝒏
−𝟏
𝒌
Our
Ourresults
results
• Upper bounds on 𝑑(𝑃, 𝑃𝑘 ) for polytopes in 0,1 𝑛
• Matching lower bound: a random 0/1 polytope, with prob ¼
• Hard packing IPs: sparse cuts are bad
𝑑 𝑃, 𝑃𝑘
𝑘 (density)
Our results
• Upper bounds on 𝑑(𝑃, 𝑃𝑘 ) for polytopes in 0,1 𝑛
• Matching lower bound: a random 0/1 polytope, with prob ¼
• Hard packing IPs: sparse cuts are bad
≈
𝑑 𝑃, 𝑃𝑘
𝑘 (density)
𝒏
𝒌
𝐥𝐨𝐠(𝒏. #𝐯𝐞𝐫𝐭 𝑷 )
Upper bound
• Show: 𝑑 𝑃, 𝑃𝑘 <
𝑛
𝑘
𝑙𝑜𝑔 𝑛. #𝑣𝑒𝑟𝑡 𝑃
= 2𝜆
𝑢
2𝜆
𝑷
𝑘-sparse cut
• Start with 𝑑 of norm 1 st 𝑑𝑃 ≤ 𝑏 − 𝜆 and 𝑑𝑢 ≥ 𝑏 + 𝜆
• Randomly round 𝑑 to vector 𝐷: scaling 𝛼 =
𝑘
2 𝑛
• Show: with non-zero prob. 𝐷 is 𝑘-sparse, 𝐷𝑃 ≤ 𝑏 and 𝐷𝑢 > 𝑏
Upper bound
• Show: 𝑑 𝑃, 𝑃𝑘 <
𝑛
𝑘
𝑙𝑜𝑔 𝑛. #𝑣𝑒𝑟𝑡 𝑃
= 2𝜆
𝑢
𝑷
𝑑
𝐷
• Start with 𝑑𝑃 ≤ 𝑏 − 𝜆 and 𝑑𝑢 ≥ 𝑏 + 𝜆; 𝑑 of unit norm
• Randomly “round” 𝑑 to vector 𝐷: scaling 𝛼 =
𝑑1𝑖 with prob 𝛼𝑑
wp 𝛼𝑑𝑖 𝑖
𝛼
𝐷𝑖 = 𝛼
00 with
𝑤𝑝 prob
1 − 𝛼𝑑
1−
𝑖 𝛼𝑑𝑖
𝑘
2 𝑛
• Show: with non-zero prob. 𝐷 is 𝑘-sparse, 𝐷𝑃 ≤ 𝑏 and 𝐷𝑢 > 𝑏
Upper bound
• Show: 𝑑 𝑃, 𝑃𝑘 <
𝑛
𝑘
𝑙𝑜𝑔 𝑛. #𝑣𝑒𝑟𝑡 𝑃
= 2𝜆
𝑢
𝑷
𝑑
𝐷
• Start with 𝑑𝑃 ≤ 𝑏 − 𝜆 and 𝑑𝑢 ≥ 𝑏 + 𝜆; 𝑑 of unit norm
• Randomly “round” 𝑑 to vector 𝐷: scaling 𝛼 =
𝑘
2 𝑛
𝑖)
𝑑𝑠𝑖𝑔𝑛(𝑑
𝑖
with𝛼𝑑
prob 𝛼 𝑑𝑖
wp
𝛼
𝑖
𝐷𝑖 = 𝑑𝑖
𝐷𝑖 = 𝛼
00 𝑤𝑝
− 𝛼𝑑1𝑖 − 𝛼 𝑑𝑖
with1prob
• Show: with non-zero
if 𝜶 𝒅 ≤prob.
𝟏 𝐷 is 𝑘-sparse, 𝐷𝑃
if 𝜶≤𝒅𝑏 and
> 𝟏𝐷𝑢
𝒊
𝒊
Upper bound
• Show: 𝑑 𝑃, 𝑃𝑘 <
𝑛
𝑘
𝑙𝑜𝑔 𝑛. #𝑣𝑒𝑟𝑡 𝑃
= 2𝜆
𝑢
𝑷
𝑑
𝐷
• Start with 𝑑𝑃 ≤ 𝑏 − 𝜆 and 𝑑𝑢 ≥ 𝑏 + 𝜆; 𝑑 of unit norm
• Randomly “round” 𝑑 to vector 𝐷: scaling 𝛼 =
𝑑𝑑𝑖𝑖 with prob 𝛼𝑑
wp 𝛼𝑑𝑖 𝑖
𝛼
𝐷𝑖 = 𝛼
00 with
𝑤𝑝 prob
1 − 𝛼𝑑
1−
𝑖 𝛼𝑑𝑖
𝑘
2 𝑛
• Show: prob > 0, 𝐷 is 𝑘-sparse, 𝐷𝑃 ≤ 𝑏 and 𝐷𝑢 > 𝑏
Upper bound
Obs: For every 𝑣, E 𝐷𝑣 = 𝑑𝑣; Var 𝐷𝑣 =
1
𝛼
2
𝑣
𝑖 𝑖 |𝑑𝑖 |
Claim 1: With high probability 𝐷 is k-sparse
• E[#non-zeros in 𝐷] =
𝑖 𝛼𝑑𝑖
≤ 𝑘/2
•
Stddev(#non-zeros in 𝐷) ≤ 𝑘
•
Since 𝐷𝑖 ’s are independent, #non-zeros ≈ + 𝑘 ≤ 𝑘
𝑘
2
Bernstein’s Inequality
Upper bound
Obs: For every 𝑣, E 𝐷𝑣 = 𝑑𝑣; Var 𝐷𝑣 =
1
𝛼
2
𝑣
𝑖 𝑖 |𝑑𝑖 |
Claim 1: With high probability 𝐷 is k-sparse
Claim 2: With high probability 𝐷𝑃 ≤ 𝑏
•
max 𝐷𝑝 ≤
𝑝∈𝑃
max
𝑝∈𝑣𝑒𝑟𝑡(𝑃)
𝐷𝑝
• For fixed vertex 𝑝, E 𝐷𝑝 = 𝑑𝑝 ≤ 𝑏 − 𝜆…
• …and Stddev 𝐷𝑝 ≤
2𝑛
𝑘
≤
𝜆
log(𝑛.#vert 𝑃 )
• Pr 𝐷𝑝 > 𝑏 ≤ Pr 𝐷𝑝 > 𝐸 𝐷𝑝 + 𝜆 ≤
• By union bound, Pr( max
𝑝∈𝑣𝑒𝑟𝑡(𝑃)
1
𝑛.#𝑣𝑒𝑟𝑡(𝑃)
𝐷𝑝 > 𝑏) < 1/n
Upper bound
Obs: For every 𝑣, E 𝐷𝑣 = 𝑑𝑣; Var 𝐷𝑣 =
1
𝛼
2
𝑣
𝑖 𝑖 |𝑑𝑖 |
Claim 1: With high probability 𝐷 is k-sparse
Claim 2: With high probability 𝐷𝑃 ≤ 𝑏
Claim 3: With probability 1/2n, 𝐷𝑢 > 𝑏
•
•
•
•
𝐷(𝑢 − 𝑣) = 𝐷(2𝜆𝑑), so 𝐷𝑢 = 2𝜆𝐷𝑑 + 𝐷𝑣
E 𝐷𝑣 = 𝑑𝑣 = 𝑏 − 𝜆, so 𝐷𝑢 ≈ 2𝜆𝐷𝑑 + 𝑏 − 𝜆
Show: with prob 1/2𝑛, 2𝜆𝐷𝑑 > 𝜆 ≡ 𝑫𝒅 > 𝟏/𝟐
E[𝐷𝑑] = 𝑑𝑑 = 1
• 𝐷𝑑 ≤
1 2
𝑖 𝛼 𝑑𝑖
≤𝑛
• 𝐷𝑑 > 1/2 with prob 1/2𝑛 (Markov’s ineq to 𝑛 − 𝐷𝑑)
𝑣
𝑢
2𝜆
𝑷
𝑑
𝑑𝑥 = 𝑏
Upper bound
Obs: For every 𝑣, E 𝐷𝑣 = 𝑑𝑣; Var 𝐷𝑣 =
1
𝛼
2
𝑣
𝑖 𝑖 |𝑑𝑖 |
Claim 1: With high probability 𝐷 is k-sparse
Claim 2: With high probability 𝐷𝑃 ≤ 𝑏
Claim 3: With probability 1/2n, 𝐷𝑢 > 𝑏
Taking union bound over the claims, with prob > 0 𝐷 is 𝑘-sparse,
𝐷𝑃 ≤ 𝑏 and 𝐷𝑢 > 𝑏
Obs: Bottleneck of analysis is to control max𝑝∈𝑃 𝐷𝑝 in Claim 2. Can
use different parameters of 𝑃 (e.g. covering number, chaining)
Lower bound
Lemma: Let 𝑃 be convex hull of 𝑡 random points from 0,1 𝑛 . Then
with prob 1/4, 𝑑 𝑃, 𝑃𝑘 ≥
𝑛
𝑘
log 𝑡 1 −
𝑑 𝑃, 𝑃𝑘
𝑘 (density)
1
𝑘
3
2
− log 𝑡
Lower bound
Lemma: Let 𝑃 be convex hull of 𝑡 random points from 0,1 𝑛 . Then
𝑛
𝑘
with prob 1/4, 𝑑 𝑃, 𝑃𝑘 ≥
log 𝑡 1 −
1
𝑘
3
2
− log 𝑡
Idea: Explicitly find point in 𝑃𝑘 far from 𝑃
Step 1: Show that inequality
𝑛
2
𝑖 𝑥𝑖 ≤ + [𝑒𝑟𝑟] is valid for 𝑃
Step 2: Show that if 𝑎𝑥 ≤ 𝑏 is valid for 𝑃𝑘 , then 𝑏 ≥
⇒ point ≈
1
2
+
log 𝑡
𝑘
𝑒 belongs to P^k
1
2
+
log 𝑡
𝑘
𝑖 𝑎𝑖
Lower bound
Lemma: Let 𝑃 be convex hull of 𝑡 random points from 0,1 𝑛 . Then
𝑛
𝑘
with prob 1/4, 𝑑 𝑃, 𝑃𝑘 ≥
log 𝑡 1 −
1
𝑘
3
2
− log 𝑡
Idea: Explicitly find point in 𝑃𝑘 far from 𝑃
Step 1: Show that inequality
𝑛
2
𝑖 𝑥𝑖 ≤ + [𝑒𝑟𝑟] is valid for 𝑃
Step 2: Show that if 𝑎𝑥 ≤ 𝑏 is valid for 𝑃𝑘 , then 𝑏 ≥
⇒ point ≈
1
2
+
log 𝑡
𝑘
𝑒 belongs to P^k
Anticoncentration: Pr 𝑎𝑋 ≥ E 𝑎𝑋 +
1
2
+
log 𝑡
𝑘
𝑖 𝑎𝑖
Hard packing IPs
0/1 with
prob 1/2
𝑥 ≤
𝐴
𝑥 ∈ 0,1
𝑏
#1′ 𝑠 𝑖𝑛 𝑟𝑜𝑤
2
𝑛
Used commonly as computational test-instances [Freville and
Plateau 96, Chu and Beasly 98, Kaparis and Letchford 08 and 10, …]
Theorem: With probability at least ½, 𝑑
for 𝑘 ≥ 𝑛/2.
𝑃, 𝑃𝑘
≥~ 𝑛
𝑛
𝑘
Obs 1: Almost matches upper bound: as bad as it gets
Obs 2: Still have distance 𝑂( 𝑛) even with sparsity Ω(𝑛)
−1 ,
Conclusion
• Push for theoretical study of sparse cutting planes
Results
• Matching upper and lower bounds on approximation of sparse cuts:
3 phases, dependence on number of vertices
• Analysis of hard packing IPs: sparse cuts are bad
Questions
•
•
•
•
Relationship with sparsity of formulation?
When should we use denser cuts?
Sparsify cutting planes?
Reformulations that allow good sparse cuts
Thank you!