For many combinatorial problems encountered in practical applications, there are currently no efficient solution algorithms available. In particular, such problems are often NP-hard and thus especially difficult to solve for larger instances. However, exact solutions are often not necessary in practice. While, depending on the specific problem, algorithms for finding approximate solutions might already be available, methods based on machine learning have not yet found widespread use in this domain.

In general, any systematic approach to NP-hard combinatorial problems by means of machine learning techniques faces two major challenges: First, combinatorial problems are discrete in nature, and it is typically difficult to map discrete results with machine learning methods. Second, due to the large solution space of NP-hard problems, it takes large computational effort, or is even practically impossible, to generate labels for supervised machine learning. Therefore, in this dissertation, we present an approach that circumvents these obstacles, and thus allows for efficiently predicting solutions to combinatorial problems with machine learning. More specifically, we overcome the problem of discrete solutions with a relaxation approach. The problem of label generation, on the other hand, is avoided with label-free learning via the loss function: The loss function represents the objective function, which computes the objective value of the combinatorial problem itself. Instead of labels, the loss function thereby immediately directs the adaption of the parameters during the gradient-based training of the  machine learning algorithm.

Although the approach presented here is applicable to a much more general class of problems, we will focus on the so-called hybrid flow shop scheduling problem to demonstrate our methods. It consists of two subproblems: a permutation problem and an assignment problem. We analyze the hybrid flow shop in depth, including a formal mathematical description. Additionally, we give an extensive overview of the theoretical foundations of gradient-based machine learning to provide a theoretical foundation for understanding the proposed approach.

Most importantly, we provide a detailed explanation of the suggested approach of learning via the loss function and the literature that has thus far treated the topic.
For each subproblem, we train a neural network and describe the architecture and training method in detail, as well as the connection between the two networks to address the entire hybrid flow shop problem.

To assess the effectiveness of our approach, we compare the results of the neural networks, both individually and combined for the complete approach, with those of a basic Monte Carlo algorithm, as well as a more advanced mixed-integer linear programming approach. The results demonstrate noteworthy benefits in terms of efficiency and scalability of the proposed approach. Finally, we give suggestions for further research concerning the topic.