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.
58 questions
3
votes
1
answer
189
views
Plotting dual values for the bin packing problem in PySCIPOpt, colgen2025 exercise
I have been solving the exercises in: https://github.com/mmghannam/colgen2025/tree/main
The first bonus exercise asks for plotting the evolution of the dual values but I haven't understood how SCIP ...
0
votes
0
answers
34
views
Pseudo-polynomial time dynamic programing for this subset sum variant
We define the all-subset-sum problem as follows. Given a set $S$ of positive integers and a target $T$, the goal is to find all the maximal distinct subsets of $S$ summing to $T$.
A maximal set is a ...
- 303
2
votes
1
answer
316
views
is there a name for Assignment Problem with one extra inequality?
Hello long lost friends!
Summary
Does the formulation below, i.e., an Assignment Problem with one extra linear inequality, have a name, and has it been studied?
Context
Just for reference: there are ...
- 131
1
vote
2
answers
239
views
integer programming relaxation problem
How can the formulation of $P2$ guarantee that it is a relaxation of $P1$?
(if $w=0$, $1$ is much bigger than $2$).
- 13
1
vote
0
answers
85
views
DP for a variation of the knapsack problem?
I have a variation of the knapsack problem where each item has a profit ($p_i$), weight ($w_i$), and penalty ($t_i$). The objective is to maximize the summation of the selected items' profits minus ...
- 613
2
votes
1
answer
1k
views
Is 0-1 knapsack problem still NP-Hard (1) with an equality constraint and (2) when all the weights in the constraint are equal to one?
Is 0-1 knapsack problem still NP-Hard with an equality constraint?
$$\begin{aligned}
& \text { maximize } \sum_{i=1}^n v_i x_i \\
& \text { subject to } \sum_{i=1}^n w_i x_i = W \text { and } ...
- 43
1
vote
0
answers
161
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
1
answer
156
views
0-1 Knapsack optimization problem
Can anyone explain how the writer rewrite the objective function in (7) to be written as (8)?
- 15
0
votes
2
answers
239
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 + ...
1
vote
0
answers
136
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'...
- 1,317
1
vote
0
answers
209
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
0
votes
1
answer
139
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
0
answers
60
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 ...
- 165
3
votes
2
answers
152
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,320
5
votes
2
answers
507
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,563