Improving a Formulation of the Quadratic Knapsack Problem

  • Daniel Grainger
  • Adam N. Letchford
    • Categories 0-1 Programming Tags , Short URL: https://optimization-online.org/?p=10154

    The Quadratic Knapsack Problem can be formulated, using an idea of Glover, as a mixed 0-1 linear program with only 2n variables. We present a simple method for strengthening that formulation, which gives good results when the profit matrix is dense and non-negative.

    Citation

    Working Paper, Department of Management Science, Lancaster University, May 2007.

    Article

    Download

    View Improving a Formulation of the Quadratic Knapsack Problem