[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Nigel Galloway
Subject: Re: [Help-glpk] Option to set to generate all solutions
Date: Sat, 23 Apr 2011 06:47:06 -0700

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
324 rows, 729 columns, 2916 non-zeros
729 integer variables, all of which are binary
 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)
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)
Time used:   1.0 secs
Memory used: 1.2 Mb (1212314 bytes)
Writing MIP solution to `out.sol'...

Which is:


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
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:
Some other background is in the article "Using Software Tools to Provide Improved Hazmat Visibility for Freight Railroads" found in 

-- - Send your email first class

Description: Zip compressed data

reply via email to

[Prev in Thread] Current Thread [Next in Thread]