3 ms·

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

by 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

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.