Re: [Help-glpk] Preprocessing

[glpk xypron]

Hello Andrew,

I implemented an elimination of linear dependent rows in appended
glpnpp06.c.

This cuts the solution time for Kevin's problem down from several
hours to 9 minutes.

I am aware that you are currently focused on improving the branch
and bound algorithm, and do not expect a short term response.

The following patches are needed in addition to glpnpp06c:

--- glpk-4.44/src/glpnpp.h      2010-06-03 10:00:00.000000000 +0200
+++ glpk-4.44-npp/src/glpnpp.h  2010-10-15 20:22:13.000000000 +0200
@@ -515,6 +515,10 @@
 int npp_integer(NPP *npp, const glp_iocp *parm);
 /* process MIP prior to applying branch-and-bound method */

+#define npp_remove_dupliate_rows _glp_remove_dupliate_rows
+int npp_remove_duplicate_rows(NPP *npp);
+/* remove duplicate rows */
+
 #endif

 /* eof */

--- glpk-4.44/src/glpnpp05.c    2010-06-03 10:00:00.000000000 +0200
+++ glpk-4.44-npp/src/glpnpp05.c        2010-10-15 20:25:51.000000000 +0200
@@ -664,6 +664,10 @@
       processing = 1;
       while (processing)
       {  processing = 0;
+#if 1 /* 15/X-2010 */
+         ret = npp_remove_duplicate_rows(npp);
+         if (ret != 0) goto done;
+#endif
          /* process all active rows */
          for (;;)
          {  row = npp->r_head;


--- glpk-4.44/src/Makefile.am   2010-06-03 10:00:00.000000000 +0200
+++ glpk-4.44-npp/src/Makefile.am       2010-10-15 20:26:42.000000000 +0200
@@ -90,6 +90,7 @@
 glpnpp03.c \
 glpnpp04.c \
 glpnpp05.c \
+glpnpp06.c \
 glpqmd.c \
 glprgr.c \
 glprng01.c \


Best regards

Xypron

-------- Original-Nachricht --------
> Datum: Wed, 13 Oct 2010 07:44:23 -0400
> Betreff: Re: [Help-glpk] Preprocessing
> 
> Update: I let it run overnight.  It finally solved, but it took GLPK 
> 3h43m to solve.
> 
> -----
> ...
> *504000: obj =   3.072361858e+06  infeas =  2.662e-09 (0)
> *504008: obj =   3.072361858e+06  infeas =  2.058e-09 (0)
> OPTIMAL SOLUTION FOUND
> Time used:   13339.0 secs
> Memory used: 184.7 Mb (193680871 bytes)
> 
> $
> -----
> 
> Cheers,
> 
> Kevin

-- 
GRATIS! Movie-FLAT mit über 300 Videos. 
Jetzt freischalten unter http://portal.gmx.net/de/go/maxdome

glpnpp06.c.gz
Description: application/gzip