Connectedness of efficient solutions in multiple criteria combinatorial optimization |
| |
| Institution: | 1. Department of Ophthalmology, Stanford University, CA;2. Department of Neurology & Neurological Sciences, Stanford University, CA;3. Center for Population Health Sciences, Stanford University, CA;4. Department of Anesthesiology, Walter Reed Military Medical Center, Bethesda, MD;5. Center for Clinical and Translational Sciences, University of Illinois, Chicago, IL;6. Department of Ophthalmology and Visual Sciences, University of Illinois, Chicago, IL;7. Department of Anesthesiology, University of Illinois, Chicago, IL;1. Dipartimento di Ingegneria Meccanica, Chimica e dei Materiali, Università degli Studi di Cagliari, Via Marengo 2, Cagliari 09123, Italy;2. Procter & Gamble, Pomezia R&D Research Center, Via Ardeatina 100, Pomezia 00040, Italy;3. Institute of Theoretical and Applied Mechanics ASCR, Centre of Excellence Telč, Batelovská 485, Telč CZ-58856, Czech Republic |
| |
| Abstract: | In multiple criteria optimization an important research topic is the topological structure of the set Xe of efficient solutions. Of major interest is the connectedness of Xe, since it would allow the determination of Xe without considering non-efficient solutions in the process. We review general results on the subject, including the connectedness result for efficient solutions in multiple criteria linear programming. This result can be used to derive a definition of connectedness for discrete optimization problems. We present a counterexample to a previously stated result in this area, namely that the set of efficient solutions of the shortest path problem is connected. We will also show that connectedness does not hold for another important problem in discrete multiple criteria optimization: the spanning tree problem. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
