[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Re: octave-glpk MIPGAP
From: |
Marcelo Pinto |
Subject: |
Re: Re: octave-glpk MIPGAP |
Date: |
Tue, 5 Apr 2011 22:58:59 -0300 |
Hi Tommaso,
The diff output that posted some days ago, does exactly that. Here it is again:
73c73
< #define NRealP 10
---
> #define NRealP 11
126c126,127
< 1e-7
---
> 1e-7,
> 1e-4
139c140,141
< LPX_K_TOLOBJ
---
> LPX_K_TOLOBJ,
> LPX_K_MIPGAP
341c343
< if (errnum == LPX_E_OK)
---
> if (errnum == LPX_E_OK || errnum == LPX_E_MIPGAP)
812a815,816
>
> OCTAVE_GLPK_GET_REAL_PARAM ("mipgap", 10);
With this patch applied to the current version of __glpk__.cc, the
values of fmin, xmin, status and extra returns normally, when the
optimization reach 0.1% from the optimal LP solution. Here is the
output to param.msglev = 3; and param.mipgap = 0.1/100;, with this
patch:
GLPK Simplex Optimizer, v4.43
99 rows, 288 columns, 5280 non-zeros
Preprocessing...
99 rows, 288 columns, 5280 non-zeros
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 = 99
0: obj = 0.000000000e+00 infeas = 4.266e+03 (0)
* 107: obj = 1.897850000e+05 infeas = 0.000e+00 (0)
* 127: obj = 1.825400000e+05 infeas = 0.000e+00 (0)
OPTIMAL SOLUTION FOUND
GLPK Integer Optimizer, v4.43
99 rows, 288 columns, 5280 non-zeros
288 integer variables, none of which are binary
Integer optimization begins...
+ 127: mip = not found yet >= -inf (1; 0)
+ 317: >>>>> 1.826200000e+05 >= 1.825400000e+05 < 0.1% (51; 0)
+ 317: mip = 1.826200000e+05 >= 1.825400000e+05 < 0.1% (45; 10)
RELATIVE MIP GAP TOLERANCE REACHED; SEARCH TERMINATED
Now, here is the output to the same script (param.mipgap = 0.1/100),
with your patch applied to the current __glpk__.cc:
GLPK Integer Optimizer, v4.43
99 rows, 288 columns, 5280 non-zeros
288 integer variables, none of which are binary
Preprocessing...
99 rows, 288 columns, 5280 non-zeros
288 integer variables, none 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 = 99
Solving LP relaxation...
GLPK Simplex Optimizer, v4.43
99 rows, 288 columns, 5280 non-zeros
0: obj = 0.000000000e+00 infeas = 4.266e+03 (0)
* 107: obj = 1.897850000e+05 infeas = 0.000e+00 (0)
* 127: obj = 1.825400000e+05 infeas = 0.000e+00 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+ 127: mip = not found yet >= -inf (1; 0)
+ 698: >>>>> 1.834800000e+05 >= 1.825400000e+05 0.5% (97; 0)
+ 840: >>>>> 1.828800000e+05 >= 1.825400000e+05 0.2% (114; 15)
+ 852: >>>>> 1.827600000e+05 >= 1.825400000e+05 0.1% (89; 63)
+ 5724: mip = 1.827600000e+05 >= 1.825400000e+05 0.1% (735; 260)
+ 10490: mip = 1.827600000e+05 >= 1.825400000e+05 0.1% (1342; 446)
+ 15153: mip = 1.827600000e+05 >= 1.825400000e+05 0.1% (1941; 626)
As you can see, in this case, when the solution is 0.1% from the
optimal LP solution , the optimization continues running indefinitely,
like the current version.
Note: The solution (fmin = 1.827600000e+05) with my patch matches the
LINDO solution.
Regards,
Marcelo.
On Mon, Apr 4, 2011 at 4:46 PM, <address@hidden> wrote:
> On Apr 4, 2011 7:36pm, Marcelo Pinto <address@hidden> wrote:
>> I applied the patch and could see that it really has much more
>> features. However, when I ran a script that I know that the best
>> solution is 0.1% away from the optimal solution, the optimization
>> doesn't stop, even configuring 'param.mipgap = 0.1/100'.
>
> One additional remark. Don't panic when you'll see that the patch you posted
> cannot produce solutions that make sense when the gap is reached. This is
> due to the fact that you didn't update the errnum check to include a reached
> gap. In other words, in your patch if the gap is reached, xmin is never
> retrieved and therefore it is always [NA,...,NA]. Fix that and go through 2)
> and 3) again. Of course make sure you don't have random matrices/vectors in
> your script, otherwise you won't get much insight by using CPLEX or Gurobi.
>
> Regards,
>
> Tommaso
- Re: octave-glpk MIPGAP, (continued)
- Re: octave-glpk MIPGAP, Jordi GutiƩrrez Hermoso, 2011/04/02
- Re: octave-glpk MIPGAP, Jordi GutiƩrrez Hermoso, 2011/04/02
- Re: Re: octave-glpk MIPGAP, tommaso . balercia, 2011/04/02
- Re: Re: octave-glpk MIPGAP, Marcelo Pinto, 2011/04/02
- Re: Re: octave-glpk MIPGAP, Martin Helm, 2011/04/02
- Re: Re: octave-glpk MIPGAP, tommaso . balercia, 2011/04/03
- Message not available
- Re: octave-glpk MIPGAP, Marcelo Pinto, 2011/04/04
- Re: octave-glpk MIPGAP, Marcelo Pinto, 2011/04/04
- Re: Re: octave-glpk MIPGAP, tommaso . balercia, 2011/04/04
- Re: Re: octave-glpk MIPGAP, tommaso . balercia, 2011/04/04
- Re: Re: octave-glpk MIPGAP,
Marcelo Pinto <=
Re: Re: Re: octave-glpk MIPGAP, tommaso . balercia, 2011/04/03
Re: Re: Re: octave-glpk MIPGAP, tommaso . balercia, 2011/04/06
Re: Re: Re: Re: octave-glpk MIPGAP, tommaso . balercia, 2011/04/06