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.
53
questions
2
votes
1
answer
877
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 } ...
- 23
1
vote
0
answers
99
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
125
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
163
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
111
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'...
- 618
1
vote
0
answers
109
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
88
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
42
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 ...
- 145
3
votes
2
answers
115
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,252
5
votes
2
answers
322
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,471
1
vote
1
answer
87
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
1
answer
396
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
6
votes
2
answers
288
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 ...
- 113
0
votes
2
answers
107
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{...
4
votes
2
answers
112
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