[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] [Fwd: Re: [Fwd: glpsol not converging]]
|
From: |
Meketon, Marc |
|
Subject: |
Re: [Help-glpk] [Fwd: Re: [Fwd: glpsol not converging]] |
|
Date: |
Wed, 1 Aug 2012 22:36:41 -0500 |
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: 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.
_______________________________________________
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.