4 ms·

Aren't those two different problems? I was under the impression that Travelling Salesman was about efficiently visiting multiple points in any order, where as

by Lio 4y ago

Aren't those two different problems? I was under the impression that Travelling Salesman was about efficiently visiting multiple points in any order, where as navigation directions are ordered point-to-point, even if you add multiple waypoints. As such Travelling Salesman would be much, much more complex. I'm probably way out on current best solutions[1] but you could do one with Djikstra's Algorithm or A* but the other would require something probabilistic like Simulated Annealing. 1. Sorry, I'm almost certain that these are not optimal algorithms but I'm just using them as illustration for "small" graphs. I'd be very happy to be enlightened on what's more current.

eru 4y ago
If you want an exact solution, and are willing to wait for it, you can use an integer linear programming solver to work on your Traveling Salesman Problem for you. If you abort them early, these solvers can give you an approximate solution and *crucially* also a guarantee how far away they are from the optimal solution. Eg at most 3.7% longer than the optimal solution.
- bumby 4y ago
  Relating to the article on construction, I think this may be an instance where the theory breaks down in practice. Construction jobs aren’t just optimal linear programming because the order often impacts both the costs and duration of subsequent work, making much of it nonlinear.
  - eru 4y ago
    Linear integer programming can model these kinds of dependencies.
    - bumby 4y ago
      Can you elaborate? My understanding is they can in an iterative fashion, but the dependencies I’m talking about are not constraints but nonlinear dependencies between decision variables. As an example, the decision variables may be integers denoting schedule blocks, but the cost is a nonlinear function of time and the other variables. Meaning each time block can be solved with linear programming iteratively, but to solve across all time blocks requires nonlinear optimization
      - eru 4y ago
        The general answer is that linear integer programming is NP-complete. The more specific answer is that you can abuse integer variables to do Boolean logic and then eg model piece-wise linear functions relatively easily. In practice, this abuse might or might not be very performant, it depends on exactly what you are doing and what your solving is doing. It might be fine, or you might be better off with quadratic or complex programming solvers. If you have a more specific example, I can try to model it.
        bumby 4y ago
        Say we have some equipment condition estimated by time variant non-linear function like the Weibull reliability function. [1] Say the cost of repair is based on a nonlinear relationship between between the equipment replacement cost and current condition. Something like cost = replace_cost * [(100-current_condition)/(100 - failing_condition)]^2 After repair, the condition increases to some assumed value (say, 95). The overall facility condition is the cost-weighted average of the constituent equipment conditions at any point in time. facility_cond = sum(equip_cond * equip_cost)/sum(equip_cost) I want to plan repairs over some time period (say, 10 years) to optimize facility condition within some budget. Can I do this with linear programming? I can set it up as a linear problem for a single snapshot in time, but haven't thought of a way to efficiently do it as a linear program concurrently across multiple time steps. [1] https://weibull.com/hotwire/issue7/relbasics7.htm https://weibull.com/hotwire/issue7/relbasics7.htm
        eru 4y ago
        You _can_ do this as a mixed integer linear program. Whether it's a good idea, is another question.
        bumby 4y ago
        How would one go about setting that up? It’s been done on a per year basis, but every approach that looks at multiple years seems to require non-linear optimization
- Lio 4y ago
  Oh that reminds me of something I worked on from long ago. Not sure I'd use LP for Travelling Salesman[1] but I think it can be applied to production planning for scheduling in factories. That at least seems similar to what these construction workers are doing. I think I recall that a floating point linear program will solve much faster than an integer one, at least with Simplex algorithm which is the only one I've ever really used. I'm pretty sure it's possible to set up operation scheduling problems so that the decision variables become either 1.0 or 0. i.e. 1.0: do this operation at this preset time - or - 0: don't do it. Does that sound about right? It was a long time ago that I did any LP though and I'm very rusty, so many pinches of salt recommended to be taken with this comment. :) 1. It'll work for Travelling Salesman but I suspect it will probably be too slow for anything not trivial.
  - eru 4y ago
    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.

by Lio 4y ago

eru 4y ago

If you want an exact solution, and are willing to wait for it, you can use an integer linear programming solver to work on your Traveling Salesman Problem for you. If you abort them early, these solvers can give you an approximate solution and *crucially* also a guarantee how far away they are from the optimal solution. Eg at most 3.7% longer than the optimal solution.

bumby 4y ago
Relating to the article on construction, I think this may be an instance where the theory breaks down in practice. Construction jobs aren’t just optimal linear programming because the order often impacts both the costs and duration of subsequent work, making much of it nonlinear.
- eru 4y ago
  Linear integer programming can model these kinds of dependencies.
  - bumby 4y ago
    Can you elaborate? My understanding is they can in an iterative fashion, but the dependencies I’m talking about are not constraints but nonlinear dependencies between decision variables. As an example, the decision variables may be integers denoting schedule blocks, but the cost is a nonlinear function of time and the other variables. Meaning each time block can be solved with linear programming iteratively, but to solve across all time blocks requires nonlinear optimization
    - eru 4y ago
      The general answer is that linear integer programming is NP-complete. The more specific answer is that you can abuse integer variables to do Boolean logic and then eg model piece-wise linear functions relatively easily. In practice, this abuse might or might not be very performant, it depends on exactly what you are doing and what your solving is doing. It might be fine, or you might be better off with quadratic or complex programming solvers. If you have a more specific example, I can try to model it.
      - bumby 4y ago
        Say we have some equipment condition estimated by time variant non-linear function like the Weibull reliability function. [1] Say the cost of repair is based on a nonlinear relationship between between the equipment replacement cost and current condition. Something like cost = replace_cost * [(100-current_condition)/(100 - failing_condition)]^2 After repair, the condition increases to some assumed value (say, 95). The overall facility condition is the cost-weighted average of the constituent equipment conditions at any point in time. facility_cond = sum(equip_cond * equip_cost)/sum(equip_cost) I want to plan repairs over some time period (say, 10 years) to optimize facility condition within some budget. Can I do this with linear programming? I can set it up as a linear problem for a single snapshot in time, but haven't thought of a way to efficiently do it as a linear program concurrently across multiple time steps. [1] https://weibull.com/hotwire/issue7/relbasics7.htm https://weibull.com/hotwire/issue7/relbasics7.htm
        eru 4y ago
        You _can_ do this as a mixed integer linear program. Whether it's a good idea, is another question.
        bumby 4y ago
        How would one go about setting that up? It’s been done on a per year basis, but every approach that looks at multiple years seems to require non-linear optimization
Lio 4y ago
Oh that reminds me of something I worked on from long ago. Not sure I'd use LP for Travelling Salesman[1] but I think it can be applied to production planning for scheduling in factories. That at least seems similar to what these construction workers are doing. I think I recall that a floating point linear program will solve much faster than an integer one, at least with Simplex algorithm which is the only one I've ever really used. I'm pretty sure it's possible to set up operation scheduling problems so that the decision variables become either 1.0 or 0. i.e. 1.0: do this operation at this preset time - or - 0: don't do it. Does that sound about right? It was a long time ago that I did any LP though and I'm very rusty, so many pinches of salt recommended to be taken with this comment. :) 1. It'll work for Travelling Salesman but I suspect it will probably be too slow for anything not trivial.
- eru 4y ago
  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.