# 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,244
Accepted

• 22.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 ...
• 22.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}$. ...
• 5,893

### 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,275
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,809
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 ...
• 31.1k
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 ...
• 22.7k
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. ...
• 250

### 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 ...
• 5,445

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

BPPLIB – A Bin Packing Problem Library: http://or.dei.unibo.it/library/bpplib
• 22.7k
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 ...
• 22.7k
Accepted

• 10.4k
Accepted

### Dynamic Programming - Formulating recurrence relation

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