The shortest path algorithm that uses a linear objective function can only approximate the true objective function in this example.
The objective function is a non-linear combination of two concepts: * A "score" created by an outside program that we have no visibility to how it truly works. The score represents how good the route is, and considers the population centers, the "iconic" value of nearby places, how well protected the railyards are, the quality of the railline, and about 25 other factors. Presumably very non-linear. * A judgement based on the transportation plan that could use the routes. For example, one route may be served by a number of local trains that require lots of switching of the rail wagon, and another route is served by a single "road" train that requires no intermediate switching of the wagon. The optimizer finds a number of potential feasible solutions, each one is scored by the external program and examined for other transportation factors, and then one solution is picked. Since thousands of solutions are possible, most with minor variations, we need to pick only the "interesting" ones to score. An INFORMS presentation is here: http://blog.railplanning.com/wp-content/uploads/2010/11/Hazmat_2010_Informs.pdf Some other background is in the article "Using Software Tools to Provide Improved Hazmat Visibility for Freight Railroads" found in http://www.innovativescheduling.com/Files/RAS/RASIG-Fall-2008-Newsletter.pdf ________________________________ From: Nigel Galloway [mailto:[email protected]] Sent: Thursday, April 14, 2011 8:25 AM To: Meketon, Marc Cc: [email protected] Subject: Re: [Help-glpk] Option to set to generate all solutions If a problem is really linear then one input has one output, almost the definition. In abstract cases which have multiple solutions one may treat the problem as linear by consistantly choosing a particular solution. Usually the one which makes some resulting propery continuous, or at least more so. Perhaps in this railway case you could be modern and politcally correct by factoring in an environmental cost and selecting the route with the lowest carbon footprint. -- Nigel Galloway [email protected]<mailto:[email protected]> On Tue, 12 Apr 2011 14:49 -0500, "Meketon, Marc" <[email protected]> wrote: Since we're sharing stories of using multiple solutions... One of the products of my group helps railways plan to route hazardous materials. We use a specialized K-shortest path algorithm to generate a number of alternatives, which are then evaluated by another system out of our control; this evaluation is way beyond what can be modeled as a simple linear cost function. The problem with using K-shortest paths is that in complex networks, many of the solutions are just minor variations that are very uninteresting. In the US, consider the problem of going from the East cost to the West Coast. If I take I-80 I go from New York to Chicago to Omaha to Salt Lake City to San Francisco. If I take I-40, it's a southern route through Raleigh North Carolina, Memphis Tennessee, and onto Los Angeles. But a K-shortest path algorithm generally returns minor variations, such as two I-40 routes, but one uses a bypass that goes around Knoxville and adds 5 miles to the total mileage and is dfferent by around 15 miles from the normal I-40 route. In this case, getting all the solutions is worse than useless - it's distracting. A lot of work is needed to weed out the minor variations from the really important differences. I suspect this is similar to many other situations in which someone says "I want all the solutions." -Marc ________________________________ From: [email protected] [mailto:[email protected]] On Behalf Of Suleyman Demirel Sent: Tuesday, April 12, 2011 1:52 PM Cc: [email protected] Subject: Re: [Help-glpk] Option to set to generate all solutions To address Andrew's earlier comment, "Nevertheless, imagine that you have obtained all the feasible or optimal solutions. In which way would you use them?", I want to cite an anecdote. My department is trying to match the skill sets and strengths of students (around 90 of them) with projects (around 30 of them). They solve a typical assignment problem to create 30 teams of size 2-4. In a typical assignment problem, you have costs of assigning a person to a project and you minimize the total cost. In reality, this is restrictive. First, how do you decide these cost coefficients? Second, what if you do not know your exact objective function? (For example, when you see a solution, you feel like there is something wrong that you do not like about it, but it is hard to express why you don't like it in linear equations). The department usually plays with these cost coefficients and obtains several solutions and make judgement calls to see which one is the best. (This is roughly the story, I am skipping many details.) It would be interesting to generate all solutions. If that is expensive, generating a lot of reasonable solutions would be great. This is an example of a case where you want to see all (or many) feasible solutions. I suspect that it should be the case when a problem involves the human factor. 2011/4/12 Michael Hennebry <[email protected]<mailto:[email protected]>> On Mon, 11 Apr 2011, Klas Markström wrote: I think that Jeff had approximately the right idea. In the callback to check possible integer feasible solutions test whether it is actaully fesible. If so, add it to your list, add a constraint and declare it infeasible. If not, proceeed as usual. At the end, GLPK will return infeasible and I think that the list will contain at least the extreme points of the convex hull. -- Michael [email protected]<mailto:[email protected]> "Pessimist: The glass is half empty. Optimist: The glass is half full. Engineer: The glass is twice as big as it needs to be." _______________________________________________ Help-glpk mailing list [email protected]<mailto:[email protected]> http://lists.gnu.org/mailman/listinfo/help-glpk -- _________________________________________ Sent via my good, old desktop. _________________________________________ Suleyman Demirel - Office: (734) 647-3167 PhD Candidate in Operations Management Stephen M. Ross School of Business University of Michigan, Ann Arbor Web: http://www.umich.edu/~sdemirel _________________________________________ ________________________________ This e-mail and any attachments may be confidential or legally privileged. If you received this message in error or are not the intended recipient, you should destroy the e-mail message and any attachments or copies, and you are prohibited from retaining, distributing, disclosing or using any information contained herein. Please inform us of the erroneous delivery by return e-mail. Thank you for your cooperation. _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk -- http://www.fastmail.fm - A fast, anti-spam email service. ________________________________ This e-mail and any attachments may be confidential or legally privileged. If you received this message in error or are not the intended recipient, you should destroy the e-mail message and any attachments or copies, and you are prohibited from retaining, distributing, disclosing or using any information contained herein. Please inform us of the erroneous delivery by return e-mail. Thank you for your cooperation.
_______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
