New problems and algorithms in combinatorial optimization

Abstract

Combinatorial optimization seeks optimal solutions from a finite set of objects. It is widely applied to many real-world problems, such as logistics, network design, and experimental design. Although the finite search space guarantees that an optimal solution can always be obtained by exhaustive search, for many real-world problems, this is intractable. NP-hardness is one of the key features shared by intractable combinatorial optimization problems. This dissertation includes the study of three new NP-hard combinatorial optimization problems and/or new algorithms for them. The first problem considers data collection in a humanitarian logistics setting. We formulate a new type of vehicle routing problem, in which vehicles are tasked with data collection, and the objective function measures data quality using a nonlinear, nonseparable experimental design criterion. We create novel exact methods for this problem, and demonstrate their practical potential in a realistic case study using a state-of-the-art earthquake simulator. The second problem considers a more stylized knapsack problem in which each experiment has a known cost, and data collection is subject to a budget constraint. Novel deterministic, polynomial-time approximation algorithms are introduced, extending the classical local search algorithm while providing rigorous performance guarantees. The algorithms outperform the only existing method for this problem from both theoretical and empirical standpoints. The third problem arises from minimizing the latency of telecommunication networks, named the minimum stretch spanning tree problem. We introduce a straightforward and promising carousel greedy algorithm to tackle this challenging combinatorial optimization problem. By numerical experiments, we show that our algorithm significantly outperforms the best-known algorithms in the literature for both unweighted and weighted graphs on both constructed challenging instances and real-world instances, demonstrating superior solution quality with efficient running time.