Title
Tightening Concise Linear Reformulations of 0-1 Cubic Programs
Document Type
Article
Publication Date
2016
Department
Mathematics
Language
English
Publication Title
Optimization
Abstract
A common strategy for solving 0-1 cubic programs is to reformulate the non-linear problem into an equivalent linear representation, which can then be submitted directly to a standard mixed-integer programming solver. Both the size and the strength of the continuous relaxation of the reformulation determine the success of this method. One of the most compact linear representations of 0-1 cubic programs is based on a repeated application of the linearization technique for 0-1 quadratic programs introduced by Glover. In this paper, we develop a pre-processing step that serves to strengthen the linear programming bound provided by this concise linear form of a 0-1 cubic program. The proposed scheme involves using optimal dual multipliers of a partial level-2 RLT formulation to rewrite the objective function of the cubic program before applying the linearization. We perform extensive computational tests on the 0-1 cubic multidimensional knapsack problem to show the advantage of our approach.
DOI
10.1080/02331934.2015.1091821
Recommended Citation
Forrester, Richard J. "Tightening Concise Linear Reformulations of 0-1 Cubic Programs." Optimization 65, no. 4 (2016): 877-903.
Comments
For more information on the published version, visit Taylor and Francis's Website.