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 - Jim OstrowskyExport this event to calendar

Friday, December 4, 2009 — 3:30 PM to 4:30 PM EST

Symmetry in Integer Programming

Speaker: Jim Ostrowsky
Affiliation: University of Waterloo
Room: Mathematics & Computer Building (MC) 5158

Abstract:

Symmetry has long been considered a curse in integer linear programming, and auxiliary (often extended) formulations are sought to reduce the amount of symmetry in an integer linear programming (ILP) formulation. A standard method for solving integer programs is branch-and-bound. In branch-and-bound, the set of feasible solutions is partitioned, forming more easily-solved subproblems. The presence of symmetry means that many of these subproblems are equivalent. Only one member of each collection of equivalent subproblems needs to be solved. Failure to recognize that many subproblems are equivalent results in a waste of computational resources. In this talk, we will discuss how to recognize and exploit the symmetry of an ILP, as well as discuss why the current methods of dealing with symmetry are not enough.

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. 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)