Click here to Skip to main content
15,936,850 members
Home / Discussions / Algorithms
   

Algorithms

 
GeneralRe: Travelling Salesman Problem Pin
wscwt0118-Mar-20 11:12
wscwt0118-Mar-20 11:12 
GeneralRe: Travelling Salesman Problem Pin
Member 147935355-Apr-20 19:53
Member 147935355-Apr-20 19:53 
AnswerRe: Travelling Salesman Problem Pin
Greg Utas18-Mar-20 9:28
professionalGreg Utas18-Mar-20 9:28 
GeneralRe: Travelling Salesman Problem Pin
wscwt0118-Mar-20 11:11
wscwt0118-Mar-20 11:11 
QuestionVehicle routing problem for large graph Pin
Member 147325527-Mar-20 12:23
Member 147325527-Mar-20 12:23 
GeneralRe: Vehicle routing problem for large graph Pin
harold aptroot7-Mar-20 13:35
harold aptroot7-Mar-20 13:35 
GeneralRe: Vehicle routing problem for large graph Pin
Member 147325528-Mar-20 0:51
Member 147325528-Mar-20 0:51 
GeneralRe: Vehicle routing problem for large graph Pin
harold aptroot8-Mar-20 4:28
harold aptroot8-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.
GeneralRe: Vehicle routing problem for large graph Pin
Member 147325528-Mar-20 6:41
Member 147325528-Mar-20 6:41 
GeneralRe: Vehicle routing problem for large graph Pin
harold aptroot8-Mar-20 7:48
harold aptroot8-Mar-20 7:48 
GeneralRe: Vehicle routing problem for large graph Pin
Member 147325528-Mar-20 8:07
Member 147325528-Mar-20 8:07 
AnswerRe: Vehicle routing problem for large graph Pin
Hailu Worku Obsse17-Mar-20 20:15
professionalHailu Worku Obsse17-Mar-20 20:15 
QuestionRecursion Pin
Member 1475643326-Feb-20 10:10
Member 1475643326-Feb-20 10:10 
AnswerRe: Recursion Pin
Daniel Pfeffer26-Feb-20 21:22
professionalDaniel Pfeffer26-Feb-20 21:22 
GeneralRe: Recursion Pin
Member 1475643326-Feb-20 22:39
Member 1475643326-Feb-20 22:39 
GeneralRe: Recursion Pin
Daniel Pfeffer26-Feb-20 23:25
professionalDaniel Pfeffer26-Feb-20 23:25 
GeneralRe: Recursion Pin
Member 1475643326-Feb-20 23:33
Member 1475643326-Feb-20 23:33 
QuestionNegating a number Pin
Nand3219-Feb-20 2:53
Nand3219-Feb-20 2:53 
AnswerRe: Negating a number Pin
Richard MacCutchan19-Feb-20 3:04
mveRichard MacCutchan19-Feb-20 3:04 
GeneralRe: Negating a number Pin
Nand3219-Feb-20 3:08
Nand3219-Feb-20 3:08 
GeneralRe: Negating a number Pin
Richard MacCutchan19-Feb-20 3:47
mveRichard MacCutchan19-Feb-20 3:47 
AnswerRe: Negating a number Pin
Richard Deeming19-Feb-20 3:23
mveRichard Deeming19-Feb-20 3:23 
GeneralRe: Negating a number Pin
Nand3219-Feb-20 3:32
Nand3219-Feb-20 3:32 
QuestionLALR vs LR parsing Pin
honey the codewitch13-Feb-20 3:53
mvahoney the codewitch13-Feb-20 3:53 
AnswerRe: LALR vs LR parsing Pin
Member 1298255823-Feb-20 6:45
Member 1298255823-Feb-20 6:45 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.