On March 17, 2020, Dabeen Lee (이다빈) from IBS discrete mathematics group presented a talk on his result proving that the closure of a polyhedron by some generalization of the Chvátal-Gomory cuts gives a polyhedron. The title of his talk is “On a generalization of the Chvátal-Gomory closure“.

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

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.

## Combinatorial and Discrete Optimization (2019 KSIAM Annual Meeting)

# Special Session @ 2019 KSIAM Annual Meeting

A special session on “Combinatorial and Discrete Optimization” at the 2019 KSIAM Annual Meeting is organized by Dabeen Lee. URL: https://www.ksiam.org/conference/84840fb6-87b0-4566-acc1-4802bde58fbd/welcome

## Date

**Nov 8, 2019** – **Nov 9, 2019** Address: 61-13 Odongdo-ro, Sujeong-dong, Yeosu-si, Jeollanam-do (전남 여수시 오동도로 61-13)

## Venue

Venezia Hotel & Resort Yeosu, Yeosu, Korea (여수 베네치아 호텔) Address: 61-13 Odongdo-ro, Sujeong-dong, Yeosu-si, Jeollanam-do (전남 여수시 오동도로 61-13)

## Speakers

**Hyung-Chan An (안형찬)**,*Yonsei University***Tony Huynh**,*Monash University***Dong Yeap Kang (강동엽)**,*KAIST / IBS Discrete Mathematics Group***Dabeen Lee (이다빈)**,*IBS Discrete Mathematics Group***Kangbok Lee (이강복)**,*POSTECH***Sang-il Oum (엄상일)**,*IBS Discrete Mathematics Group / KAIST***Kedong Yan**,*Nanjing University of Science and Technology***Se-Young Yun (윤세영)**,*KAIST*

## Schedules

- Combinatorial and Discrete Optimization I: November 8, 2019 Friday, 14:20 – 15:40.
- Kangbok Lee
- Kedong Yan
- Dabeen Lee
- Se-young Yun

- Combinatorial and Discrete Optimization II: November 9, 2019 Saturday, 10:00 – 11:20.
- Hyung Chan An
- Dong Yeap Kang
- Tony Huynh
- Sang-il Oum

## Abstracts

#### Kangbok Lee (이강복), Bi-criteria scheduling

#### Kedong Yan, Cliques for multi-term linearization of 0-1 multilinear program for boolean logical pattern generation

#### Dabeen Lee (이다빈), **Joint Chance-constrained programs and the intersection of mixing sets through a submodularity lens**

The intersection of mixing sets with common binary variables arise when modeling joint linear chance-constrained programs with random right-hand sides and finite sample space. In this talk, we first establish a strong and previously unrecognized connection of mixing sets to submodularity. This viewpoint enables us to unify and extend existing results on polyhedral structures of mixing sets. Then we study the intersection of mixing sets with common binary variables and also linking constraint lower bounding a linear function of the continuous variables. We propose a new class of valid inequalities and characterize when this new class along with the mixing inequalities are sufficient to describe the convex hull.

#### Se-Young Yun (윤세영), Optimal sampling and clustering algorithms in the stochastic block model

#### Hyung-Chan An (안형찬), Constant-factor approximation algorithms for parity-constrained facility location problems

*Facility location*is a prominent optimization problem that has inspired a large quantity of both theoretical and practical studies in combinatorial optimization. Although the problem has been investigated under various settings reflecting typical structures within the optimization problems of practical interest, little is known on how the problem behaves in conjunction with parity constraints. This shortfall of understanding was rather disturbing when we consider the central role of

*parity*in the field of combinatorics. In this paper, we present the first constant-factor approximation algorithm for the facility location problem with parity constraints. We are given as the input a metric on a set of

*facilities*and

*clients*, the opening cost of each facility, and the

*parity requirement*—$\mathsf{odd}$, $\mathsf{even}$, or $\mathsf{unconstrained}$—of every facility in this problem. The objective is to open a subset of facilities and assign every client to an open facility so as to minimize the sum of the total opening costs and the assignment distances, but subject to the condition that the number of clients assigned to each open facility must have the same parity as its requirement. Although the unconstrained facility location problem as a relaxation for this parity-constrained generalization has unbounded gap, we demonstrate that it yields a structured solution whose parity violation can be corrected at small cost. This correction is prescribed by a $T$-join on an auxiliary graph constructed by the algorithm. This graph does not satisfy the triangle inequality, but we show that a carefully chosen set of shortcutting operations leads to a cheap and

*sparse*$T$-join. Finally, we bound the correction cost by exhibiting a combinatorial multi-step construction of an upper bound. At the end of this paper, we also present the first constant-factor approximation algorithm for the parity-constrained $k$-center problem, the bottleneck optimization variant.

#### Dong Yeap Kang (강동엽), On minimal highly connected spanning subgraphs in dense digraphs

In 1985, Mader showed that every $n(\geq4k+3)$-vertex strongly $k$-connected digraph contains a spanning strongly $k$-connected subgraph with at most $2kn-2k^2$ edges, and the only extremal digraph is a complete bipartite digraph $DK_{k,n−k}$. Nevertheless, since the extremal graph is sparse, Bang-Jensen asked whether there exists g(k) such that every strongly $k$-connected $n$-vertex tournament contains a spanning strongly $k$-connected subgraph with $kn + g(k)$ edges, which is an “almost $k$-regular” subgraph.

#### Tony Huynh, Stable sets in graphs with bounded odd cycle packing number

#### Sang-il Oum, Rank-width: Algorithmic and structural results

## Dabeen Lee received the INFORMS Optimization Society Student Paper Prize on October 20, 2019

On October 20, 2019, Dabeen Lee (이다빈), a research fellow at the IBS discrete mathematics group, received the 2nd place prize in the INFORMS Optimization Society Student Paper Prize. This prize was established in 2006 by the Optimization Society of the Institute for Operations Research and the Management Sciences and is awarded annually at the INFORMS Annual Meeting for the most outstanding paper in optimization. This year, the INFORMS Annual Meeting was held in Seattle, USA.

Dabeen was awarded for the paper co-authored with his Ph.D. advisor Prof. Gérard Cornuéjols, titled “On some polytopes contained in the 0,1 hypercube that have a small Chvátal rank“. This paper was published in Mathematical Programming in November 2018.

## Dabeen Lee (이다빈) presented his work on algorithmic problems of finding a clutter minor at the Discrete Math Seminar

On July 16, 2019, Dabeen Lee (이다빈) from IBS Discrete Mathematics Group presented his work on identifying a clutter minor related to ideal clutters at the Discrete Math Seminar. The title of his talk was “Integrality of set covering polyhedra and clutter minors”.

## Dabeen Lee (이다빈), Integrality of set covering polyhedra and clutter minors

Given a finite set of elements $V$ and a family $\mathcal{C}$ of subsets of $V$, the set covering problem is to find a minimum cardinality subset of $V$ intersecting every subset in the family $\mathcal{C}$. The set covering problem, also known as the hitting set problem, admits a simple integer linear programming formulation. The constraint system of the integer linear programming formulation defines a polyhedron, and we call it the set covering polyhedron of $\mathcal{C}$. We say that a set covering polyhedron is integral if every extreme point is an integer lattice point. Although the set covering problem is NP-hard in general, conditions under which the problem becomes polynomially solvable have been studied. If the set covering polyhedron is integral, then it is straightforward that the problem can be solved using a polynomial-time algorithm for linear programming.

In this talk, we will focus on the question of when the set covering polyhedron is integral. We say that the family $\mathcal{C}$ is a clutter if every subset in $\mathcal{C}$ is inclusion-wise minimal. As taking out non-minimal subsets preserves integrality, we may assume that $\mathcal{C}$ is a clutter. We call $\mathcal{C}$ ideal if the set covering polyhedron of it is integral. To understand when a clutter is ideal, the notion of clutter minors is important in that $\mathcal{C}$ is ideal if and only if so is every minor of it. We will study two fundamental classes of non-ideal clutters, namely, deltas and the blockers of extended odd holes. We will characterize when a clutter contains either a delta or the blocker of an extended odd hole as a minor.

This talk is based on joint works with Ahmad Abdi and Gérard Cornuéjols.

## Welcome Dabeen Lee (이다빈), a new research fellow in the IBS discrete mathematics group

The IBS discrete mathematics group welcomes Dr. **Dabeen Lee** (이다빈), a new research fellow at the IBS discrete mathematics group from June 2019.

He received his Ph.D. from the Program of Algorithms, Combinatorics, and Optimization at the Carnegie Mellon University under the supervision of Prof. Gérard P. Cornuéjols in 2019. Welcome!