12,000

We have over 12,000 students, from over 100 countries, within one of the safest campuses in the UK

93%

93% of Lancaster students go into work or further study within six months of graduating

Home > Research > Publications & Outputs > Separation algorithms for 0-1 knapsack polytopes
View graph of relations

« Back

Separation algorithms for 0-1 knapsack polytopes

Research output: Contribution to journalJournal article

Published

Journal publication date07/2010
JournalMathematical Programming
Journal number1-2
Volume124
Number of pages23
Pages69-91
Early online date8/05/10
Original languageEnglish

Abstract

Valid inequalities for 0-1 knapsack polytopes often prove useful when tackling
hard 0-1 Linear Programming problems. To generate such inequalities, one needs separation algorithms for them, i.e., routines for detecting when they are violated. We present new exact and heuristic separation algorithms for several classes of inequalities, namely lifted cover, extended cover, weight and lifted pack inequalities. Moreover, we show how to improve a recent separation algorithm for the 0-1 knapsack polytope itself. Extensive computational results, on MIPLIB and OR Library instances, show the strengths and limitations of the inequalities and algorithms considered.