Re: [Help-glpk] Option to set to generate all solutions

The University's undergraduate course is called Decision Mathematics. I am considering proposing a prospectus for a course on Indecision or Consultant Mathematics.

Thanks for the links, these seem to be using the good old (what else is there) Excel spreadsheet as the interface, my thoughts go to ieSudoku. This consists of a MPS file (SuDoku.rules.gz) which may be considered to contain the solution to all SuDoku problems, and a GUI which helps a user to extract a required solution.

This can be run without any user input, by using the GUI and pressing Solve without entering any values (see attached if you don't want to install it) or using glpsol as follows:

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 non-zeros
729 integer variables, all of which are binary
2689 records were read
GLPK Integer Optimizer, v4.45
325 rows, 729 columns, 2916 non-zeros
729 integer variables, all of which are binary
Preprocessing...
324 rows, 729 columns, 2916 non-zeros
729 integer variables, all of which are binary
Scaling...
A: min|aij| = 1.000e+000 max|aij| = 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 non-zeros
      0: obj = 0.000000000e+000 infeas = 2.160e+002 (0)
*   470: obj = 0.000000000e+000 infeas = 1.125e-014 (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.

Nigel Galloway

address@hidden

On Thu, 14 Apr 2011 09:13 -0500, "Meketon, Marc" <address@hidden> wrote:

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
Subject:	Re: [Help-glpk] Option to set to generate all solutions
Date:	Sat, 23 Apr 2011 06:47:06 -0700