You can use integer programming for the traveling salesman. The typical approach that I heard about goes as follows:
You model your map as a network flow graph. Ie each node has to have one salesman arrive and one salesman leave. Conceptually, that's half the work done.
If you solve this and get a single tour, it's guaranteed to be optimal.
If you solve this, and get multiple disconnected tours, you have a problem.
To fix this, for each way to split the graph in twain, you add a constraint that says that the tour has to go through that split at least once. (So you can't have independent tours.) That's called the (no-) subtour constraint.
In principle, that's enough to solve the problem.
In practice, there's an exponential number of inequalities for your subtour constraints. So what you do is add them one by one, as required: you solve your current problem, check the solution, then add violated subtour constraints, and repeat.
That's the most basic way to model the traveling salesman in linear programming. There are much better ways, I think.
Your recollection about scheduling problems is roughly correct.
You model your map as a network flow graph. Ie each node has to have one salesman arrive and one salesman leave. Conceptually, that's half the work done.
If you solve this and get a single tour, it's guaranteed to be optimal.
If you solve this, and get multiple disconnected tours, you have a problem.
To fix this, for each way to split the graph in twain, you add a constraint that says that the tour has to go through that split at least once. (So you can't have independent tours.) That's called the (no-) subtour constraint.
In principle, that's enough to solve the problem.
In practice, there's an exponential number of inequalities for your subtour constraints. So what you do is add them one by one, as required: you solve your current problem, check the solution, then add violated subtour constraints, and repeat.
That's the most basic way to model the traveling salesman in linear programming. There are much better ways, I think.
Your recollection about scheduling problems is roughly correct.