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's gravatar image

accept rate: 0%

edited 21 Jul '14, 12:07

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

(21 Jul '14, 12:07) Chivalry

Sure, why not?

(23 Jul '14, 08:26) Austin Buchanan

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%20Luebbecke's gravatar image

Marco Luebbecke ♦
accept rate: 16%

Your answer
toggle preview

Follow this question

By Email:

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



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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



Asked: 21 Jul '14, 10:54

Seen: 956 times

Last updated: 23 Jul '14, 21:25

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