Hi, I have been asked to give a course to mathematicians. By mathematicians I mean PhD students in pure mathematics who would attend a doctoral school at Institut Henri Poincaré link text I welcome therefore suggestions on topics that would resonate well. AFAIK, they are interested in seeing how mathematics can impact the real world, and OR is certainly a very good area for this.

Adding some initial topics that seem no brainers 1. Linear programming, geometry of the polytope, duality theorem. 2. Complexity (P vs NP) polynomial methods for LP, simplex algorithm 3. Symmetry handling, computational group theory 4. Combinatorial problems, MIP, applications 5. Research directions, stochastic, non linear, etc

asked 20 Sep '12, 06:51

jfpuget's gravatar image

jfpuget
2.5k310
accept rate: 8%

edited 20 Sep '12, 12:53

2

If you want to score points, cover linear programming in infinite dimensions (in a Hilbert space). Not that I know of any practical applications.

(20 Sep '12, 10:24) Paul Rubin ♦♦

I may enter a zone too far form my comfort zone here, but I'll keep it in mind when preparing material

(20 Sep '12, 10:39) jfpuget

sounds as if you think that there are any operations researchers other than mathematicians, and that you have to do fancy stuff with these "outsiders". the contrary is true. (applied) mathematicians are very open to optimization and operations research, no Hilbert needed here. and again: no real OR without maths. ;-)

(20 Sep '12, 11:49) Marco Luebbecke ♦
1

Marco, I know the audience. These are pure math guys, definitely NOT OR people. That's why I am looking for the pure math angle each time. The course requester is Cedric Villani, Fields medal. He is famous for optimal transport. Well, if you look at what he calls optimal transport you'll see that it has very little to do with the kind of transportation we optimize in OR!

(20 Sep '12, 12:17) jfpuget
1

Following on to what Paul has said, the book "Optimization by Vector Space Methods" by David Luenberger may be helpful. It talks about optimization in vector spaces (linear space, Hilbert space, etc.)

It's a novel math text on optimization (approached from a functional analysis perspective), but it straddles the line between pure mathematics and engineering. The author (of Luenberger observer fame) is extremely well-known in the electrical engineering community.

(20 Sep '12, 14:27) Gilead ♦

Another good resource is Schrijver's Theory of Linear and Integer Programming. Plenty of "real math" there.

(20 Sep '12, 16:25) Matthew Salt... ♦

@Gilead, thanks for the reference

(24 Sep '12, 06:59) jfpuget

Mathew, I agree, Lex' book is a good base for many of the topics I had in my primary list

(27 Sep '12, 08:19) jfpuget
showing 5 of 8 show 3 more comments

Applications of stochastic models (Markov chains, queueing, simulation).

Nonlinear optimization.

Optimal control theory (ties nicely to NLP and linear optimization).

link

answered 20 Sep '12, 10:15

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

thank you, I agree, I hint at these in my last bullet but they deserve a bullet each probably.

(20 Sep '12, 10:20) jfpuget
2

There's a paper by Dantzig about "generalized linear programming" (LP models for optimal control). It uses what amounts to basis functions (I think - read it a long time ago), which should appeal to doctoral candidates in math.

(20 Sep '12, 10:23) Paul Rubin ♦♦

Thanks again I'll try to find it

(20 Sep '12, 10:42) jfpuget

My bad -- it's a book chapter, not a paper.

@INBOOK{Dantzig1971, chapter = {Generalized Linear Programming and Decomposition}, pages = {75--123}, title = {Optimization Methods for Large-scale Systems ... with Applications}, publisher = {McGraw-Hill}, year = {1971}, editor = {David A. Wismer}, author = {George B. Dantzig and Richard M. {van Slyke}}, address = {New York} }

(20 Sep '12, 11:29) Paul Rubin ♦♦

There's also a related paper by Dantzig:

@ARTICLE{Dantzig1966, author = {George B. Dantzig}, title = {Linear Control Processes and Mathematical Programming}, journal = {SIAM Journal on Control and Optimization}, year = {1966}, volume = {4}, pages = {56--60}, number = {1} }

(20 Sep '12, 11:34) Paul Rubin ♦♦

great, thanks

(20 Sep '12, 12:47) jfpuget
showing 5 of 6 show 1 more comments

Any of the following:

link

answered 20 Sep '12, 11:09

yeesian's gravatar image

yeesian
846210
accept rate: 3%

edited 20 Sep '12, 11:19

1

Thanks, I'll think about it. Remember, this is about mathematics, not algorithms. Some of what you say have clear mathematical treatment though.

(20 Sep '12, 12:21) jfpuget
1

I have been careful in not including (meta-)heuristics for that reason: it isn't because meta-heuristics are weak practice, but because it is very hard to proceed (mathematically) from such algorithms to discuss about their properties.

In contrast, it will be alot easier to talk about convergence/approximations when discussing about convex-problems/subgradients/etc. Recent developments in parallel/distributed optimisation also follow nicely from duality/column-generation/decomposition-methods, and are equally relevant to the real world.

(21 Sep '12, 05:01) yeesian

There is some beautiful work done by Jean Lasserre on integer programming duality that connects seemingly unrelated areas of mathematics: lattices, generating series, functional transforms, etc. I believe that Lasserre recently published a book on the area as well. There are also very nice connections between integer programming and ideas from algebraic geometry (e.g., the works of Rekha Thomas, Bernd Sturmfels, etc).

In the realm of interior points methods there are connections between self-scaled barrier functions in conic programming and Euclidean Jordan algebras.

link

answered 26 Sep '12, 16:53

shoda's gravatar image

shoda
612
accept rate: 0%

Thanks, I wasn't aware of that. It looks indeed promising in this context.

(27 Sep '12, 08:20) jfpuget

Metaheuristics, eg: simulated annealing, tabu search, genetic algorithms.

link

answered 20 Sep '12, 09:50

DC%20Woods's gravatar image

DC Woods ♦
4.1k22546
accept rate: 5%

I agree this is a key OR area. What is the mathematical angle I should use according to you? I would think about convergence theorems, approximation algorithms, etc. Do you have something else in mind?

(20 Sep '12, 10:18) jfpuget
1

Just because they are mathematicians, does this mean that anything that isn't mathematical will be uninteresting to them? Metaheuristics are a major part of OR and fascinating regardless of the number of greek symbols and equations. Their power to solve problems that math programming techniques completely fail on might give mathematicians some humility.

(20 Sep '12, 18:02) DC Woods ♦

Well, if they were interested in learning something non mathematical they wouldn't come to my (future) course. As explained by @yeesian, the mathematics of meta heuristics aren't that developed. There are some convergence theorems though, eg for simulated annealing, which is what I might use to introduce some metaheuristics.

(24 Sep '12, 07:06) jfpuget

Sequential convexification methods for identifying convex hulls of discrete sets, including Balas's lift-and-project technique and Adams and Sherali's RLT (reformulation-linearization technique).

link

answered 20 Sep '12, 16:29

Matthew%20Saltzman's gravatar image

Matthew Salt... ♦
4.7k310
accept rate: 17%

Good point, thanks.

(24 Sep '12, 07:07) jfpuget

Sensitivity analysis?

link

answered 20 Sep '12, 09:55

Andrea%20Raiconi's gravatar image

Andrea Raiconi
111
accept rate: 0%

In which context? Duality for LP (or more complex problems)provides some of it, doesn't it? MIP is another story however.

(20 Sep '12, 10:42) jfpuget

Your original set of topics (LP, MIP, complexity, etc) sound great. Pure math students should have some exposure there, and there are books for those topics that would appeal to those who are not afraid of math. I would also recommend adding networks, since many math students have had graph theory. The pure math people I know do not have much knowledge of stochastic methods, so start with the basics if you introduce any stochastic OR topics.

link

answered 26 Sep '12, 16:30

lamclay's gravatar image

lamclay
1314
accept rate: 0%

@lamclay, thanks for confirming my intuition here. Adding network is indeed important. This is really helpful, especially the warning about stochastic methods.

(27 Sep '12, 08:21) jfpuget

It sounds like your audience might be looking for good Applied OR examples. I would suggest looking at past Edelman Award winners for ideas on applied OR. Some examples of OR in practice include Sabre Airline Solutions and IBM. Perhaps talk a little history about the origins of OR from WWII.

link

answered 27 Sep '12, 13:06

larrydag%201's gravatar image

larrydag 1 ♦
3.2k51326
accept rate: 9%

I definitely agree and was planning to introduce the course with extreme ROI examples. Saying that what follows has documented return in excess of 170 billion dollars (cumulated Edelman finalists return) makes people listen more carefully...

PS. Note that I am from IBM where I'm the technical lead for optimization product development ;)

(27 Sep '12, 14:07) jfpuget

A brief introduction to applied techniques, which require both statistics and optimization, would be interesting for statistics-oriented students. Some examples are economic control charts, response surface methodology, and simulation optimization. You might also mention applications of statistical tools in OR. One example that comes to my mind quickly is the application of DOE in tuning parameters of metaheuristics.

link

answered 20 Sep '12, 10:45

Ehsan's gravatar image

Ehsan ♦
4.8k31122
accept rate: 16%

What would be the pure math angle you suggest here?

(20 Sep '12, 12:52) jfpuget

I was thinking algebra and combinatorial design as many statistical techniques require them.

(20 Sep '12, 13:41) Ehsan ♦
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×8
×6

Asked: 20 Sep '12, 06:51

Seen: 2,165 times

Last updated: 27 Sep '12, 14:07

OR-Exchange! Your site for questions, answers, and announcements about operations research.