Re: [Help-glpk] [Fwd: glpsol not converging]

[Meketon, Marc]

Not sure if this is relevant:

Recently I've been trying to solve some scheduling models with GLPK.  The model 
is very well scaled, there are no "Big M" constants, most if not all of the 
coefficients in the A matrix are 0 or 1.

The Simplex part works very well, and solves the LP in a 20 seconds of time.  
But then the MIP (that has on 6 integer variables) immediately goes into the 
same behavior that Narendra finds:  it goes into a feasibility loop after the 
MIP begins and gives output exactly like Narendra's last line.  And does so for 
hours before I kill the process.

-Marc

-----Original Message-----
From: address@hidden [mailto:address@hidden On Behalf Of glpk xypron
Sent: Wednesday, August 01, 2012 12:56 AM
To: Narendra Devta-Prasanna
Cc: address@hidden
Subject: Re: [Help-glpk] [Fwd: glpsol not converging]

Hello Andrew,

looking at the output Narendra provided GLPK is stuck in the warm up phase and 
cannot find an initial LP solution. Here the time limit of the mip solver is 
ignored.

Would it be possible to pass the tmlim parameter to the simplex solver?

@Narendra
Looking at the value of your objective function "obj =   3.241402100e+07" could 
it be that you have very large ratios between the smallest and largest matrix 
elements of your problem?

Please, start your model again without --check and provide start of the output, 
e.g.
Model has been successfully generated
GLPK Integer Optimizer, v4.47
289 rows, 480 columns, 1680 non-zeros
240 integer variables, all of which are binary Preprocessing...
288 rows, 480 columns, 1440 non-zeros
240 integer variables, all of which are binary Scaling...
 A: min|aij| =  1.000e+00  max|aij| =  1.500e+01  ratio =  1.500e+01
GM: min|aij| =  9.586e-01  max|aij| =  1.043e+00  ratio =  1.088e+00
EQ: min|aij| =  9.189e-01  max|aij| =  1.000e+00  ratio =  1.088e+00
2N: min|aij| =  9.375e-01  max|aij| =  1.000e+00  ratio =  1.067e+00 
Constructing initial basis...
Size of triangular part = 286
Solving LP relaxation...
GLPK Simplex Optimizer, v4.47

The ratio provided in the scaling phase gives a good indication if your model 
is well conditioned.

Analyze your model whether you are using some big M approach or dummy costs 
with very high numbers and try to find a better scaled formulation.

Best regards

Xypron


-------- Original-Nachricht --------
> Datum: Tue, 31 Jul 2012 16:41:40 -0700
> Betreff: Re: [Help-glpk] [Fwd: glpsol not converging]

> Hi Xypron,
>
> Yes, I have re-checked the parameters again. I used 10000 (10E5) and
> not
> 10E6 for --tmlim.
>
> The last 10 lines of output from the run are:
>
> |16587000: obj =   3.241402100e+07  infeas =  1.037e-09 (2)
> |16587500: obj =   3.241402100e+07  infeas =  7.363e-10 (2)
> |16588000: obj =   3.241402100e+07  infeas =  5.294e-10 (2)
> |16588500: obj =   3.241402100e+07  infeas =  6.339e-10 (2)
> |16589000: obj =   3.241402100e+07  infeas =  9.333e-10 (2)
> |16589500: obj =   3.241402100e+07  infeas =  1.177e-09 (2)
> |16590000: obj =   3.241402100e+07  infeas =  3.791e-09 (2)
> |16590500: obj =   3.241402100e+07  infeas =  1.787e-09 (2)
> |16591000: obj =   3.241402100e+07  infeas =  8.604e-10 (2)
> |16591500: obj =   3.241402100e+07  infeas =  1.154e-09 (2)
>
> This process is running on a 64-bit Linux m/c with 2G of memory
> reserved for this process. I also know that there is no slowdown
> happening because of any memory swapping etc. I am using v4.47 version
> as indicated by this message in the output of the run:
>
> GLPSOL: GLPK LP/MIP Solver, v4.47
>
> I also ran with --check option and the tool output is as below:
>
> GLPSOL: GLPK LP/MIP Solver, v4.47
> Parameter(s) specified in the command line:
>  -m tam.mod -d step1.dat
>  --check
> Reading model section from tam.mod...
> 226 lines were read
> Reading data section from step1.dat...
> 2390 lines were read
> Generating IOSingleMode...
> Generating TotalInputIOs...
> Generating TotalOutputIOs...
> Generating IOPreInputMode...
> Generating IOPreOutputMode...
> Generating PreDefInput...
> Generating PreDefOutput...
> Generating UsedIOIsInput1...
> Generating UsedIOIsInput2...
> Generating UsedIOIsOutput1...
> Generating UsedIOIsOutput2...
> Generating InputIOUsedOnce...
> Generating OutputIOUsedOnce...
> Generating BlockInputIOUsedOnce...
> Generating BlockOutputIOUsedOnce...
> Generating FlatPreDefInput...
> Generating FlatPreDefOutput...
> Generating BlockInputFlatUnused...
> Generating BlockOutputFlatUnused...
> Generating FlatUsedIOIsInput...
> Generating FlatUsedIOIsOutput...
> Generating FlatBlockInputAssigned...
> Generating FlatBlockOutputAssigned...
> Generating FlatIOUsedOnceIn...
> Generating FlatIOUsedOnceOut...
> Generating FlatWireLengthIn...
> Generating FlatWireLengthOut...
> Generating WireLengthOut...
> Generating WireLengthIn...
> Generating WireLength...
> Generating Routing...
> Model has been successfully generated
>
> I specified the --first option as I was trying different things to
> check if it helps in speeding up. I have also tried without that
> option, but I still get stuck in an endless run.
>
> I really appreciate your help on this.
>
> Thanks again and Best regards,
> -Narendra
>
>
> On Tue, Jul 31, 2012 at 4:22 PM, glpk xypron <address@hidden> wrote:
>
> > Hello Narendra,
> >
> > if tmlim is 100000 (10E5) the optimization should have stopped after
> > 28 hours. Please, check you did not enter 1000000 (10E6).
> >
> > On Linux you can use
> > ps -df
> > to check the parameters of your running process.
> >
> > To better understand your problem, please, provide:
> > - last output lines of your "endless" run
> > - operating system you run on (including whether its 32 or 64bit)
> > - version of GLPK you are using.
> > - output of glpsol -m tam.mod -d step1.dat --check
> >
> > The parameter --first typically will slow down the solution. You
> > should only specify it, if you are sure about how your variables are
> > sorted and why you want to always branch on the first integer variable.
> >
> > Best regards
> >
> > Xypron

_______________________________________________
Help-glpk mailing list
address@hidden
https://lists.gnu.org/mailman/listinfo/help-glpk

This e-mail and any attachments may be confidential or legally privileged. If 
you received this message in error or are not the intended recipient, you 
should destroy the e-mail message and any attachments or copies, and you are 
prohibited from retaining, distributing, disclosing or using any information 
contained herein.  Please inform us of the erroneous delivery by return e-mail. 
Thank you for your cooperation.