[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] Understanding the LPX_K_TOLOBJ parameter
From: |
Andrew Makhorin |
Subject: |
Re: [Help-glpk] Understanding the LPX_K_TOLOBJ parameter |
Date: |
Sat, 23 Feb 2008 16:25:08 +0300 |
> I have a binary integer program I'm solving with GLPK. I've
> noticed excessive Branch Bound time, so thought I would play with the
> tolerance for accepting an integer solution. In CPLEX, I'd set the
> mipgap value appropriately. After reading through the GLPK manual, I
> think the parameter that is equivalent is the LPX_K_TOLOBJ. Am I
> correct? My C code looks something like this (with lots of stuff left
> out):
> bip = lpx_read_model(argv[INDEX_MODL], argv[INDEX_DATA], NULL);
> lpx_set_real_parm(bip, LPX_TOLOBJ, 0.005); /* 0.5% mipgap */
> If this is wrong please let me know. For most of my data sets, the
> solution to the relaxation is integer, so this doesn't get exercised
> too much. But, I think something is wrong because the tail from a run
> on one of my datasets (that is currently still running) looks like
> this:
> +293011: mip = 4.200000000e+02 >= 4.183237456e+02 0.4% (176; 789)
> Time used: 38906.0 secs. Memory used: 257.4 Mb.
> +293163: mip = 4.200000000e+02 >= 4.183237456e+02 0.4% (177; 789)
> Time used: 38977.0 secs. Memory used: 257.5 Mb.
> +293273: mip = 4.200000000e+02 >= 4.183237456e+02 0.4% (178; 789)
> Time used: 39047.0 secs. Memory used: 257.5 Mb.
> |293568: objval = 4.194444443e+02 infeas = 4.340972026e-14 (37417)
> +293568: mip = 4.200000000e+02 >= 4.183237456e+02 0.4% (178; 790)
> Time used: 39143.0 secs. Memory used: 257.5 Mb.
> So, I was hoping that it would take the "420" solution and bail
> since the gap is less than 0.5%. Please help me understand what I am
> missing. I can provide more info if helpful.
Do not change tol_obj. Set the relative mip gap, say, to 0.01 (that
means 1%) to prematurely stop the search. In this case you obtain
a suboptimal solution. Besides, you can try enabling cutting planes;
sometimes this helps to reduce the solution time.