Re: [Bug-glpk] mark binary using 'glpk_set_col_kind' and 'GLP_BV'

[Andrew Makhorin]

> 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.