Matteo Fischetti
The simpler the better: Thinning out MIP's by Occam's razor
Tuesday, June 16
Entia non sunt multiplicanda sine necessitate (Entities must not be multiplied beyond necessity)
Occam's razor, or law of parsimony (lex parsimoniae), is a problem-solving principle devised by the English Franciscan friar and philosopher William of Ockham (1287–1347). The principle states that among competing hypotheses, the one with the fewest assumptions is more likely be true and should be preferred. Other, more complicated solutions may ultimately prove correct, but—in the absence of certainty—the fewer assumptions that are made, the better. In science, Occam's razor is used as a heuristic guide in the development of theoretical models. In particular, the law of parsimony played a role in Albert Einstein's formulation of special relativity, and in the development of quantum mechanics by Max Planck, Werner Heisenberg and Louis de Broglie.
In my talk I'll show how the law of parsimony can be applied to Mathematical Programming Computation with the aim of “thinning out” unnecessarily complicated models and algorithms. Applications to some specific classes of Mixed-Integer Programming problems will be illustrated, showing that surprisingly simple solutions are sometimes available for notoriously hard problems. My focus will not be on the actual way to achieve the simplification (machinery here being pretty standard), but on the underlying idea that one should try simple approaches before resorting to more complicated ones—thus adhering to Occam's philosophy.
A final word of caution: Occam's razor should not misinterpreted and used as an excuse to only address oversimplified models. Quoting Albert Einstein: “In my view, more complicated systems and their combinations should be considered if there exist physical-empirical reasons to do so ... Everything should be kept as simple as possible, but no simpler.”
Bio
Matteo Fischetti received his master's degree in Electronic Engineering in 1982, and his PhD degree in System Engineering in 1987, both from the University of Bologna. Since 1997 he is full professor of Operation Research at the Department of Information Engineering of the University of Padua. In 1987 he received the “Best Ph.D. Dissertation on Transportation” prize awarded by the Operations Research Society of America, while in 2008 he was part the team receiving the “INFORMS Franz Edelman award” for the work “The New Dutch Timetable: The O.R. Revolution”. Dr. Fischetti is a member of the Editorial Board of the international journals Mathematical Programming Computation and Journal of Combinatorial Optimization. His research interests include mixed-integer programming, combinatorial optimization, vehicle routing and scheduling problems, and polyhedral combinatorics. He published 100+ papers on international journals.
Rüdiger Schultz
Since 1998, Rüdiger Schultz is a Full Professor for Discrete Mathematics and Optimization in the Department of Mathematics at the University of Duisburg-Essen, Germany. His doctoral and habilitation degrees in Mathematics he has received from the Humboldt University Berlin in 1985 and 1995. Dr. Schultz' primary research interests are in optimization under uncertainty, discrete optimization, and in industrial applications of mathematical optimization. His research accomplishments include seminal work on structure, stability, and algorithmic treatment of stochastic programs, in particular of models involving integer variables, risk aversion, and, more recently, also PDE constraints. He has made contributions to real-life applications of mathematical optimization in the power, natural gas, and chemical processes industries. He has co-authored more than 100 scientific papers. Currently, Dr. Schultz is Editor-in-Chief of the journal Computational Management Science" and Area Editor Linear and Stochastic Optimization of Operations Research Letters". He is serving as a member of the editorial boards of five further research journals in Applied Mathematics and Operations Research.
2015 © INFORMS. ALL Rights Reserved.
