Home > Research > Publications & Outputs > Cutting planes for RLT relaxations of mixed 0-1...

Links

Text available via DOI:

View graph of relations

Cutting planes for RLT relaxations of mixed 0-1 polynomial programs

Research output: Contribution to journalJournal article

Published

Standard

Cutting planes for RLT relaxations of mixed 0-1 polynomial programs. / Djeumou Fomeni, Franklin; Kaparis, Konstantinos; Letchford, Adam.

In: Mathematical Programming, Vol. 151, No. 2, 2015, p. 639–658.

Research output: Contribution to journalJournal article

Harvard

APA

Vancouver

Author

Bibtex

@article{ea7fce428f694b6492c7b0437b9890f5,
title = "Cutting planes for RLT relaxations of mixed 0-1 polynomial programs",
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, quadratic knapsack problem",
author = "{Djeumou Fomeni}, Franklin and Konstantinos Kaparis and Adam Letchford",
year = "2015",
doi = "10.1007/s10107-015-0863-8",
language = "English",
volume = "151",
pages = "639–658",
journal = "Mathematical Programming",
issn = "0025-5610",
publisher = "Springer-Verlag GmbH and Co. KG",
number = "2",

}

RIS

TY - JOUR

T1 - Cutting planes for RLT relaxations of mixed 0-1 polynomial programs

AU - Djeumou Fomeni, Franklin

AU - Kaparis, Konstantinos

AU - Letchford, Adam

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

KW - polynomial optimisation

KW - cutting planes

KW - mixed-integer nonlinear programming

KW - quadratic knapsack problem

U2 - 10.1007/s10107-015-0863-8

DO - 10.1007/s10107-015-0863-8

M3 - Journal article

VL - 151

SP - 639

EP - 658

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 2

ER -