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

[Andrew Makhorin]

-------- Forwarded Message --------
From: Narendra Devta-Prasanna <address@hidden>
To: Meketon, Marc <address@hidden>
Cc: glpk xypron <address@hidden>, address@hidden
<address@hidden>, Andrew Makhorin <address@hidden>
Subject: Re: [Help-glpk] [Fwd: glpsol not converging]
Date: Wed, 1 Aug 2012 10:45:55 -0700

Hello Everyone,

Thank you very much for your comments and help.

Hi Xypron,

I am not using Big-M method or something similar. From the tool message,
it shows that the problem data is well scaled. The tool message is shown
below.

Hi Marc,

I think the problem I am facing is exactly the same as yours. For other
smaller instances of this model, the tool solved in <5min.

The tool output (starting part) is:

GLPSOL: GLPK LP/MIP Solver, v4.47
Parameter(s) specified in the command line:
 -m /lsi/dv/tm14/ndprasan/HiTest/tam_ip_optimization/tam_io_assignment.mod
 -d ./glpk_co_top/co_top_TAM_IP_glpk_step1.dat
-o ./glpk_co_top/co_top_TAM_IP_glpk_step1.out
 -y ./glpk_co_top/co_top_TAM_IP_glpk_step1.res --first --cuts --tmlim
100000
 --mipgap 0.25
Reading model section
from /lsi/dv/tm14/ndprasan/HiTest/tam_ip_optimization/tam_io_assignment.mod...
226 lines were read
Reading data section from ./glpk_co_top/co_top_TAM_IP_glpk_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
GLPK Integer Optimizer, v4.47
1058440 rows, 469125 columns, 1868778 non-zeros
469120 integer variables, all of which are binary
Preprocessing...
122402 rows, 117792 columns, 472842 non-zeros
117792 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 = 122400
Solving LP relaxation...
GLPK Simplex Optimizer, v4.47
122402 rows, 117792 columns, 472842 non-zeros
      0: obj =   4.068158300e+07  infeas =  9.600e+02 (2)
    500: obj =   4.084578300e+07  infeas =  9.400e+02 (2)
   1000: obj =   4.106858100e+07  infeas =  9.130e+02 (2)
   1500: obj =   4.128631500e+07  infeas =  8.900e+02 (2)

Best Regards,
-Narendra


On Wed, Aug 1, 2012 at 5:07 AM, Meketon, Marc
<address@hidden> wrote:
        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.