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.

Comments

For more information on the published version, visit Taylor and Francis's Website.

DOI

10.1080/02331934.2015.1091821

Full text currently unavailable.

COinS