I have i items and I should pre-packed m knapsacks with identical items where only K<n items can be packed. Also, we should have only one of each item in each sack. The time capacity for knapsacks preparation is limited to Cm for each sack. The ti is the packaging time of item i. The objective is to minimize the packaging costs. I believe it is a multiply constrained knapsack problem and it is also bounded. However, It has some similarities and differences with bin packing problem as well. I am wondering if this problem is a variant of knapsack problem. Is it still NP-hard? If so, how can I prove it? Thanks.

The formulation is:

\[ \begin{array}{} \min &\sum_{i \in I} c_i z_i x_m &~ &~\\ ~ &\sum_{i \in I} z_i &\le K &~\\ ~ &\sum_{i \in I} t_i x_{m} &\le C_m &\forall ~m \in M\\ ~ &x_m &\le u &\forall ~m \in M\\ ~ &x_m \in \mathbb{Z}_{+} &~ &\forall ~m \in M\\ ~ &z_i \in \{0,1\} &~ &\forall ~i \in I \end{array} \]

asked 07 Jun '16, 10:23

Rezi's gravatar image

accept rate: 0%

retagged 08 Jun '16, 11:41

Rob%20Pratt's gravatar image

Rob Pratt

  1. It seems to me that bags should have capacity and items have weights.

  2. What is "the time limit on filling each bag"? Are the bags being filled consecutively or something else? How do you write it as a constraint?

  3. What is the packing cost? Is the time required to pack each item or each tiem value?

Your question seems too vague to get a good answer.

(07 Jun '16, 11:06) Ehsan ♦

We don't consider weight for bags; however, we can fill the bags in limited the time as much as we can. The time limit on filing the each bags is the time capacity which is restricted to our model. The bags should fill simultaneously and identically as well. The packing cost includes the labor cost and operations costs.

(07 Jun '16, 11:13) Rezi

Could you provide a verbal definition of your variables?

(08 Jun '16, 05:33) Sune

\(z_{i}=1\) if the item i is selected
\(x_{m}\) is the number of package for knapsack m

(08 Jun '16, 09:13) Rezi

OK, can you specify the sign of the the coefficients \(c_i\), \(t_i\) and \(C_m\)?

It also seems like something is wrong with the objective function. You are only summing over the index set \(I\) but the \(x\)-variable is index by \(m\).

(09 Jun '16, 02:33) Sune
Be the first one to answer this question!
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: 07 Jun '16, 10:23

Seen: 493 times

Last updated: 09 Jun '16, 02:33

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