BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv5.4.0//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Discrete Mathematics Group
X-ORIGINAL-URL:https://dimag.ibs.re.kr
X-WR-CALDESC:Events for Discrete Mathematics Group
BEGIN:VTIMEZONE
TZID:Asia/Seoul
BEGIN:STANDARD
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:KST
DTSTART:20200101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200317T163000
DTEND;TZID=Asia/Seoul:20200317T173000
DTSTAMP:20210301T232046
CREATED:20200307T133007Z
LAST-MODIFIED:20200629T005907Z
UID:2180-1584462600-1584466200@dimag.ibs.re.kr
SUMMARY:Dabeen Lee (이다빈)\, On a generalization of the Chvátal-Gomory closure
DESCRIPTION: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. \nThe 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. \nThis talk is based on a joint work with Sanjeeb Dash and Oktay Günlük.
URL:https://dimag.ibs.re.kr/event/2020-03-17/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR