Tightening concise linear reformulations of 0-1 cubic programs. (2nd April 2016)

• Record Type: Journal Article
• Authors: Forrester, Richard J.
• Is Part Of: Optimization. Volume 65:Number 4(2016)
• Page Start: 877
• Page End: 903
• Publication Date: 2016-04-02
• Subjects: 0-1 cubic program -- linearization -- reformulation-linearization technique (RLT); 90C30 -- 90C11; Mathematical optimization -- Periodicals; 519.7
• DOI: 10.1080/02331934.2015.1091821
• Languages: English
• ISSNs: 0233-1934

Abstract

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.