 |
||||||||||
| Volume 3, Number 1, January 2007, pp. 99-112 | ||||||||||
|
Hiroo Saito and Kazuo Murota
|
||||||||||
| Key words: | ||||||||||
| mixed integer programming, robust optimization, ellipsoidal uncertainty, Benders decomposition | ||||||||||
| Mathematices Subject Classification: 90C11, 90C25 | ||||||||||
| References | ||||||||||
|
||||||||||||||||||||||||||||||||||||||||
| Abstract: | |||
| We consider mixed integer programming (MIP) problems with ellipsoidal uncertainty in problem data. Robust solutions to such problems are formulated as solutions of second-order cone programming problems with integer constraints, which we solve by an adaptation of the Benders decomposition technique towards MIP with conic constraints. Numerical computation against robust 0-1 knapsack problems and generalized assignment problems indicates that robustness can be achieved without substantial deterioration in optimal values. | |||
| Benders decomposition approach to robust mixed integer programming | ||