Separation algorithms for 0-1 knapsack polytopes

DOI10.1007/s10107-010-0359-5zbMath1198.90297OpenAlexW2117522563WikidataQ57702190 ScholiaQ57702190MaRDI QIDQ2638369

Adam N. Letchford, Konstantinos Kaparis

Publication date: 16 September 2010

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://eprints.lancs.ac.uk/id/eprint/49749/1/10.pdf

zbMATH Keywords

integer programming cutting planes knapsack problems

Mathematics Subject Classification ID

Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

Related Items

Implicit cover inequalities, Knapsack polytopes: a survey, On the complexity of sequentially lifting cover inequalities for the knapsack polytope, The min-up/min-down unit commitment polytope, A branch-and-price-and-cut approach for sustainable crop rotation planning, Knapsack problems -- an overview of recent advances. I: Single knapsack problems, Order acceptance and scheduling problems in two-machine flow shops: new mixed integer programming formulations, Bin packing and cutting stock problems: mathematical models and exact algorithms, An implementation of exact knapsack separation, A cutting plane method for knapsack polytope, Improving problem reduction for 0-1 multidimensional knapsack problems with valid inequalities, A cutting plane algorithm for the capacitated connected facility location problem, On the complexity of separation from the knapsack polytope, Fast separation for the three-index assignment problem, Lifting the knapsack cover inequalities for the knapsack polytope, Combinatorial Benders Decomposition for the Two-Dimensional Bin Packing Problem, Novel Formulations and Logic-Based Benders Decomposition for the Integrated Parallel Machine Scheduling and Location Problem, Chance-Constrained Binary Packing Problems, A cut-and-solve based algorithm for the single-source capacitated facility location problem, A comparison of integer programming models for the partial directed weighted improper coloring problem, A cut-and-branch algorithm for the quadratic knapsack problem, Lifting for the integer knapsack cover polyhedron, Approximating polyhedra with sparse inequalities, An effective hybrid approach to the two-stage capacitated facility location problem, On the transportation problem with market choice, An improved cut-and-solve algorithm for the single-source capacitated facility location problem, A branch-and-cut algorithm for the two-echelon capacitated vehicle routing problem with grouping constraints, Recoverable robust knapsacks: the discrete scenario case, A MIP-based approach to solve the prize-collecting local access network design problem, On the exact separation of mixed integer knapsack cuts, The generalized reserve set covering problem with connectivity and buffer requirements, Ray projection for optimizing polytopes with prohibitively many constraints in set-covering column generation, Optimization algorithms for the disjunctively constrained knapsack problem, On lifted cover inequalities: a new lifting procedure with unusual properties, New valid inequalities for the fixed-charge and single-node flow polytopes, Computational Testing of a Separation Procedure for the Knapsack Set with a Single Continuous Variable, An exact separation algorithm for unsplittable flow capacitated network design arc-set polyhedron, Directed fixed charge multicommodity network design: a cutting plane approach using polar duality, Formulations and algorithms for the recoverable \({\varGamma}\)-robust knapsack problem, The incremental connected facility location problem, On the exact separation of cover inequalities of maximum-depth

Uses Software

Cites Work