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 language | English |
---|---|
Pages (from-to) | 1-12 |
Number of pages | 12 |
Journal | Naval Research Logistics |
Volume | 57 |
Issue number | 1 |
DOIs | |
State | Published - 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)