Clique-based facets for the precedence constrained knapsack problem

DOI10.1007/S10107-010-0438-7zbMATH Open1259.90071OpenAlexW2141422661WikidataQ59139576 ScholiaQ59139576MaRDI QIDQ431007FDOQ431007

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

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

zbMATH Keywords

clique inequalitiesprecedence constrained knapsack problem

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (12)

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

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)