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
1 vote
1 answer
105 views

0-1 Knapsack optimization problem

Can anyone explain how the writer rewrite the objective function in (7) to be written as (8)?
AhmedHassan's user avatar
-1 votes
2 answers
140 views

Need help with integer programming exercise

This is an exercise from Wolsey that I can't solve. Show how to go from Equivalence (1) to (2) and from Equivalence (2) to (3): $$ \begin{align} X &= \{ x \in \{0, 1\}^4~\mid~97x_1 + 32x_2 + ...
Tio Pikachu Lizardon's user avatar
1 vote
0 answers
108 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'...
J. Dionisio's user avatar
1 vote
0 answers
72 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 ...
Mats Granvik's user avatar
0 votes
1 answer
84 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\}$...
Mr.Robot's user avatar
  • 171
1 vote
0 answers
39 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 ...
Miss Mae's user avatar
  • 131
3 votes
2 answers
96 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 ...
Clement's user avatar
  • 2,224
5 votes
2 answers
272 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 ...
Joris Kinable's user avatar
1 vote
1 answer
83 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 (...
davypough's user avatar
  • 113
1 vote
1 answer
331 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 ...
Jwem93's user avatar
  • 333
6 votes
2 answers
214 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 ...
CHE's user avatar
  • 113
0 votes
2 answers
102 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{...
OpenAtTheClose's user avatar
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 ...
xtyner's user avatar
  • 41
5 votes
1 answer
109 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,...
Vergil's user avatar
  • 51
2 votes
1 answer
273 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. ...
B Marshall's user avatar
3 votes
2 answers
465 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 ...
will's user avatar
  • 31
3 votes
1 answer
983 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$. (...
Ralph Asher's user avatar
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 ...
baradhili's user avatar
  • 133
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} \...
Jeffrey's user avatar
  • 53
5 votes
2 answers
834 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 ...
Eddie's user avatar
  • 197
5 votes
1 answer
218 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{ ...
Max's user avatar
  • 534
3 votes
1 answer
94 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 ...
Andreas's user avatar
  • 313
6 votes
2 answers
911 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 ...
stats_noob's user avatar
2 votes
1 answer
68 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 ...
Eddiee's user avatar
  • 533
2 votes
1 answer
725 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 ...
stats_noob's user avatar
3 votes
1 answer
237 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 ...
Aisec Nory's user avatar
6 votes
1 answer
377 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 ...
Eddie's user avatar
  • 197
5 votes
1 answer
324 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 ...
Eddie's user avatar
  • 197
5 votes
2 answers
553 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 $\...
Joseph Turian's user avatar
0 votes
0 answers
210 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 ...
Matheus Diógenes Andrade's user avatar
4 votes
3 answers
437 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 ...
somedude's user avatar
1 vote
1 answer
203 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 ...
user620842's user avatar
5 votes
1 answer
242 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 \\ &\...
Pete S's user avatar
  • 123
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$. ...
Pete S's user avatar
  • 123
0 votes
1 answer
177 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. ...
Mark K's user avatar
  • 429
5 votes
1 answer
654 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: $$\...
mike's user avatar
  • 101
2 votes
1 answer
98 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 ...
Psyndrom Ventura's user avatar
4 votes
3 answers
218 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.
user67275's user avatar
  • 141
3 votes
1 answer
164 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 ...
kjetil b halvorsen's user avatar
5 votes
0 answers
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 ...
winterwyvern's user avatar
8 votes
2 answers
720 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: ...
Cesar Canassa's user avatar
3 votes
1 answer
682 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 ...
Cesar Canassa's user avatar
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 ...
21vs's user avatar
  • 489
2 votes
1 answer
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 ...
S moran's user avatar
  • 325
5 votes
1 answer
476 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 ...
Joffrey L.'s user avatar
20 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 ...
Joffrey L.'s user avatar
7 votes
1 answer
198 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 ...
Surya's user avatar
  • 73
11 votes
1 answer
253 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?...
gornvix's user avatar
  • 331
7 votes
1 answer
405 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 ...
Tomasz Kot's 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 ...
Dave's user avatar
  • 233