Santanu S. Dey

Strengthening AC optimal power flow relaxation through offline bound tightening and linear approximations

Xiangxin An, Constance Crozier, Santanu S. Dey

The alternating-current optimal power flow (ACOPF) problem is fundamental to power system operation and planning, but its nonconvexity makes globally optimal solutions of large-sca…

math.PR2026

Vertex crossings in a symmetric Markov multinomial model

Arjun Pemmasani

We observe a ball bouncing down a Galton board with any number of directions. At each peg it either keeps its direction with some fixed probability or randomly turns to one of the…

Copositive Matrices with Ordered Off-Diagonal Entries

Grigoriy Blekherman, Santanu S. Dey, Alex Dunbar +1

We study copositive matrices which admit a decomposition into a sum of a positive semidefinite matrix and a matrix with nonnegative entries. Our main result shows that if the off-d…

Probabilistic analysis of dual decomposition on two-stage stochastic integer programs

Santanu S. Dey, Marco Molinaro, Jingye Xu

Two-stage stochastic integer programs provide a powerful framework for modeling decision-making under uncertainty, but they are notoriously difficult to solve at scale due to their…

Accelerating Column Generation in Highly Degenerate Integer Programming Problems with Template Pricing

Luke Marshall, Prachi Shah, Santanu S. Dey

We propose a new pricing strategy for column generation (CG), referred to as Template pricing. This method is motivated by the desire to coordinate solutions of different pricing s…

Chvátal-Gomory Rounding of Eigenvector Inequalities for QCQPs

Santanu S. Dey, Nan Jiang, Aleksandr Kazachkov +2

We introduce and analyze a class of valid inequalities for nonconvex quadratically constrained optimization problems (QCQPs) which we call Eigen-CG inequalities. These inequalities…

Asymptotically tight Lagrangian dual of smooth nonconvex problems via improved error bound of Shapley-Folkman Lemma

Santanu S Dey, Jingye Xu

In convex geometry, the Shapley-Folkman Lemma asserts that the nonconvexity of a Minkowski sum of $n$ dimensional bounded nonconvex sets does not accumulate once the number of summ…

Change-Point Detection via Piecewise Linear Fitting Using MIP

Apoorva Narula, Santanu S. Dey, Yao Xie

We present a new mixed-integer programming (MIP) approach for offline multiple change-point detection by casting the problem as a globally optimal piecewise linear (PWL) fitting pr…

Strengthening Dual Bounds for Multicommodity Capacitated Network Design with Unsplittable Flow Constraints

Lacy M. Greening, Santanu S. Dey, Alan L. Erera

Multicommodity capacitated network design (MCND) models can be used to optimize the consolidation of shipments within e-commerce fulfillment networks. In practice, fulfillment netw…

Extreme Strong Branching for QCQPs

Santanu S. Dey, Dahye Han, Yang Wang

For mixed-integer programs (MIPs), strong branching is a highly effective variable selection method to reduce the number of nodes in the branch-and-bound algorithm. Extending it to…

Convexification of a Separable Function over a Polyhedral Ground Set

Santanu S. Dey, Burak Kocuk

In this paper, we study the set $S^{κ} = {(x, y) \in G \times R^{n} : y_{j} = x_{j}^{κ}, j = 1, \dots, n}$ , where $κ > 1$ and the ground set $G$ is a nonempty…

Geoffrion's theorem beyond finiteness and rationality

Santanu S. Dey, Frédéric Meunier, Diego Moran Ramirez

Geoffrion's theorem is a fundamental result from mathematical programming assessing the quality of Lagrangian relaxation, a standard technique to get bounds for integer programs. A…

A second-order cone representable class of nonconvex quadratic programs

Santanu S. Dey, Aida Khajavirad

We consider the problem of minimizing a sparse nonconvex quadratic function over the unit hypercube. By developing an extension of the Reformulation-Linearization Technique (RLT) t…

Improving Full Strong Branching Decisions by Incorporating Additional Information

Prachi Shah, Santanu S. Dey

The full strong branching (FSB) rule is well known to produce extremely small branch-and-bound trees. This rule guides branching decisions based exclusively on the information rega…

math.OA2024

On the rank of extremal marginal states

Repana Devendra, Pankaj Dey, Santanu Dey

Let $ρ_{1}$ and $ρ_{2}$ be two states on $C^{d_{1}}$ and $C^{d_{2}}$ respectively. The marginal state space, denoted by $C (ρ_{1}, ρ_{2})$ , is the set of all states $…

Approximating the Gomory Mixed-Integer Cut Closure Using Historical Data

Berkay Becu, Santanu S. Dey, Feng Qiu +1

Many operations related optimization problems involve repeatedly solving similar mixed integer linear programming (MILP) instances with the same constraint matrix but differing obj…

Lagrangian dual with zero duality gap that admits decomposition

Diego Cifuentes, Santanu S. Dey, Jingye Xu

For mixed integer programs (MIPs) with block structures and coupling constraints, on dualizing the coupling constraints the resulting Lagrangian relaxation becomes decomposable int…

Aggregation of Bilinear Bipartite Equality Constraints and its Application to Structural Model Updating Problem

Santanu S Dey, Dahye Han, Yang Wang

In this paper, we study the strength of convex relaxations obtained by convexification of aggregation of constraints for a set $S$ described by two bilinear bipartite equalities. A…