Apologies for replying to myself twice, but a bit of experimenting has shown me a partial explanation for the mystery I raised in the quoted text below. As well as the fact that the MIP software used by the authors of the paper linked below might have been specifically written for transport problems, I have also found, to my surprise (though it makes sense when you think about it), that, in a "bridge and torch" problem, the larger the number of people who are allowed to "cross the river" in one go, the more easily GLPK is able to resolve it. Since the large scale problems they claim to have resolved in the paper are about optimising transport in a city, they will have been discussing buses and trains - which, of course, carry large numbers of people simultaneously.
I wasn't expecting this, because according to the academic paper at http://www.zib.de/Publications/Reports/SC-95-27.ps.Z (from Konrad-Zuse-Zentrum für Informationstechnik Berlin), river crossing problems can be resolved using integer programming with planar cuts. Would I be correct in thinking that to achieve the level of results described in that paper, one would have to program the planar cuts explicitly for this problem, rather than use the generalised cuts provided with GLPK, or is there something I can do to make the model resolve more quickly?
Add other email accounts to Hotmail in 3 easy steps. Find out how.
New! Receive and respond to mail from other email accounts from within Hotmail Find out how.
|