Date: May, 9th, 11h30
Place: Room P.OF2070 – ULB Bruxelles
Abstract: We consider 0-1 optimization problems and their k-Delete recoverable robust (k-del RR) version. K-del RR is a two stage process to deal with cost-uncertainties. In the first stage, a solution of the underlying problem is fixed. In the second stage, depending on the revealed cost, at most k elements of this solution are deleted to reduce the cost. We prove in the first part of the talk that the k-del RR shortest path and minimum matching problem are strongly NP-hard and provide on the other hand polynomial solvable cases. In the second part of the talk we focus on exact algorithms to solve these problems. We will therefore derive several different IP-formulations and provide preliminary computational results on the run-time.
