Clique-based facets for the precedence constrained knapsack problem

DOI10.1007/S10107-010-0438-7zbMath1259.90071OpenAlexW2141422661WikidataQ59139576 ScholiaQ59139576MaRDI QIDQ431007

Renata Sotirov, Gary Froyland, Christopher Fricke, Andreas Bley, Natashia Boland

Publication date: 26 June 2012

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

Full work available at URL: https://doi.org/10.1007/s10107-010-0438-7

zbMATH Keywords

clique inequalitiesprecedence constrained knapsack problem

Mathematics Subject Classification ID

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

Related Items (9)

Subset sum problems with digraph constraints ⋮ Primal-Dual Algorithms for Precedence Constrained Covering Problems ⋮ Knapsack problems -- an overview of recent advances. I: Single knapsack problems ⋮ Primal-dual algorithms for precedence constrained covering problems ⋮ The knapsack problem with neighbour constraints ⋮ The precedence constrained knapsack problem: separating maximally violated inequalities ⋮ A strengthened formulation and cutting planes for the open pit mine production scheduling problem ⋮ A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts ⋮ Capacitated multi-layer network design with unsplittable demands: polyhedra and branch-and-cut

Uses Software

• Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lifting cover inequalities for the precedence-constrained knapsack problem
• Polyhedral results for the precedence-constrained knapsack problem
• An application of branch and cut to open pit mine scheduling
• Lifting valid inequalities for the precedence constrained knapsack problem
• A strengthened formulation and cutting planes for the open pit mine production scheduling problem
• Conflict analysis in mixed integer programming
• Approximation Algorithms for Certain Scheduling Problems
• Disjunctive Programming
• On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees
• Routing and Capacity Optimization for IP Networks

This page was built for publication: Clique-based facets for the precedence constrained knapsack problem