Fast, right or best? Algorithms for practical optimization problems

Good algorithms exhibit three key qualities: speed, accuracy, and optimal objective value. We explore the interaction among these criteria through optimization problems grounded in practical applications while maintaining a theoretical perspective. Our research focuses on developing algorithms that not only perform well but also possess provable properties, combining machine learning with combinatorial optimization for enhanced performance.

We begin with the single-source many-targets shortest path problem (SSMTSP), where the goal is to find the shortest path from a source node to multiple target nodes in a directed weighted graph. We propose an adapted Dijkstra's algorithm enhanced by machine learning predictions that estimate shortest path distances, allowing for efficient pruning of the search space and reducing operational overhead. In later chapters, we address the casting problem, a variant of the generalized assignment problem, which involves assigning items to knapsacks while maximizing utilization ratios. We prove the NP-completeness of its feasibility aspect and introduce bicriteria approximation algorithms, presenting empirical results that demonstrate our algorithms' effectiveness.

We also examine Large Neighborhood Search (LNS), a versatile method for optimization. We integrate machine learning in two ways: the Learning-Enhanced Neighborhood Selection (LENS) method, which smartly chooses routes for destruction, and a Neighborhood Creation approach, where routes are selected iteratively using reinforcement learning. Both implementations target practical applications, particularly in vehicle routing challenges