> 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. _______________________________________________ Bug-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/bug-glpk
