The feasible solution set of a Combinatorial Optimization Problem (COP) is discrete and finite. Solving a COP is to find optimal solutions in the set of feasible solutions such that the value of a given cost function is minimized or maximized. In the literature, there exist both complete and incomplete methods for solving COPs. The complete (or exact) methods return the optimal solutions with the proof of the optimality, for example the branch-and-cut search. The incomplete methods try to find hight-quality solutions which are as close to the optimal solutions as possible, for example local search. In this thesis we focus on solving four distinct COPs: the Quorumcast Routing Problem (QRP), the Elementary Shortest Path Problem on graphs with negative-cost cycles (ESPP), the Elementary Longest Path Problem on graphs with positive-cost cycles (ELPP), and the Agricultural Land Allocation Problem (ALAP). In order to solve these problems with the complete methods, we use the Branch-and-Infer search, the Branch-and-Cut search, and the Branch-and-Price search. We also solve ALAP by the incomplete methods, such as Local Search, Tabu Search, Constraints-Based Local Search that combine with metaheuristics. The experimental evaluations on well-known benchmarks show that all proposed algorithms for all the first three COPs (QRP, ESPP and ELPP) are better than the-state-the art algorithms. Specially, we describe ALAP, formulate it as a combination of three COPs, and propose several complete and incomplete algorithms for these COPs.
展开▼
