Tag Archives: lp relaxations

Knapsack formulations

Integer programming is all about formulations. Preferably tight formulations. I will show you here two equivalent formulations of the famous knapsack problem. Knapsack problem: Given a set of weights of objects, a knapsack of capacity and  values select a subset of objects such that their total weight is less than and the total value is maximized. Let’s […]