18
$\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$
  • 6
    $\begingroup$ Did someone say "linear algebra"? $\endgroup$ – David Aug 1 at 11:44
  • 2
    $\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 at 19:23
  • 1
    $\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 at 11:15
  • 1
    $\begingroup$ Re: the close vote for OR.Meta - from what I've seen, usually long lists are still on-topic on Main rather than Meta. E.g. from MSE, there is the tag (big-list) for such questions. @Rob $\endgroup$ – TheSimpliFire Aug 2 at 12:23
  • 2
    $\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 at 13:14
16
$\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.  

$\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 at 12:04
  • 2
    $\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 at 8:26
10
$\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.

$\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 at 18:53
  • 3
    $\begingroup$ interesting to count graph theory to pure maths... isn't then combinatorial optimization all pure maths? $\endgroup$ – Marco Lübbecke Aug 3 at 23:42
  • 2
    $\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 at 0:05
10
$\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.

$\endgroup$
9
$\begingroup$

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

$\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.

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

$\endgroup$
3
$\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.

$\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.