An Analysis of Algorithms and Heuristics for Combinatorial Optimization
Loading...
Date
2023-05
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
The Ohio State University
Abstract
Combinatorial optimization problems involve a search in a finite search
space of multiple parameters that minimize a set metric. In this work, the
practical implementation of a classical combinatorial optimization problem and applicable heuristics are explored in a survey of several models. The combinatorial problem explored is combining the possibilities
of flights and hotels across a search window proportionally longer than
the number of travel days where optimality is defined solely on cost of
hotels and flights. For the trivial case, only all of the departing flights,
hotels, and return flights for a single destination are considered. Then
the trivial problem is expanded to include a second destination so the
problem's dynamics necessitate finding the cheapest itinerary for visiting
both locations given the total trip time. For this expanded problem, the
matrix data structure fails to capture the magnitude of the data and so
the data is queried from two databases but aggregated into a graph data
structure modeling the problem as a classic Shortest Path Problem in the
field of Combinatorial Optimization. The work compares the reduction in
time complexity leveraging the problem dynamics to preprocess the graph
and prune branches and then finding the optimal solution with Dijkstra's
Algorithm. The work then explores the effect of assuming uncertainty
in the prices transforming the problem into an NP-Hard problem in the
scenario-represented uncertainty. By modeling the uncertainty as arc intervals, the problem can be solved in polynomial-time. Finally the work
explores the applicability of heuristic algorithms to the multi-destination
graph with certainty in the arc weights.
Description
Keywords
combinatorial optimization