Simge Küçükyavuz

A Parametric Approach for Solving Convex Quadratic Optimization with Indicators Over Trees

  • Aaresh Bhathena
  • Salar Fattahi
  • Andrés Gómez
  • Simge Küçükyavuz
    • Categories (Mixed) Integer Nonlinear Programming, Dynamic Programming, Quadratic Programming Tags , , , , ,

    This paper investigates convex quadratic optimization problems involving $n$ indicator variables, each associated with a continuous variable, particularly focusing on scenarios where the matrix $Q$ defining the quadratic term is positive definite and its sparsity pattern corresponds to the adjacency matrix of a tree graph. We introduce a graph-based dynamic programming algorithm that solves this … Read more

    Polyhedral Analysis of Quadratic Optimization Problems with Stieltjes Matrices and Indicators

  • Peijing Liu
  • Alper Atamturk
  • Andrés Gómez
  • Simge Küçükyavuz
    • Categories (Mixed) Integer Nonlinear Programming Tags , , , ,

    In this paper, we consider convex quadratic optimization problems with indicators on the continuous variables. In particular, we assume that the Hessian of the quadratic term is a Stieltjes matrix, which naturally appears in sparse graphical inference problems and others. We describe an explicit convex formulation for the problem by studying the Stieltjes polyhedron arising … Read more

    An outer approximation method for solving mixed-integer convex quadratic programs with indicators

  • Linchuan Wei
  • Simge Küçükyavuz
    • Categories (Mixed) Integer Nonlinear Programming, Quadratic Programming Tags , ,

    Mixed-integer convex quadratic programs with indicator variables (MIQP) encompass a wide range of applications, from statistical learning to energy, finance, and logistics. The outer approximation (OA) algorithm has been proven efficient in solving MIQP, and the key to the success of an OA algorithm is the strength of the cutting planes employed. In this paper, … Read more

    Mixed-Integer Programming for a Class of Robust Submodular Maximization Problems

  • Hsin-Yi Huang
  • Hao-Hsiang Wu
  • Simge Küçükyavuz
    • Categories (Mixed) Integer Linear Programming, Robust Optimization, Stochastic Programming

    \(\) We consider robust submodular maximization problems (RSMs), where given a set of \(m\) monotone submodular objective functions, the robustness is with respect to the worst-case (scaled) objective function. The model we consider generalizes two variants of robust submodular maximization problems in the literature, depending on the choice of the scaling vector. On one hand, by … Read more

    Mixed-Integer Programming Approaches to Generalized Submodular Optimization and its Applications

  • Simge Küçükyavuz
  • Qimeng Yu
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches Tags , , ,

    Submodularity is an important concept in integer and combinatorial optimization. A classical submodular set function models the utility of selecting homogenous items from a single ground set, and such selections can be represented by binary variables. In practice, many problem contexts involve choosing heterogenous items from more than one ground set or selecting multiple copies … Read more

    On Constrained Mixed-Integer DR-Submodular Minimization

  • Qimeng Yu
  • Simge Küçükyavuz
    • Categories (Mixed) Integer Nonlinear Programming, Polyhedra Tags , , ,

    DR-submodular functions encompass a broad class of functions which are generally non-convex and non-concave. We study the problem of minimizing any DR-submodular function, with continuous and general integer variables, under box constraints and possibly additional monotonicity constraints. We propose valid linear inequalities for the epigraph of any DR-submodular function under the constraints. We further provide … Read more

    On the convex hull of convex quadratic optimization problems with indicators

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

    We consider the convex quadratic optimization problem with indicator variables and arbitrary constraints on the indicators. We show that a convex hull description of the associated mixed-integer set in an extended space with a quadratic number of additional variables consists of a single positive semidefinite constraint (explicitly stated) and linear constraints. In particular, convexification of … Read more

    A Graph-based Decomposition Method for Convex Quadratic Optimization with Indicators

  • Peijing Liu
  • Salar Fattahi
  • Andrés Gómez
  • Simge Küçükyavuz
    • Categories (Mixed) Integer Nonlinear Programming, Statistics Tags , , , , , ,

    In this paper, we consider convex quadratic optimization problems with indicator variables when the matrix Q defining the quadratic term in the objective is sparse. We use a graphical representation of the support of Q, and show that if this graph is a path, then we can solve the associated problem in polynomial time. This … Read more

    Strong valid inequalities for a class of concave submodular minimization problems under cardinality constraints

  • Simge Küçükyavuz
  • Qimeng Yu
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Polyhedra Tags , ,

    We study the polyhedral convex hull structure of a mixed-integer set which arises in a class of cardinality-constrained concave submodular minimization problems. This class of problems has an objective function in the form of $f(a^\top x)$, where $f$ is a univariate concave function, $a$ is a non-negative vector, and $x$ is a binary vector of … Read more

    Chance-Constrained Optimization under Limited Distributional Information: A Review of Reformulations Based on Sampling and Distributional Robustness

  • Simge Küçükyavuz
  • Ruiwei Jiang
    • Categories Stochastic Programming Tags , , ,

    Chance-constrained programming (CCP) is one of the most difficult classes of optimization problems that has attracted the attention of researchers since the 1950s. In this survey, we focus on cases when only a limited information on the distribution is available, such as a sample from the distribution, or the moments of the distribution. We first … Read more