
From:  Nigel Galloway 
Subject:  Re: [Helpglpk] Option to set to generate all solutions 
Date:  Sat, 23 Apr 2011 06:47:06 0700 
C:\KuKu3>glpsol SuDoku9x9.rules.gz o out.sol
GLPSOL: GLPK LP/MIP Solver, v4.45
Parameter(s) specified in the command line:
SuDoku9x9.rules.gz o out.sol
Reading problem data from `SuDoku9x9.rules.gz'...
SuDoku9x9.rules.gz:8: warning: missing model name in field 3
Objective: R0
325 rows, 729 columns, 2916 nonzeros
729 integer variables, all of which are binary
2689 records were read
GLPK Integer Optimizer, v4.45
325 rows, 729 columns, 2916 nonzeros
729 integer variables, all of which are binary
Preprocessing...
324 rows, 729 columns, 2916 nonzeros
729 integer variables, all of which are binary
Scaling...
A: minaij = 1.000e+000 maxaij = 1.000e+000 ratio = 1.000e+000
Problem data seem to be well scaled
Constructing initial basis...
Size of triangular part = 324
Solving LP relaxation...
GLPK Simplex Optimizer, v4.45
324 rows, 729 columns, 2916 nonzeros
0: obj = 0.000000000e+000 infeas = 2.160e+002 (0)
* 470: obj = 0.000000000e+000 infeas = 1.125e014 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+ 470: mip = not found yet >= inf (1; 0)
+ 3138: >>>>> 0.000000000e+000 >= 0.000000000e+000 0.0% (56; 0)
+ 3138: mip = 0.000000000e+000 >= tree is empty 0.0% (0; 111)
INTEGER OPTIMAL SOLUTION FOUND
Time used: 1.0 secs
Memory used: 1.2 Mb (1212314 bytes)
Writing MIP solution to `out.sol'...
Which is:
517923468
348176592
296458371
831564927
625719843
974832156
452387619
163295784
789641235
Interestingly the solutions are different.
In conclusion: glpk could be modified so that it produced an out.sol for every possible problem and the user could then search through them for the solution they want, or the intelligence required to generate all meaningful train routes could be encapsulated in an MPS file and the users provided with a tool:
that can understand an MPS file
has a GUI making it easy for them to extract the one they want.
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 nonlinear 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 nonlinear.
 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/wpcontent/uploads/2010/11/Hazmat_2010_Informs.pdfSome 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/RASIGFall2008Newsletter.pdf
 http://www.fastmail.fm  Send your email first class
SuDoKu9x9.zip
Description: Zip compressed data
[Prev in Thread]  Current Thread  [Next in Thread] 