Clique-based facets for the precedence constrained knapsack problem
The authors present a novel approach for determining facets of the precedence constrained knapsack problem (PCKP) based on clique inequalities. The PCKP is an NP-hard combinatorial optimization problem that finds many interesting applications especially in manufacturing and mining. The main idea is to investigate clique inequalities derived from a directed graph representing pairwise conflict relationships between the integer variables and derive necessary and sufficient conditions under which they represent the convex hull of the associated PCKP polyhedron. There is presented as well a comparison between the previous defined covers and cliques in the conflict graph. In the last part of the paper, there are described applications of the clique-based inequalities in the case of some PCKP examples, showing their relative strengthening effect on the LP relaxation. Computational results are reported in the case of two classes of instances, demonstrating benefits of using the clique constraints to realistic problems, with respect to the reduction of the solution times.
- 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
- 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
- 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?)
- 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
- Polyhedral results for the precedence-constrained knapsack problem
- Subset sum problems with digraph constraints
- The knapsack problem with neighbour constraints
- A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts
- Knapsack problems -- an overview of recent advances. I: Single knapsack problems
- The clique problem with multiple-choice constraints under a cycle-free dependency graph
- A strengthened formulation and cutting planes for the open pit mine production scheduling problem
- Capacitated multi-layer network design with unsplittable demands: polyhedra and branch-and-cut
- A pegging approach to the precedence-constrained knapsack problem
- Primal-dual algorithms for precedence constrained covering problems
- Primal-dual algorithms for precedence constrained covering problems
- The precedence constrained knapsack problem: separating maximally violated inequalities
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)
