Optimization: A Way of Life
Since I got into the optimization swimming pool, I have been witnessing closely that this field has been greatly improving our lives over the last years. In short words, optimization is the choice of the best possible decision in a given context. Examples of optimization problems can be seen in my previous article Some Classical Applications of Operations Research. While this field is fascinating, I have been struggling to find/build a comprehensive taxonomy for it. In fact, optimization problems can be classified from different perspectives. For instance, a problem can be seen from its functions/variables leading to a first classification, which is continuous vs discrete optimization. A problem can also be seen from its constraints leading to a second classification, which is constrained vs unconstrained optimization. It can also be seen from its objective leading to a third classification, which is one vs several (or multi-) objective(s). In addition to these ones, there are also many other classifications for optimization problems. Furthermore, a problem can be simultaneously continuous, constrained, and multi-objective. This highlights the complexity of building a universal taxonomy.
In this article, I present a view based on the courses I attended in my university, Polytechnique Montreal (Poly), located in one of the greatest optimization spots worldwide. While sharing this view, I aim to present briefly some leading researchers, subjects as well as examples. This may serve as an introductory guide to any student who seeks a research career in optimization without having a clear perception of its subfields.
1. Integer Optimization
An optimation problem in which a portion of the variables are integers (or in some cases binary). When both the constraints and the objective function are linear, we talk about integer linear optimization. In Poly, this course (MTH6404) is provided by Pr. Guy Desaulniers and Pr. Andrea Lodi.
2. Combinatorial Optimization
An optimization problem in which we seek to find an optimal object from a finite set of objects. Some classical examples include the traveling salesman problem and the knapsack problem. When optimization is both integer and combinatorial, we usually call it discrete optimization. In Poly, this course (MTH6311) is provided by Pr. Alain Hertz.
3. Graph Optimization
An optimization problem, which is represented as a graph with vertices and edges. Some classical examples include the shortest path problem and the maximum flow. In Poly, this course (MTH6405) is also provided by Pr. Alain Hertz.
4. Stochastic Optimization
An optimization problem in which we seek the best possible solution under uncertainty. This type of problem is formulated using random variables and distributions. In Poly, this course (MTH6415) is provided by Pr. Michel Gendreau. In many applications, the actual value of data becomes known over time, and the decisions that need to be made now depend on the value of these parameters. For instance, in a simple crop planning problem, the farmer has to make a strategic decision about how much land to devote to each crop prior to knowing the weather conditions. Stochastic programming offers a powerful tool to model such optimization problems. We note that there are other approaches for optimization under uncertainties such as Probabilistic Optimization and Robust Optimization.
5. Dynamic Optimization
An optimization problem in which several dependent decisions are taken over time. One of the classical problems is inventory management in which decisions should be taken based on the available stock from the past as well as the expected demand in the future. In Poly, this course is presented as part of the stochastic optimization course (MTH6415) provided by Pr. Michel Gendreau.
6. Robust Optimization
An optimization problem in which we seek a specific threshold of robustness. The latter is the ability of a given model to perform well under a variety of conditions and probability distributions. It is another famous approach employed to tackle uncertainty like stochastic optimization. It is slightly discussed in the stochastic course (MTH6415) as well as the advanced optimization course (MTH6416).
7. Derivative-Free Optimization
An optimization problem in which we do not use the derivative (in a mathematical way) to reach optimal solutions because it is unavailable, or impractical to obtain. In Poly, this course (MTH8418) is provided by Pr. Charles Audet.
8. Blackbox Optimization
An optimization problem in which the derivative is not accessible. In Poly, it is also presented in the course (MTH8418) by Pr. Charles Audet.
9. Real-Time Optimization
An optimization problem in which decisions are taken as we progress through time and more information becomes available. In Poly, this course (MTH8418) is provided by Pr. Issmaïl El Hallaoui.
10. Large-Scale Optimization
An optimization problem in which the number of variables and constraints are significantly high. It is the case in airline planning for instance. In Poly, this topic is discussed in two classes, which are the course (MTH8418) provided by Pr. Issmaïl El Hallaoui as well as the course (MTH6404) provided by Pr. Guy Desaulniers.
While these great courses are overlapping, the art of choosing which optimization approach is the most suitable for a given problem is crucial. In Poly, one of the greatest courses (MTH6406) called Modeling in Operations Research and provided by one of the pioneer researchers, Pr. Soumis François. Combining this course with the ones presented briefly above is an efficient way to get into the optimization swimming pool given the theoretical insights, practical acumen, and expertise of world-class researchers.
When it comes to real-life challenges, the theoretical and practical insights gained must be combined with the involvement of the relevant stakeholders (like companies, managers, operators, etc) from the beginning. The latter usually own the tacit knowledge about processes and systems and play a key role in the efficient implementation of the optimized solution(s) for the business problem considered.
Optimization will definitely become more and more popular in the upcoming years given the global challenges faced by humans. Do you agree? I am looking forward to hearing your ideas :-).
