**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**

**Abstract:**

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 *Σ*^{p}_{2} 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"** [...]