[Help-glpk] Re: Bug or unsolvable ?? MIP problem; Fixed output buffer overflow problem, where to submit ?

[Andrew Makhorin]

> 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
> working."

> 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
Generating Objective...
Generating TotalDiscount...
Generating TotalDiscountLowerBound...
Generating TotalDiscountUpperBound...
Generating TrayCount...
Generating TrayCountLowerBound...
Generating TrayCountUpperBound...
Generating TraySize...
Generating Threshold...
Generating Inclusion...
Generating MutualExclusion...
Generating AllSorted...
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
Scaling...
 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)
170968
5
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, 
> Abhilash