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 - Laurent PoirrierExport this event to calendar

Friday, February 14, 2014 — 3:30 PM EST

Multi-row Approaches to Cutting Plane Generation

Speaker: Jintai Ding
Affiliation: University of Cincinnati
Room: Mathematics and Computer Building (MC) 5168

Abstract: 

We cover two topics in the generation of multi-row cutting planes.

In the first one, we present a separation method for two-row cuts.
Two-row cuts are intersection cuts from two rows of a simplex tableau
describing the LP relaxation of the problem. The specificity of the approach adopted here is that it does not rely on an "infinite relaxation" point of view and generate intersection cuts from fixed lattice-free sets. Instead, given a fractional point, it aims at always finding a most violated
facet-defining inequality for the two-row model. This is known to be
achievable by optimizing over the polar set of the integer hull of the
model. We develop an improvement on this approach, by means of a polyhedron that is equivalent to the polar for our purpose, but has a more compact representation. We perform row-generation in order to avoid the costly computations of integer hulls of two-dimensional cones, and provide a simple oracle for finding violated constraints. An implementation of the resulting algorithm performs separation of two-row cuts in a few milliseconds on average, on the standard MIPLIB 3 and 2003 test sets.

While this two-row separator is quick, the measurements of the computational usefulness of the cuts do not yield satisfactory results.
Since all the cuts generated are facet-defining, this might suggest that the underlying two-row models are too weak. This observation prompted an attempt to evaluate the strength of various multi-row relaxations, on small instances, using a generic separator. To that end, a separator is developed, which is able to compute facet-defining inequalities from arbitrary (yet reasonably small) mixed-integer sets. A row-generation approach is again adopted, but this time the slave part consists in the resolution of a mixed-integer problem instead of a closed-form oracle. Some interesting computational tricks are necessary in order to speed up the inherently hard computations.

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 (84)
    1. October (1)
    2. September (7)
    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)