Final published version
Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
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 -