Clique-based facets for the precedence constrained knapsack problem

DOI10.1007/S10107-010-0438-7MaRDI QIDQ431007zbMATH OpenOpenAlexWikidataFDO

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

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

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

Recommendations

• Polyhedral results for the precedence-constrained knapsack problem
• Primal-dual algorithms for precedence constrained covering problems
• Lifting valid inequalities for the precedence constrained knapsack problem
• Lifting cover inequalities for the precedence-constrained knapsack problem
• A pegging approach to the precedence-constrained knapsack problem

Cites work

• scientific article; zbMATH DE number 6118217 (Why is no real title available?)
• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A strengthened formulation and cutting planes for the open pit mine production scheduling problem
• An application of branch and cut to open pit mine scheduling
• Approximation Algorithms for Certain Scheduling Problems
• Conflict analysis in mixed integer programming
• Disjunctive Programming
• Lifting cover inequalities for the precedence-constrained knapsack problem
• Lifting valid inequalities for the precedence constrained knapsack problem
• On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees
• Polyhedral results for the precedence-constrained knapsack problem
• Routing and capacity optimization for IP networks

Cited in

(12)

• Primal-dual algorithms for precedence constrained covering problems
• The precedence constrained knapsack problem: separating maximally violated inequalities
• Capacitated multi-layer network design with unsplittable demands: polyhedra and branch-and-cut
• Primal-dual algorithms for precedence constrained covering problems
• The clique problem with multiple-choice constraints under a cycle-free dependency graph
• Polyhedral results for the precedence-constrained knapsack problem
• Subset sum problems with digraph constraints
• A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts
• The knapsack problem with neighbour constraints
• A strengthened formulation and cutting planes for the open pit mine production scheduling problem
• A pegging approach to the precedence-constrained knapsack problem
• Knapsack problems -- an overview of recent advances. I: Single knapsack problems

Describes a project that uses

Uses Software

• SCIP

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q431007)