15,920,031 members
Home / Discussions / Algorithms

# Algorithms

 Re: Travelling Salesman Problem Greg Utas18-Mar-20 9:28 Greg Utas 18-Mar-20 9:28
 Re: Travelling Salesman Problem wscwt0118-Mar-20 11:11 wscwt01 18-Mar-20 11:11
 Vehicle routing problem for large graph Member 147325527-Mar-20 12:23 Member 14732552 7-Mar-20 12:23
 Re: Vehicle routing problem for large graph harold aptroot7-Mar-20 13:35 harold aptroot 7-Mar-20 13:35
 Re: Vehicle routing problem for large graph Member 147325528-Mar-20 0:51 Member 14732552 8-Mar-20 0:51
 Re: Vehicle routing problem for large graph harold aptroot8-Mar-20 4:28 harold aptroot 8-Mar-20 4:28
 Re: Vehicle routing problem for large graph Member 147325528-Mar-20 6:41 Member 14732552 8-Mar-20 6:41
 Re: Vehicle routing problem for large graph harold aptroot8-Mar-20 7:48 harold aptroot 8-Mar-20 7:48
 Member 14732552 wrote:Plus when I am deep enough i "freeze" the solution found so far and I use LP to solve what's left.I wouldn't put it like that, it's more that the LP solution naturally tends to become integral at some point (meaning it's a "real solution", not just an estimate) and then you can use it directly. It's just something that happens automatically and you can use it as a shortcut when it does. Member 14732552 wrote:Do you think this could be solved in less than 5 minutes considering that the size of the graph is ~250 nodes?IDK, I've solved TSP of that size and a bit faster. But VRP is a bit different. For both of them goes, how fast it is depends a lot on how good the estimates are. There are many advanced techniques to improve the basic LP, mostly techniques that look at a fractional solution and then generate a "cut" that adds a constraint to the LP such that it brings the new optimal solution closer to what the integer solution would be. Gomory cuts can be used, but the really high quality stuff is specific to the problem. Member 14732552 wrote:use the B&B approach without the linear programmingYou can do that, you just need some optimistic estimate. It doesn't matter how you get it, but it should be optimistic: a pessimistic estimate (eg doing a quick greedy search or whatever) would mean that the sub-tree with the optimal solution in it might be skipped because the estimate said the sub-tree is bad. Member 14732552 wrote:Would It make sense to create a heuristic that makes explore first "hypothetically better solutions"? (not sure if I am able to do it)There is a lot of freedom in the B&B framework. Nodes can be explored in basically whatever order, you can order the variables however you want (with an LP based estimate, an interesting strategy is picking a variable to branch on that the LP solution was "least sure about" - closest to 0.5 - rather than a variable that was close to 0 or 1), you can dynamically change the strategies even.
 Re: Vehicle routing problem for large graph Member 147325528-Mar-20 8:07 Member 14732552 8-Mar-20 8:07
 Re: Vehicle routing problem for large graph Hailu Worku Obsse17-Mar-20 20:15 Hailu Worku Obsse 17-Mar-20 20:15
 Recursion Member 1475643326-Feb-20 10:10 Member 14756433 26-Feb-20 10:10
 Re: Recursion Daniel Pfeffer26-Feb-20 21:22 Daniel Pfeffer 26-Feb-20 21:22
 Re: Recursion Member 1475643326-Feb-20 22:39 Member 14756433 26-Feb-20 22:39
 Re: Recursion Daniel Pfeffer26-Feb-20 23:25 Daniel Pfeffer 26-Feb-20 23:25
 Re: Recursion Member 1475643326-Feb-20 23:33 Member 14756433 26-Feb-20 23:33
 Negating a number Nand3219-Feb-20 2:53 Nand32 19-Feb-20 2:53
 Re: Negating a number Richard MacCutchan19-Feb-20 3:04 Richard MacCutchan 19-Feb-20 3:04
 Re: Negating a number Nand3219-Feb-20 3:08 Nand32 19-Feb-20 3:08
 Re: Negating a number Richard MacCutchan19-Feb-20 3:47 Richard MacCutchan 19-Feb-20 3:47
 Re: Negating a number Richard Deeming19-Feb-20 3:23 Richard Deeming 19-Feb-20 3:23
 Re: Negating a number Nand3219-Feb-20 3:32 Nand32 19-Feb-20 3:32
 LALR vs LR parsing honey the codewitch13-Feb-20 3:53 honey the codewitch 13-Feb-20 3:53
 Re: LALR vs LR parsing Member 1298255823-Feb-20 6:45 Member 12982558 23-Feb-20 6:45
 Re: LALR vs LR parsing honey the codewitch23-Feb-20 7:29 honey the codewitch 23-Feb-20 7:29
 Routing algorithm Rocks10028-Jan-20 8:23 Rocks100 28-Jan-20 8:23
 Last Visit: 31-Dec-99 18:00     Last Update: 19-Jun-24 13:40 Refresh ᐊ Prev1...14151617181920212223 Next ᐅ