  


Separation Algorithms for 01 Knapsack Polytopes
Konstantinos Kaparis (k.kaparissoton.ac.uk) Abstract: Valid inequalities for 01 knapsack polytopes often prove useful when tackling hard 01 Linear Programming problems. To use such inequalities effectively, one needs separation algorithms for them, i.e., routines for detecting when they are violated. We show that the separation problems for the socalled extended cover and weight inequalities can be solved exactly in O(nb) time and O((n + a_max)b) time, respectively, where n is the number of items, b is the knapsack capacity and a_max is the largest item weight. We also present fast and effective separation heuristics for the extended cover and lifted cover inequalities. Finally, we present a new exact separation algorithm for the 01 knapsack polytope itself, which is faster than existing methods. Extensive computational results are also given. Keywords: integer programming, branchandcut, knapsack problems Category 1: Integer Programming (01 Programming ) Category 2: Integer Programming (Cutting Plane Approaches ) Category 3: Combinatorial Optimization (Polyhedra ) Citation: K. Kaparis & A.N. Letchford (2010) Separation algorithms for 01 knapsack polytopes. Math. Program., 124(12), 6991. Download: Entry Submitted: 06/07/2007 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  