relaxations

Exact Approaches for the Knapsack Problem with Setups

  • Fabio Furini
  • Michele Monaci
  • Emiliano Traversi
    • Categories 0-1 Programming, Integer Programming Tags , , , ,

    We consider a generalization of the knapsack problem in which items are partitioned into classes, each characterized by a fixed cost and capacity. We study three alternative Integer Linear Programming formulations. For each formulation, we design an efficient algorithm to compute the linear programming relaxation (one of which is based on Column Generation techniques). We … Read more

    Solving Lift-and-Project Relaxations of Binary Integer Programs

  • Samuel Burer
  • Dieter Vandenbussche
    • Categories 0-1 Programming, Linear, Cone and Semidefinite Programming Tags , , , ,

    We propose a method for optimizing the lift-and-project relaxations of binary integer programs introduced by Lov\’asz and Schrijver. In particular, we study both linear and semidefinite relaxations. The key idea is a restructuring of the relaxations, which isolates the complicating constraints and allows for a Lagrangian approach. We detail an enhanced subgradient method and discuss … Read more