Sunday, 20 January 2013

Back to School

Each year the Dutch Operations Research society (NGB) organizes a seminar together with the Dutch Network on the Mathematics of Operations Research (LNMB). This year we organised the seminar for the 15th time, which traditionally is held in the geographical middle of the Netherlands, Lunteren. In the past few years the central theme for the seminar has been the practical application of Operations Research in a specific area, we had themes like health care, traffic, energy, supply chain optimisation, marketing and humanitarian aid. This year we decided to take a different angle. We wanted to give our members the opportunity to upgrade their knowledge of Operations Research by offering them tutorials on new developments in OR. This idea had gradually grown from the feedback we had had on several webinars and in-company lectures on topics in OR, for example on Portfolio Optimisation (with Professor Sam Savage) and on Robust Optimisation (with Professor Dick den Hertog). These lectures seemed to fill a need to keep up with new developments in OR especially for people that had graduated from university (either on PhD or Master level) some time ago. Theme for the 15thseminar therefore became Back to School.

Conference center "De Werelt", Lunteren

The two main subjects for the seminar we chose are Robust Optimisation (RO) and Mixed Integer Nonlinear Programing (MINLP). Each tutorial consisted of a theoretical introduction by a specialist in the field. For RO we invited Professor Dick denHertog form Tilburg University, for MINLP we invited Professor Jeff Linderoth (@jefflinderoth) from the University of Wisconsin-Madison. Their in-depth discussion aimed to explain the essence of the new developments and focus on the practical use of the techniques presented. Second part of the lecture focussed on the practical application. Marcel Hunting from AIMMS shared insights and modelling tricks in practical MINLP modelling. We closed the seminar with a lecture from Ruud Brekelmans on the use of MINLP in optimizing the Dutch dike heights, a project that has been elected finalist for the 2013 Franz Edelman Award.

Robust optimisation is a recent development in the field of optimisation, having its roots in the early 1970’s. It explicitly takes parameter uncertainty (e.g. measurement, estimation or implementation errors) into account without assuming a specify probability distribution of that uncertainty. Professor Den Hertog explained that instead of seeking to immunize the solution in some probabilistic sense to stochastic uncertainty, with RO a solution is constructed that is optimal for any realization of the uncertainty in a given set. RO starts with modelling the uncertainty region and creating the robust counterpart of the original model. Under certain conditions on the structure of the uncertainty the robust counterpart can be solved with relative ease using LP, CQP or a Conic Optimisation solver. From a practical point of view Professor Den Hertog’s advice on applying RO is to first test the robustness of the solution to the original problem with standard sensitivity analysis or simulation (a best practice in any optimisation challenge). If it is not robust use stochastic programming if the distribution of the uncertain parameter is known, if that’s not the case use RO. In applying RO one must avoid equality constraints when formulating the robust counterpart because this can cause inconsistencies between the solution to the original problem and the solution of the robust counterpart. So modelling expertise required! Professor Den Hertog concluded that Robust Optimisation provides a natural way to modelling uncertainty and that the robust counterpart makes it tractable. A wide variety of applications of RO has already been documented from which we practitioners can extract information for our own robust optimisation projects.

The second main topic of the seminar was Mixed Integer Nonlinear programming (or was it MINLP Wars?) by Professor Jeff “Obi-Wan” Linderoth. As he tweeted, it was a once in a life time experience for him. Professor Linderoth started with the relevance of MINLP, which comes from the fact that the world is not linear. Many decision problems in practice suffer from nonlinearity, think of water network design, petrochemical product blending, and oilfield planning. The need for practical solution methods to address these nonlinearities is therefore high. The normal approach to solve a MINLP is to relax the integrality constraints and construct a convex relaxation of the set of feasible solutions. Then using a branch and bound approach to solve the problem. Professor Linderoth did a lot of research to develop a new approach to MINLP, leveraging on the available MILP technology. In the lecture Professor Linderoth explained the backgrounds on algorithm engineering, (disjunctive) cutting planes and pre-processing. In general he concluded that applying “traditional” techniques from MILP in the domain of MINLP can lead to significant improvements in our ability to solve MINLP instances, a conclusion that Marcel Hunting from AIMMS reconfirmed. He showed how pre-processing and cutting planes were key in performance improvements in CPLEX. He also provided advice to OR practitioners on how to improve solver performance by applying specific reformulations in a MINLP. As an example he showed how the product of integer and real variable in a constraint can be pre-processing to get more robust solutions.

The practice of MINLP was illustrated by Ruud Brekelmans from Tilburg University. He explained the modelling and solution background of a project he has worked on to determine new safety standards for dike heights in the Netherlands. Stated very simple the decision problem was to determine the timing and sizing of the dike heightenings minimizing the total cost, consisting of the investment cost of the heightening of the dike and the economic loss in case of a flood. If you would like to know more about te project, please visit the Analytics conference in San Antonio, as it was elected finalist in the 2013 Franz Edelman award. We wish the team lots of luck, yet another Dutch Edelman award in the making?

General conclusion for the OR practitioners from the MINLP lectures was to not be afraid of MINLP. The continuous improvement in (MINLP) solvers creates new possibilities that were not available several years ago. But, even today it is necessary to come up with the right model formulation to solve your problem; you need to help the solvers where you can. Again modelling expertise required.

Given the significant rise (over 30%) in number of participants of the seminar compared to the previous years, we can conclude that the seminar filled a need. Also the feedback on the content and the speakers was great, so we can look back on a successful seminar. We decided that next year’s seminar will have the same format, topics to be announced. Suggestions for topics more than welcome. See you next year in Lunteren!

No comments:

Post a Comment