A Multichoice Knapsack problem variant?

2012-06-11T10:15:28Z

Hi All,

my problem is a variant of menu-selection-multiple-choice-knapsack-problem. We have to select a meal of $N$ courses (one dish for every course) s.t. calorie count $k$ is minimized, whereas we remain within the specified budget $S$ and total selection should have at least a weight of $L$ kg.

So every dish has 4 parameters:

course $(i)$ e.g. main dish, dessert, etc. Total courses: $m$ namely: $\{N_1,N_2,N_3,...,N_m \}$
price $(s)$
weight $(l)$
calorie count $(k)$.

So the problem is:

$minimize: \sum_{i=1} ^m \sum_{j \in N_i} k_{ij} x_{ij} $

s.t.

$\sum_{i=1} ^m \sum_{j \in N_i} l_{ij} x_{ij} \ge L,$
$\sum_{i=1} ^m \sum_{j \in N_i} s_{ij} x_{ij} \le S,$
$x_{ij} \in \{ 0,1 \}, \quad i=1,...,m, \quad j \in N_i,$
$\sum_{j \in N_i} x_{ij} = 1 \quad \quad i=1,...,m.$

this can be read as:

Total weight should at least be $L$
Total price should be at most $S$
A dish cannot be partially (fractionally) selected
at least one dish should be selected for each course.

I tried solving the problem with following dynamic programming. But, I got stuck at implementing weight constraint. Budget constraint is easier i.e. till the remaining budget is more than the price of dish, we can consider the dish. But what to do with Weight constraint? specially because its "greater than" and not "less than". Any help/pointer here?

for i in all courses upto m do
    for s in all budgets upto S do
        for l in all Weights upto L do
            for j in all dishes belonging to i do
                s_pr = price of j
                l_pr = weight of j
                k_pr = calorie count of j
                if s >= s_pr:
                    PTable[i][l][s] = min(PTable[i][l][s]  , PTable[i - 1][l-l_pr][s - s_pr] + k_pr)
                end if
            end for
         end for
    end for
end for

All the cells of the table PTable have been initalized with $-\infty$, Except the initial 'plane', which is zero.

Thanks in advance.

A Multichoice Knapsack problem variant? - MathOverflow

A Multichoice Knapsack problem variant?