21
$\begingroup$

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

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

Improve this question
$\endgroup$
4
  • 8
    $\begingroup$ Did someone say "linear algebra"? $\endgroup$
    – David
    Commented Aug 1, 2019 at 11:44
  • 4
    $\begingroup$ It depends on what is considered "pure" math. Once "pure" math is applied to O.R., it's now applied math. $\endgroup$
    – Mark L. Stone
    Commented Aug 1, 2019 at 19:23
  • 3
    $\begingroup$ 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. $\endgroup$
    – Rob
    Commented Aug 2, 2019 at 11:15
  • 3
    $\begingroup$ 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. $\endgroup$
    – LarrySnyder610
    Commented Aug 2, 2019 at 13:14

9 Answers 9

Reset to default
18
$\begingroup$

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.  

Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ Very interesting examples, particularly the latter one - I have never thought of instances where OR can be applied to pure mathematics! $\endgroup$
    – TheSimpliFire ♦
    Commented Jul 31, 2019 at 12:04
  • 3
    $\begingroup$ 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". $\endgroup$
    – Arnaud D.
    Commented Aug 1, 2019 at 8:26
15
$\begingroup$

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.

Improve this answer
$\endgroup$
10
$\begingroup$

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

Improve this answer
$\endgroup$
10
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ Yes, I would count combinatorics as a branch. Though I tend not to think of statistics (like probability distributions) as "pure"... $\endgroup$
    – TheSimpliFire ♦
    Commented Jul 31, 2019 at 13:46
  • 4
    $\begingroup$ Fair enough. I was thinking metric spaces (pure) > probability (applied) > OR. I added a middle step. :) $\endgroup$
    – LarrySnyder610
    Commented Jul 31, 2019 at 13:52
  • 3
    $\begingroup$ Then measure theory counts as well since it is the pure foundation of probabilty. $\endgroup$
    – Thomas Kalinowski
    Commented Jul 31, 2019 at 21:49
  • 3
    $\begingroup$ 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. $\endgroup$
    – prubin ♦
    Commented Jul 31, 2019 at 21:55
8
$\begingroup$

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.

Improve this answer
$\endgroup$
5
$\begingroup$

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.

Improve this answer
$\endgroup$
3
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ +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 $\endgroup$
    – Mark L. Stone
    Commented Sep 21, 2020 at 12:28
2
$\begingroup$

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.

Improve this answer
$\endgroup$
-1
$\begingroup$

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

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.