Is Traveling Salesman Problem "Combinatorial Optimization" or "Integer Optimization"?

Question

I am looking at the Traveling Salesman Problem and I can not figure out if this problem is a type of "Integer Optimization Problem", or is a type of "Combinatorial Optimization Problem"?

It seems like this is a Combinatorial Optimization Problem. Is this correct?

Answer 1

I'm not sure that the terminology is used consistently enough to give a firm answer. Pretty much everyone would agree (I think) that the TSP is a combinatorial optimization problem. To me, asking whether it is an "integer optimization problem" or an "integer programming problem" assumes a particular representation (encoding?) of the TSP. Can I solve a TSP using an integer program? Yes (at least for modest problem sizes). Is that the only way to represent or solve it? I think not.

Answer 2

The versatility of the combinatorial optimization model stems from the fact that in many practical problems, activities and resources, such as machines, airplanes, and people, are indivisible. Also, many problems have only a finite number of alternative choices and consequently can appropriately be formulated as combinatorial optimization problems — the word combinatorial refers to the fact that only a finite number of alternative feasible solutions exists. Combinatorial optimization models are often referred to as integer programming models where programming refers to “planning” so that these are models used in planning where some or all of the decisions can take on only a finite number of alternative possibilities.

Also, Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combinatorial optimization problems are the traveling salesman problem ("TSP"), the minimum spanning tree problem ("MST"), and the knapsack problem.