Ordinal optimization: Difference between revisions

Revision as of 08:26, 27 October 2021

Revision as of 09:20, 22 August 2022

Line 1:

In [[mathematical optimization]], '''ordinal optimization''' is the maximization of functions taking values in a [[partially ordered set]] ("poset").<ref name=dh03>[[Brenda L. Dietrich{{sfn|Dietrich, B. L.]]; [[Alan J. Hoffman|Hoffman, A. J.]] On greedy algorithms, partially ordered sets, and submodular functions. ''IBM J. Res. Dev.'' 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. }}{{isbnsfn|0-691-03244-0Topkis|1998}} <!-- MR1614637 (99i:90024) --></ref><ref>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. {{isbnsfn|0-471-16015-6Singer|1997}} <!-- MR1461544 --></ref><ref>Björner, Anders{{sfn|Bj&ouml; rner|Ziegler, Günter M. Introduction to greedoids. ''Matroid applications'', 284–357, Encyclopedia Math. Appl., 40, Cambridge Univ. Press, Cambridge, |1992,<!-- MR1165545 (94a:05038) --></ref>}} Ordinal optimization has applications in the theory of [[queuing theory|queuing]] [[flow network|networks]].

== 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]].{{sfn|Fujishige|2005}}{{sfn|Gondran|Minoux|2008}}{{sfn|Dietrich|Hoffman|2003}}{{sfn|Murota|2003}}{{sfn|Topkis|1998}}{{sfn|Zimmermann|1981}}{{sfn|Cuninghame-Green|1979}}

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 name=dh03/><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|___location = River Edge,&nbsp;NJ|year= 2002|pages=xx+367|isbn=981-238-067-1|mr=1921556}}</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 booksfn| 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 booksfn|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 booksfn|author1=Heidergott, Bernd |author2=Oldser, Geert Jan |author3=van &nbsp;der &nbsp;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|mr=2188299 }}</ref>

== See also ==

* [[Stochastic optimization]]

* [[Computational complexity theory]]

Line 110 ⟶ 109:

== References ==

{{reflist|colwidth=30em}}

== Further reading ==

* {{wikicite|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={{harvid|Fujishige|2005}}}}

* {{wikicite|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={{harvid|Gondran|Minoux|2008}}}}

* 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) -->

* {{wikicite|Dietrich, B. L.; Hoffman, A. J. On greedy algorithms, partially ordered sets, and submodular functions. ''IBM J. Res. Dev.'' 47 (2003), no. 1, 25–30. <!-- MR1957350 (2003k:90102) -->|ref={{harvid|Dietrich|Hoffman|2003}}}}

* 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) -->

* {{wikicite|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={{harvid|Murota|2003}}}}

* Dietrich, B. L.; Hoffman, A. J. On greedy algorithms, partially ordered sets, and submodular functions. ''IBM J. Res. Dev.'' 47 (2003), no. 1, 25–30. <!-- MR1957350 (2003k:90102) -->

* {{wikicite|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={{harvid|Topkis|1998}}}}

* 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) -->

* {{wikicite|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. {{isbn|0-471-16015-6}} <!-- MR1461544 -->|ref={{harvid|Singer|1997}}}}

* 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) -->

* {{wikicite|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) -->|ref={{harvid|Bj&ouml;rner|Ziegler|1992}}}}

* 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. {{isbn|0-471-16015-6}} <!-- MR1461544 -->

* {{wikicite|Zimmermann, U. ''Linear and combinatorial optimization in ordered algebraic structures''. Ann. Discrete Math. 10 (1981), viii+380 pp. <!-- MR0609751 -->|ref={{harvid|Zimmermann|1981}}}}

* 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) -->

* {{wikicite|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={{harvid|Cuninghame-Green|1979}}}}

* Zimmermann, U. ''Linear and combinatorial optimization in ordered algebraic structures''. Ann. Discrete Math. 10 (1981), viii+380 pp. <!-- MR0609751 -->

* {{cite book|author1author-last1=Baccelli, |author-first1=François &nbsp;Louis |author2author-last2=Cohen, |author-first2=Guy |author3author-last3=Olsder, |author-first3=Geert &nbsp;Jan |author4author-last4=Quadrat, |author-first4=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}}

* 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 -->

* {{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|author1author-last1=Heidergott, |author-first1=Bernd |author2author-last2=Oldser, |author-first2=Geert &nbsp;Jan |author3author-last3=van &nbsp;der &nbsp;Woude, |author-first3=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|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. Ilić]]. ''Price-Based Commitment Decisions in the Electricity Market''. Advances in industrial control. London: Springer, 1999. {{isbn|978-1-85233-069-9}}