# Integral formulation for knackpack

 2 1 I heard that Ising model problem could be converted into a knack pack problem... Is there a integral formulation for the knackpack polytope so that it could be efficiently solved the same way as traveler sales man? Thank you :) I think one important aspect is that the converted knackpack problem should allow negative weight and negative cost... asked 21 Jul '14, 10:54 Chivalry 229●2●18 accept rate: 0% 1 Here's the standard formulation for 0-1 knapsack. (21 Jul '14, 12:01) Austin Buchanan Does it allow negative weight and negative cost? thank you:D (21 Jul '14, 12:07) Chivalry 1 Sure, why not? (23 Jul '14, 08:26) Austin Buchanan

 4 Theoretically, the convex hull of incidence vectors of feasible knapsack packings is an integral polytope, that is, its vertices have integer coordinates. If you had a linear description of this polytope, i.e., given as linear constraints, you only needed to solve an LP in order to get an integral solution. So far, this applies to any (in particular hard) discrete optimization problem. In practice, we usually do not have this formulation, and complexity theory tells us that (this is handwaving now) we will not "get" such a formulation for hard problems. Pushing this aside: there is a way to formulate the knapsack problem as a linear program which has integral basic solutions: there is a network flow formulation for knapsack. Essentially, you are sending one unit of flow (= look for a shortest path) in a network, where node represent "the amount of capacity used" and arcs represent whether or not items are packed. This is not a polynomial formulation since it uses as many nodes as the size of the capacity is. Still, since it is a network flow formulations, the verticec of the corresponding polytope is integral. Don't know if this is what you are looking for. answered 23 Jul '14, 21:25 Marco Luebbecke ♦ 3.4k●1●6●15 accept rate: 16%
 toggle preview community wiki

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags:

Asked: 21 Jul '14, 10:54

Seen: 815 times

Last updated: 23 Jul '14, 21:25

### Related questions

OR-Exchange! Your site for questions, answers, and announcements about operations research.