1
$\begingroup$

Can Gradient Based Optimization Techniques be used to solve Travelling Salesperson Problem?

The Travelling Salesperson Problem is a famous optimization problem in which a Salesperson has to figure out which order to travel across "n" cities - such that the total distance travelled is minimum and each city is visited once.

The "objective function" in this problem is a function that maps "different orders of cities" to the "total distance corresponding to that order of cities". As an example, the objective function might look something like this:

enter image description here

My Question: In the case of the Travelling Salesperson Problem - is the Objective Function "differentiable" in the same sense that the equation of a parabola (y = x^2) is differentiable?

At first glance, the answer obviously seems to be "no". Afterall, how can we take the derivative of the above function? The above function is not defined over a continuous domain!

Thus, can we say that in the case of the Travelling Salesperson Problem (i.e. discrete combinatorial optimization problems), the objective functions are "non-differentiable"? If this is true - is it then "impossible to use Gradient Based Optimization on Travelling Salesperson"?

Or even in such cases, the objective functions can still be said to be differentiable?

Can someone please comment on this?

Thanks!

$\endgroup$
5
  • $\begingroup$ You might want to check out Vishnoi’s “Algorithms for Convex Optimization”. It covers continuous optimization algos for discrete/combinatorial problems. $\endgroup$
    – V.S.e.H.
    Jan 24, 2022 at 7:46
  • $\begingroup$ @ V.S.e.H.: thank you so much for your reply! I am having difficulty in understanding this following point: if the objective function is discrete and is not defined over a continuous domain, is the objective function called "non differentiable"? can we use gradient based optimization techniques on "non differentiable objective functions"? $\endgroup$
    – stats_noob
    Jan 24, 2022 at 7:52
  • $\begingroup$ Generally, a simple gradient will not be sufficient to solve a discrete problem (but it can in some particular cases, see total unimodularity). What is often done is to relax the variables in the formulation to real values, then solve the relaxed formulation (in the case of linear programming this can be done efficiently via the simplex algorithm - this is a gradient based algorithm), then use a branch & bound algorithm to fix the variables to integers. This will generally gives an exponential algoritmh, but it can provides very good dual bounds, and in practice, it can work very well. $\endgroup$
    – caduk
    Jan 24, 2022 at 8:28
  • $\begingroup$ Please don't shout so much. $\endgroup$
    – user1015917
    Jan 24, 2022 at 9:06
  • $\begingroup$ Being nondifferentialble means that the derivative does not exist on the domain of of the objective, which does not have to be the case for discrete problems, but happens quite often. Vishnoi explains that quite clearly in his book, and points to some new developments regarding the TSP using convex optimization. The max-flow problem is an instance of a combinatorial problem solved with gradient methods, and in fact more efficiently. $\endgroup$
    – V.S.e.H.
    Jan 24, 2022 at 18:33

2 Answers 2

1
$\begingroup$

Certainly not.

The objective function of the TSP is nothing but a field of local minima in which any continuous method (say obtained by interpolation) would be trapped. And it would be foolish to try intermediate coordinates when you know that the solution occurs at the given data points.

TSP is a combinatorial issue, full stop.


For an analogy, consider the minimization of

$$\sin x+\left(\frac x{1000}-1\right)^2$$

enter image description here

$\endgroup$
1
$\begingroup$

A particular case of continuous optimization is linear programming (LP), where we have a linear objective function and a set of linear constraints over variables (constrained to be real). LPs are convex and can be solved efficiently via gradient based algorithms, like the simplex algorithm.
A related problem is mixed-integer linear programming (MILP), where we also have a linear objective function and a set of linear constraints, but this time, the variables can be constrained to be integer. This offers much more expressiveness, and we can easily show that every $NP$-problem can be expressed as a (polynomially small) MILP problem. However, the gradient methods are no longer guaranteed to converge to optimality as the problem is now discrete. But if we relax the integrality constraints on variables, the optimum often gives a strong dual bound on our problem. Combined with tree search (via a branch and bound), this can drastically speed up the resolution (though complexity remains exponential).

It is still possible to express combinatorial problems with convex functions. Using an exponential set of constraints, we can express the Travelling Salesman Problem as a linear problem. This can be achieved by expressing the problem as a SAT instance. The set of points formed by the corresponding binary vectors will always be convex, so we can take as constraints all the facets of the convex hull. Unfortunately, it is known that we will always end up with an exponential number of facets, no matter how we model the Travelling Salesman Problem. In fact, we still don't know any polynomial time algorithm for $NP$-hard problems.

$\endgroup$
6
  • $\begingroup$ The simplex algorithm is not gradient based, it is combinatorial. Interior point methods are gradient based (and in fact 2nd order). Also, a problem being nonconvex does not necessarily mean that gradient based methods won't work. Pretty much all of NN training is nonconvex and done with SGD. $\endgroup$
    – V.S.e.H.
    Jan 24, 2022 at 18:26
  • $\begingroup$ Wikipedia defines a gradient method as an algorithm where search directions are defined by the gradient of the function at the current point. In the simplex algorithm, the next pivot is decided by analysing the gradient. But I agree that interior point methods are more gradient like. Generally, for a non-convex function, gradient is only garanteed to find a local optimum, so it doesn't "solve" the problem strictly speaking. $\endgroup$
    – caduk
    Jan 25, 2022 at 9:49
  • $\begingroup$ I don't know where you get your information about LPs, but the simplex method does not choose a pivot by analyzing the gradient (and to be pedantic, no mention of "gradient" in the wiki article about LPs). However, please point to appropriate reference otherwise. Not being able to "solve" the problem, as in finding the global optimizer, is not the same as "gradient methods will no-longer work", as stated in your answer. $\endgroup$
    – V.S.e.H.
    Jan 25, 2022 at 10:51
  • $\begingroup$ Pivots are chosen along variables for which the derivative of the objective with respect to that variable is negative (and is often chosen to be the steepest one). The simplex is quite similar to a gradient descent, except it is restricted to move on edges instead of anywhere in the polytope. I will edit the "no-longer work" with something more precise. $\endgroup$
    – caduk
    Jan 25, 2022 at 14:35
  • $\begingroup$ In fact, this is not a problem of convexity, but more that the problem is no more continuous. $\endgroup$
    – caduk
    Jan 25, 2022 at 14:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .