#9617 closed defect (invalid)
Broken export of LP files....
Reported by: | ncohen | Owned by: | jason, jkantor |
---|---|---|---|
Priority: | major | Milestone: | sage-duplicate/invalid/wontfix |
Component: | linear programming | Keywords: | CPLEX, GLPK, glpsol, MPS, file |
Cc: | leif, jhpalmieri | Merged in: | |
Authors: | Reviewers: | Nathann Cohen | |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
This error has been noticed throuugh #9584
After taking a look at the corresponding part of the code, *OF COURSE* something needed to be changedm but to be honest I have no inkling why Sage did not report this as an error : I was adding str(k) in a string while k.... was not defined ? O_o
Nathann
Attachments (1)
Change History (14)
Changed 11 years ago by
comment:1 Changed 11 years ago by
- Status changed from new to needs_review
comment:2 Changed 11 years ago by
- Keywords CPLEX GLPK glpsol MPS file added
comment:3 Changed 11 years ago by
The good news: Your patch here seems to work fine.
The bad news: I've again exported (now valid) MPS and LP files for the edge_disjoint_spanning_trees()
example with 30 vertices and run glpsol
on those files on both a 64-bit machine and on the 32-bit machine (P4 Prescott) where that example did not terminate. The logs are slightly different, but both terminate:
GLPSOL: GLPK LP/MIP Solver, v4.44 Parameter(s) specified in the command line: --freemps edst-30_vertices.mps Reading problem data from `edst-30_vertices.mps'... edst-30_vertices.mps:8: warning: missing model name in field 3 Objective: R0000000 1720 rows, 3650 columns, 10040 non-zeros 1370 integer variables, all of which are binary 8412 records were read GLPK Integer Optimizer, v4.44 1720 rows, 3650 columns, 10040 non-zeros 1370 integer variables, all of which are binary Preprocessing... 1670 rows, 3605 columns, 9790 non-zeros 1325 integer variables, all of which are binary Scaling... A: min|aij| = 1.000e+00 max|aij| = 1.000e+00 ratio = 1.000e+00 Problem data seem to be well scaled Constructing initial basis... Size of triangular part = 1670 Solving LP relaxation... GLPK Simplex Optimizer, v4.44 1670 rows, 3605 columns, 9790 non-zeros 0: obj = 0.000000000e+00 infeas = 2.610e+02 (0) 500: obj = 0.000000000e+00 infeas = 2.610e+02 (0) 1000: obj = 0.000000000e+00 infeas = 2.330e+02 (0) 1500: obj = 0.000000000e+00 infeas = 1.172e+00 (0) * 1589: obj = 0.000000000e+00 infeas = 2.132e-14 (0) OPTIMAL SOLUTION FOUND Integer optimization begins... + 1589: mip = not found yet >= -inf (1; 0) + 4531: mip = not found yet >= 0.000000000e+00 (26; 0) + 8462: mip = not found yet >= 0.000000000e+00 (62; 0) + 14689: mip = not found yet >= 0.000000000e+00 (106; 0) + 28430: >>>>> 0.000000000e+00 >= 0.000000000e+00 0.0% (223; 3) + 28430: mip = 0.000000000e+00 >= tree is empty 0.0% (0; 451) INTEGER OPTIMAL SOLUTION FOUND Time used: 19.1 secs Memory used: 5.6 Mb (5848196 bytes)
(64-bit machine, time due to high sysload)
GLPSOL: GLPK LP/MIP Solver, v4.44 Parameter(s) specified in the command line: --freemps /home/leif/Sage/new-mps-lp/edst-30_vertices.mps Reading problem data from `/home/leif/Sage/new-mps-lp/edst-30_vertices.mps'... /home/leif/Sage/new-mps-lp/edst-30_vertices.mps:8: warning: missing model name in field 3 Objective: R0000000 1720 rows, 3650 columns, 10040 non-zeros 1370 integer variables, all of which are binary 8412 records were read GLPK Integer Optimizer, v4.44 1720 rows, 3650 columns, 10040 non-zeros 1370 integer variables, all of which are binary Preprocessing... 1670 rows, 3605 columns, 9790 non-zeros 1325 integer variables, all of which are binary Scaling... A: min|aij| = 1.000e+00 max|aij| = 1.000e+00 ratio = 1.000e+00 Problem data seem to be well scaled Constructing initial basis... Size of triangular part = 1670 Solving LP relaxation... GLPK Simplex Optimizer, v4.44 1670 rows, 3605 columns, 9790 non-zeros 0: obj = 0.000000000e+00 infeas = 2.610e+02 (0) 500: obj = 0.000000000e+00 infeas = 2.610e+02 (0) 1000: obj = 0.000000000e+00 infeas = 2.330e+02 (0) 1500: obj = 0.000000000e+00 infeas = 1.172e+00 (0) * 1589: obj = 0.000000000e+00 infeas = 2.132e-14 (0) OPTIMAL SOLUTION FOUND Integer optimization begins... + 1589: mip = not found yet >= -inf (1; 0) + 3426: mip = not found yet >= 0.000000000e+00 (10; 0) + 4687: mip = not found yet >= 0.000000000e+00 (21; 0) + 5604: mip = not found yet >= 0.000000000e+00 (32; 0) + 6640: mip = not found yet >= 0.000000000e+00 (44; 0) + 7802: mip = not found yet >= 0.000000000e+00 (58; 0) + 9123: mip = not found yet >= 0.000000000e+00 (72; 0) + 11067: mip = not found yet >= 0.000000000e+00 (86; 0) + 13203: mip = not found yet >= 0.000000000e+00 (101; 0) + 15411: mip = not found yet >= 0.000000000e+00 (117; 1) + 18254: mip = not found yet >= 0.000000000e+00 (135; 1) + 21870: mip = not found yet >= 0.000000000e+00 (156; 1) Time used: 60.1 secs. Memory used: 3.8 Mb. + 26285: mip = not found yet >= 0.000000000e+00 (186; 4) + 29923: >>>>> 0.000000000e+00 >= 0.000000000e+00 0.0% (253; 15) + 29923: mip = 0.000000000e+00 >= tree is empty 0.0% (0; 535) INTEGER OPTIMAL SOLUTION FOUND Time used: 67.4 secs Memory used: 4.9 Mb (5146500 bytes)
(32-bit machine/Pentium 4 Prescott)
That means the bug causing the non-termination sits somewhere in the Sage library interface to GLPK.
All files were generated on the 64-bit machine; I've not yet tried to generate them on the 32-bit machine (they might differ, so I'll check that later).
(The LP/MPS files of that example are too big to upload them here, approx. 260KB.)
comment:4 follow-up: ↓ 6 Changed 11 years ago by
Weird O_o
Short of these names, there is really no difference between the code used to produce the file and the one building the data structure for GLPK. Did you use the very Random Graph which produced timeouts before, or generated a different one ?
Nathann
comment:5 Changed 11 years ago by
By the way, why do you think the non-termination is a bug ?
It just takes ages to solve, that's all... Sometimes the solver use non-deterministic methods, or detect a good cut for some reason... It would be weird to find out that the same problem always takes ages to solve through Sage, and is quickly done with through files, but other than this a LP which takes ages to be solved happens quite often.
For example the pretty pictures displayed there :
http://www-sop.inria.fr/members/Nathann.Cohen/acyclicedgecoloring/
stop at step 10. The reason is that the LP I wrote for 12 was still running after 4 days.
Nathann
comment:6 in reply to: ↑ 4 Changed 11 years ago by
Replying to ncohen:
Weird O_o
Short of these names, there is really no difference between the code used to produce the file and the one building the data structure for GLPK.
Yes, except for the variable and constraint names, which is why I believe something goes wrong in constructing the problem on the 32-bit machine (and this should be observable through differences in the generated files).
Did you use the very Random Graph which produced timeouts before, or generated a different one ?
I did generate files for all examples, the logs above are from exactly the 30-vertices random graph one. (I made sure they are the same on both machines by adding some more doctests).
comment:7 Changed 11 years ago by
Hello !!!
By carefully looking at the two logs, the one you just gave and the one given by John on #9584, I noticed a difference, even though all the number of entries, lines/etc were the same. Yours
+ 1589: mip = not found yet >= -inf (1; 0)
His
+ 1589: mip = not found yet <= +inf (1; 0)
And all the following inequalities are reversed... Well, it sounds like you are working on a minimization problem, while John his working on a maximization problem. That's when I remembered a problem I had had with GLPK a long time ago when using it through the command-line (but perhaps it was CPLEX or CBC, I do not remember). At least one of them was completely ignoring the direction of the optimization given in the file, and only behaved nicely when given the good flag... Could you give it a try with one of those ?
--min minimization --max maximization
I am really sorry but I can not do it myself, I am travelling these days and unable to find any place where I could use my own computer ^{};
Nathann
comment:8 follow-up: ↓ 9 Changed 11 years ago by
This is really funny. I've now exported the MPS file on the 32-bit machine, too.
While the doctest itself did not terminate (at least not within reasonable time, so I manually killed the orphan process after the time-out), running glpsol
on the exported (in theory identical) problem succeeds rather quickly:
GLPSOL: GLPK LP/MIP Solver, v4.44 Parameter(s) specified in the command line: --freemps edst-30_vertices.x86.mps Reading problem data from `edst-30_vertices.x86.mps'... edst-30_vertices.x86.mps:8: warning: missing model name in field 3 Objective: R0000000 1720 rows, 3650 columns, 10040 non-zeros 1370 integer variables, all of which are binary 8412 records were read GLPK Integer Optimizer, v4.44 1720 rows, 3650 columns, 10040 non-zeros 1370 integer variables, all of which are binary Preprocessing... 1670 rows, 3605 columns, 9790 non-zeros 1325 integer variables, all of which are binary Scaling... A: min|aij| = 1.000e+00 max|aij| = 1.000e+00 ratio = 1.000e+00 Problem data seem to be well scaled Constructing initial basis... Size of triangular part = 1670 Solving LP relaxation... GLPK Simplex Optimizer, v4.44 1670 rows, 3605 columns, 9790 non-zeros 0: obj = 0.000000000e+00 infeas = 2.610e+02 (0) 500: obj = 0.000000000e+00 infeas = 2.610e+02 (0) 1000: obj = 0.000000000e+00 infeas = 2.330e+02 (0) 1500: obj = 0.000000000e+00 infeas = 1.172e+00 (0) * 1589: obj = 0.000000000e+00 infeas = 2.132e-14 (0) OPTIMAL SOLUTION FOUND Integer optimization begins... + 1589: mip = not found yet >= -inf (1; 0) + 3426: mip = not found yet >= 0.000000000e+00 (10; 0) + 4687: mip = not found yet >= 0.000000000e+00 (21; 0) + 5604: mip = not found yet >= 0.000000000e+00 (32; 0) + 6640: mip = not found yet >= 0.000000000e+00 (44; 0) + 7802: mip = not found yet >= 0.000000000e+00 (58; 0) + 9123: mip = not found yet >= 0.000000000e+00 (72; 0) + 11067: mip = not found yet >= 0.000000000e+00 (86; 0) + 13203: mip = not found yet >= 0.000000000e+00 (101; 0) + 15411: mip = not found yet >= 0.000000000e+00 (117; 1) + 18105: mip = not found yet >= 0.000000000e+00 (134; 1) + 21758: mip = not found yet >= 0.000000000e+00 (154; 1) Time used: 60.1 secs. Memory used: 3.8 Mb. + 26154: mip = not found yet >= 0.000000000e+00 (183; 4) + 29923: >>>>> 0.000000000e+00 >= 0.000000000e+00 0.0% (253; 15) + 29923: mip = 0.000000000e+00 >= tree is empty 0.0% (0; 535) INTEGER OPTIMAL SOLUTION FOUND Time used: 67.6 secs Memory used: 4.9 Mb (5146500 bytes)
(This is again "inverted".)
comment:9 in reply to: ↑ 8 Changed 11 years ago by
Replying to leif:
This is really funny. I've now exported the MPS file on the 32-bit machine, too.
While the doctest itself did not terminate [...], running
glpsol
on the exported (in theory identical) problem succeeds rather quickly [...]
Hmmm, even more weird (i.e. unexpected, but correct), the exported MPS files on both machines are identical; running glpsol
with --min
or --max
on this file (on the 32-bit machine) succeeds in almost the same time, though p.solve()
in the doctest (which should do nearly the same, acting on the same problem) does not terminate (I've added some doctests to ensure e.g. that the random graph is the same as on the other machine):
... Trying: g = digraphs.RandomDirectedGNP(Integer(30),RealNumber('.3'))###line 3427:_sage_ >>> g = digraphs.RandomDirectedGNP(30,.3) Expecting nothing ok Trying: g.num_edges()###line 3428:_sage_ >>> g.num_edges() Expecting: 274 ok Trying: g.is_connected(), g.is_strongly_connected()###line 3430:_sage_ >>> g.is_connected(), g.is_strongly_connected() Expecting: (True, True) ok Trying: g.dig6_string()###line 3432:_sage_ >>> g.dig6_string() Expecting: ']SgO??BsCQ_a?_ZEbOOJW@_glO_CZ`WkGQCQxD_]bOaVa@AQtGQROOwwGkG?_SKECgKe?QH`cf@@B@IOSQEhAO?GQ@MbmvGAAOOeG_[E?F?LoOo?O@GomMoQoWEdICAS@G@W@j?oCY@U_HeWCPG@SZI' ok Trying: k = Integer(g.edge_connectivity()) ; k###line 3434:_sage_ >>> k = Integer(g.edge_connectivity()) ; k Expecting: 5 ok Trying: arborescences = g.edge_disjoint_spanning_trees(k,save_to_mps="edst-30_vertices.x86.mps")###line 3436:_sage_ >>> arborescences = g.edge_disjoint_spanning_trees(k,save_to_mps="edst-30_vertices.x86.mps") Expecting nothing Writing problem data to `edst-30_vertices.x86.mps'... 8412 records were written Running the solver... GLPK Integer Optimizer, v4.44 1719 rows, 3650 columns, 10040 non-zeros 1370 integer variables, all of which are binary Preprocessing... 1670 rows, 3605 columns, 9790 non-zeros 1325 integer variables, all of which are binary Scaling... A: min|aij| = 1.000e+00 max|aij| = 1.000e+00 ratio = 1.000e+00 Problem data seem to be well scaled Constructing initial basis... Size of triangular part = 1670 Solving LP relaxation... GLPK Simplex Optimizer, v4.44 1670 rows, 3605 columns, 9790 non-zeros 0: obj = 0.000000000e+00 infeas = 2.610e+02 (0) 500: obj = 0.000000000e+00 infeas = 2.610e+02 (0) 1000: obj = 0.000000000e+00 infeas = 2.330e+02 (0) 1500: obj = 0.000000000e+00 infeas = 1.172e+00 (0) * 1589: obj = 0.000000000e+00 infeas = 0.000e+00 (0) OPTIMAL SOLUTION FOUND Integer optimization begins... + 1589: mip = not found yet <= +inf (1; 0) + 3027: mip = not found yet <= 0.000000000e+00 (10; 0) + 4012: mip = not found yet <= 0.000000000e+00 (21; 0) + 4827: mip = not found yet <= 0.000000000e+00 (33; 0) + 6016: mip = not found yet <= 0.000000000e+00 (45; 0) + 7325: mip = not found yet <= 0.000000000e+00 (57; 0) + 8418: mip = not found yet <= 0.000000000e+00 (71; 0) + 10058: mip = not found yet <= 0.000000000e+00 (86; 0) + 12057: mip = not found yet <= 0.000000000e+00 (102; 0) + 14306: mip = not found yet <= 0.000000000e+00 (119; 0) + 16920: mip = not found yet <= 0.000000000e+00 (138; 1) + 19724: mip = not found yet <= 0.000000000e+00 (161; 4) Time used: 60.1 secs. Memory used: 4.5 Mb. + 25085: mip = not found yet <= 0.000000000e+00 (160; 37) + 30069: mip = not found yet <= 0.000000000e+00 (169; 66) + 35413: mip = not found yet <= 0.000000000e+00 (164; 114) + 40592: mip = not found yet <= 0.000000000e+00 (162; 148) + 46308: mip = not found yet <= 0.000000000e+00 (156; 202) + 50687: mip = not found yet <= 0.000000000e+00 (162; 226) + 53833: mip = not found yet <= 0.000000000e+00 (185; 227) + 58922: mip = not found yet <= 0.000000000e+00 (197; 235) + 63603: mip = not found yet <= 0.000000000e+00 (220; 239) + 68927: mip = not found yet <= 0.000000000e+00 (234; 267) + 74057: mip = not found yet <= 0.000000000e+00 (235; 309) + 79491: mip = not found yet <= 0.000000000e+00 (243; 327) Time used: 120.1 secs. Memory used: 5.2 Mb. + 84964: mip = not found yet <= 0.000000000e+00 (249; 370) + 90218: mip = not found yet <= 0.000000000e+00 (246; 424) + 94528: mip = not found yet <= 0.000000000e+00 (262; 448) + 98002: mip = not found yet <= 0.000000000e+00 (274; 495) +101638: mip = not found yet <= 0.000000000e+00 (269; 598) +104424: mip = not found yet <= 0.000000000e+00 (281; 683) +108994: mip = not found yet <= 0.000000000e+00 (271; 780) +113239: mip = not found yet <= 0.000000000e+00 (272; 853) +116931: mip = not found yet <= 0.000000000e+00 (277; 924) +120486: mip = not found yet <= 0.000000000e+00 (288; 955) +125828: mip = not found yet <= 0.000000000e+00 (278; 1021) +131593: mip = not found yet <= 0.000000000e+00 (283; 1070) Time used: 180.2 secs. Memory used: 5.7 Mb. ... Time used: 480.2 secs. Memory used: 7.1 Mb. +409472: mip = not found yet <= 0.000000000e+00 (389; 6372) +414372: mip = not found yet <= 0.000000000e+00 (392; 6505) +418908: mip = not found yet <= 0.000000000e+00 (391; 6604) +423799: mip = not found yet <= 0.000000000e+00 (403; 6673) +429213: mip = not found yet <= 0.000000000e+00 (398; 6769) +434852: mip = not found yet <= 0.000000000e+00 (389; 6876) +439868: mip = not found yet <= 0.000000000e+00 (394; 6948) +445276: mip = not found yet <= 0.000000000e+00 (401; 7011) +449608: mip = not found yet <= 0.000000000e+00 (400; 7105) +453674: mip = not found yet <= 0.000000000e+00 (409; 7184) +458621: mip = not found yet <= 0.000000000e+00 (412; 7281) +464380: mip = not found yet <= 0.000000000e+00 (391; 7412) Time used: 540.3 secs. Memory used: 7.1 Mb. +469098: mip = not found yet <= 0.000000000e+00 (399; 7494) *** *** Error: TIMED OUT! PROCESS KILLED! *** *** [600.9 s] ---------------------------------------------------------------------- The following tests failed: sage -t -verbose "devel/sage-main/sage/graphs/generic_graph.py" # Time out Total time for all tests: 600.9 seconds +473909: mip = not found yet <= 0.000000000e+00 (391; 7592) +479067: mip = not found yet <= 0.000000000e+00 (391; 7669) +484074: mip = not found yet <= 0.000000000e+00 (402; 7739) +489588: mip = not found yet <= 0.000000000e+00 (405; 7825) +493883: mip = not found yet <= 0.000000000e+00 (401; 7943) +498222: mip = not found yet <= 0.000000000e+00 (408; 8030) +503017: mip = not found yet <= 0.000000000e+00 (402; 8153) +507610: mip = not found yet <= 0.000000000e+00 (412; 8231) +512031: mip = not found yet <= 0.000000000e+00 (413; 8334) +516681: mip = not found yet <= 0.000000000e+00 (410; 8439) +520300: mip = not found yet <= 0.000000000e+00 (415; 8560) Time used: 600.3 secs. Memory used: 7.1 Mb. ... Time used: 3001.1 secs. Memory used: 9.6 Mb. +2797586: mip = not found yet <= 0.000000000e+00 (474; 56897) +2802741: mip = not found yet <= 0.000000000e+00 (460; 57042) +2807948: mip = not found yet <= 0.000000000e+00 (453; 57174) +2811236: mip = not found yet <= 0.000000000e+00 (449; 57252) +2814551: mip = not found yet <= 0.000000000e+00 (446; 57289)
(At this point I killed the orphaned Python process, since I'm pretty sure it wouldn't terminate. A previous run hadn't stopped after more than 44,000 seconds; cf. #9584.)
Sorry for abusing this ticket, which originally only dealt with the invalid MPS/LP file export issue.
comment:10 Changed 11 years ago by
- Component changed from numerical to linear programming
comment:11 Changed 11 years ago by
This ticket should be closed, as it is made invalid because of #10043
Nathann
comment:12 Changed 11 years ago by
- Milestone changed from sage-4.6.1 to sage-duplicate/invalid/wontfix
- Resolution set to invalid
- Status changed from needs_review to closed
comment:13 Changed 11 years ago by
- Reviewers set to Nathann Cohen
Thanks for (hopefully) fixing this; I won't be able to test/review this until tomorrow though. (But then will try to track down the non-terminating doctest from #9584 further.)
-Leif