6 ms·

> There might also be better approaches than Hilbert Curves. For example, we could view it as an instance of the Traveling Salesman Problem with a couple of hun

by ufo 9y ago

> There might also be better approaches than Hilbert Curves. For example, we could view it as an instance of the Traveling Salesman Problem with a couple of hundred points; it should be possible to have a good heuristic solution for that. On the other hand, a TSP solution doesn't necessarily only have short jumps, so it might not be that good? TSP is actually very amenable to heuristics and state of the art branch-and-bound algorithms can often find optimal solutions even for instances with thousands of points. Does anyone here know if there is a good open-source solver that we could throw this problem instance at?

modalduality 9y ago
The issue isn't about approximating a TSP instance, but ensuring that points aren't too far apart from each other, even at the cost of increasing total length. I can't immediately think of a reduction that would factor this in so the best thing may be to just reduce this to the appropriate ILP instance and use a mixed ILP approximator like GLPK (or Gurobi is free for students too). Incidentally, achieving a polynomially-sized ILP formulation for TSP isn't quite obvious. Wikipedia has a good explanation of how to do this: https://en.wikipedia.org/wiki/Travelling_salesman_problem#Integer_linear_programming_formulation https://en.wikipedia.org/wiki/Travelling_salesman_problem#In.... I'm not sure if the metric TSP has a simpler formulation. Edit: Now that I think about it, it may be difficult to express the constraint that edges should be balanced out in a linear way. I happened to write about a similar problem a while ago (https://modalduality.org/posts/optimizing-color-coding/ https://modalduality.org/posts/optimizing-color-coding/), I ended up giving up on finding a linear formulation and went for sequential least squares instead.
- deleted 9y ago
  [deleted]
- Retric 9y ago
  If you want to minimize the long distance walks add an exponential weight for distance then solve. There are many ways to go about this stuff, but the goal is to map your preferences to the weight function.
  - modalduality 9y ago
    Right, but then the problem is no longer linear and approximating is more difficult. I'm not exactly sure what you mean by "exponential weight" in a linear program, do you have an example?
    - Spivak 9y ago
      So say you have a graph on distance, d, that you want to weight based on a preference, p, from 0-5 going from least preferred to most preferred. You might make your weight function as w(d, p) = d * (2 ^ p)
      - modalduality 9y ago
        That's fine, but `p` is a variable, not a constant, in the original post's case, right?
        Evelin789 9y ago
        what Ralph answered I didnt know that anybody can get paid $6830 in 1 month on the > computer . i was reading this>>>>>>>>>>>http://ow.ly/iBXm30dNtIZ http://ow.ly/iBXm30dNtIZ
        tgb 9y ago
        That doesn't seem necessary. Picking a value of p just selects how much you prefer short hope to shorter total distance.
    - Retric 9y ago
      I am not sure what your asking? Your just assigning constants for weights on each trip a>b = K1, a>c = K2. I am saying you may map K1 as √((x1-x2)^2+(y1-y2)^2) to find least distance, but TSP allows for arbitrary constants. So remove the √ and long trips will be strongly avoided. PS: As far as I know you can use any arbitrary set of constants then use a linear solver. Or am I forgetting about something?
CamperBob2 9y ago
TSP is actually very amenable to heuristics and state of the art branch-and-bound algorithms can often find optimal solutions even for instances with thousands of points. With that many points, how do you prove that your solution is optimal?
- modalduality 9y ago
  Often in approximations you can prove an upper bound on the optimal solution, even if you don't know the optimal solution itself. An easy example is by using duality when solving linear programs. And sometimes your upper bound is close enough to what you already have so you can just say something like "well my solution gets 190 points, I have an upper bound of 190.5 points, and all point rewards are integral so I must have the optimal solution."
- amalcon 9y ago
  TSP (in the traditional sense of finding an optimal solution) is NP-complete, so (by definition of NP-complete) it's much easier to check a proposed correct answer than to find that answer.
  - CamperBob2 9y ago
    Hmm. So there's a polynomial-time method for verifying that you've found the shortest path in TSP, but not for finding it in the first place?
    - Merovius 9y ago
      Yes. Crash-course complexity theory: This is easy to understand with integer factorization: It is very hard to factor large integers. Yet, if I where to give you two numbers, it is very easy to verify that their product is the integer you where looking at. So factorization is easy to verify, but hard to do (side-note: This is an intentional illustrative simplification. Integer factorization is not known to actually be "hard" and it is not known whether "hard" is even a thing. See below). And that's the definition of an NP problem: It has a polynomial time deterministic algorithm to verify a solution. An NP-complete problem is a problem that is at least as hard as any NP problem. That is, if you have an algorithm for an NP-complete problem, you can take any NP problem, transform it efficiently into that problem, use your algorithm and transform the solution efficiently back. Thus, if you've solved an NP-complete problem efficiently, you can solve all NP problems efficiently. TSP is NP-complete. Whether or not Integer Factorization is NP-complete is unknown. Lastly, there is the question of whether there are problems that are in NP (that is, have a polynomial algorithm to verify a solution) but not in P (that is, have a polynomial algorithm to find a solution). That's the famous P vs. NP question, which is currently undecided.
rlanday 9y ago
Concorde is open source and I believe holds the record for largest instance of TSP solved optimally (85,900 cities): http://www.math.uwaterloo.ca/tsp/concorde.html http://www.math.uwaterloo.ca/tsp/concorde.html Note that the licensing terms do restrict its free use to "academic research."
- cyphar 9y ago
  > Note that the licensing terms do restrict its free use to "academic research." Then it is not "open source" (violates "No Discrimination Against Fields of Endeavor") nor is it free software (violates the freedom to use for any purpose). It's proprietary -- just because the source code is available doesn't make something "open source" nor does it make it free software.
  - nullc 9y ago
    Unfortunately, such terms are ubiquitous in operations research.
cbhl 9y ago
If you wanted to guarantee you "only have short jumps", it would probably be good to consider that you can teleport to the top of the towers and hang-glide down from them (at the cost of some loading time) much more easily than climbing up a cliff.
- Merovius 9y ago
  Given that this wasn't about actually walking the map, but about just finding the locations still missing (and those locations where few and sparse), this really isn't necessary. It would be, if you'd want to do a speedrun, though.
srean 9y ago
You might get a laugh out of the fact that Hilbert curves are used to approximate Euclidean TSP. If I remember correctly it yields a log n approximation where n is the number of cities.
cpitman 9y ago
OptaPlanner is an open source constraint satisfaction solver (https://www.optaplanner.org/ https://www.optaplanner.org/). Here is an explanation of how it can be used to solve the Vehicle Routing Problem, closely related to TSP: https://www.optaplanner.org/learn/useCases/vehicleRoutingProblem.html https://www.optaplanner.org/learn/useCases/vehicleRoutingPro...
Xcelerate 9y ago
> TSP is actually very amenable to heuristics and state of the art branch-and-bound algorithms can often find optimal solutions even for instances with thousands of points. In own research (inverse problems related to signal recovery), I've noticed that a lot of NP-hard problems are actually easily solvable given that the data has some kind of structure to it. I know very little about computational complexity theory, but I've read some papers describing how there is often a phase transition where a high SNR puts the problem in P territory, but a sufficiently low SNR moves the problem moves to NP territory (but it's still solvable). Beyond the phase transition, a solution is information theoretically impossible. I wonder if most of these real world TSP problems actually lie in P, but I don't know how one would go about showing that. (I haven't performed a literature search, but I wouldn't be surprised if someone has already demonstrated this.)
- drostie 9y ago
  That's very unlikely to be true in general, as the proofs that a problem lives in NP usually have a very high signal-to-noise ratio -- i.e. in order to prove that solving this problem is at least as hard as solving an arbitrary boolean circuit, we need to find a subset of the problem which behaves like wires and boolean gates do, and the resulting "circuits" are very heavily structured.
- deleted 9y ago
  [deleted]

by ufo 9y ago

modalduality 9y ago

The issue isn't about approximating a TSP instance, but ensuring that points aren't too far apart from each other, even at the cost of increasing total length. I can't immediately think of a reduction that would factor this in so the best thing may be to just reduce this to the appropriate ILP instance and use a mixed ILP approximator like GLPK (or Gurobi is free for students too). Incidentally, achieving a polynomially-sized ILP formulation for TSP isn't quite obvious. Wikipedia has a good explanation of how to do this: https://en.wikipedia.org/wiki/Travelling_salesman_problem#Integer_linear_programming_formulation https://en.wikipedia.org/wiki/Travelling_salesman_problem#In.... I'm not sure if the metric TSP has a simpler formulation. Edit: Now that I think about it, it may be difficult to express the constraint that edges should be balanced out in a linear way. I happened to write about a similar problem a while ago (https://modalduality.org/posts/optimizing-color-coding/ https://modalduality.org/posts/optimizing-color-coding/), I ended up giving up on finding a linear formulation and went for sequential least squares instead.

deleted 9y ago
[deleted]
Retric 9y ago
If you want to minimize the long distance walks add an exponential weight for distance then solve. There are many ways to go about this stuff, but the goal is to map your preferences to the weight function.
- modalduality 9y ago
  Right, but then the problem is no longer linear and approximating is more difficult. I'm not exactly sure what you mean by "exponential weight" in a linear program, do you have an example?
  - Spivak 9y ago
    So say you have a graph on distance, d, that you want to weight based on a preference, p, from 0-5 going from least preferred to most preferred. You might make your weight function as w(d, p) = d * (2 ^ p)
    - modalduality 9y ago
      That's fine, but `p` is a variable, not a constant, in the original post's case, right?
      - Evelin789 9y ago
        what Ralph answered I didnt know that anybody can get paid $6830 in 1 month on the > computer . i was reading this>>>>>>>>>>>http://ow.ly/iBXm30dNtIZ http://ow.ly/iBXm30dNtIZ
      - tgb 9y ago
        That doesn't seem necessary. Picking a value of p just selects how much you prefer short hope to shorter total distance.
  - Retric 9y ago
    I am not sure what your asking? Your just assigning constants for weights on each trip a>b = K1, a>c = K2. I am saying you may map K1 as √((x1-x2)^2+(y1-y2)^2) to find least distance, but TSP allows for arbitrary constants. So remove the √ and long trips will be strongly avoided. PS: As far as I know you can use any arbitrary set of constants then use a linear solver. Or am I forgetting about something?

CamperBob2 9y ago

TSP is actually very amenable to heuristics and state of the art branch-and-bound algorithms can often find optimal solutions even for instances with thousands of points. With that many points, how do you prove that your solution is optimal?

modalduality 9y ago
Often in approximations you can prove an upper bound on the optimal solution, even if you don't know the optimal solution itself. An easy example is by using duality when solving linear programs. And sometimes your upper bound is close enough to what you already have so you can just say something like "well my solution gets 190 points, I have an upper bound of 190.5 points, and all point rewards are integral so I must have the optimal solution."
amalcon 9y ago
TSP (in the traditional sense of finding an optimal solution) is NP-complete, so (by definition of NP-complete) it's much easier to check a proposed correct answer than to find that answer.
- CamperBob2 9y ago
  Hmm. So there's a polynomial-time method for verifying that you've found the shortest path in TSP, but not for finding it in the first place?
  - Merovius 9y ago
    Yes. Crash-course complexity theory: This is easy to understand with integer factorization: It is very hard to factor large integers. Yet, if I where to give you two numbers, it is very easy to verify that their product is the integer you where looking at. So factorization is easy to verify, but hard to do (side-note: This is an intentional illustrative simplification. Integer factorization is not known to actually be "hard" and it is not known whether "hard" is even a thing. See below). And that's the definition of an NP problem: It has a polynomial time deterministic algorithm to verify a solution. An NP-complete problem is a problem that is at least as hard as any NP problem. That is, if you have an algorithm for an NP-complete problem, you can take any NP problem, transform it efficiently into that problem, use your algorithm and transform the solution efficiently back. Thus, if you've solved an NP-complete problem efficiently, you can solve all NP problems efficiently. TSP is NP-complete. Whether or not Integer Factorization is NP-complete is unknown. Lastly, there is the question of whether there are problems that are in NP (that is, have a polynomial algorithm to verify a solution) but not in P (that is, have a polynomial algorithm to find a solution). That's the famous P vs. NP question, which is currently undecided.

rlanday 9y ago

Concorde is open source and I believe holds the record for largest instance of TSP solved optimally (85,900 cities): http://www.math.uwaterloo.ca/tsp/concorde.html http://www.math.uwaterloo.ca/tsp/concorde.html Note that the licensing terms do restrict its free use to "academic research."

cyphar 9y ago
> Note that the licensing terms do restrict its free use to "academic research." Then it is not "open source" (violates "No Discrimination Against Fields of Endeavor") nor is it free software (violates the freedom to use for any purpose). It's proprietary -- just because the source code is available doesn't make something "open source" nor does it make it free software.
- nullc 9y ago
  Unfortunately, such terms are ubiquitous in operations research.

cbhl 9y ago

If you wanted to guarantee you "only have short jumps", it would probably be good to consider that you can teleport to the top of the towers and hang-glide down from them (at the cost of some loading time) much more easily than climbing up a cliff.

Merovius 9y ago
Given that this wasn't about actually walking the map, but about just finding the locations still missing (and those locations where few and sparse), this really isn't necessary. It would be, if you'd want to do a speedrun, though.

srean 9y ago

You might get a laugh out of the fact that Hilbert curves are used to approximate Euclidean TSP. If I remember correctly it yields a log n approximation where n is the number of cities.

cpitman 9y ago

OptaPlanner is an open source constraint satisfaction solver (https://www.optaplanner.org/ https://www.optaplanner.org/). Here is an explanation of how it can be used to solve the Vehicle Routing Problem, closely related to TSP: https://www.optaplanner.org/learn/useCases/vehicleRoutingProblem.html https://www.optaplanner.org/learn/useCases/vehicleRoutingPro...

Xcelerate 9y ago

> TSP is actually very amenable to heuristics and state of the art branch-and-bound algorithms can often find optimal solutions even for instances with thousands of points. In own research (inverse problems related to signal recovery), I've noticed that a lot of NP-hard problems are actually easily solvable given that the data has some kind of structure to it. I know very little about computational complexity theory, but I've read some papers describing how there is often a phase transition where a high SNR puts the problem in P territory, but a sufficiently low SNR moves the problem moves to NP territory (but it's still solvable). Beyond the phase transition, a solution is information theoretically impossible. I wonder if most of these real world TSP problems actually lie in P, but I don't know how one would go about showing that. (I haven't performed a literature search, but I wouldn't be surprised if someone has already demonstrated this.)

drostie 9y ago
That's very unlikely to be true in general, as the proofs that a problem lives in NP usually have a very high signal-to-noise ratio -- i.e. in order to prove that solving this problem is at least as hard as solving an arbitrary boolean circuit, we need to find a subset of the problem which behaves like wires and boolean gates do, and the resulting "circuits" are very heavily structured.
deleted 9y ago
[deleted]