precedence constrained knapsack problem

Optimal Macroitem Sequences in the Precedence Constrained Knapsack Problem

  • Valerio Dose
  • Fabio Furini
  • Marco Locatelli
    • Categories Combinatorial Optimization, Graphs and Matroids, Linear Programming Tags , , ,

    The Precedence Constrained Knapsack Problem (PCKP) asks for a maximum-profit subset of items, subject to a knapsack capacity constraint and precedence constraints encoded by a directed acyclic graph. We study the structure of optimal solutions of the Linear Programming (LP) relaxation of the natural Integer Linear Programming formulation of the PCKP. We introduce the notion … Read more

    Clique-based facets for the precedence constrained knapsack problem

  • Andreas Bley
  • Natashia Boland
  • Gary Froyland
  • Renata Sotirov
  • Christopher Fricke
    • Categories Cutting Plane Approaches Tags , ,

    We consider a knapsack problem with precedence constraints imposed on pairs of items, known as the precedence constrained knapsack problem (PCKP). This problem has applications in manufacturing and mining, and also appears as a subproblem in decomposition techniques for network design and related problems. We present a new approach for determining facets of the PCKP … Read more