0
$\begingroup$

I was wondering whether the following knapsack ILP is modelled correctly. The model is as follows:

Knapsack problem

The knapsack model has a vector $\mathbf{w} = (w_{1}, \cdots, w_{j}, \cdots, w_{n})$, which contain the weights of every item $j$ and has a vector $\mathbf{x} = (x_{1}, \cdots, x_{j}, \cdots, x_{n})$ containing all the decision variables, which are defined as:

$$ x_{j}= \begin{cases} 1, & \text{if item $j$ is chosen}\\ 0, & \text{otherwise} \end{cases} $$

Now, on to the conditions:

  1. In the first constraint, I would like to state that the weight $w_{j}$ of every item $j$ should be less than 15% of the weights of the items that are selected.
  2. In the second constraint, I would like to state that the weights of the circle objects do not exceed $5\%$ of the total weights. The variable $v_{j}$ is a binary variable which states whether an object is a circle. The $\mathbf{v}$ vector is a parameter, not a decision variable, as correctly stated in the comments. $$ v_{j}= \begin{cases} 1, & \text{if item $j$ is a circle}\\ 0, & \text{otherwise} \end{cases} $$
  3. The third constraint should state that the weighted average number of the selected items should be at least 10. $\mathbf{u} = (u_{1}, \cdots, u_{j}, \cdots, u_{n})$ are numbers given for each item and can be different.
  4. The last constraint should state that the average weight should be less than 20. The $\mathbf{u}$ vector is a parameter, not a decision variable.

The first constraint is regarding the individual items that can be selected in the knapsack, while the latter three constraints are regarding the properties of the knapsack solution.

Now several questions regarding this model:

  • Is it modelled correctly? Given the description of the constraints? (Is the math exactly describing what I am describing in words?)
  • Can constraint 1 and constraint 4 be written more concise using vector notation?

Any improvements of suggestions regarding the model are welcome (maybe some constrains are contradictory and will never result in a solution, but this cannot be seen from the model and its constraints I think, but perhaps I am missing something or perhaps constraint 1 and 4 can be combined into one).

-EDIT- Extended clarifications:

  • The vector $\mathbf{u}$ contains another property of the items that we can pick, just as vector $\mathbf{v}$. $\mathbf{u}$ can be thought as a number written on the items, but are not the weights of the items that can go into the knapsack. Hereby an example: given that $\mathbf{x} = (1,1,1)$ and $\mathbf{u} = (11, 22, 31)$ and $\mathbf{w} = (1,2,3)$. The third constraint should compute the weighted average of $\mathbf{u}$:

$$\mathbf{x}\mathbf{u}^{T}\mathbf{w} = (11 \cdot 1 + 22 \cdot 2 + 31 \cdot 3)$$ $$148 / (11+22+31) = 2.3$$

so it violates condition 3.

  • With the last constraint I want to say that the average weight of the items in the knapsack should be below 20. Not the maximum weight. So suppose, I pick the following items with weights 11, 22, 31 in a knapsack then their average weight is:

$$(11+22+31)/3 = 21\frac{1}{3}$$

which violates constraint 4.

  • The only decision variable I have are in the vector $\mathbf{x}$, which should make this model a lot simpler.
$\endgroup$
  • $\begingroup$ A few clarifications: 1) you have one unit of each item and you can either select it or not. Then what does constraint 3 says? I didn't understand what is vector $u$. 2) Is the last constraint just trying to say that your max weight in your knapsack should be less than 20? btw, in terms of notation, I can only think that you can use $\mathbf{1} \cdot \mathbf{x} = \sum x_i$ if you need any more conciseness $\endgroup$ – EhsanK Apr 23 at 0:47
  • $\begingroup$ Also, in the current formulation, you have the multiplication of two decision variables $x$ and $v$. But I assume you know in advance which objects are circle and that's how you are trying to limit their weights. So, $v$ is a parameter and it shouldn't be a variable. $\endgroup$ – EhsanK Apr 23 at 1:09
  • $\begingroup$ With your new clarification, it seems that constraint 3 can be stated as "average weight of items that have property $u$ should be at least 10$. If so, then what you wrote doesn't seem wrong. $\endgroup$ – EhsanK Apr 23 at 21:34

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.