Serpil Sayın
Koç University
College of Administrative Sciences and Economics
Rumeli Feneri Yolu
34450 Sarıyer, İstanbul, Turkey
ssayin@ku.edu.tr
Introduction
Various concepts and tools associated with robustness have been appearing more and more in the literature during the last few years. Many alternative definitions of robustness are made in different contexts. Moreover, there are different subjects of robustness, such as robust decisions, robust solutions, or robust methods and algorithms. In its general form, robustness refers to the ability of the subject to cope well with uncertainties. The different ways in which the performance of the subject is evaluated and the framework used for modeling the uncertainties lead to many alternative definitions of robustness. The concepts and definitions of robustness originally emerged as independent of the field of multiple criteria decision making (MCDM). In recent years, however, the relationship between robustness and multiple criteria decision analysis has been observed by a number of researchers (see, for instance, Roy (1998), Vincke (1999), Hites et al. (2003)). The previous issues of this newsletter have featured articles by prominent MCDM researchers contributing to the discussion of robustness mostly from the point of view of multiple criteria decision analysis. In this article, we will look at the issue more from an optimization perspective.
Robustness without probabilities
Since uncertainty is a critical element of robustness, taking a probabilistic modeling approach to the problem sounds quite natural. However, for the purposes of solution practicality and interpretation ease, it is possible to avoid a probabilistic approach and study the problem under a fully deterministic optimization setting. As such, the field of robust optimization has been the focus of several studies. One construct in robust optimization calls for introducing different scenarios into a single objective optimization problem to hedge against the uncertainties in the decision environment as it occurs with different realizations of data. Scenarios can be defined in two different ways, by defining continuous intervals (Averbakh (2004), Yaman (2001)) or by defining discrete scenarios. For the case of continuous intervals, there are certain parallels to parametric programming. Whether this class of research relates to previous studies in MCDM which considers multiple objective optimization with interval data poses an interesting question.
Robust Optimization and Multiple Objective Optimization
On the discrete scenarios front, the deviation robust decision, as Kouvelis and Yu (1997) have defined it, is a decision that minimizes the maximum deviation from individual criterion best values. This is what has been known as minimizing the Tchebycheff distance to the ideal solution of a multiple objective optimization problem in MCDM. Bowman (1975) introduced this approach as a means of characterizing efficient solutions. Kouvelis and Yu (1997) have noticed that the robust optimization problem and the multiple objective optimization problem have similarities when certain assumptions are met. This implies, obviously, that the relationship between the two different problems can lead to interesting developments for the solution of both.
The similarity between the discrete scenario optimization problem and the multiple objective optimization problem can lead to interesting new research topics. In general, the robust optimization problems that are dealt with have resulted in proposition of novel solution procedures and algorithms for efficient solution of the problem. Whether these solution approaches can be utilized to solve particular multiple objective optimization problems is a question worthy of investigation. Recently, Kouvelis and Sayin (2005) have studied the computational aspects of an algorithm for bicriteria discrete optimization motivated by ideas in robust optimization. Their algorithm performs an exhaustive search in the weight space while solving corresponding weighted robust optimization problems. The algorithm is originally designed to obtain all efficient solutions of the Multiple Objective Discrete Optimization problem but it can be customized to generate a representative sample of the efficient set as well.
A recent study that relates robustness to Multiple Criteria Optimization in a different way is given by Perny, Spanjaard and Storme (2004). Their work is representative of an alternative way of approaching the relationship between robustness and efficiency. By describing robustness in one particular way that guarantees efficiency of resulting solutions, they argue that an algorithm for finding robust solutions to a decision problem can serve as a means of creating a sample of efficient solutions since the set of efficient solutions may be too large to be useful especially in discrete optimization problems.
Another link between robust optimization and multiple objective optimization is possible via the max-ordering problem which calls for optimizing the worst of several objective functions and is therefore by definition a min-max type problem. Although this problem is not equivalent to the multiple objective optimization problem as it is, it is possible to generalize the problem definition to lexicographic max-ordering, and then a further generalization of the objective function by the introduction of weights brings equivalence to multiple objective optimization (Ehrgott (1997)). Relating the max-ordering problem with studies that work on equivalent definitions of robustness may lead to further research questions.
As discussed above, we see more and more algorithms that use concepts of robust optimization for finding some or all of efficient solutions of the multiple objective optimization problem. When robustness is defined based on possible variations of data representations in the objective function of a single objective optimization problem, the parallelism is in a sense not surprising. As research in robust optimization has led to cultivation of many specialized algorithms to solve the defined robust problems, this approach provides a new opportunity for enumerating efficient solutions of certain multiple objective optimization problems.
Robustness in a probabilistic setting
There are also many unexplored alternatives, especially regarding probabilistic definitions of robustness. Although the parallelism between such studies of robustness and multiple objective optimization is not as straight forward as in the deterministic case, and the presence of probabilistic definitions might pose difficulties in terms of describing and interpreting the associated multiple objective optimization problem, such efforts might turn out to be quite rewarding since these robustness algorithms are usually computationally more efficient than their deterministic discrete scenarios counterparts. In particular, Bertsimas and Sim (2003) show that while the use of discrete scenarios lead to NP-hard problems even for cases where the simple single objective optimization problem is polynomially solvable, their definition of robustness leads to a polynomially solvable problem when the original problem is a polynomially solvable 0-1 programming problem.
Conclusion
We have seen that some definitions and tools of robust optimization are being used in multiple objective optimization to find the efficient solutions. In the future, working on alternative, perhaps more selective, definitions of efficiency might lead to establishing links to certain other forms of robustness that have been demonstrated to lead to computationally more tractable solution algorithms. In that respect, the bibliography of robust optimization given by Nikulin (2004) constitutes a good starting point.
References
Averbakh, I. & Lebedev, V., “Interval data minmax regret network optimization problems,” Discrete Applied Mathematics, 138(3), 289–301, 2004.
Bertsimas, D., Sim, M., “Robust discrete optimization and network flows,” Mathematical Programming, 98, 49-71, 2003.
Bowman, V.J., “On the relationship of the Tchebycheff norm and the efficient frontier of multiple criteria objectives,” Lecture Notes in Economics and Mathematical Systems, 130:76–85, 1975.
Ehrgott, M. Multiple Criteria Optimization: Classification and Methodology. Shaker Verlag, Aaachen, 1997.
Hites, R., De Smet, Y., Risse, N., Salazar-Neumann M., Vincke, P., “A comparison between multicriteria and robustness frameworks,” IS-MG 2003/16, Universite Libre de Bruxelles.
Kouvelis, P. and Sayin, S., “Algorithm robust for the bicriteria discrete optimization problem,” Annals of Operations Research, forthcoming, 2005.
Kouvelis, P. and Yu, G.. Robust Discrete Optimization and Its Applications. Kluwer,1997.
Nikulin, Y., “Robustness in Combinatorial Optimization and Scheduling Theory: An Annotated Bibliography,” http://www.optimization-online.org/DB_HTML/2004/11/995.html, 2004.
Perny, P., Spanjaard, O., L.X. Storme, “A decision-theoretic approach to robust optimization in multivalued graphs,” University of Paris, Working Paper, 2004.
Roy, B., “A missing link in operational research decision aiding: robustness analysis,” Foundations of Computing and Decision Sciences, 23(3):141-160, 1998.
Vincke, P., “Robust solutions and methods in decision aid,” Journal of Multicriteria Decision Analysis, 8:181-187, 1999.
Yaman, H., Karasan, O. E., & Pinar, M. C., “The robust spanning tree problem with interval data,” Operations Research Letters, 29(1), 31–40, 2001.
EWG-MCDA Newsletter, Series 3, No.11, Spring 2005