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.

Filter by
Sorted by
Tagged with
3 votes
1 answer
108 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 ...
user avatar
  • 133
5 votes
1 answer
138 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} \...
user avatar
  • 53
5 votes
2 answers
744 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 ...
user avatar
  • 197
5 votes
1 answer
93 views

Dynamic program for knapsack in $O(W)$ space?

A familiar dynamic programming algorithm for the binary knapsack problem $$ \begin{align} \text{maximize}\quad & v \cdot x \\ \text{subject to} \quad & w \cdot x \leq W \\ \quad&x_i \text{ ...
user avatar
  • 346
3 votes
1 answer
73 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 ...
user avatar
  • 303
5 votes
2 answers
229 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 ...
user avatar
  • 1,839
2 votes
1 answer
53 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 ...
user avatar
  • 533
2 votes
1 answer
281 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 ...
user avatar
  • 1,839
3 votes
1 answer
140 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 ...
user avatar
6 votes
1 answer
347 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 ...
user avatar
  • 197
5 votes
1 answer
310 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 ...
user avatar
  • 197
5 votes
2 answers
505 views

Combinatorial optimization, implementation needed

I have k sets of items. I want to choose n items from each set, $n \cdot k$ items total. I would like to choose the $n \cdot k$ items under some optimization criterion, e.g. that the sum of the $\...
user avatar
0 votes
0 answers
129 views

Check VRP instance is feasibility

Beforehand, this is a very long thread, in case you want to know in advance, to see if this thread's interests match with yours, this thread concerns fast ways of determining whether a VRP instance is ...
user avatar
4 votes
3 answers
288 views

Is there a Bin Packing Library similar to TSPLIB?

I have concluded there is not, or if there is it's not openly published? I am trying to identify if there are "top solutions/formulations" for the 3d BPP. Looking to apply in a parcel ...
user avatar
1 vote
1 answer
147 views

Dynamic Programming - Formulating recurrence relation

We wish to apply dynamic programming techniques to find the optimal betting strategy for a pool to wager on the outcome of the NCAA men's basketball tournament 64 teams compete in a single ...
user avatar
5 votes
1 answer
123 views

NP-hardness of a special case of multiple choice knapsack problem

Let us consider the following problem: \begin{align} \max &\quad\sum_{i=1}^n\sum_{j=1}^m v_{i,j}\cdot x_{i,j} \\ \text{s.t.}&\quad \sum_{i=1}^n x_{i,j} =1 &\forall j =1,\dots,m \\ &\...
user avatar
  • 123
7 votes
0 answers
106 views

Estimate lagrangian multiplier based on instance characteristics

Assume we have a simple resource allocation problem, where all players have the same cost, but a different utility $a_s$. The resources assigned to a certain player must be between $L$ and $M$. ...
user avatar
  • 123
0 votes
1 answer
163 views

Solving weekday and weekend fare movies

Thinking if it is a Knapsack problem. Here is the scenario: Michael and his daughter (7 year old kid) enjoy going to cinema for movies. ...
user avatar
  • 429
5 votes
1 answer
279 views

0-1 knapsack with non-linear objective function

There's efficient algorithms for solving the 0-1 knapsack problems when the objective function is just a sum of profits. I am dealing with the following problem with non-linear objective function: $$\...
user avatar
2 votes
1 answer
91 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 ...
user avatar
4 votes
3 answers
164 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.
user avatar
  • 141
3 votes
1 answer
128 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 ...
user avatar
5 votes
0 answers
56 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 ...
user avatar
8 votes
2 answers
470 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: ...
user avatar
3 votes
1 answer
320 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 ...
user avatar
0 votes
1 answer
2k 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 ...
user avatar
  • 459
2 votes
1 answer
176 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 ...
user avatar
  • 305
5 votes
1 answer
367 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 ...
user avatar
18 votes
3 answers
4k 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 ...
user avatar
7 votes
1 answer
170 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 ...
user avatar
  • 73
11 votes
1 answer
226 views

Looking for books in the same style as Hans Kellerer 2004, Knapsack Problems

I really enjoyed reading Hans Kellerer, David Pisinger, Ulrich Pferschy 2004 book Knapsack Problems. Can anybody recommend books in a similar style, about some other classes of problems / optimisation?...
user avatar
  • 331
7 votes
1 answer
301 views

Shipments consolidation - how to model mutually exclusive items with OR-Tools CP Solver in Python (multi-knapsack, updated)

I am implementing a solution for packages consolidation (basing on Nurse Problem solution) with OR-Tools CP Solver. There is a factory that manufactures some small Packages that need to be ...
user avatar
13 votes
3 answers
1k views

Allocating credit card points

I’m interested in the idea behind this in general, so I thought this would be the best place to post, though I have a practical and semi-urgent need of allocating the points on my credit card towards ...
user avatar
  • 233
16 votes
1 answer
966 views

Prove that these linear programming problems are bounded by $O(k^{1/2})$

Prove that these linear programming problems are bounded by $O(k^{1/2})$ Conjecturally the expanded partial sums of the Möbius transform of the Harmonic numbers have two out of three properties in ...
user avatar