Combinatorial optimization problems can be characterized as searching for the best element of some finite set of items. These problems are pervasive in our modern, globalized society. The GPS device in our car solves a combinatorial optimization problem to find the shortest route from origin to destination. A production planning software determines an optimized sequence in which to produce goods and assigns machines to production batches. Transportation and courier companies use combinatorial optimization to determine which truck or delivery van will visit which customers and in which order so as to meet deadlines while minimizing fuel consumption. Train and bus schedules, garbage collection and mail delivery routes are designed using some form of combinatorial optimization, as are telecommunication networks and distribution networks for gas, water, and electricity. Production, distribution, telecommunication, governance, traffic, environmental concerns, health care, finance, it is hard to find an aspect of our modern-day economy whose design, management and control do not critically rely on the solution of one or more combinatorial optimization problems.
Given the pervasiveness of combinatorial optimization problems, the importance of the development of efficient solution methods for such problems cannot be overestimated. There exists a broad spectrum of solution methods for combinatorial optimization problems ranging from exact algorithms to a variety of heuristic approaches. Exact methods guarantee to find the optimal (i.e. best possible) solution, but this guarantee may come at the expense of prohibitively large computing time. Exact methods are therefore generally used to solve small and relatively simple problems, or to gain insight into the mathematical structure of an optimization problem. On the other side of the spectrum, heuristic solution methods (heuristics) do not guarantee to provide the optimal solution, but attempt to find a good solution in a short amount of computing time. In other words, heuristic methods sacrifice the guarantee of finding optimal solutions for the sake of getting good solutions in a limited available time.
Many combinatorial optimization problems are still not “satisfactorily” solved and pose a strong challenge to nowadays optimization techniques. The extraordinary computing power currently at our disposal is a fantastic enabler for making the solution of optimization problems conceivable, but it is rarely sufficient to offset the complexity and size of many real-life combinatorial optimization problems. Rather, the complexity of modern-day real-life optimization problems requires the development of novel methods that can efficiently exploit the increasing computer power available. As a result, the study of combinatorial optimization problems and the development of effective algorithms for their solution is one of the most active research areas in operations research. Currently, only simplified small to medium size versions of many problems can be solved by exact methods. However, many practically relevant problems are large in scale and display features such as multiple objectives, dynamically changing data, or stochastic data that make their solution more complex. Although heuristics can tackle such large and complex instances, they still can require significant development time and they produce optimality gaps (i.e., differences in quality between the heuristic solution and the optimal one) which, in many cases, still remains significant.
The strategic importance of operations research and optimization, in particular, is illustrated by the recent LANCS Initiative which allocates a funding of more than 12 million British Pounds, from 2008 to 2013, to strengthen these fields at four leading UK universities.
The main objectives of this project are:
– Bring together the available Belgian expertise on combinatorial optimization problems, exploit synergies between the partner research groups, and create a network with a sufficient mass to attract young and experienced top-level scientists in Belgium, and further financing for research in the field.
– Train young researchers in the field of combinatorial optimization. These profiles are in high demand, both in academic research centers worldwide and in private organizations.
– Develop new models, algorithmic techniques and implementations for complex, large-scale combinatorial optimization problems.
– Develop new international collaborations with other large teams working in the field of combinatorial optimization. An active and recognized Belgian network would facilitate international collaborations, in particular in the framework of large scale international projects.
Successful achievement of these objectives will lead to (i) a number of important, fundamental research contributions, (ii) a significant impact on the different sectors where combinatorial optimization problems arise, and (iii) to a considerable added value for the Belgian economy.
The development of efficient methods for combinatorial optimization is a very active research domain worldwide. All teams participating in this project are very well-positioned in this landscape: they have a strong international reputation, an excellent publication record, and are active at an international level, be it in international societies (Mathematical Programming Society, EURO – the Association of European Operational Research Societies), or the organization of international conferences. The partners know each other well and they meet regularly, for example, at the yearly ORBEL conference. In addition, the partners on the French-speaking side have an ongoing collaboration through a project subsidized by the FNRS, and organize a common yearly conference where PhD and post-doc researchers have the opportunity to present their work and establish contacts.
The participating teams follow a common approach to solving optimization problems, from building a mathematical model of the underlying problem to developing efficient solution methods. In other words, they share some fundamental view of how to tackle difficult combinatorial optimization problems and, thus, collaboration can happen in a seamless manner . The research teams are highly complementary for what concerns their main expertise . The specificities of the teams arise from the different models they use (linear vs. Non-linear, continuous vs. Discrete variables, deterministic vs. Stochastic, single objective vs. Multi-objective …), from the algorithms they design, develop and deploy to solve these problems (the teams are experts on either exact methods or heuristic methods), and from the application domains (supply chain management, telecommunications, transport, scheduling, …).
Main research directions
The main research directions followed in the project are:
a) Study and modelling of problems. Progress in combinatorial optimization relies on an appropriate modelling of problems and the study of the combinatorial structure of these problems. Combinatorial optimization problems can typically be formulated as Mixed Integer Linear Programs. The formulation can then be strenghthened by the addition of problem-specific valid inequalities. Extending the knowledge of efficient families of valid inequalities proves to be very important for solving real world instances. The choice of variable space is also very important to solve the problems efficiently. In this context, an objective of the project is to further develop the knowledge of problems studied by the different teams to provide better families of strong valid inequalities and/or strong extended formulations.
B) Advancements in algorithmic techniques . Novel research contributions are expected on exact and heuristic algorithms and, in particular, the combination of these techniques. In fact, it is widely acknowledged that breakthroughs in the domain of combinatorial optimization will most likely come from an integration of both exact and heuristic methods to exploit the complementarity of these two types of approaches. Another promising line is the combination of techniques of artificial intelligence with heuristics. Examples are the use of machine learning and decision making inside heuristics and data mining to discover features impacting algorithm behavior. Synergies among the partners will be instrumental for these directions. Additional progress will be made on exact algorithms, for example, by the further investigation of decomposition techniques and on heuristic algorithms, for example, by developing a sound generic methodology for their development.
C) Implementation of solution methods for large-scale, practically relevant problems. Applications drive research and often require solving ever larger and more realistic models of real-world optimization problems. Including more details in a model typically increases the number of decision variables and therefore the complexity of the optimization problem. This complexity is further increased by including multiple objectives and dynamically changing stochastic data. We aim at developing efficient implementations for such large-scale problems arising in areas like production, distribution, telecommunication, health care or traffic management, in which members of the proposal are already active.
In conclusion, COMEX will allow increased collaborations between the teams, will generate a number of basic research contributions and breakthroughs, and will create the largest excellence pole in combinatorial optimization in Belgium. In addition, it will be instrumental in developing the international collaborations and increasing the international visibility of the teams.