License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CALCO.2021.9
URN: urn:nbn:de:0030-drops-153643
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15364/
Bonchi, Filippo ;
Di Giorgio, Alessandro ;
Zanasi, Fabio
From Farkas' Lemma to Linear Programming: an Exercise in Diagrammatic Algebra ((Co)algebraic pearls)
Abstract
Farkas' lemma is a celebrated result on the solutions of systems of linear inequalities, which finds application pervasively in mathematics and computer science. In this work we show how to formulate and prove Farkas' lemma in diagrammatic polyhedral algebra, a sound and complete graphical calculus for polyhedra. Furthermore, we show how linear programs can be modeled within the calculus and how some famous duality results can be proved.
BibTeX - Entry
@InProceedings{bonchi_et_al:LIPIcs.CALCO.2021.9,
author = {Bonchi, Filippo and Di Giorgio, Alessandro and Zanasi, Fabio},
title = {{From Farkas' Lemma to Linear Programming: an Exercise in Diagrammatic Algebra}},
booktitle = {9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021)},
pages = {9:1--9:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-212-9},
ISSN = {1868-8969},
year = {2021},
volume = {211},
editor = {Gadducci, Fabio and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15364},
URN = {urn:nbn:de:0030-drops-153643},
doi = {10.4230/LIPIcs.CALCO.2021.9},
annote = {Keywords: String diagrams, Farkas Lemma, Duality, Linear Programming}
}
|
Keywords: |
|
String diagrams, Farkas Lemma, Duality, Linear Programming |
|
Collection: |
|
9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
08.11.2021 |
