Exploring optimization approaches for machine learning: Subgroup discovery (Bachelor)

Subgroup discovery is a broadly applicable data mining technique aimed at discovering interesting relationships between different objects in a set (e.g., history of purchases of a person) and come property which if of interest (e.g., whether specific product will be bought or not). The aim of the thesis is to provide a tutorial-like introduction into the subgroup discovery from the optimization perspective. You will provide an overview over widespread variants of the subgroup discovery and try to model (some) of them as mixed-integer problems. You will also discuss applications of the subgroup discovery and critically appreciate and explain one existing optimization approach (or its selected elements) to solve this problem.

Herrera, F., Carmona, C., González, P., & de Jesus M. (2011). An overview of subgroup discovery: Foundations and applications. Knowledge and Information Systems, 29, 495–525.

Capacitated arc routing problem and snow plowing operations -  A case study and a literature review (Bachelor)

In Lower Bavaria (Niederbayern) we have a lot of snow on the streets during the winter months, especially in the region around the Bavarian forest. This requires a lot of snow plowing operations to clean the streets. This kind of problems can be modelled as “capacitated arc routing problems”. The goal of this thesis is it to present a basic model of the capacitated arc routing problem in a tutorial like manner. Further, you will create a case study based on the Lower Bavarian forest area, and compare the optimal solution with the current operational policy.

Golden, Bruce L.; Wong, Richard T. (1981): Capacitated arc routing problems. In: Networks 11 (3), S. 305–315. DOI: 10.1002/net.3230110308.

Perrier, Nathalie; Langevin, André; Campbell, James F. (2007): A survey of models and algorithms for winter road maintenance. Part III: Vehicle routing and depot location for spreading. In: Computers & Operations Research 34 (1), S. 211–257.

Methodological advances on metaheuristics (Bachelor/Master)

Metaheuristics is a a currently most widely used optimization approach in industry, engineering, disaster relief etc.etc. The aim of the thesis is to provide a tutorial-like summary on how metaheuristics can be analyzed formally, which conclusions can be drived from these pieces of analysis etc. You will have to explain in depth one or several selected results (e.g., most relevant, most interesting…)

Jansen, T. (2013). Analyzing Evolutionary Algorithms The Computer Science Perspective. Springer.

DeJong, K. (2006). Evolutionary Computation: A Unified Approach. MIT Press.

Literature review on the novel ng-route relaxation approach for routing problems (Bachelor/Master)

Baldacci, Mingozzi and Roberti (2011) proposed the ng-routes as compromise between elementary and non-elementary routes. Given a TSP route, an elementary route is a route where each customer in the tour is visited exactly once. A non-elementary route relaxes this criterion by visiting some customers more than once or omits some customers in the final tour. The ng-routes pose dynamically computed restrictions on which customers can be visited next. This relaxation belongs to the state-of-the-art path relaxations for routing problems and is key in the development of state-of-the-art routing algorithms.

Baldacci, Roberto; Mingozzi, Aristide; Roberti, Roberto (2011): New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem. In: Operations Research 59 (5), S. 1269–1283.

Roberti, Roberto; Mingozzi, Aristide (2014): Dynamic ng-Path Relaxation for the Delivery Man Problem. In: Transportation Science 48 (3), S. 413–424.

Fast solution of certain scheduling problems: Transformation to Gilmore-Gomory TSP (Bachelor/Master)

Gilmore and Gomory (1964) developed a brilliant algorithm which is able to solve a special case of the travelling salesman problem (TSP) in polynomial time. Since then, the algorithm and the problem have been used in different areas such as scheduling.  The aim of this thesis is to find, review and categorize the studies which have used Gilmore-Gomory algorithm in scheduling problems and extract theoretical and practical insights on their applications.

* Gilmore, P. C. , & Gomory, R. E. (1964). Sequencing a one state-variable machine: A solvable case of the traveling salesman problem. Operations Research, 12, 655–679.

* Bagchi, T. P., Gupta, J. N., & Sriskandarajah, C. (2006). A review of TSP-based approaches for flowshop scheduling. European Journal of Operational Research, 169, 816–854.

The Benders decomposition algorithm: Novel use cases, trends and acceleration strategies (Master)

The Benders decomposition algorithm is a well-established  exact solution method originally proposed by Benders (1962), which was successfully applied to solve complicated problems in many divers fields, including planning and scheduling, health care, transportation and telecommunications, energy and resource management, and chemical process design. In recent years, it is in trend again for solving complicated combinatorial optimization problems which can be formulated as a mixed-integer linear program. Novel extensions, acceleration methods and hybrid applications (e.g. in combination with metaheuristics) have been recently introduced. The first step of this thesis is to get an overview about the functionality of the classical Benders decomposition algorithm and its extensions  from the survey by Rhamaniani et al. 2017, as well as extensing this survey by further relevant works published since 2017. In the next step, the candidate should either identify a new use case suitable for Benders decomposition and apply the algorithm on that problem, or select a classical use case for Benders decomposition and extend the existing implementation by novel acceleration strategies or features.

Rahmaniani, R., Crainic, T.G., Gendreau, & M. Rei, W. (2017). The Benders decomposition algorithm: A literature review. European Journal of Operational Research, 259, 801-817.