|
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.
|
|
|
|
|
Mmh that's very interesting, thanks a lot!
So if I understood correctly I explore all solutions with recursion, using B&B to cut the branch that would lead (up to a gentle estimation) to solutions that are worse than "so far optimal".
Plus when I am deep enough i "freeze" the solution found so far and I use LP to solve what's left.
Is that right?
Do you think this could be solved in less than 5 minutes considering that the size of the graph is
~250 nodes?
And if I just use the B&B approach without the linear programming (which I am not 100% familiar) do you think this approach could work as well?
Would It make sense to create a heuristic that makes explore first "hypothetically better solutions"? (not sure if I am able to do it)
I am afraid that after the failure with the tabu search I could implement this and end up with something-not-working because of the size of the problem
|
|
|
|
|
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.
|
|
|
|
|
Thank you very much, I will try this approach!
|
|
|
|
|
I have tried similar problem using Genetic Algorithm and the results were astonishing. I think trying Genetic Algorithm may be wonderful for you too in speeding the search time.
|
|
|
|
|
I'm confused about recursion in mergesort. I've tried putting comments in the code that track the variables so its easier to understand what's going on, but I'm still struggling.
For an array of size 4, I understand the initial process -
mergesort(o,3).
0 is less than 3, so we find the middle value = 1. Low = 0, Middle,1 and High = 3
mergesort(0,1)
0 is less than 1, so we find the middle value = 0. Low = 0, Middle = 0, High 1
0 is not < 0, so the function is called again but with (middle +1 and high) as its parameters.
1 is not < 1, so the function merge is called with the parameters (0,0,1).
So far so good ! 
But when the recursive function kicks in again, this time it has the values (0,2,3) which has been passed to the second recursive function (middle +1, high)  How did this happen ?? Is it because the second recursive function is using the same parameters as the first function on its second iteration? (0,1,3).
I've been looking all over for this, and lots of people just seem to skim over this step. I'm new, so would really appreciate any advice anyone has to give. I've tried experimenting with recursive functions, like finding the nth term in fib series, and sum of triangular numbers, which I can do now, but it doesnt seem to be helping in solving this problem.
Big thanks
public void mergesort (int low, int high) {
sum ++;
System.out.println("Round " + sum + ". Parameters being passed in = " + low + " " + middle + " " +high);
if (low<high) {
int middle = low + (high - low)/2;
System.out.println("Checking left ---- if " + low + " is < " + high);
System.out.println("Current value of high = " + high);
System.out.println("Current value of mid = " + middle);
System.out.println("low, mid and high =" + low + "" + middle + "" + high);
System.out.println();
mergesort(low,middle);
System.out.println("low, mid and high =" + low + "" + middle + "" + high);
mergesort(middle +1,high);
System.out.println("Checking right ---- if " + (middle +1) + " is < " + high);
System.out.println("low, mid and high =" + low + "" + middle + "" + high);
merge(low,middle,high);
}
|
|
|
|
|
If helps to view recursion in terms of a stack of work items. For example, you start with a work item:
mergesort(0, 3)
This is popped off the stack and executed, giving:
mergesort(0, 1)
mergesort(2, 3)
The top entry is popped off the stack, and executed, giving
mergesort(0, 0)
mergesort(1, 1)
mergesort(2, 3)
No work needs be performed for the first item (0, 0)
No work needs be performed for the second item (1, 1)
==> merge(0, 0, 1)
We now have mergesort(2, 3) left on the stack, which is precisely what you see.
Freedom is the freedom to say that two plus two make four. If that is granted, all else follows.
-- 6079 Smith W.
|
|
|
|
|
Hi Daniel,
I don't understand your third call of mergesort. The first time it calls (0,3) which is the first and last index of the array.
The second time it calls (0,1), which is the first half, or first two indexes in the list.
But then why is it going to (2,3) ?
Surely as 0<1, the function would give (0,0) at which point it would exit finding the left half as the base condition has been met ?
I've read it then retains the value of (0,1), which is then passed into the second instance of mergesort (mid +1,high), to give (1,1), which means the left and right sides are both ready to be merged ?
I'll try to think of it more in terms of a stack, thanks for the pointer on that. I know how to program stacks, so I might try something this afternoon to see if I can get a full picture of whats going on underneath the recursive process,
Thanks for your help 
|
|
|
|
|
If you move your print statements out of the if (low < high) { … } block, you will see the extra calls to mergesort() that I added. In the cases of mergesort(0, 0) and mergesort(1, 1) you don't ender the if() block, so you don't see them at present.
Freedom is the freedom to say that two plus two make four. If that is granted, all else follows.
-- 6079 Smith W.
|
|
|
|
|
Thank you, I will try this today
|
|
|
|
|
How do I convert ANY number to negative representation? I'm trying this in Excel.
To converting a positive number X, I just multiply with -1 & it gets converted to X * -1 = -X.
But what if I a number that is negative already, and the same formula should work seamlessly.
For example if it's -X & I multiply with -1 it gets converted to +X. Like -X * -1 = X.
which I don't want.
On a list containing both negative & positive values, I want this formula to have an impact only with the negative numbers.
modified 19-Feb-20 9:34am.
|
|
|
|
|
=IF(X>0,-X,X) ' where X is the cell reference
|
|
|
|
|
Richard MacCutchan wrote: =IF(X>0,-X,X)
Wow, that's sweet. 
|
|
|
|
|
Excel functions generally are.
|
|
|
|
|
Another option would be to use the ABS function:
=-ABS(X) ABS function - Office Support[^]
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
Terrific. 
|
|
|
|
|
Okay, so I know the table generation algorithms are slightly different in that LALR merges entries and a canonical LR parser will not.
My question is, is about the actual *use* of those entries - the final parse table.
Is there a difference between how a LALR parser parses and an LR parser *parses*?
Specifically, can I use the same parser code regardless of where I got the parse table? (whether from an LR algo or the LALR ago)
Real programmers use butterflies
|
|
|
|
|
shift/reduce parsing: the difference between LALR (1) and LR (1) is that LALR is based
on an LR (0) automaton.
Operationally they are the same: shift when you have to shift, reduce when you have to
reduce and give an error message when there is a mismatch between the set of expected tokens
and the received token
|
|
|
|
|
anyway thanks for your answer, i figured it out eventually the day i asked it but i didn't think to close the question (and i don't know if that's expected)
Real programmers use butterflies
|
|
|
|
|
Hi all, just seeking some advice please on how to approach this problem.
I need to create an algorithm for a small courier company.
The basic parameters would be x amount of drivers and a list of deliveries, pickup and drop-off postcodes with delivery time slots.
My thinking is to first create a matrix of all the pick up and delivery job postcodes and populate it with distance and journey times using Google’s API, then somehow loop through the jobs and match journey time’s with the delivery slots but not really sure where to start or even if this is a viable approach.
Any suggestions much appreciated !!!
Many thanks in advance 😊
|
|
|
|
|
Sounds like a nightmare version of the "travelling salesman" problem to me. 
Traveling Salesman Problem | Solve the Traveling Salesman Problem[^]
All I can offer is that you should check whether the API returns the actual driving distance, or the "as the crow flies" straight-line distance. Once you start taking things like rivers and one-way systems into account, someone who is geographically closer to a destination might take considerably longer to reach it than someone who is technically further away.
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
Hey, yep definitely is that, the journey time’s returned are actual driving times based on Google’s distance API 😊
|
|
|
|
|
|
Get a UPS, USPS or FedEx account and use their costing algorithms (and maybe their services, all told).
It was only in wine that he laid down no limit for himself, but he did not allow himself to be confused by it.
― Confucian Analects: Rules of Confucius about his food
|
|
|
|
|
Kindly help me out to solve this question fro the book "Foundation of Algorithm"
There are two algorithms called Alg1 and Alg2 for a problem of size n. Alg1 runs in n2 microseconds and Alg2 runs in 100n log n microseconds. Alg1 can be implemented using 4 hours of programmer time and needs 2 minutes of CPU time. On the other hand, Alg2 requires 15 hours of programmer time and 6 minutes of CPU time. If programmers are paid 20 dollars per hour and CPU time costs 50 dollars per minute, how many times must a problem instance of size 500 be solved using Alg2 in order to justify its development cost?
thanks
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
