[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Bug-glpk] mark binary using 'glpk_set_col_kind' and 'GLP_BV'
From: |
Andrew Makhorin |
Subject: |
Re: [Bug-glpk] mark binary using 'glpk_set_col_kind' and 'GLP_BV' |
Date: |
Tue, 22 Dec 2009 00:34:12 +0300 |
> I have encountered difficulties solving some of my
> mixed-0-1 problems and I want to rule out the
> possibility that GLPK is the cause.
> Indeed I wonder if the following API call to mark
> column 5 (for the sake of argument) as a binary
> variable is implemented correctly:
> glpk_set_col_kind(pMip, 5, GLP_BV)
> The reason I ask is that a hand-checkable and
> apparently perfectly good MIP problem with one binary
> variable yields 'GLP_NOFEAS' when solved using the
> 'glp_simplex' and 'glp_intopt' calls in that order and
> with the GLPK default presolver setting (disabled):
> 0: obj = 0.000000000e+00 infeas = 3.000e+07 (10)
> * 11: obj = 9.600000000e-01 infeas = 0.000e+00 (0)
> OPTIMAL SOLUTION FOUND
> Integer optimization begins...
> + 11: mip = not found yet >= -inf (1; 0)
> + 11: mip = not found yet >= tree is empty (0; 1)
> PROBLEM HAS NO INTEGER FEASIBLE SOLUTION
> The printed solution using 'glp_print_mip' is (with row
> and col information removed for brevity):
> Problem: pro-151314.dc-1
> Rows: 16
> Columns: 11 (1 integer, 1 binary)
> Non-zeros: 26
> Status: INTEGER EMPTY
> Objective: obj.tsolve-nodal = 0 (MINimum)
> [snip - row and col information]
> Integer feasibility conditions:
> KKT.PE: max.abs.err = 0.00e+00 on row 0
> max.rel.err = 0.00e+00 on row 0
> High quality
> KKT.PB: max.abs.err = 3.00e+07 on row 2
> max.rel.err = 1.00e-00 on row 2
> SOLUTION IS INFEASIBLE
> However exporting the GLPK problem instance to CPLEX LP
> format using:
> glp_write_lp(pMip, NULL, "pro-105007.dc-1")
> and then invoking 'glpsol' works fine:
> $ glpsol --cpxlp pro-105007.dc-1.prob
> GLPSOL: GLPK LP/MIP Solver 4.40
> Parameter(s) specified in the command line:
> --cpxlp pro-105007.dc-1.prob
> Reading problem data from `pro-105007.dc-1.prob'...
> 16 rows, 11 columns, 26 non-zeros
> One variable is binary
> 54 lines were read
> ipp_basic_tech: 16 row(s) and 11 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
> Objective value = 0.96
> INTEGER OPTIMAL SOLUTION FOUND BY MIP PRESOLVER
> Time used: 0.0 secs
> Memory used: 0.0 Mb (43468 bytes)
> Moreover, disabling the presolver also works:
> $ glpsol --cpxlp --nointopt pro-105007.dc-1.prob
> Alternatively, my calling code could very well be the
> cause of this problem. Most of this code dates from
> GLPK 4.17. And although I have progressively migrated
> to the new APIs as these are released, I could easily
> have introduced a bug in the calling logic.
> I have not implemented this example as a stand-alone
> C/C++ program, but can easily do so if this might help.
> Any comments much appreciated.
Thank you for the bug report.
It is a scaling issue. Running your instance with options
'--nointopt --noscale' shows that.
The error happens due to constraint:
con07.teas~oxid~to~elec~1.hi~bound:
+ var07.teas~oxid~to~elec~1.block~io~out
- 100000000 vab05.teas~oxid~to~elec~1.trip~if~zero <= 0
where big M is too big; it is reduced by the mip presolver, so
the error does not appear.