# 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.

53 questions
Filter by
Sorted by
Tagged with
882 views

1 vote
111 views

### Applications of Knapsack and Cutting Stock in Pure Math

I'm giving a seminar to PhD students in pure math, and one of the things I'd like to do is show that more applied optimization can also make its way into pure Mathematics. As for classical problems, I'...
• 638
1 vote
167 views

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

The original goal was to program a knapsack problem that gives the rows of the following matrix as the solutions: which has the definition: $$T(n,k)=a(\gcd(n,k))$$ where the Dirichlet inverse of the ...
• 281
89 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
1 vote
42 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 ...
• 145
116 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,252
323 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,481
1 vote
87 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
400 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
292 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 ...
• 113
107 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{...
112 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
110 views

• 564
95 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
1k 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,841
71 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
834 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,841
248 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
383 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
327 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
557 views

• 963
207 views

### How to convert 3D bin packing problem to 2D bin packing approximation?

I'm trying to approximately solve a 3D container loading problem. Is it possible to use 2D bin packing algorithms? If so, how do we make the transformation? What are the conditions needed to make the ...
• 73