University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

Tutte seminar - Sanjeeb DashExport this event to calendar

Friday, December 14, 2012 — 3:30 PM to 4:30 PM EST

Cutting planes for mixed-integer programs derived from multi-branch split cuts

Speaker: Sanjeeb Dash
Affiliation: IBM TJ Watson Research Center
Room: Mathematics & Computer Building (MC) 5158

Abstract:

Cutting planes (cuts, for short), or inequalities satisfied by integral solutions of systems of linear inequalities, are important tools used in modern solvers for integer programming problems. The split cuts of Cook, Kannan and Schrijver (1990) -- and related Gomory mixed-integer cuts -- form an important class of cutting planes, and have recently been generalized in different ways. Lattice-free cuts, or cuts based on general lattice-free sets in Rn, form one generalization. We study a different generalization called multi-branch split cuts (also called t-branch split cuts by Li and Richard, 2008) and discuss connections with lattice-free cuts. 
We show how to express lattice-free cuts as t-branch split cuts for some integer t > 0. We prove an exponential lower bound on t, by constructing lattice-free sets in Rn which cannot be covered by a sub-exponential number of split sets.These results are related to the problem of covering convex sets with strips -- sets of points between two parallel hyperplanes. We use these results to construct a pure cutting plane algorithm for mixed-integer programs. We also settle a conjecture of Li and Richards on t-branch split cuts, and show that there are mixed-integer programs with n+1 variables which are unsolvable by (n-1)-branch split cuts, thus extending the well-known 3-variable example of Cook, Kannan and Schrijver which is unsolvable by split cuts. 

This is joint work with Neil Dobbs, Oktay Gunluk, Tomasz Nowicki, and Grzegorz Swirczsz.

Location 
MC - Mathematics & Computer Building
5158
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
  1. 2021 (85)
    1. October (1)
    2. September (8)
    3. August (7)
    4. July (10)
    5. June (12)
    6. May (7)
    7. April (9)
    8. March (13)
    9. February (8)
    10. January (10)
  2. 2020 (119)
    1. December (5)
    2. November (12)
    3. October (12)
    4. September (12)
    5. August (11)
    6. July (17)
    7. June (11)
    8. May (6)
    9. March (11)
    10. February (11)
    11. January (11)
  3. 2019 (167)
  4. 2018 (136)
  5. 2017 (103)
  6. 2016 (137)
  7. 2015 (136)
  8. 2014 (88)
  9. 2013 (48)
  10. 2012 (39)
  11. 2011 (36)
  12. 2010 (40)
  13. 2009 (40)
  14. 2008 (39)
  15. 2007 (15)