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

[Robbie Morrison]

Hello GLPK API users

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.

best wishes to all
Robbie
---

The CPLEX problem formulation follows.  I guess the
"Generals" designation (rather than "Binary") is
correct for the sole binary variable.

By way of background, this (sub)problem represents an
HTC biocoal-fired electricity generating unit (of 50MW)
which trips below a certain output (zero in this case)
and is subject to nodal pricing (the bid is 0.032
$/MJ), duly supplying a price-inelastic load (of 30MW).
The object-oriented simulation program from which this
GLPK problem instance derives is named 'xeona'.

--- cplex starts ---

\* Problem: pro-105007.dc-1 *\

Minimize
 obj.tsolve~nodal:
 + 3.2e-08 var09.asop~lmp~2.lmp~stated~ts1.bid~01

Subject To
 con01.teas~load~elec~ts~1.factor~bal:
 + var02.teas~load~elec~ts~1.sink~in
 - var01.teas~load~elec~ts~1.factor = 0
 con02.teas~load~elec~ts~1.fixed~bound:
 + var02.teas~load~elec~ts~1.sink~in = 30000000
 con03.teas~oxid~to~elec~1.factor~bal:
 - var06.teas~oxid~to~elec~1.block~io~in
 + var03.teas~oxid~to~elec~1.factor = 0
 con04.teas~oxid~to~elec~1.output~bal:
 + var07.teas~oxid~to~elec~1.block~io~out
 - var04.teas~oxid~to~elec~1.output = 0
 con05.teas~oxid~to~elec~1.efficiency:
 - 0.0925925925925926 var07.teas~oxid~to~elec~1.block~io~out
 + var06.teas~oxid~to~elec~1.block~io~in = 0
 con06.teas~oxid~to~elec~1.lo~bound:
 + var07.teas~oxid~to~elec~1.block~io~out >= 0
 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
 con08.iface~bal:
 - var04.teas~oxid~to~elec~1.output
 + var01.teas~load~elec~ts~1.factor = 0
 con09.asop~lmp~2.lmp~stated~ts1.bidset~bal:
 + var09.asop~lmp~2.lmp~stated~ts1.bid~01
 - var08.asop~lmp~2.lmp~stated~ts1.bidset = 0
 con10.asop~lmp~2.lmp~stated~ts1.bid~01.lo~band:
 + var09.asop~lmp~2.lmp~stated~ts1.bid~01 >= 0
 con11.asop~lmp~2.lmp~stated~ts1.bid~01.hi~band:
 + var09.asop~lmp~2.lmp~stated~ts1.bid~01 <= 80000000
 con12.asop~lmp~2.couple.osp~coupling:
 - var08.asop~lmp~2.lmp~stated~ts1.bidset
 + var04.teas~oxid~to~elec~1.output = 0
 con13.teas~source~biocoal~1.output~bal:
 + var11.teas~source~biocoal~1.source~out
 - var10.teas~source~biocoal~1.output = 0
 con14.teas~source~biocoal~1.lo~bound:
 + var11.teas~source~biocoal~1.source~out >= 0
 con15.teas~source~biocoal~1.hi~bound:
 + var11.teas~source~biocoal~1.source~out <= 5000000
 con16.iface~bal: - var10.teas~source~biocoal~1.output
 + var03.teas~oxid~to~elec~1.factor = 0

Bounds
 0 <= vab05.teas~oxid~to~elec~1.trip~if~zero <= 1

Generals
 vab05.teas~oxid~to~elec~1.trip~if~zero

End

--- cplex ends ---

---
Robbie Morrison
PhD student -- policy-oriented energy system simulation
Institute for Energy Engineering (IET)
Technical University of Berlin (TU-Berlin), Germany
University email (redirected) : address@hidden
Webmail (preferred)           : address@hidden
[from IMAP client]