MOMIP: Multi-objective (mixed) integer programming

We live in a world full of trade-offs and quite often we only know comparably little about them. In almost every problem situation we encounter it is difficult to define the one and only goal to aim for, especially whenever more than one decision maker or stakeholder is involved. Thus, many if not all practical problems involve several and often conflicting objectives. Prominent examples are environmental concerns versus cost or customer satisfaction versus profitability. Our research is mainly rooted in the fields of transportation, logistics, and supply chain management and many relevant problems arising in these fields can be modeled as mixed integer linear programs. This means that there exist only rather simple, linear relationships between input parameters and decision variables and some variables may assume only integer values, e.g., the decision whether a distribution center should be built or not can only be 1 (yes) or 0 (no) but not 0.2. Despite the fact that these problems are often comparably easy to formulate they are quite often very difficult to solve. In addition, whenever multiple conflicting objectives are of concern, it is usually not possible to identify one best solution with respect to all of the considered goals. Rather, a set of optimal compromise solutions exists which are better than the other possible solutions and incomparable among each other. Each such solution represents a possible trade-off. The computation of this set of optimal trade-off solutions is not a complex task. All currently available exact methods have limitations. Either they are only applicable to problems with at most two objectives or they cannot describe the complete set of trade-off solutions. The kernel of this project is the development of efficient generic algorithms, using the branch-and-bound idea in a way that allows to exploit the multi- objective nature of the considered problems, and thus to close this gap for mixed integer linear programs with up to three objectives. In order to illustrate the applicability of our algorithms, we will use them to solve practical problems arising in sustainable supply chain management, disaster relief distribution planning and green vehicle routing. Decision makers will thus receive additional information on the trade-off relationship between the considered goals. They will be given the possibility to compare different solutions and to finally choose the most suitable solution out of the set of all optimal compromise solutions.

In practice, it is often not possible to define a single goal that should be optimized, especially in situations where more than one decision maker or stakeholder is involved. Prominent examples are environmental concerns versus cost or customer satisfaction versus profitability. In the fields of transportation, production, logistics, and supply chain management, many important practical problems can be formulated as so-called integer or mixed integer linear programs, depending on the types of decision variables that are required to model them. For problems with a single objective there exists a whole bundle of established commercial software products as well as open source tools. For problems with multiple objectives - despite their high practical relevance - this has so far not been the case. Whenever multiple conflicting objectives are of concern, it is usually not possible to identify one best solution with respect to all of the considered goals. Rather, a set of optimal compromise solutions exist which are "better" than all other solutions and incomparable among each other. Each such solution represents a possible trade-off. The computation of this set of optimal trade-off solutions is a complex task, especially for problems with integer decision variables and more than two objectives, and in the case where continuous as well as integer variables are necessary to model them. This project has been dedicated to the development of efficient solution algorithms, relying on the so-called branch-and-bound paradigm, to compute the proven optimal set of trade-off-solutions for multi-objective optimization problems with integer variables and for bi-objective problems featuring mixed (integer as well as continuous) decision variables. Branch-and-bound algorithms are the backbone of most successful single objective solvers. They follow a tree like structure where in every iteration, the solution space is split into smaller subspaces, some of which can be discarded based on estimates how good the best possible solutions in this subspace can be. These estimates are called bounds. In multi-objective optimization, bounds are not single numerical values but sets, so-called bound sets. In this project, new efficient algorithms, among others, for computing bound sets, for efficiently deriving feasible solutions from bound sets, and for early detection if the considered subspace can be discarded or reduced in size, have been developed. They together make an important contribution towards the goal of a general-purpose software tool for efficiently solving any multi-objective optimization problem that can be modeled as a mixed integer linear program. Furthermore, we have developed tailored exact and approximate algorithms for applications in facility location for disaster relief, sustainable supply chain network design, and car-sharing, underlining the practical relevance of solution approaches that are able to efficiently handle multiple objectives.