Bachelor

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.