I am trying to solve a problem of the form $$\min_{x_1,\dots,x_n} f(x_1,\dots,x_n)$$ subject to a constraint that $\mathrm{length}(\mathrm{TSP}(x_1,\dots,x_n))\leq c$, where $x_1,\dots,x_n$ are all points in $\mathbb{R}^2$, $f$ is a convex function, and $\mathrm{TSP}()$ denotes the shortest TSP tour through the points. There are obvious ways to formulate this as an IP or a QIP by introducing a binary variable $y_{ij}$ representing the tour and doing the usual tricks (big $M$ for IP, and taking products $y_{ij}\|x_i-x_j\|$.

I am wondering if anyone has had any experience with problems of this sort, and if there are additional tricks that could improve performance? A reference would help too as I don't know what to google to find similar results.

  • $\begingroup$ You may try to solve the problem as a black-box problem, using Concord or even a TSP heuristic to solve the TSP subproblem. It wouldn't be exact since the TSP constraint is certainly non-convex, but might be enough to find good solutions in reasonable time $\endgroup$
    – fontanf
    Commented Dec 10, 2023 at 21:49
  • $\begingroup$ That's a great idea! Any recommendations for a decent black-box solver? $\endgroup$ Commented Dec 11, 2023 at 2:11
  • $\begingroup$ Either a derivative free solver such as Nomad, see doi.org/10.1007/s10898-021-01085-0 for other ones, or a derivative based solver such as Ipopt (open source) or Knitro (commercial) $\endgroup$
    – fontanf
    Commented Dec 11, 2023 at 8:41
  • 1
    $\begingroup$ Out of curiosity, what is the objective to optimize? $\endgroup$
    – fontanf
    Commented Dec 11, 2023 at 11:34
  • $\begingroup$ It's just $\sum_i \|x_i - p_i \|$, for given points $p_i$. And in fact I'm not even married to this specific version, I'd be happy to reverse the objective and constraint, or even just take a weighted combintation of the two. $\endgroup$ Commented Dec 11, 2023 at 17:42


Your Answer

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