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.

$\endgroup$
  • 7
    $\begingroup$ Did someone say "linear algebra"? $\endgroup$ – David Aug 1 '19 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 Aug 1 '19 at 19:23
  • 2
    $\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 Aug 2 '19 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 Aug 2 '19 at 13:14

10 Answers 10

17
$\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$
  • 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 Jul 31 '19 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. Aug 1 '19 at 8:26
14
$\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$
11
$\begingroup$

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.

Zais, Mark and Manuel Laguna. "A graph coloring approach to the deployment scheduling and unit assignment problem." Journal of Scheduling 19.1 (2016): 73-90.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Thanks for your detailed answer (and the links). I'm very surprised at how much pure mathematics can be involved in OR! $\endgroup$ – TheSimpliFire Jul 31 '19 at 18:53
  • 4
    $\begingroup$ interesting to count graph theory to pure maths... isn't then combinatorial optimization all pure maths? $\endgroup$ – Marco Lübbecke Aug 3 '19 at 23:42
  • 3
    $\begingroup$ @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. $\endgroup$ – Dipayan Banerjee Aug 4 '19 at 0:05
9
$\begingroup$

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

| improve this answer | |
$\endgroup$
9
$\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$
  • 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 Jul 31 '19 at 13:46
  • 3
    $\begingroup$ Fair enough. I was thinking metric spaces (pure) > probability (applied) > OR. I added a middle step. :) $\endgroup$ – LarrySnyder610 Jul 31 '19 at 13:52
  • 3
    $\begingroup$ Then measure theory counts as well since it is the pure foundation of probabilty. $\endgroup$ – Thomas Kalinowski Jul 31 '19 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 Jul 31 '19 at 21:55
7
$\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$
4
$\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$
2
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • $\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 Sep 21 at 12:28
1
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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