Applications of Linear Programming to pure mathematics

Question

This semester I'm taking a course in Linear Programming. While the topic is very interesting, all the applications I can find about this topic seem to be outside of mathematics. What are some applications of Linear Programming to pure math? (specially in number theory / algebra / algebraic geometry)

Answer 1

At first, it should be noted that Linear Programming (LP) has benefited from many mathematical tools, for a review, see e.g., Algebraic and Topological Tools in Linear Optimization and Integer Programming and Number Theory.

Moreover, due to its widespread usage, LP has become a strong driver for the study of challenging math problems such as $d$-step conjecture for polyhedrons (see this Acta Mathematica paper: The d-step conjecture for polyhedra of dimension $d<6$) or the development of branches of mathematics such as convex analysis and tropical geometry (see Chapter 1.2 in the book Introduction to Tropical Geometry and pages 1031-1032 in this paper).

The relationship between LP and mathematics is not one-sided and LP and its well-known extensions, such as convex optimization and integer programming, has been applied in different fields of mathematics.

• Convex Optimization, a nice non-linear extension of LP that can be solved efficiently, has found many applications in geometry such as projection on a set, distance between sets, Euclidean distance and angle problems, extremal volume ellipsoids, etc. (see chapter 8 of the book Convex Optimization)
• Integer programming, a discrete counterpart of LP that can be solved efficiently using LP-based branch-and-bound, has been also applied for analyzing and solving difficult graph-theoretic problems (see chapters on applications of the book Combinatorial Optimization). The paper pointed out by @MishaLavrov in a comment is an interesting usage of integer programming to disprove conjectures and improve several lower bounds in extremal combinatorics.
• Semidefinite Programming (SDP) is a very recent extension of LP, for which an efficient algorithm designed by Farid Alizadeh. In SDP, the order $\ge$ is replaced by $\succeq$. A number of recent papers provided direct or computer-assisted proofs based on Flag Algebras, allowing one to establish bounds through a double-counting argument by solving SDP models to prove various results in extremal combinatorics (see this paper and references therein).
• The major theoretical breakthrough that LP models with rational input data can be solved in polynomial time is a key result in theoretical computer science (see The New York Times paper Leonid Khachiyan, 52; Helped to Advance Computer Math and chapter 3 of the book 7).
• Another interesting application of LP is in probability theory where the Wasserstein distance (used to compare different probability measures) can be obtained from a transportation problem when the sample space is finite (a well-known LP problem taught in undergrad LP courses, can be solved in polynomial time).
• The second application of LP in probability theory is to derive sharp analytical bounds for the probability of the union of events or other quantity with partial information, see these interesting papers 13, 14, 15, and references therein.
• LP enables us to obtain a Nash equilibrium for a two-player zero-sum game with finite strategy sets in polynomial time, which is of high theoretical importance as still no polynomial algorithm has discovered to find a Nash equilibrium of two-player general-sum game with finite strategy sets. In fact, this brilliant application of LP in game theory warmly opened the door to develop the amazing concept of duality in optimization (inspired by John von Neumann's min-max concept) with many theoretical applications in other fields.
• LP bounding has been used in the sphere packing problem (what fraction of $\mathbb R^n$ can be covered by congruent balls not intersecting except along their boundaries). Here, I list a number of papers published in $\color{red}{\text{Annals of Mathematics}}$, the most prestigious journal in mathematics, on sphere packing in which linear programming has been successfully used:
• Universal optimality of the $E_8$ and Leech lattices and interpolation formulas,
• The sphere packing problem in dimension 24
• New upper bounds on sphere packings I

I quote the following statement from the third paper:

Linear programming bounds (Delsarte, 1972) are the most powerful known technique for producing upper bounds in such problems. In particular, Kabatiansky and Levenshtein (1978) use this technique to prove the best bounds known for sphere packing density in high dimensions.

Answer 2

Some applications of duality in linear programming are:

• It provides a unifying framework for a lot of min-max theorem (Kőnig-Egervary theorem, Hall's theorem, Tutte-Berge formula, Menger's theorem, Max-flow min-cut, Dilworth’s theorem, matroid intersection theorem...)
• Is is the basis for a lot of approximation guarantee results, by the use of rounding procedures.
• It can give some theoretical bounds (LP bound and MRRW bound in the theory of codes, LP bounds for sphere packing)