# Tag Info

## Hot answers tagged knapsack

18

For the knapsack problem, you just use the Pisinger's code. It implements an exact algorithm, it is the fastest algorithm known in the literature, and it is open-source: http://hjemmesider.diku.dk/~pisinger/codes.html

13

Your linear program is similar to a mathematical formulation of a bounded Knapsack problem and has a similar linear relaxation. First note that $x_1$ is only restricted by $x_1\geq -1$ and thus $x_1=-1$ at optimality. The sum of remaining variables is bounded by $1-k$ (indeed has to be equal to $1-k$) and since variables with lower indices have higher value ...

10

With the OP's clarifications I would say this is a straight-forward variant of the knapsack problem where you want to pack as many saved dollars into your budget of points. Find below the simple formalization where the index $i$ spans across all items on the current bill: Capacity of the knapsack: $C$ = Available points Item weight: $w_i$ = number of ...

9

A comprehensive comparison of different approaches to solving the knapsack problem is given in the recent paper1 by Ezugwu et al., where the authors compare the performance of the following approaches both in small size and large size problems: Genetic algorithms, Simulated annealing, Branch and bound, Dynamic programming, Greedy search algorithm, ...

8

This seems like some sort of knapsack problem: Suppose you have a set of purchases and a certain amount of points. Each purchase can be "paid" by points as a whole, no partial usage of points for each purchase is viable. Let's declare some sets and parameters: let $P={1,\ldots,n}$ be the set of purchases which each get a number to distinguish them. For each ...

7

That sounds like you could formulate it as MIP. You have a fixed set of planned purchases, right? Each of them ($p$) will yield a constraint of the form $x_p + c_p \cdot y_p = t_p$, where $x_p$ is the amount of money you will spend on that purchase, $y_p$ the amount of points with the conversion rate (per purchase) and $t$ the total price. $x \ge 0$ would ...

7

I waited some time but apparently no easy answer here. Thanks for providing some more hints in the comments to your question. One specialty about the knapsack book is: it is a monograph, that is, written by the same author(s). There are only few other books about a particular combinatorial optimization problem, with theory and algorithmic components, and ...

7

Even though knapsack problems are relatively easy to solve in practice, there does not exist a polynomial-time algorithm to solve even the standard knapsack problem, unless $\mathcal{P}=\mathcal{NP}$. The knapsack problem can be solved in pseudo-polynomial time $\mathcal{O}(nC)$. Even when the input length (=number of digits describing the problem) is small, ...

6

So it costs \$13 for the two of them on a weekday and \$24 for the two of them on a weekend. If you want to maximize the number of movies, skip the expensive ones and the \$100 budget yields$\lfloor 100/13 \rfloor = 7$movies. If you prefer writing it explicitly as an optimization (yes, knapsack) problem, let integer decision variables$x$and$y$be the ... 6 If "total duration" means sum of durations, this is called the generalized assignment problem. If "total duration" means maximum of durations, this is called the bottleneck generalized assignment problem. You might also find something useful by searching for makespan minimization. 6 Hold the phone... You can keep this linear. Just sum the selection variables and multiply by the min average requirement. No division required. import pyomo.environ as pyo v = {'hammer': 1, 'wrench': 3, 'screwdriver': 1, 'towel': 2} w = {'hammer': 5, 'wrench': 7, 'screwdriver': 4, 'towel': 3} limit = 14 M = pyo.ConcreteModel() M.ITEMS = pyo.Set(... 6 If "out of capacity" means "if you violate capacity, you get infinite capacity for a large cost" the problem reduces to solving a knapsack problem and checking if the profit of this is higher than all positive profits summed minus the large cost. 5 If all$B_{i,j}$are known, you can solve the problem via integer linear programming as follows. Let binary decision variable$x_{i,j}$indicate whether entry$(i,j)$is selected, let binary decision variable$r_i$indicate whether row$i$is selected, and let binary decision variable$c_j$indicate whether column$j$is selected. The problem is to ... 4 Simulated annealing is just a (meta)heuristic strategy to help local search to better escape local optima. Local search for combinatorial optimization is conceptually simple: move from a solution to another one by changing some (generally a few) decisions, and then evaluate if this new solution is better or not than the previous one. For an introduction to ... 4 Here is a MILP formulation, in case you did something different. Let binary variable$F_j$indicate whether subset$j$is chosen. Let binary variable$T_i$indicate whether item$i$appears in two or more of the chosen subsets. The problem is to minimize$\sum_i T_isubject to: \begin{align} \sum_j F_j &= 140 \tag1 \\ \sum_j M_{i,j} F_j - 1 &\le ... 4 It looks like there is no relationship between different knapsacks, so you can solve this exactly asm$independent 0-1 knapsack problems. Also, for knapsack$j$, you can eliminate any items$i$that have$p(i,j)\le 0$. 4 You can introduce a nonnegative surplus variable$y$with large cost$M$and maximize$\sum_j v_j x_j-M y$subject to$\sum_j w_j x_j \le W+y$. Alternatively, if you want to impose a one-time fixed cost$M$if there is any violation, let$y$be binary and change the constraint to$\sum_j w_j x_j \le W+Uy$, where$U$is some upper bound. 4 Here is a workaround for your nonlinear problem: solver_manager = SolverManagerFactory('neos') #solver = pyo.SolverFactory("BARON") solution = solver_manager.solve(M, solver = 'couenne') #solver.solve(M) for i in M.ITEMS: print(i,':',pyo.value(M.x[i])) You can either use a local nonlinear solver like BARON, or some solvers in NEOS server. I ... 4 You have an instance of the 0-1 knapsack problem where you want to determine which teams to select to maximize the number of wins, subject to a budget. The linked page provides a DP recurrence, which is obtained by conditioning on whether or not you select the next team. The optimal objective value for your instance is 28: \begin{matrix} \text{team} & ... 3 I think the problem is NP-hard since: it will reduce to the 0-1 Knapsack problem with an equality constraint; and, changing$\leq$to$=$in the 0-1 Knapsack constraint does not change its complexity (see explanation below). So, your problem is NP-hard as 0-1 Knapsack is. P.S. To see why (2) is correct, suppose all weights and values are equal. Then the ... 3 This is not too big of a leap from the basic Knapsack problem and can be handled with only 3 constraints for the bin size, all-or-nothing, and the prohibited placements. Below is an example that I think fits the design pattern. This is casted in pyomo. I think OR-Tools is pretty similar in structure. It should not be a major leap. # multi-knapsack, ... 3 According to the attached file: In the$m$-dimensional bin packing problem ($m$-BPP) there are many large boxes of equal sizes, which are called bins, and the objective is to pack all$n$items into a minimum number of bins. We can translate any$m$-BPP instance into an instance of$(m+1)$-SPP (strip packing problem), where the additional$(m+1)$st ... 2 You don't give that bit of information, but you might be able to use a far more efficient algorithm when knapsack size (let's call it$S$) is small enough (small enough to create an array of each possible value you could get) and all the items have positive (or zero) weight. For example, if maximum knapsack size is$10^7\$ units, you could easily create an ...

1

If the intent is a per unit penalty, rather than a fixed penalty for violation regardless of the size of the violation, you can switch to a generalized assignment problem with three destinations. The first destination is the original knapsack, with its original capacity. The second destination is an "overflow knapsack" with a sufficiently large ...

1

You can use the linear constraint function to add additional constraints which prohibit mutually exclusive pairs. I'd imagine that each mini package has to be scheduled on one date so this leads to the following code: for (product_a, product_b) in conflict_list: mps_with_productb = [mp for mp, p in enumerate(products) where p == product_b] for mp1 ...

Only top voted, non community-wiki answers of a minimum length are eligible