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.
48
questions
19
votes
3
answers
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 ...
- 943
16
votes
1
answer
1k
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 ...
- 281
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 ...
- 233
11
votes
1
answer
248
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?...
- 331
8
votes
2
answers
691
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:
...
- 215
7
votes
1
answer
194
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
7
votes
1
answer
395
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 ...
- 73
7
votes
0
answers
120
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$. ...
- 123
6
votes
2
answers
774
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
6
votes
1
answer
371
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
6
votes
2
answers
190
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 ...
- 111
5
votes
2
answers
817
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
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
545
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 $\...
- 153
5
votes
1
answer
615
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:
$$\...
- 101
5
votes
2
answers
249
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,396
5
votes
1
answer
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
5
votes
1
answer
206
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{ ...
- 524
5
votes
1
answer
468
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 ...
- 943
5
votes
1
answer
108
views
Identifying the variant of such a knapsack-like problem
I am not too familiar with variants of knapsack problems (or variants of possibly other classical OR problems), but I would like to identify the following Integer Programming problem:
$$\min_{x_i,y_{i,...
- 51
5
votes
1
answer
232
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 \\
&\...
- 123
5
votes
0
answers
63
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 ...
- 51
4
votes
3
answers
214
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
4
votes
3
answers
410
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 ...
- 51
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
3
votes
2
answers
431
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
3
votes
1
answer
162
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 ...
3
votes
1
answer
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
3
votes
1
answer
212
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
3
votes
1
answer
654
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 ...
- 215
3
votes
2
answers
88
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,180
3
votes
1
answer
90
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
2
votes
1
answer
666
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
2
votes
1
answer
96
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 ...
- 315
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
187
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 ...
- 325
2
votes
1
answer
854
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$. (...
- 743
2
votes
1
answer
258
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.
...
- 23
1
vote
1
answer
199
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 ...
- 271
1
vote
1
answer
266
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
1
vote
1
answer
79
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
0
answers
67
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
176
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.
...
- 429
0
votes
2
answers
98
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{...
0
votes
1
answer
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 ...
- 469
0
votes
1
answer
78
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
36
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 ...
- 121
0
votes
0
answers
197
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 ...
- 1,198