[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Help-glpk] Re: Bug or unsolvable ?? MIP problem; Fixed output buffer ov
[Help-glpk] Re: Bug or unsolvable ?? MIP problem; Fixed output buffer overflow problem, where to submit ?
Fri, 4 Dec 2009 05:34:39 +0300
> Helloe evryone,
> This is my first email and cry for help.
> However, I have been playing around with Glpk for a while.
> Let me jump right into my problem.
> I recently hit a particular instance of my problem, that seems like a
> bug, but I am not sure what #39;s going on, since glpk does not crash.
> However, it just keeps running, for hours.
> I tested for around 28-29 hours before saying "This is just not
> The way I see it from the log ....., it has solved the problem,
> however it keeps trying to optimise it, and just could not.
> I am not sure if this qualifies as a bug or not.
This is not a bug. Your mip instance is hard for the
branch-and-bound method used by glpsol by default: it finds the
solution, however, it continues running to prove its optimality.
The branch-and-cut method with MIR cuts, i.e. 'glpsol --mir', solves
your instance on the root level for less than a second:
GLPSOL: GLPK LP/MIP Solver 4.40
Parameter(s) specified in the command line:
-m ampl_model.txt -d s4gc.1a --mir
Reading model section from ampl_model.txt...
121 lines were read
Reading data section from s4gc.1a...
1596 lines were read
Model has been successfully generated
ipp_basic_tech: 12 row(s) and 0 column(s) removed
ipp_reduce_bnds: 3 pass(es) made, 7 bound(s) reduced
ipp_basic_tech: 0 row(s) and 0 column(s) removed
ipp_reduce_coef: 1 pass(es) made, 0 coefficient(s) reduced
glp_intopt: presolved MIP has 295 rows, 155 columns, 803 non-zeros
glp_intopt: 148 integer columns, all of which are binary
A: min|aij| = 1.000e+000 max|aij| = 1.560e+002 ratio = 1.560e+002
GM: min|aij| = 4.301e-001 max|aij| = 2.325e+000 ratio = 5.406e+000
EQ: min|aij| = 1.894e-001 max|aij| = 1.000e+000 ratio = 5.280e+000
2N: min|aij| = 1.250e-001 max|aij| = 1.172e+000 ratio = 9.375e+000
Constructing initial basis...
Size of triangular part = 295
Solving LP relaxation...
0: obj = 0.000000000e+000 infeas = 1.960e+002 (0)
* 1: obj = 0.000000000e+000 infeas = 0.000e+000 (0)
* 162: obj = 1.709740000e+005 infeas = 0.000e+000 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
MIR cuts enabled
+ 162: mip = not found yet <= +inf (1; 0)
+ 246: >>>>> 1.709680000e+005 <= 1.709680000e+005 0.0% (1; 0)
+ 246: mip = 1.709680000e+005 <= tree is empty 0.0% (0; 1)
INTEGER OPTIMAL SOLUTION FOUND
Time used: 0.1 secs
Memory used: 1.3 Mb (1312020 bytes)
300 1 0
851 40 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
852 9 42 44 45 46 47 49 50 53 58
853 6 59 60 61 62 63 64
1285 20 41 43 48 51 52 54 55 56 57 65 66 67 68 69 70 71 72 73 74 75
Model has been successfully processed
> Also, I know for sure I have solved much bigger problems than this
> before. So, I am not even sure if this is the limit of glpk, which i
> suppose it is not.
> I want to know three things from you:
> 1. Am I emailing to the wrong list/ person ? If that #39;s the case,
> please do tell me where not to email, since I hate spammers, and would
> hate to be labeled one.
You are emailing to the right list.
> 2. Is there some sort of limit on glpk ? Is there an upper limit to
> the number of rows,columns, non-zeroes, etc. that could tell me what
> is the biggest problem it could solve. And I am not even talking about
> millions, more like thousands maybe ?
There is no such limit. However, if glpk cannot finish within an hour,
it may mean that the instance you are trying to solve is hard for it.
> 3. I know for sure that I have solved bigger problems like this
> before, with the same ampl (gmpl) code and different data. So I really
> am puzzled why this is not getting solved.
> here #39;s my setup:
> I am using glpsol.exe (v. 4.38), this way
> "glpsol --model ampl_model.txt --data " << dataFile.c_str() << "
> --display " << blah blah
> on windows xp command line
> Also, find attached my glpsol.log (it would show u a lot of files, i
> am running all of them in a sequence, i am sending the one that
> failed....it is the last one on glpsol.log) ,ampl_model.txt and data
> file (s4gc.1a)
> Any help would be highly appreciated.
> Oh and by the way, I did make changes to glpk source code to fix the
> output buffer overflow problem a while back (more like 2 months or so
> back) How am I supposed to submit that code to you guys ?
This problem has been fixed in glpk 4.41.
> Thanks a ton,
|[Prev in Thread]
||[Next in Thread]|
- [Help-glpk] Re: Bug or unsolvable ?? MIP problem; Fixed output buffer overflow problem, where to submit ?,
Andrew Makhorin <=