Simge Küçükyavuz – Page 2 – Optimization Online

Conic Mixed-Binary Sets: Convex Hull Characterizations and Applications

Published: 2020/12/29

(Mixed) Integer Nonlinear Programming best subset selection, conic mixed-binary sets, conic quadratic optimization, convex hull, distributionally robust optimization, extended polymatroid inequalities, fractional binary optimization, submodularity

We consider a general conic mixed-binary set where each homogeneous conic constraint involves an affine function of independent continuous variables and an epigraph variable associated with a nonnegative function, $f_j$, of common binary variables. Sets of this form naturally arise as substructures in a number of applications including mean-risk optimization, chance-constrained problems, portfolio optimization, lot-sizing … Read more

An Exact Cutting Plane Method for hBcsubmodular Function Maximization

Published: 2020/08/03, Updated: 2021/06/28

Simge Küçükyavuz

Qimeng Yu

(Mixed) Integer Linear Programming, Cutting Plane Approaches, Polyhedra

A natural and important generalization of submodularity—$k$-submodularity—applies to set functions with $k$ arguments and appears in a broad range of applications, such as infrastructure design, machine learning, and healthcare. In this paper, we study maximization problems with $k$-submodular objective functions. We propose valid linear inequalities, namely the $k$-submodular inequalities, for the hypograph of any $k$-submodular … Read more

Strong Formulations for Distributionally Robust Chance-Constrained Programs with Left-Hand Side Uncertainty under Wasserstein Ambiguity

Published: 2020/07/13, Updated: 2020/12/06

Robust Optimization, Stochastic Programming chance constraints, covering and packing, distributionally robust optimization, mixing inequalities, wasserstein ambiguity

Distributionally robust chance-constrained programs (DR-CCP) over Wasserstein ambiguity sets exhibit attractive out-of-sample performance and admit big-$M$-based mixed-integer programming (MIP) reformulations with conic constraints. However, the resulting formulations often suffer from scalability issues as sample size increases. To address this shortcoming, we derive stronger formulations that scale well with respect to the sample size. Our focus … Read more

Ideal formulations for constrained convex optimization problems with indicator variables.

Published: 2020/06/29, Updated: 2021/06/15

Andrés Gómez

Simge Küçükyavuz

Linchuan Wei

(Mixed) Integer Nonlinear Programming, Semi-definite Programming combinatorial constraints, convexification, indicator variables, perspective reformulation

Motivated by modern regression applications, in this paper, we study the convexification of a class of convex optimization problems with indicator variables and combinatorial constraints on the indicators. Unlike most of the previous work on convexification of sparse regression problems, we simultaneously consider the nonlinear non-separable objective, indicator variables, and combinatorial constraints. Specifically, we give … Read more

Consistent Second-Order Conic Integer Programming for Learning Bayesian Networks

Published: 2020/05/22, Updated: 2022/05/06

(Mixed) Integer Nonlinear Programming, Data-Mining, Network Optimization bayesian networks, consistency, directed acyclic graphs, early stopping criterion, mixed-integer conic programming

Bayesian Networks (BNs) represent conditional probability relations among a set of random variables (nodes) in the form of a directed acyclic graph (DAG), and have found diverse applications in knowledge discovery. We study the problem of learning the sparse DAG structure of a BN from continuous observational data. The central problem can be modeled as … Read more

Distributionally Robust Chance-Constrained Programs with Right-Hand Side Uncertainty under Wasserstein Ambiguity

Published: 2020/03/29, Updated: 2020/05/28

(Mixed) Integer Linear Programming, Stochastic Programming chance constraints, distributional robustness, mixing sets, wasserstein ambiguity

We consider exact deterministic mixed-integer programming (MIP) reformulations of distributionally robust chance-constrained programs (DR-CCP) with random right-hand sides over Wasserstein ambiguity sets. The existing MIP formulations are known to have weak continuous relaxation bounds, and, consequently, for hard instances with small radius, or with a large number of scenarios, the branch-and-bound based solution processes suffer … Read more

A Polyhedral Approach to Bisubmodular Function Minimization

Published: 2020/03/12, Updated: 2020/09/28

Simge Küçükyavuz

Qimeng Yu

0-1 Programming, Cutting Plane Approaches, Polyhedra

We consider minimization problems with bisubmodular objective functions. We propose a class of valid inequalities, which we call the poly-bimatroid inequalities and prove that these inequalities, along with trivial bound constraints, fully describe the convex hull of the epigraph of a bisubmodular function. We develop a cutting plane algorithm for general bisubmodular minimization problems using … Read more

On the convexification of constrained quadratic optimization problems with indicator variables

Published: 2020/01/14

Andrés Gómez

Simge Küçükyavuz

Linchuan Wei

(Mixed) Integer Nonlinear Programming, Quadratic Programming combinatorial constraints, convexification, indicator variables, perspective formulation, quadratic programming

Motivated by modern regression applications, in this paper, we study the convexification of quadratic optimization problems with indicator variables and combinatorial constraints on the indicators. Unlike most of the previous work on convexification of sparse regression problems, we simultaneously consider the nonlinear objective, indicator variables, and combinatorial constraints. We prove that for a separable quadratic … Read more

Joint chance-constrained programs and the intersection of mixing sets through a submodularity lens

Published: 2019/10/03

Fatma Kılınç-Karzan

Simge Küçükyavuz

Dabeen Lee

(Mixed) Integer Linear Programming, Stochastic Programming chance constraints, mixing inequalities, mixing sets

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 paper, we first revisit basic mixing sets by establishing a strong and previously unrecognized connection to submodularity. In particular, we … Read more

Integer Programming for Learning Directed Acyclic Graphs from Continuous Data

Published: 2019/04/20, Updated: 2020/06/19

(Mixed) Integer Linear Programming, Statistics continuous data, directed acyclic graph, integer programming, structural learning

Learning directed acyclic graphs (DAGs) from data is a challenging task both in theory and in practice, because the number of possible DAGs scales superexponentially with the number of nodes. In this paper, we study the problem of learning an optimal DAG from continuous observational data. We cast this problem in the form of a … Read more