Clique-based facets for the precedence constrained knapsack problem

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

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

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

Cites Work

• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (9)

• Primal-dual algorithms for precedence constrained covering problems
• Capacitated multi-layer network design with unsplittable demands: polyhedra and branch-and-cut
• 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
• 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

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)