If I were to solve the linear relaxation of a knapsack problem via column generation how could I model the master problem and pricing subproblem? Given a set $N$ of items with value $v_{i}$ and weight $w_{i}$ ($i \in N$) and maximum capacity $W$, I was thinking of doing:

$$max \sum_{s \in 2^{N}} p_{s}\lambda_{s}$$

Subject to:

$$\sum_{s \in 2^{N}}\lambda_{s} = 1$$

$$\lambda_{s} \in \{0,1\} \forall s \in 2^{N}$$

This way, each column would be a subset $s$ of the items. I think the pricing subproblem would be another knapsack problem, defined like this ($u$ is the dual value of the above constraint):

$$ max \sum_{i \in N} (v_{i} - uw_{i})x_{i}$$

Subject to:

$$ \sum_{i \in N} w_{i}x_{i} \leq W$$

Is this idea correct? If not how can I correct it? If it's not possible to solve the knapsack this way, are there any other very simple problems that can be solved using column generation? I'm trying to learn how to implement a branch and price algorithm and to grasp the main concepts I decided to solve a very simple problem like the knapsack.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.