5
$\begingroup$

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?

$\endgroup$

2 Answers 2

16
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ For more details, please see this and this link. $\endgroup$
    – A.Omidi
    Commented Jan 31, 2022 at 7:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.