[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] Binary Problem
From: |
Andrew Makhorin |
Subject: |
Re: [Help-glpk] Binary Problem |
Date: |
Thu, 24 Apr 2008 22:29:18 +0400 |
> 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)