Optimization Online


Cutting Planes for RLT Relaxations of Mixed 0-1 Polynomial Programs

Franklin Djeumou Fomeni (F.DjeumouFomeni***at***lancaster.ac.uk)
Konstantinos Kaparis (K.Kaparis***at***lancaster.ac.uk)
Adam N Letchford (A.N.Letchford***at***lancaster.ac.uk)

Abstract: The Reformulation-Linearization Technique (RLT), due to Sherali and Adams, can be used to construct hierarchies of linear programming relaxations of mixed 0-1 polynomial programs. As one moves up the hierarchy, the relaxations grow stronger, but the number of variables increases exponentially. We present a procedure that generates cutting planes at any given level of the hierarchy, by optimally weakening linear inequalities that are valid at any given higher level. Computational experiments, conducted on instances of the quadratic knapsack problem, indicate that the cutting planes can close a significant proportion of the integrality gap.

Keywords: polynomial optimisation, cutting planes, mixed-integer nonlinear programming

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

Category 2: Global Optimization

Citation: Eventually published as: F. Djeumou Fomeni, K. Kaparis & A.N. Letchford (2015) Cutting planes for RLT relaxations of mixed 0-1 polynomial programs. Math. Program., 151(2), 639658.


Entry Submitted: 01/14/2014
Entry Accepted: 01/14/2014
Entry Last Modified: 05/19/2015

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