Min-ordering and max-ordering scalarization methods for multi-objective robust optimization

Several robustness concepts for multi-objective uncertain optimization have been developed during the last years, but not many solution methods. In this paper we introduce two methods to find min-max robust efficient solutions based on scalarizations: the min-ordering and the max-ordering method. We show that all point-based min-max robust weakly efficient solutions can be found with the max-ordering method and that the min-ordering method finds set-based min-max robust weakly efficient solutions, some of which cannot be found with formerly developed scalarization based methods. We then show how the scalarized problems may be approached for multi-objective uncertain combinatorial optimization problems with special uncertainty sets. We develop compact mixed-integer linear programming formulations for multi-objective extensions of bounded uncertainty (also known as budgeted or G-uncertainty). For interval uncertainty, we show that the resulting problems reduce to well-known single-objective problems.