Click here to Skip to main content
15,920,031 members
Home / Discussions / Algorithms
   

Algorithms

 
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 
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 
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 programming
You 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.
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 PinPopular
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 PinPopular
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 
GeneralRe: LALR vs LR parsing Pin
honey the codewitch23-Feb-20 7:29
mvahoney the codewitch23-Feb-20 7:29 
QuestionRouting algorithm Pin
Rocks10028-Jan-20 8:23
Rocks10028-Jan-20 8:23 

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.