Simge Küçükyavuz

Ideal formulations for constrained convex optimization problems with indicator variables.

  • Andrés Gómez
  • Simge Küçükyavuz
  • Linchuan Wei
    • Categories (Mixed) Integer Nonlinear Programming, Semi-definite Programming Tags , , ,

    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

  • Simge Küçükyavuz
  • Ali Shojaie
  • Hasan Manzour
  • Linchuan Wei
  • Hao-Hsiang Wu
    • Categories (Mixed) Integer Nonlinear Programming, Data-Mining, Network Optimization Tags , , , ,

    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

  • Nam Ho-Nguyen
  • Fatma Kılınç-Karzan
  • Simge Küçükyavuz
  • Dabeen Lee
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , , ,

    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

  • Simge Küçükyavuz
  • Qimeng Yu
    • Categories 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

  • Andrés Gómez
  • Simge Küçükyavuz
  • Linchuan Wei
    • Categories (Mixed) Integer Nonlinear Programming, Quadratic Programming Tags , , , ,

    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

  • Fatma Kılınç-Karzan
  • Simge Küçükyavuz
  • Dabeen Lee
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , ,

    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

  • Simge Küçükyavuz
  • Hasan Manzour
  • Ali Shojaie
  • Hao-Hsiang Wu
    • Categories (Mixed) Integer Linear Programming, Statistics Tags , , ,

    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

    An Exact Method for Constrained Maximization of the Conditional Value-at-Risk of a Class of Stochastic Submodular Functions

  • Simge Küçükyavuz
  • Hao-Hsiang Wu
    • Categories Integer Programming, Stochastic Programming

    We consider a class of risk-averse submodular maximization problems (RASM) where the objective is the conditional value-at-risk (CVaR) of a random nondecreasing submodular function at a given risk level. We propose valid inequalities and an exact general method for solving RASM under the assumption that we have an efficient oracle that computes the CVaR of … Read more

    Risk Aversion to Parameter Uncertainty in Markov Decision Processes with an Application to Slow-Onset Disaster Relief

  • Simge Küçükyavuz
  • Merve Merakli
    • Categories Integer Programming, Stochastic Programming, Supply Chain Management Tags , , , , ,

    In classical Markov Decision Processes (MDPs), action costs and transition probabilities are assumed to be known, although an accurate estimation of these parameters is often not possible in practice. This study addresses MDPs under cost and transition probability uncertainty and aims to provide a mathematical framework to obtain policies minimizing the risk of high long-term … Read more

    On Intersection of Two Mixing Sets with Applications to Joint Chance-Constrained Programs

  • Fatma Kılınç-Karzan
  • Simge Küçükyavuz
  • Xiao Liu
    • Categories Integer Programming, Stochastic Programming

    We study the polyhedral structure of a generalization of a mixing set described by the intersection of two mixing sets with two shared continuous variables, where one continuous variable has a positive coefficient in one mixing set, and a negative coefficient in the other. Our developments are motivated from a key substructure of linear joint … Read more