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

[Andrew Makhorin]

-------- Forwarded Message --------
From: Narendra Devta-Prasanna <address@hidden>
To: Meketon, Marc <address@hidden>
Cc: Andrew Makhorin <address@hidden>, address@hidden <address@hidden>
Subject: Re: [Help-glpk] [Fwd: Re: [Fwd: glpsol not converging]]
Date: Thu, 2 Aug 2012 16:11:06 -0700

Hi Marc,

Thanks so much for the suggestion. I tried this approach and introduced
random perturbations (<1%) to the cost function and now the optimal
solution is found within few hours which is acceptable in terms of run
time. The shortest run time was ~1 hr and the longest so far has been ~5
hr.

Thanks again.

Regards,
-Narendra


On Wed, Aug 1, 2012 at 8:36 PM, Meketon, Marc
<address@hidden> wrote:
        Since Andrew said that it was probably not finding dual
        feasibility due to multiple optimal (dual-degeneracy), I tried
        my scheduling problem with small random perturbations on the
        cost function.
        
        The linear program relaxation took much longer to solve - say
        from 20 seconds to 60 seconds.
        
        The integerization piece went from being unsolvable (the system
        never finding a dual-feasible solution) to solving in a few
        seconds.
        
        -Marc
        
        -----Original Message-----
        From: address@hidden
        [mailto:address@hidden
        On Behalf Of Andrew Makhorin
        Sent: Wednesday, August 01, 2012 1:56 PM
        To: address@hidden
        Subject: [Help-glpk] [Fwd: Re: [Fwd: glpsol not converging]]
        
        -------- 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: help-glpk-bounces
        address@hidden
                [mailto:help-glpk-bounces
        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.
        
        
        
        
        _______________________________________________
        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.