The LP/IP History viewed by Martin Grötschel in 24 Questions

The concluding talk of CPAIOR this year was given by Martin Grötschel who asked 24 interesting questions about the history of LP and IP.

- The questions about LP were:
- Who described the first linear equations solver?
- Who had the first LP solver (without knowing it)?
- Who formulated the first LP instance?
- Who described the first LP solver?
- Who described the first LP solver with impact in practice?
- Who described the currently most frequently used LP solver?
- Who implemented the first commercial LP code?
- Who received a Nobel Prize for LP?
- Who proved expected polyn. running time of the simplex method first?
- Who described the first polynomial time linear equations solver?
- Who had the first polynomial time LP solver (without knowing it)?
- Who described the first polynomial time LP solver?
- Who described the first polynomial time LP solver with practical impact?
- Who described the currently most frequently used barrier LP solver?
- What is the state of the art in LP solving?

- Which is the most important paper on integer programming?
- Which is the most important paper on combinatorial algorithms?
- Who described the first cutting plane algorithm?
- Who described the first branch&bound algorithm?
- Who described the first branch&cut algorithm?
- Who described the first column generation algorithm?
- Who implemented the first commercial IP code?
- Who described the first polynomial time IP solver?
- What is the state of the art in MIP solving?

- Who described the first CP solver?
- Who had the first CP solver (without knowing it)?
- Who formulated the first CP instance?
- Who described the first CP solver with impact in practice?
- Who described the currently most frequently used CP solver?
- Who implemented the first commercial CP code?
- Who received a Nobel Prize for CP? (I'm not sure we have one ;-) )
- Who described the first backtracking search?
- Who described the Branch and Bound for CP?
- Who described the first global constraint and its filtering algorithm?
- Who described/solved the first scheduling problem with CP?
- ...

Any suggestion/remarks on what the questions/answers could be for CP are very welcome.

Probably some answers can be found in a talk given by Pascal Van Hentenryck at CPAIOR08: "30 Years of Constraint Programming". Maybe CP is simply too young and it doesn't really make sense yet... I like to think that the major discoveries for CP are still to come ;-)

## Aucun commentaire:

## Enregistrer un commentaire