GOM Seminar: Christina Busing Monday, May 9th 2016 – k-Delete Recoverable Robustness

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.

Comments are closed.