Re: [Help-glpk] Binary Problem

[Andrew Makhorin]

>   I have written a problem with a lot of binary variables (see the
> attached lp matrix).  I am working with glpk410 calling the routines
> by VB for Excel as follows:

>       lp = glpk_read_cpxlp(Trim(DireccionOPT   probname))

>      Call glpk_set_real_parm(lp, 313, 20000)

>       'Optimizar problema LP

>       status = glpk_integer(lp)

>       status = glpk_mip_status(lp)

>       '

>       'Obtener estado solución problema LP

>       status = glpk_intopt(lp)

>       If status <> 200 Then

>           MsgBox "No existe solución"

>       End If

>      

>    'Obtener solución de un rango de variables

>       cur_numcols =
>  glpk_get_num_cols(lp)

>   When I execute the above code I have not been able to see the
> solution for the attached matrix, I mean GLPK does not end. I know
> that there are some parameters that I have to tune in order to find a
> solution of this kind of problem, could you help to set the right
> parameters that I might use in order to find a quickly solution to the
> attached matrix please?

Using options --mir and --bestp I could solve your instance with
glpsol 4.28 to optimality for about 20 minutes on my pc:

glp_read_lp: reading problem data from `ProblemaProyecto_CP.lp'...
glp_read_lp: 205 rows, 1000 columns, 2000 non-zeros
glp_read_lp: 1000 integer columns, all of which are binary
glp_read_lp: 1560 lines were read
ipp_basic_tech:  0 row(s) and 0 column(s) removed
ipp_reduce_bnds: 1 pass(es) made, 0 bound(s) reduced
ipp_basic_tech:  0 row(s) and 0 column(s) removed
ipp_reduce_coef: 1 pass(es) made, 0 coefficient(s) reduced
lpx_intopt: presolved MIP has 205 rows, 1000 columns, 2000 non-zeros
lpx_intopt: 1000 integer columns, all of which are binary
lpx_adv_basis: size of triangular part = 205
Solving LP relaxation...
*     0:   objval =   0.000000000e+00   infeas =   0.000000000e+00 (0)
*   200:   objval =   2.752104823e+02   infeas =   3.774758284e-15 (0)
*   400:   objval =   3.089689084e+02   infeas =   5.784345645e-15 (0)
*   473:   objval =   3.107554039e+02   infeas =   2.321403252e-16 (0)
OPTIMAL SOLUTION FOUND
Generating cutting planes...
&   473: obj =   3.107554039e+02   frac =     8   cuts =     0 (0)
&   473: obj =   3.107554039e+02   frac =     8   cuts =     0 (0)
Integer optimization begins...
+   473: mip =     not found yet <=              +inf        (1; 0)
MIR cuts enabled
+   825: mip =     not found yet <=   3.107504751e+02        (342; 0)
+  1242: mip =     not found yet <=   3.107504751e+02        (696; 0)
+  1268: >>>>>   3.057711647e+02 <=   3.107504751e+02   1.6% (716; 0)
+  1801: mip =   3.057711647e+02 <=   3.107504751e+02   1.6% (1076; 1)
+  2212: >>>>>   3.067672398e+02 <=   3.107504751e+02   1.3% (1409; 1)
+  2582: mip =   3.067672398e+02 <=   3.107504751e+02   1.3% (1542; 168)
+  2641: >>>>>   3.091187582e+02 <=   3.107504751e+02   0.5% (1578; 168)
+  3278: mip =   3.091187582e+02 <=   3.107504751e+02   0.5% (1820; 335)
+  3810: mip =   3.091187582e+02 <=   3.107504751e+02   0.5% (2051; 337)
+  3848: >>>>>   3.096069213e+02 <=   3.107504751e+02   0.4% (2079; 337)
+  4571: mip =   3.096069213e+02 <=   3.107504751e+02   0.4% (2107; 847)
+  5224: mip =   3.096069213e+02 <=   3.107504751e+02   0.4% (2290; 853)
+  5796: mip =   3.096069213e+02 <=   3.107504751e+02   0.4% (2451; 856)
+  6191: mip =   3.096069213e+02 <=   3.107504751e+02   0.4% (2514; 857)
+  6201: >>>>>   3.097143841e+02 <=   3.107504751e+02   0.3% (2522; 857)
. . . . . . .
+ 71288: >>>>>   3.105658536e+02 <=   3.106467919e+02 < 0.1% (83; 22464)
+ 71562: mip =   3.105658536e+02 <=   3.106467919e+02 < 0.1% (47; 22595)
+ 71825: mip =   3.105658536e+02 <=   3.106467919e+02 < 0.1% (25; 22658)
+ 72197: mip =   3.105658536e+02 <=   3.106467919e+02 < 0.1% (20; 22723)
+ 72315: >>>>>   3.105671007e+02 <=   3.106467919e+02 < 0.1% (17; 22739)
+ 72644: mip =   3.105671007e+02 <=   3.106467919e+02 < 0.1% (24; 22782)
+ 72805: mip =   3.105671007e+02 <=   3.106467919e+02 < 0.1% (17; 22833)
+ 72989: mip =   3.105671007e+02 <=     tree is empty   0.0% (0; 22911)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   1132.5 secs
Memory used: 28.5 Mb (29878045 bytes)