Combinatorial Optimization

The term “combinatorial optimization” encompasses any optimization problem involving binary variables, together with appropriate techniques for solving such problems. In its most general form, a combinatorial optimization problem finds the best feasible subsets from a discrete set. This chapter presents two very well-known problems of combinatorial optimization: the traveling salesman problem (TSP) and the vehicle routing problem (VRP). The TSP can be divided into two types, each with several different variants: the symmetric traveling salesman problem and the asymmetric traveling salesman problem (ATSP). Methods for solving the ATSP are generally split into two categories: exact methods and approximate methods. ATSPs are often solved optimally with the branch-and-bound method. Branch-and-cut method requires the optimization problem to be transformed into an integer linear programming problem. The VRP is a key link in the field of logistics.