# Questions tagged [knapsack]

For questions related to the knapsack problem that seeks to find the number of each item to include in a limited container (in an integer knapsack or whether to include an item in a binary knapsack), given each item's weight and value, with the goal of maximizing the total value.

49 questions
Filter by
Sorted by
Tagged with
-2 votes
0 answers
39 views

### Optimize Packaging Dimension

I want to optimize the transport packaging (which is in carton/box) in logistics activity. The key question in this case is what is the optimal dimension of the carton, as the number of cartons ...
• 589
1 vote
0 answers
54 views

### Finding the divisors of the numbers 2 to 13 as a knapsack problem

I don't know how to write this as Latex formulas, but here are anyways two examples, the divisors of $9$ and $12$ as the solutions to knapsack problems. Beware that there is some ...
• 281
0 votes
1 answer
75 views

### Knapsack Problem with Multiple Properties

Problem Description I have many examples (say $N$) to choose from to train my machine learning model. However, I could only select $n \ll N$ based on a set of $K$ attributes $\{a_1, a_2, \cdots, a_k\}$...
• 171
0 votes
0 answers
35 views

### Why does changing this one thing in the Primal Effective Capacity Heuristic improve the solutions it generates for the MDK problem?

For a long-done project presentation, I implemented the Primal Effective Capacity (PECH) Heuristic to look for initial greedy solutions for the Multidimensional Knapsack (MDK) problem in Python. I ...
• 111
3 votes
2 answers
82 views

### Knapsack Constraint

Is the following expression a knapsack constraint? $\sum_i a(i) y(i) \ge W$, where $y(i)$ binaries, $a(i),W$ reals. What confuses me is the $\ge$ sign. Alternatively, do solvers generate cuts out of ...
• 2,170
4 votes
2 answers
225 views

### Separating violated cover inequalities

Consider a knapsack problem with binary variables and a standard knapsack constraint $\sum_{j\in N}a_jx_j\leq b$. A set $C\subseteq N$ is a cover if $\sum_{j\in C}a_j >b$ If $C\subseteq N$ is a ...
• 3,342
1 vote
1 answer
77 views

### How to Set Up an Optimization Problem Like the 0/1 Knapsack

I'd like some help in understanding and setting up (what may be) an optimization problem that has some similarities to the 0/1 knapsack problem. In this problem the items are a given number of words (...
• 113
1 vote
1 answer
216 views

### Optimal to-do list scheduling in Python using Pyomo

I am trying to optimally schedule a series of tasks with fixed durations between 9am and 5pm in the day (I guess kind of like a constrained knapsack problem, or job scheduling problem). I have broken ...
• 333
6 votes
2 answers
167 views

### Cover cuts for knapsack constraint with integer variables

It is known for knapsack type constraint $\sum_{i \in N} a_i x_i \leq b , x \in \{0,1\}$, we can generate the so called cover cuts that have the sum of coefficient in a set C greater than b. The cover ...
• 71
0 votes
2 answers
96 views

### Bellman Equation for nonlinear model

Consider the following model: \begin{align*} max \quad Z &= 19x_1 - 3x_1^2 + 5x_2^2 - x_2^4 + 4x_3 \\ & s.t. \quad x_1 + 3x_2 + 3x_3 \leq 7 \\ & \quad \quad \quad x_1,x_2,x_3 \geq 0 \end{...
4 votes
2 answers
111 views

### A sum with a product-penalty

Let us consider the following optimization-problem: For a given set of tuples $T=(a_1,b_1),\dots,(a_n,b_n)$ and integers $k,C$. The task is to \begin{align} \max \quad & \sum_{i=1}^n x_i \cdot a_i ...
• 41
5 votes
1 answer
108 views

• 524
3 votes
1 answer
89 views

### Are there examples where introducing clusters of binary variables provides a benefit for solving?

I have a larger model with a large number of binary variables among many others. For the purpose of this question, consider the effect that the binary variables impose on the model to be similar to ...
• 313
6 votes
2 answers
627 views

### Confusion Between Different Types of Optimization Problems

I do not have a background in optimization and I am trying to teach myself more about this topic. I find myself having a lot of trouble understanding the different "types" of optimization ...
• 1,821
2 votes
1 answer
67 views

### A variable being a set...?

I am currently doing a coursera course on optimization. They are using minizinc and they modeled a problem where the decision is a choice of things --> a set. We all know this is a knapsack and it ...
• 533
2 votes
1 answer
621 views

### Mixed Integer Programming/Optimization using the Genetic Algorithm

I am working with the R programming language. Given a data set ("my_data"), I am trying to use an mixed integer optimization algorithm (e.g. genetic algorithm) to find out which filters ...
• 1,821
3 votes
1 answer
205 views

### How to redefine separation procedure to get 0-1 knapsack with odd number of items

So I have a 0-1 knapsack problem: \begin{align}\max&\quad \sum_j c_j x_j\\ \text{s.t.}&\quad \sum_j a_j x_j \leq b\\ &\quad x_j \in \{0,1\}\end{align} but it has an additional requirement ...
• 161
6 votes
1 answer
368 views

### Optimize for bonuses within a group (knapsack)

I am trying to create an LP problem which is like the knapsack problem but with groups of items. Let's say there are 10 groups of items each with up to 5 items. Each group has one special item and you ...
• 197
5 votes
1 answer
323 views

### How to optimize on a fixed-cost based on number of results?

I am trying to create an LP problem which is like the knapsack problem but where there is a fixed bonus/penalty based on the number of items chosen. There are 20 items to choose from with some weight ...
• 197
5 votes
2 answers
540 views

• 281