Optimization Online


Scoring positive semidefinite cutting planes for quadratic optimization via trained neural networks

Radu Baltean-Lugojan (rb2309***at***imperial.ac.uk)
Pierre Bonami (pierre.bonami***at***es.ibm.com)
Ruth Misener (r.misener***at***imperial.ac.uk)
Andrea Tramontani (andrea.tramontani***at***it.ibm.com)

Abstract: Semidefinite programming relaxations complement polyhedral relaxations for quadratic optimization, but global optimization solvers built on polyhedral relaxations cannot fully exploit this advantage. This paper develops linear outer-approximations of semidefinite constraints that can be effectively integrated into global solvers. The difference from previous work is that our proposed cuts are (i) sparser with respect to the number of nonzeros in the row and (ii) explicitly selected to improve the objective. We select which cuts to generate using objective structure and explore engineering trade-offs for sparsity patterns, e.g. cut dimensionality and chordal extensions. A neural network estimator is key to our cut selection strategy: ranking each cut based on objective improvement involves solving a semidefinite optimization problem, but this is an expensive proposition at each Branch&Cut node. The neural network estimator, trained a priori of any instance to solve, takes the computation offline by predicting the objective improvement for any cut. Most of this paper discusses quadratic programming with box constraints as a test bed for the relevant engineering trade-offs. We also show how the engineering decisions may immediately extend to quadratically constrained instances, particularly ones with rich quadratic objective structure.

Keywords: mixed-integer nonlinear programming, quadratic programming, cutting planes, convex and semidefinite relaxations, neural networks, cut selection

Category 1: Global Optimization

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 3: Nonlinear Optimization (Quadratic Programming )

Citation: November 2019

Download: [PDF]

Entry Submitted: 11/26/2018
Entry Accepted: 11/26/2018
Entry Last Modified: 11/19/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society