# Tag Info

### Solving a knapsack problem with a lot of items

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/~...
• 1,514
Accepted

• 32.7k
Accepted

### Solving weekday and weekend fare movies

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 ...
• 32.7k
Accepted

### 0-1 knapsack with non-linear objective function

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}$. ...
• 6,212

### Allocating credit card points

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 ...
• 2,316
Accepted

### Looking for books in the same style as Hans Kellerer 2004, Knapsack Problems

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, ...
• 5,929
Accepted

### Mixed Integer Programming/Optimization using the Genetic Algorithm

It is possible (but a bit tricky) to write a mixed-integer linear program for this problem. If you are willing to accept a good but not guaranteed optimal solution, though, the GA is easily modified ...
• 39.6k
Accepted

### Knapsack - How to optimize bonuses for each pair of items

One approach is to introduce the pairs dynamically only when needed. Initially, solve a relaxation where every pair yields the highest bonus. (Note: I am suggesting to relax the objective and not to ...
• 32.7k
Accepted

### 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?

The general case where not all weights are equal to one, is ${NP}$ hard, as the subset sum problem reduces to it with a constant objective function. If all weights $w_i$ are equal to one, the problem ...
• 6,647
Accepted

### knapsack problem with non-linear constraint

Hold the phone... You can keep this linear. Just sum the selection variables and multiply by the min average requirement. No division required. ...
• 252

### Is there a knapsack problem which allows 'out-of-capacity'?

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 ...
• 6,647
Accepted

### Looking for a similar optimization problem

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 ...
• 32.7k

### Is there a Bin Packing Library similar to TSPLIB?

BPPLIB – A Bin Packing Problem Library: http://or.dei.unibo.it/library/bpplib
• 32.7k