15,936,850 members
Home / Discussions / Algorithms

# Algorithms

 Re: Travelling Salesman Problem wscwt0118-Mar-20 11:12 wscwt01 18-Mar-20 11:12
 Re: Travelling Salesman Problem Member 147935355-Apr-20 19:53 Member 14793535 5-Apr-20 19:53
 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
 It's on wikipedia as well. The basic idea is to recursively construct all solutions, but at every step down the recursion tree also optimistically estimate (using eg LP) how good the best possible solution in this sub-tree could be. If the estimate is worse than the best solution found thus far, there is no point exploring that sub-tree, and that lets you skip a (usually) huge amount of exploration. With LP based estimations, it can also easily happen that it actually gives an integer solution (that doesn't tend to happen early on, but it does tend to happen before the bottom of the search tree is reached) and in that case it would be the actual best solution in this sub-tree. There is an ILP formulation of VRP on the wikipedia page of VRP, dropping the integrality constraint turns it into an LP formulation suitable for such estimates. Some extras that strenthen the linear relaxation are also mentioned. Using just the "basic" formulation works, but the estimates are not very good then.
 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
 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
 Last Visit: 31-Dec-99 18:00     Last Update: 14-Jul-24 11:06 Refresh ᐊ Prev1...14151617181920212223 Next ᐅ