AN IMPROVED REDUCTION METHOD FOR THE ROBUST OPTIMIZATION OF THE ASSIGNMENT PROBLEM

We are concerned with a variation of the assignment problem, where the assignment costs differ under different scenarios. We give a surrogate relaxation approach to derive a lower bound and an upper bound quickly, and show that the pegging test known for zero–one programming problems is also applicable to this problem. Next, we discuss how the computation time for pegging can be shortened by taking the special structure of the assignment problem into account. Finally, through numerical experiments we show that the developed method finds exact solutions for instances with small number of scenarios in relatively small CPU time, and good approximate solutions in case of many scenarios.