Loading Events

« All Events

  • This event has passed.
:

Dabeen Lee (이다빈), On a generalization of the Chvátal-Gomory closure

Tuesday, March 17, 2020 @ 4:30 PM - 5:30 PM KST

Room B232, IBS (기초과학연구원)

Speaker

Integer programming is the problem of optimizing a linear function over the set of integer solutions satisfying a system of inequalities. The most successful technique in practice is the so-called “cutting-plane” algorithm in combination with branch-and-bound enumeration. Cutting-planes for an integer linear program are linear inequalities that are valid for all integer feasible solutions but cut off intermediate fractional solutions.

The Chvátal-Gomory cuts, introduced by Gomory in 1958 and further studied by Chvátal in 1973 in relation to their applications in combinatorial optimization, are the first class of general-purpose cutting-planes in the literature. The split cuts, whose name was coined by Cook, Kannan, and Schrijver in 1980, are another class of important cutting-planes in modern integer programming. Although there are infinitely many cuts in each class, it is known that only finitely many of them are nonredundant, which is related to designing a finite-convergent cutting-plane algorithm. In this talk, we introduce a new class of cutting-planes that generalizes the Chvátal-Gomory cuts and generalizes a special case of the split cuts. As the two classic classes of cutting-planes, we show that only a finite number of cuts can be redundant.

This talk is based on a joint work with Sanjeeb Dash and Oktay Günlük.

Details

Date:
Tuesday, March 17, 2020
Time:
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:
,

Venue

Room B232
IBS (기초과학연구원)

Organizer

Sang-il Oum (엄상일)
View Organizer Website
IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.