Ordinal optimization: Difference between revisions

Revision as of 22:39, 29 March 2011

Revision as of 00:46, 2 September 2011

Line 27:

* The set of [[subset]]s of a given set (its [[power set]]) ordered by [[subset|inclusion]]

* The set of subspaces of a [[vector space]] ordered by inclusion.

* For a partially ordered set ''P'', the [[sequence space]] containing all [[sequence]]s of elements from ''P'', where sequence ''a'' precedes sequence ''b'' if every item in ''a'' precedes the corresponding item in ''b''. Formally, <big>(''a''_''n'')_''n''∈ℕ&nbsp;&le;≤&nbsp;(''b''_''n'')_''n''∈ℕ</big> if and only if <big>''a''_''n''&nbsp;&le;≤&nbsp;''b''_''n''</big> for all ''n'' in ℕ.

* For a set ''X'' and a partially ordered set ''P'', the [[function space]] containing all functions from ''X'' to ''P'', where ''f'' ≤ ''g'' if and only if ''f''(''x'') ≤ ''g''(''x'') for all ''x'' in ''X''.

* The vertex set of a [[directed acyclic graph]] ordered by [[reachability]].

Line 90:

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. ISBN 0-444-52086-4 <!-- MR2171629 (2006d:90098) --></ref><ref>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. ISBN 978-0-387-75449-9 <!-- MR2389137 (2009g:16066) --></ref><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>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. ISBN 0-89871-540-7 <!-- MR1997998 (2004f:90007) --></ref><ref>Topkis, Donald M. ''Supermodularity and complementarity''. Frontiers of Economic Research. Princeton University Press, Princeton, NJ, 1998. xii+272 pp. ISBN 0-691-03244-0 <!-- MR1614637 (99i:90024) --></ref><ref>Zimmermann, U. ''Linear and combinatorial optimization in ordered algebraic structures''. Ann. Discrete Math. 10 (1981), viii+380 pp. <!-- MR0609751 --></ref><ref>Cuninghame-Green, Raymond ''Minimax algebra''. Lecture Notes in Economics and Mathematical Systems, 166. Springer-Verlag, Berlin-New York, 1979. xi+258 pp. ISBN 3-540-09113-0 <!-- MR0580321 --></ref>

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&nbsp; Co.,&nbsp;Inc|River Edge,&nbsp;NJ, 2002|pages=xx+367|isbn=981-238-067-1|idmr={{MR|1921556}}|}}</ref>

== Ordinal optimization in computer science and statistics ==

Line 97:

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. ISBN 0-201-89685-0. Section 5.3.3: Minimum-Comparison Selection, pp.207&ndash;219.</ref><ref>[[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 9: Medians and Order Statistics, pp.183&ndash;196. Section 14.1: Dynamic order statistics, pp.302&ndash;308.</ref>

[[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&nbsp;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 &&nbsp;Sons|___location=New York|year=1979|pages=xxv+573|isbn=0-471-05177-2|idmr={{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>

== Applications ==

{{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|1994|pages=xiv+297|isbn=0-471-58041-4|idmr={{MR|1266839}} }}</ref><ref>{{ cite book|author=Baccelli, François Louis; Cohen, Guy; Olsder, Geert Jan; 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 |idmr={{MR|1204266}} }}</ref><ref>{{ cite book|author=Heidergott, Bernd; Oldser, Geert Jan; 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, 0-691-11763-2, 0-691-11763-2|idmr={{MR|2188299}} }}</ref>

== See also ==

Line 127:

* Cuninghame-Green, Raymond ''Minimax algebra''. Lecture Notes in Economics and Mathematical Systems, 166. Springer-Verlag, Berlin-New York, 1979. xi+258 pp.&nbsp;ISBN 3-540-09113-0 <!-- MR0580321 -->

* {{ cite book|author=Baccelli, François Louis; Cohen, Guy; Olsder, Geert Jan; 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

|idmr={{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|1994|pages=xiv+297|isbn=0-471-58041-4|idmr={{MR|1266839}}|}}

* {{ cite book|author=Heidergott, Bernd; Oldser, Geert Jan; 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, 0-691-11763-2, 0-691-11763-2|idmr={{MR|2188299}}|}}

* [[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. ISBN 9781852330699