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" [...]


  Online lending company provides a wide range of ways to get money by means of Payday Loans Tennessee. What can cause long-term use of Viagra? In the network and other sources of information, there is no reliable data on the long-term use of Viagra and its negative effects on the body.