2026-08-17T09:52:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15364 2024-03-06T10:55:14Z ddc:004 open_access

From Farkas' Lemma to Linear Programming: an Exercise in Diagrammatic Algebra ((Co)algebraic pearls) Bonchi, Filippo Di Giorgio, Alessandro Zanasi, Fabio String diagrams Farkas Lemma Duality Linear Programming 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Filippo Bonchi and Alessandro Di Giorgio and Fabio Zanasi 2021 Is Part Of LIPIcs, Volume 211, 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CALCO.2021.9 urn:nbn:de:0030-drops-153643 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2021.9 eng https://creativecommons.org/licenses/by/4.0/legalcode