16 papers
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…
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…
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…
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…