Concise RLT forms of binary programs: A computational study of the quadratic knapsack problem

Richard J. Forrester, Warren P. Adams, Paul T. Hadavas

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

The reformulation-linearization technique (RLT) is a methodology for constructing tight linear programming relaxations of mixed discrete problems. A key construct is the multiplication of "product factors" of the discrete variables with problem constraints to form polynomial restrictions, which are subsequently linearized. For special problem forms, the structure of these linearized constraints tends to suggest that certain classes may be more beneficial than others.We examine the usefulness of subsets of constraints for a family of 0-1 quadratic multidimensional knapsack programs and perform extensive computational tests on a classical special case known as the 0-1 quadratic knapsack problem. We consider RLT forms both with and without these inequalities, and their comparisons with linearizations derived from published methods. Interestingly, the computational results depend in part upon the commercial software used.

Original languageEnglish
Pages (from-to)1-12
Number of pages12
JournalNaval Research Logistics
Volume57
Issue number1
DOIs
StatePublished - Feb 2010

Scopus Subject Areas

  • Modeling and Simulation
  • Ocean Engineering
  • Management Science and Operations Research

Keywords

  • 0-1 quadratic knapsack problem
  • Linearization
  • Reformulation-linearization technique (RLT)

Fingerprint

Dive into the research topics of 'Concise RLT forms of binary programs: A computational study of the quadratic knapsack problem'. Together they form a unique fingerprint.

Cite this