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

52 questions
Filter by
Sorted by
Tagged with
1 vote
95 views

### Knapsack problem - reducing the number of decision variables

I am trying to solve something similar to a knapsack problem: $$\max \sum v_{n}P_{n}$$ subject to some basic weight constraints. However, what makes this problem difficult to solve is that $P_{n}$ is ...
• 185
1 vote
119 views

### 0-1 Knapsack optimization problem

Can anyone explain how the writer rewrite the objective function in (7) to be written as (8)?
158 views

• 51
302 views

### Multiple Knapsack with Varying Values

I wish to assign customers to their nearest distribution hubs. These hubs have maximum capacities however, and if these are breached I would like to assign customers to the next most appropriate hub. ...
501 views

### How do I solve a probability based knapsack problem?

I am looking to maximize my probability of reaching a given target value, by creating multiple groups of 6 items with different means and variances that stay within a weight limit. This is an example ...
• 31
1k views

### 3D Knapsack Problem: R or Python Packages?

For an upcoming client project, I'm looking to do a 3D variant on the knapsack problem. Basically, there's a bin of dimensions $x,y,z$, and I have $K$ units of an item with dimensions $a,b,c$. (...
• 793
146 views

### Project task scheduling based on available budget per period

I have a challenge that is a bit backwards from the usual labour resource leveling problem. In my case I have a fixed budget pool over a period to deliver some of the work packages (not enough per ...
• 133
1k views

### Knapsack problem with negative value and weights and cardinality constraint

I know there are ways to handle Knapsack problems with negative weights or cardinality constraints, but I have a problem with also negative values as well as a cardinality constraint: \begin{align} \...
• 53
836 views

### Knapsack - How to optimize bonuses for each pair of items

I am trying to solve a variation of the knapsack problem where every pair of items in my knapsack has a bonus or penalty associated with it. My knapsack can hold a dozen items There are thousands of ...
• 197
228 views

• 101
100 views

### Looking for a similar optimization problem

I want to know if there is any already defined problem that could give me a hint on how should I approach the following task. There are N tasks that should be accomplished, each task requires ...
222 views

### Is there a knapsack problem which allows 'out-of-capacity'?

I wonder if there is an option in the knapsack problem which has a huge cost for 'out-of-capacity' instead of strictly limiting the constraint.
• 141
165 views

### A variant of maximum sum subarray problem?

This is related to the foillowing Q on Cross Validated https://stats.stackexchange.com/questions/483002/experimental-design-problem-with-goofy-constraints which I am trying to answer, but the ...
65 views

### What is the generalization of the resource allocation problem I'm dealing with here?

I'm dealing with a problem as follows: I have a finite set of money $m$ to spend over $r$ different raffles, and I need to spend approximately to my budget, with the goal of maximizing my probability ...
756 views

### knapsack problem with non-linear constraint

I have a basic knapsack problem where I need to fit the most weight possible in a bin: ...
707 views

### Multiple Knapsacks with splitting

I am trying to solve a problem that I believe is a variation of the multiple knapsacks. Like the classical multiple knapsacks problem, I have a set of items, each one with a weight and a value and I ...
3k views

### How to solve knapsack problem with simulated annealing?

I was going through the course contents of Optimization with Metaheuristics in Python in udemy , where they have solved a quadratic assignment problem using Simulated annealing in python , i was ...
• 489
189 views

### Does this problem fall into any common problem definition....Knapsack maybe?

I am struggling to find a representative problem formulation for this optimization challenge. I have implemented a MILP in Matlab, but the run time is taking more then a day. My goal is to see if it ...
• 335
481 views

### Solving a variant of multiple knapsack problem/ generalized assignment problem

Consider $m$ knapsack and $n$ items. With each knapsack $j$ associated a capacity $c(j)$ and with each item $i$ associated a profit $p(i,j)$ (that depends on the knapsack, so it's not exactly the ...
• 963
5k views

### Solving a knapsack problem with a lot of items

I am wondering what are the fastest ways(faster than classical dynamic programming) to solve the knapsack problem (to optimality) with $n$ items when $n$ is nearly equal to $10000$ ? Apart from ...
• 963
202 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