Content deleted Content added
m refs using AWB |
m Manually reviewed edit to replace magic words per local rfc |
||
Line 1:
In [[mathematical optimization]], '''ordinal optimization''' is the maximization of functions taking values in a [[partially ordered set]] ("poset").<ref>Dietrich, B. L.; Hoffman, A. J. On greedy algorithms, partially ordered sets, and submodular functions. ''IBM J. Res. Develop.'' 47 (2003), no. 1, 25–30. <!-- MR1957350 (2003k:90102) --></ref><ref>Topkis, Donald M. ''Supermodularity and complementarity''. Frontiers of Economic Research. Princeton University Press, Princeton, NJ, 1998. xii+272 pp.
== Mathematical foundations ==
Line 86:
{{Main|Ordered semigroup}}
{{See also|Ordered vector space|Riesz space}}
The poset can be a [[Ordered semigroup|partially ordered algebraic structure]].<ref>Fujishige, Satoru ''Submodular functions and optimization''. Second edition. Annals of Discrete Mathematics, 58. Elsevier B. V., Amsterdam, 2005. xiv+395 pp.
In [[algebra]], an ''ordered semigroup'' is a [[semigroup]] (''S'',•) together with a [[partial order]] ≤ that is ''compatible'' with the semigroup operation, meaning that ''x'' ≤ ''y'' implies z•x ≤ z•y and x•z ≤ y•z for all ''x'', ''y'', ''z'' in ''S''. If S is a [[Group (mathematics)|group]] and it is ordered as a semigroup, one obtains the notion of [[ordered group]], and similarly if S is a [[monoid]] it may be called ''ordered monoid''. [[Ordered vector space|Partially ordered vector space]]s and [[Riesz space|vector lattice]]s are important in [[multiobjective optimization|optimization with multiple objectives]].<ref>{{cite book|last=Zălinescu|first=C.|title=Convex analysis in general vector spaces|publisher=World Scientific Publishing Co., Inc|___location = River Edge, NJ|year= 2002|pages=xx+367|isbn=981-238-067-1|mr=1921556}}</ref>
Line 93:
{{See also|Selection algorithm}}
Problems of ordinal optimization arise in many disciplines. [[Computer science|Computer scientists]] study [[selection algorithm]]s, which are simpler than [[sorting algorithm]]s.<ref>[[Donald Knuth]]. ''[[The Art of Computer Programming]]'', Volume 3: ''Sorting and Searching'', Third Edition. Addison-Wesley, 1997.
[[Statistical decision theory]] studies "selection problems" that require the identification of a "best" subpopulation or of identifying a "near best" subpopulation.<ref>Gibbons, Jean Dickinson; [[Ingram Olkin|Olkin, Ingram]], and Sobel, Milton, ''Selecting and Ordering of Populations'', Wiley, (1977). (Republished as a Classic in Applied Mathematics by SIAM.)</ref><ref>{{cite book|last1=Gupta|first1=Shanti S.|last2=Panchapakesan|first2=S.|title=Multiple decision procedures: Theory and methodology of selecting and ranking populations|series=Wiley Series in Probability and Mathematical Statistics|publisher=John Wiley & Sons|___location=New York|year=1979|pages=xxv+573|isbn=0-471-05177-2|mr=555416}} (Republished as a Classic in Applied Mathematics by SIAM.)</ref><ref>Santner, Thomas J., and Tamhane, A. C., ''Design of Experiments: Ranking and Selection'', M. Dekker, (1984).</ref><ref>Robert E. Bechhofer, Thomas J. Santner, David M. Goldsman. ''Design and Analysis of Experiments for Statistical Selection, Screening, and Multiple Comparisons''. John Wiley & Sons, 1995.</ref><ref>Friedrich Liese, Klaus-J. Miescke. 2008. ''Statistical Decision Theory: Estimation, Testing, and Selection''. Springer Verlag.</ref>
Line 100:
{{See also|Antimatroid|Max-plus algebra|Flow network|Queuing theory|Discrete event simulation}}
Since the 1960s, the field of ordinal optimization has expanded in theory and in applications. In particular, [[antimatroid]]s and the "[[max-plus algebra]]" have found application in [[flow network|network analysis]] and [[queuing theory]], particularly in queuing networks and [[discrete event simulation|discrete-event systems]].<ref>{{cite book| last1=Glasserman|first1=Paul|last2=Yao|first2=David D.|title=Monotone structure in discrete-event systems|series=Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics|publisher=John Wiley & Sons, Inc.|___location=New York|year=1994|pages=xiv+297|isbn=0-471-58041-4|mr=1266839 }}</ref><ref>{{cite book|author1=Baccelli, François Louis |author2=Cohen, Guy |author3=Olsder, Geert Jan |author4=Quadrat, Jean-Pierre |title=Synchronization and linearity: An algebra for discrete event systems|series=Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics|publisher=John Wiley & Sons, Ltd.|___location=Chichester|year=1992|pages=xx+489|isbn=0-471-93609-X |mr=1204266 }}</ref><ref>{{cite book|author1=Heidergott, Bernd |author2=Oldser, Geert Jan |author3=van der Woude, Jacob |title=Max plus at work: Modeling and analysis of synchronized systems, a course on max-plus algebra and its applications|series=Princeton Series in Applied Mathematics|publisher=Princeton University Press|___location=Princeton, NJ|year=2006|pages=xii+213|isbn=978-0-691-11763-8 |
== See also ==
Line 115:
== Further reading ==
* Fujishige, Satoru ''Submodular functions and optimization''. Second edition. Annals of Discrete Mathematics, 58. Elsevier B. V., Amsterdam, 2005. xiv+395 pp.
* Gondran, Michel; Minoux, Michel ''Graphs, dioids and semirings. New models and algorithms''. Operations Research/Computer Science Interfaces Series, 41. Springer, New York, 2008. xx+383 pp.
* Dietrich, B. L.; Hoffman, A. J. On greedy algorithms, partially ordered sets, and submodular functions. ''IBM J. Res. Develop.'' 47 (2003), no. 1, 25–30. <!-- MR1957350 (2003k:90102) -->
* Murota, Kazuo ''Discrete convex analysis''. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2003. xxii+389 pp.
* Topkis, Donald M. ''Supermodularity and complementarity''. Frontiers of Economic Research. Princeton University Press, Princeton, NJ, 1998. xii+272 pp.
* Singer, Ivan ''Abstract convex analysis''. Canadian Mathematical Society Series of Monographs and Advanced Texts. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1997. xxii+491 pp.
* Björner, Anders; Ziegler, Günter M. Introduction to greedoids. ''Matroid applications'', 284–357, Encyclopedia Math. Appl., 40, Cambridge Univ. Press, Cambridge, 1992,<!-- MR1165545 (94a:05038) -->
* Zimmermann, U. ''Linear and combinatorial optimization in ordered algebraic structures''. Ann. Discrete Math. 10 (1981), viii+380 pp. <!-- MR0609751 -->
* Cuninghame-Green, Raymond ''Minimax algebra''. Lecture Notes in Economics and Mathematical Systems, 166. Springer-Verlag, Berlin-New York, 1979. xi+258 pp.
* {{cite book|author1=Baccelli, François Louis |author2=Cohen, Guy |author3=Olsder, Geert Jan |author4=Quadrat, Jean-Pierre |title=Synchronization and linearity: An algebra for discrete event systems|series=Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics|publisher=John Wiley & Sons, Ltd.|___location=Chichester|year=1992|pages=xx+489|isbn=0-471-93609-X
|mr=1204266}}
* {{cite book| last1=Glasserman|first1=Paul|last2=Yao|first2=David D.|title=Monotone structure in discrete-event systems|series=Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics|publisher=John Wiley & Sons, Inc.|___location=New York|year=1994|pages=xiv+297|isbn=0-471-58041-4|mr=1266839}}
* {{cite book|author1=Heidergott, Bernd |author2=Oldser, Geert Jan |author3=van der Woude, Jacob |title=Max plus at work: Modeling and analysis of synchronized systems, a course on max-plus algebra and its applications|series=Princeton Series in Applied Mathematics|publisher=Princeton University Press|___location=Princeton, NJ|year=2006|pages=xii+213|isbn=978-0-691-11763-8 |
* [[Yu-Chi Ho|Ho, Y.C.]], Sreenivas, R., Vakili, P.,"Ordinal Optimization of Discrete Event Dynamic Systems", J. of DEDS 2(2), 61-88, (1992).
* Allen, Eric, and Marija D. Ilic. ''Price-Based Commitment Decisions in the Electricity Market''. Advances in industrial control. London: Springer, 1999.
== External links ==
| |||