Tuesday, 14:15 - 14:40 h, Room: H 2032


Fabio Furini
Heuristic and exact algorithms for the interval min-max regret knapsack problem

Coauthors: Manuel Iori, Silvano Martello, Mutsunori Yagiura


We consider a generalization of the 0-1 knapsack problem in which the profit of each item can take any value in a
range characterized by a minimum and a maximum possible profit. A set of specific profits is called a scenario.
The interval min-max regret knapsack problem (MRKP) is then to find a
feasible solution such that the maximum regret over all scenarios is minimized. The problem is extremely challenging both from a theoretical and a
practical point of view. Its recognition version is complete for the complexity class Σp2 hence it is most probably not in NP.
In addition, even computing the regret of a solution with respect to a scenario requires the solution of an NP-hard problem.
We examine the behavior of classical combinatorial optimization approaches when adapted to the solution of the MRKP.
We introduce an iterated local search approach and a Lagrangian-based branch-and-cut algorithm, and evaluate their performance
through extensive computational experiments.


Talk 3 of the invited session Tue.2.H 2032
"Trends in mixed integer programming III" [...]
Cluster 11
"Integer & mixed-integer programming" [...]


  Getting Payday Loans In California should be thought of many times. If you have already decided to take Levitra, be sure to consult a doctor, you don't have any contraindications and act strictly due to a prescription.