7 papers
Exact Verification of First-Order Methods via Mixed-Integer Linear Programming
Vinit Ranjan, Jisun Park, Stefano Gualandi +2
We present exact mixed-integer linear programming formulations for verifying the performance of first-order methods for parametric quadratic optimization. We formulate the verifica…
From Sequential Nodes to GPU Batches: Parallel Branch and Bound for Optimal -Sparse GLMs
Jiachang Liu, Andrea Lodi
GPUs have significantly accelerated first-order methods for large-scale optimization, especially in continuous optimization. However, this success has not transferred cleanly to pr…
Solving Max-Cut to Global Optimality via Feasibility-Preserving Graph Neural Networks
Hao Chen, Chendi Qian, Christopher Morris +2
Exact solution of hard combinatorial optimization problems often relies on strong convex relaxations, but solving these relaxations repeatedly inside a branch-and-bound algorithm c…
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…
Hardness of some optimization problems over correlation polyhedra
Alberto Caprara, Fabio Furini, Claudio Gentile +2
We prove the \textbf{NP}-hardness, using Karp reductions, of some problems related to the correlation polytope and its corresponding cone, spanned by all of the rank-on…
Sparse Cuts for the Positive Semidefinite Cone
Oktay Günlük, Paul Jünger, Jeff Linderoth +2
We consider optimization problems containing nonconvex quadratic functions for which semidefinite programming (SDP) relaxations often yield strong bounds. We investigate linear ine…