# Applications of pure mathematics in operations research

This is a question that I've been thinking about for a while, as my background is mainly on pure mathematics.

From a few OR papers that I've looked at, I could identify some areas of pure mathematics that can be applied to OR:

• (Analytic) Number Theory: deriving asymptotics such as polynomial time

• Metric Spaces: use of the Euclidean metric in TSP

• Differential Geometry: optimal transportation problems1 in this case, the Monge and Kantorovich formulations.

Are there other branches of pure mathematics that are currently applied in OR? For each branch that you specify, at least one reference to literature would be much appreciated.

Reference

 Loeper, G. (2009). On the regularity of solutions of optimal transportation problems. Acta Math. 202:241-283. doi: 10.1007/s11511-009-0037-8.

• Did someone say "linear algebra"? Aug 1, 2019 at 11:44
• It depends on what is considered "pure" math. Once "pure" math is applied to O.R., it's now applied math. Aug 1, 2019 at 19:23
• This seems like a list request, a FAQ that could be placed on our Meta. Asking for "at least one reference" for each branch will make for a long answer, and a useful FAQ for our Meta.
– Rob
Aug 2, 2019 at 11:15
• I agree that OR.SE seems OK with big list questions. We have a bunch of them. This one seems on-topic to me. As for the big-list tag, no one has raised that on Meta. I don't think I really see the need for that tag but if someone does, a Meta post would spark some discussion. Aug 2, 2019 at 13:14

In the following paper Grothendieck inequalities are applied to OR (Grothendieck was one (if not THE) pioneer of algebraic geometry.)

Briët, Jop, and Frank Vallentin. "Grothendieck inequalities for semidefinite programs with rank constraint." arXiv preprint arXiv:1011.1754 (2010).

Another example where it is the other way around, i.e. where OR is used to help pure mathematics is the following in which Linear Programming is used to calculate bounds for densities of some measurable sets:

de Oliveira Filho, Fernando Mário, and Frank Vallentin. "Fourier analysis, linear programming, and densities of distance avoiding sets in ℝn." Journal of the European Mathematical Society 12.6 (2010): 1417-1428.

• Very interesting examples, particularly the latter one - I have never thought of instances where OR can be applied to pure mathematics! Jul 31, 2019 at 12:04
• While I would never try to argue the status of Grothendieck as pioneer of algebraic geometry, it should be noted that his early work was more about functional analysis (according to Wikipedia, it seems that he switched between 1955 and 1957). In particular, the paper you linked to cites a Grothendieck paper from 1953 on the tensor product of Banach spaces, and calls Grothendieck's inequality "a fundamental inequality in the theory of Banach spaces". Aug 1, 2019 at 8:26

There's a pretty active research area on incorporating group theory into integer programming (since symmetry can cause a lot of headaches during branch-and-bound). See The Group-Theoretic Approach in Mixed Integer Programming by Richard and Dey, for example.

From graph theory, graph coloring can be applied to scheduling problems (from logistics and elsewhere in OR). An early paper by Leighton (1979) presents a scheduling algorithm based on graph coloring, and the introduction discusses the relationship between graph coloring and optimization problems as a whole. Quoting:

... the constraints are usually expressible in the form of pairs of incompatible objects (e.g. , pairs of chemicals that cannot be stored on the same shelf). Such incompatibilities are usefully embodied through the structure of a graph. Each object is represented by a node and each in compatibility is represented by an edge joining the two nodes. A coloring of this graph is then simply a partitioning of the objects into blocks (or colors) such that no two incompatible objects end up in the same block. Thus, optimal solutions to such problems may be found by determining minimal colorings for the corresponding graphs.

Recently, Januario et al. (2016) apply graph coloring for sports league scheduling, and Zais and Laguna (2016) do the same for personnel deployment scheduling. Some of the OR applications of graph coloring are applying coloring algorithms, but the fundamental ideas are from pure math.

Januario, Tiago, Sebastián Urrutia, Celso C. Ribeiro, and Dominiquede Werra. "Edge coloring: A natural model for sports scheduling." European Journal of Operational Research 254.1 (2016): 1-8.

Leighton, Frank. "A Graph Coloring Algorithm for Large Scheduling Problems." Journal of Research of the National Bureau of Standards 84.6 (1979): 489-506.

• Thanks for your detailed answer (and the links). I'm very surprised at how much pure mathematics can be involved in OR! Jul 31, 2019 at 18:53
• interesting to count graph theory to pure maths... isn't then combinatorial optimization all pure maths? Aug 3, 2019 at 23:42
• @MarcoLübbecke You could be right - I also thought about the purity of graph theory some time after submitting my answer. I don't have enough mathematical background to judge where the boundary between pure and applied math lies exactly, but I hope that if a pure mathematician comes across my answer, they will still find it interesting.
– dxb
Aug 4, 2019 at 0:05

The latest Notices have a nice article about Algebraic and Topological Tools in Linear Optimization.

I don't know if you consider combinatorics "pure math." (I do.) If so, combinatorics is ubiquitous in OR.

Calculus is also used heavily in many OR fields. One easy example is inventory theory (e.g., the newsvendor problem). Another is calculating expected values over probability distributions, etc.

Speaking of which, metric spaces are central to probability theory, and probability theory is central to many fields of OR such as stochastic processes.

• Yes, I would count combinatorics as a branch. Though I tend not to think of statistics (like probability distributions) as "pure"... Jul 31, 2019 at 13:46
• Fair enough. I was thinking metric spaces (pure) > probability (applied) > OR. I added a middle step. :) Jul 31, 2019 at 13:52
• Then measure theory counts as well since it is the pure foundation of probabilty. Jul 31, 2019 at 21:49
• Convexity (in the geometric sense, as well as the functional sense) is a foundation for much of optimization. As one small example, handling rays from unbounded LPs (which, when the LP is the dual, provides insight into why the primal is infeasible) relies implicitly on the Minkowski-Weyl theorem.
– prubin
Jul 31, 2019 at 21:55

### Boolean Algebra

Used in network flow and pseudo-Boolean optimisation.

Hammer, P. L., Rudeanu, S. (1968). Boolean Methods in Operations Research and Related Areas. ISBN: 978-3-642-85825-3.

### First-Order Logic

Primal and dual algorithms for "blockages".

Hooker, J. N. (1993). New methods for computing inferences in first order logic. Annals of Operations Research. 43(9):477-492.

Adding on to dxb's answer, we can take a step back and apply Algebraic Geometry to solve discrete constraint satisfaction problems (for example, Graph Coloring). The idea is to model the constraints as a system of multivariate polynomials then use Groebner basis to solve them.

In the case of graph coloring, to obtain a $$k$$-coloring we let each color correspond to a root of unity and set up $$n$$ variables $$x_1, \dots, x_n$$, one for each vertex of the graph. If the graph is $$k$$-colorable, there is an assignment of roots of unity (colors) to the variables $$x_1, \dots, x_n$$ such that a certain set of polynomial constraints are satisfied.

Jordan algebra is used to analyze interior-point methods for optimization over symmetric cones. Here is a random reference.

• +1 But there are other applications of Jordan Algebras mathoverflow.net/questions/230159/… . And as I wrote in my comment to the question: It depends on what is considered "pure" math. Once "pure" math is applied to O.R., it's now applied Sep 21, 2020 at 12:28

On the applied side, an interesting one is tensor calculus which is used a lot in aerodynamical optimisation. Tensors are used to employ curvilinear coordinate systems which follow the flow lines of the particles. Although this might sound specific to fluid mechanics, certain specialised methods in aerodynamics, such as calculating the adjoint derivatives of the flow equations, include a lot of interplay between the optimisation methods and the fluid mechanics math.

Another area that I looked into during my PhD was manifold evolution using the Ricci flow in order to evolve the metric tensor of the vector space so that the problem can become easier to solve.

With regards to the topic of Optimal Transportation Problem I strongly recommend

L.V. Kantorovich, On the Translocation of Masses (1942), in Management Science, vol. 5, n. 1, october 1958, pp. 1-4