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 Colloquium - Aleksandr KazachkovExport this event to calendar

Friday, November 22, 2019 — 3:30 PM EST

Title: Disjunctive Cuts through the V-Polyhedral Lens

Speaker: Aleksandr Kazachkov
Affiliation: Polytechnique Montréal
Room: MC 5501

Abstract:

Cutting planes, or cuts, are a critical component of modern integer programming solvers, but existing cuts implemented in solvers are relatively simple compared to those in the literature. We discuss the primary reasons for this disparity, as well as our recently-proposed V-polyhedral framework for mitigating some of these difficulties encountered by prior "stronger" cuts. We build a compact linear program to generate strong disjunctive cuts without resorting to a higher-dimensional formulation, such as the one used in the standard alternative, lift-and-project. Though computationally more efficient, V-polyhedral cuts cannot be directly strengthened via classical approaches, which use the values of the extra variables appearing in the lift-and-project formulation. We show how to compute these values from a solution to the linear program generating V-polyhedral disjunctive cuts, enabling future research on strengthening these cuts.

In addition to proving useful theoretical properties of the cuts, we perform computational testing of their performance through an implementation in the open source COIN-OR framework, tested with strong multiterm disjunctions built from the leaf nodes of a partial branch-and-bound tree. Our results indicate that V-polyhedral cuts significantly improve the integrality gap closed compared to reasonable baselines and that they can also decrease solving time when used with branch-and-bound within a commercial solver. The outcome shows that the V-polyhedral framework is a promising path forward to effectively using stronger cuts within solvers.

Location 
MC - Mathematics & Computer Building
5501
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. 2020 (33)
    1. March (11)
    2. February (11)
    3. January (11)
  2. 2019 (167)
    1. December (5)
    2. November (15)
    3. October (18)
    4. September (15)
    5. August (9)
    6. July (17)
    7. June (18)
    8. May (16)
    9. April (9)
    10. March (24)
    11. February (13)
    12. January (8)
  3. 2018 (138)
  4. 2017 (103)
  5. 2016 (137)
  6. 2015 (136)
  7. 2014 (88)
  8. 2013 (48)
  9. 2012 (39)
  10. 2011 (36)
  11. 2010 (40)
  12. 2009 (40)
  13. 2008 (39)
  14. 2007 (15)