Simge Küçükyavuz

SDDmiP.jl: A Software Package with a Provably Convergent Benders Algorithm for Multi-Stage Stochastic Mixed-Integer Programming

Categories Optimization Software and Modeling Systems, Stochastic Programming Tags , , , , , ,

We present an open-source software package that implements a provably convergent Benders-type decomposition algorithm for multistage stochastic integer programs. In addition to standard cut families, such as Benders, strengthened Benders, and Lagrangian cuts, the algorithm incorporates rectified linear unit (ReLU) cuts, which provide convergence guarantees for general mixed-integer state variables. However, the dual problems used … Read more

Coordinate Optimality Reformulation for Mixed-Integer Convex Programs with Indicators

Categories (Mixed) Integer Nonlinear Programming, Quadratic Programming Tags , ,

We consider mixed-integer convex optimization problems in which binary indicators control continuous variables. We introduce the Coordinate Optimality Reformulation (CORe) framework, which augments standard indicator formulations by incorporating coordinate-wise optimality information. The resulting reformulations preserve global optimality while substantially improving branch-and-bound performance, particularly in sparse and structured settings where the coordinate-wise optimality conditions expose exploitable … Read more

Solving Convex Quadratic Optimization with Indicators Over Structured Graphs

Categories (Mixed) Integer Nonlinear Programming, Dynamic Programming Tags ,

This paper studies convex quadratic minimization problems in which each continuous variable is coupled with a binary indicator variable. We focus on the structured setting where the Hessian matrix of the quadratic term is positive definite and exhibits sparsity. We develop an exact parametric dynamic programming algorithm whose computational complexity depends explicitly on the treewidth … Read more

Normalization of ReLU Dual for Cut Generation in Stochastic Mixed-Integer Programs

Categories Stochastic Programming Tags , ,

We study the Rectified Linear Unit (ReLU) dual, an existing dual formulation for stochastic programs that reformulates non-anticipativity constraints using ReLU functions to generate tight, non-convex, and mixed-integer representable cuts. While this dual reformulation guarantees convergence with mixed-integer state variables, it admits multiple optimal solutions that can yield weak cuts. To address this issue, we … Read more

An Asymptotically Optimal Coordinate Descent Algorithm for Learning Bayesian Networks from Gaussian Models

Categories (Mixed) Integer Nonlinear Programming

This paper studies the problem of learning Bayesian networks from continuous observational data, generated according to a linear Gaussian structural equation model. We consider an \(\ell_0\)-penalized maximum likelihood estimator for this problem which is known to have favorable statistical properties but is computationally challenging to solve, especially for medium-sized Bayesian networks. We propose a new … Read more

A computational study of cutting-plane methods for multi-stage stochastic integer programs

Categories Stochastic Programming Tags , ,

We report a computational study of cutting plane algorithms for multi-stage stochastic mixed-integer programming models with the following cuts: (i) Benders’, (ii) Integer L-shaped, and (iii) Lagrangian cuts. We first show that Integer L-shaped cuts correspond to one of the optimal solutions of the Lagrangian dual problem, and, therefore, belong to the class of Lagrangian … Read more

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

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

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

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