Dabeen Lee (이다빈) gave a talk on characterizing ideal multipartite clutters constructed from subspaces of finite vector spaces in terms of forbidden clutter minors at the Discrete Math Seminar

On August 29, 2023, Dabeen Lee (이다빈) from KAIST gave a talk at the Discrete Math Seminar on characterizing ideal multipartite clutters constructed from subspaces of finite vector spaces in terms of forbidden clutter minors. The title of his talk was “From coordinate subspaces over finite fields to ideal multipartite uniform clutters.”

Dabeen Lee (이다빈), From coordinate subspaces over finite fields to ideal multipartite uniform clutters

Take a prime power $q$, an integer $n\geq 2$, and a coordinate subspace $S\subseteq GF(q)^n$ over the Galois field $GF(q)$. One can associate with $S$ an $n$-partite $n$-uniform clutter $\mathcal{C}$, where every part has size $q$ and there is a bijection between the vectors in $S$ and the members of $\mathcal{C}$. In this paper, we determine when the clutter $\mathcal{C}$ is ideal, a property developed in connection to Packing and Covering problems in the areas of Integer Programming and Combinatorial Optimization. Interestingly, the characterization differs depending on whether $q$ is $2,4$, a higher power of $2$, or otherwise. Each characterization uses crucially that idealness is a minor-closed property: first the list of excluded minors is identified, and only then is the global structure determined. A key insight is that idealness of $\mathcal{C}$ depends solely on the underlying matroid of $S$. Our theorems also extend from idealness to the stronger max-flow min-cut property. As a consequence, we prove the Replication and $\tau=2$ conjectures for this class of clutters. This is joint work with Ahmad Abdi (London School of Economics).

Dabeen Lee (이다빈), Non-smooth and Hölder-smooth submodular optimization

We study the problem of maximizing a continuous DR-submodular function that is not necessarily smooth. We prove that the continuous greedy algorithm achieves an [(1−1/e)OPT−ϵ] guarantee when the function is monotone and Hölder-smooth, meaning that it admits a Hölder-continuous gradient. For functions that are non-differentiable or non-smooth, we propose a variant of the mirror-prox algorithm that attains an [(1/2)OPT−ϵ] guarantee. We apply our algorithmic frameworks to robust submodular maximization and distributionally robust submodular maximization under Wasserstein ambiguity. In particular, the mirror-prox method applies to robust submodular maximization to obtain a single feasible solution whose value is at least (1/2)OPT−ϵ. For distributionally robust maximization under Wasserstein ambiguity, we deduce and work over a submodular-convex maximin reformulation whose objective function is Hölder-smooth, for which we may apply both the continuous greedy method and the mirror-prox method.
Joint work with Duksang Lee and Nam Ho-Ngyuen.

Dabeen Lee (이다빈) gave a talk characterizing the submodular structure in the mixed-integer program arising from joint linear chance-constrained programs at the Discrete Math Seminar

On September 7, 2021, Dabeen Lee (이다빈) from the IBS Discrete Mathematics Group gave a talk at the Discrete Math Seminar characterizing the submodular structure in the mixed-integer program arising from joint linear chance-constrained programs with random right-hand sides and finite sample space. The title of his talk is “Mixing sets, submodularity, and chance-constrained optimization“.

Dabeen Lee (이다빈), Mixing sets, submodularity, and chance-constrained optimization

A particularly important substructure in modeling joint linear chance-constrained programs with random right-hand sides and finite sample space is the intersection of mixing sets with common binary variables (and possibly a knapsack constraint). In this talk, we first explain basic mixing sets by establishing a strong and previously unrecognized connection to submodularity. In particular, we show that mixing inequalities with binary variables are nothing but the polymatroid inequalities associated with a specific submodular function. This submodularity viewpoint enables us to unify and extend existing results on valid inequalities and convex hulls of the intersection of multiple mixing sets with common binary variables. Then, we study such intersections under an additional linking constraint lower bounding a linear function of the continuous variables. This is motivated from the desire to exploit the information encoded in the knapsack constraint arising in joint linear CCPs via the quantile cuts. 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. This is based on joint work with Fatma Fatma Kılınç-Karzan and Simge Küçükyavuz.

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.

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.

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.