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
Chivalry |

Theoretically, the convex hull of incidence vectors of feasible knapsack packings is an integral polytope, that is, its vertices have integer coordinates. If you 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 Don't know if this is what you are looking for.
answered
Marco Luebbecke ♦ |

Here's the standard formulation for 0-1 knapsack.

Does it allow negative weight and negative cost? thank you:D

Sure, why not?