Spring 2012 Seminar Series

DATE: May 10th
LOCATION: E62-550
TIME: 4:15pm
Reception immediately following

SPEAKER:
Ebrahim Nasrabadi

TITLE
On the power of randomization in robust optimization and network interdiction

ABSTRACT
We consider Bertsimas and Sim's robust optimization approach for discrete optimization problems with uncertain cost parameters. We interpret their models as a 2-person zero-sum game in which Player 1 chooses the decision variables and Player 2 chooses the costs. We introduce a new framework, called “randomized robust optimization”, by allowing the decision maker to select a random (mixed) strategy, where the adversary's response is based only on knowing the mixed strategy and not its realization. We show that the randomization not only improves the decision maker's expected value, but also reduces the complexity of the problem. We also consider the network interdiction problem, where an interdictor aims to reduce the capacity of the network as much as possible by removing a certain number of the arcs. We analyze the effect of randomization in network interdiction by showing how much the interdictor can improve his expected value by choosing a random strategy, rather than a pure strategy.

 

Joint work with Dimitris Bertsimas and James Orlin