[Bug-glpk] MIP presolver solves and KKT routine rejects

[Robbie Morrison]

Hello all

I don't know if this problem classifies as a bug --
perhaps not.  But in this case, the MIP presolver finds
a solution (it seems to), and the KKT routine later
rejects it.  The solver also fails completely if the
MIP presolver option is omitted.

The problem itself was created in my application
program, but the version here has been exported as a
.glpk for further testing.  That file is pasted in
below.

Very similar problems (from different time-steps) work
as expected.  But these are not identical (the wind may
have changed, for instance).

Please note that 'xglpsol' (shown below) is a bash
script that pumps out GLPSOL command-lines and
generally simplifies matters when experimenting.

The other thing that is puzzling is the 2N scaling.
My application program explicitly omits 2N scaling but
the MIP solver seems to sneak it back in to give a
worse condition metric -- which also occurs here.

Any help would be appreciated, TIA, Robbie

---

$ xglpsol -aw 008090-0010-pro-00010.dc-1.glpk

  time    : CEST +0200 Fri 06-May-2011 14:49:04
  cline   : xglpsol -aw 008090-0010-pro-00010.dc-1.glpk
  model   : 008090-0010-pro-00010.dc-1.glpk
  lines   : 100
  call    : 'glpsol --scale --presol --intopt --output /dev/stdout --glp
008090-0010-pro-00010.dc-1.glpk'

GLPSOL: GLPK LP/MIP Solver, v4.45
Parameter(s) specified in the command line:
 --scale --presol --intopt --output /dev/stdout --glp
008090-0010-pro-00010.dc-1.glpk
Reading problem data from `008090-0010-pro-00010.dc-1.glpk'...
Problem: pro-00010.dc-1
Objective: obj.tsolve-srfin
20 rows, 14 columns, 35 non-zeros
One variable is binary
100 lines were read
GLPK Integer Optimizer, v4.45
20 rows, 14 columns, 35 non-zeros
1 integer variable,  which is binary
Preprocessing...
1 constraint coefficient(s) were reduced
3 rows, 2 columns, 6 non-zeros
1 integer variable,  which is binary
Scaling...
 A: min|aij| =  1.852e-04  max|aij| =  1.000e+00  ratio =  5.400e+03
GM: min|aij| =  4.729e-01  max|aij| =  2.115e+00  ratio =  4.472e+00
EQ: min|aij| =  2.236e-01  max|aij| =  1.000e+00  ratio =  4.472e+00
2N: min|aij| =  1.896e-01  max|aij| =  1.024e+00  ratio =  5.400e+00
Constructing initial basis...
Size of triangular part = 3
Solving LP relaxation...
GLPK Simplex Optimizer, v4.45
3 rows, 2 columns, 6 non-zeros
*     0: obj =   7.640012020e+08  infeas =  0.000e+00 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+     0: mip =     not found yet >=              -inf        (1; 0)
+     0: >>>>>   7.640012020e+08 >=   7.640012020e+08   0.0% (1; 0)
+     0: mip =   7.640012020e+08 >=     tree is empty   0.0% (0; 1)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   0.0 secs
Memory used: 0.1 Mb (62840 bytes)
Writing MIP solution to `/dev/stdout'...
Problem:    pro-00010.dc-1
Rows:       20
Columns:    14 (1 integer, 1 binary)
Non-zeros:  35
Status:     INTEGER OPTIMAL
Objective:  obj.tsolve-srfin = 764001202 (MINimum)

   No.   Row name        Activity     Lower bound   Upper bound
------ ------------    ------------- ------------- -------------
     1 con01.teas-windfarm-1.output-bal
                                   0             0             =
     2 con02.teas-windfarm-1.lo-bound
                               40000             0
     3 con03.teas-windfarm-1.hi-bound
                               40000                     35702.8
     4 con04.teas-source-oxid-1.output-bal
                                   0             0             =
     5 con05.teas-source-oxid-1.lo-bound
                         9.25926e-05             0
     6 con06.teas-source-oxid-1.hi-bound
                         9.25926e-05                        0.01
     7 con07.teas-oxid-to-elec-1.factor-bal
                                   0             0             =
     8 con08.teas-oxid-to-elec-1.output-bal
                                   0             0             =
     9 con09.teas-oxid-to-elec-1.scaled-efficiency
                         9.25926e-05   9.25926e-05             =
    10 con10.teas-oxid-to-elec-1.lo-bound
                                   0             0
    11 con11.teas-oxid-to-elec-1.hi-bound
                                   0                           0
    12 con12.teas-oxid-to-elec-1.lo-ramp-restraint
                                   0         -0.06
    13 con13.teas-oxid-to-elec-1.hi-ramp-restraint
                                   0                        0.06
    14 con14.iface-bal
                                   0             0             =
    15 con15.teas-load-elec-ts-1.factor-bal
                                   0             0             =
    16 con16.teas-load-elec-ts-1.fixed-bound
                               40000         40000             =
    17 con17.junc-demand-2-split-elec-1.junction-bal
                                   0             0             =
    18 con18.iface-bal
                                   0             0             =
    19 con19.iface-bal
                                   0             0             =
    20 con20.iface-bal
                                   0             0             =

   No. Column name       Activity     Lower bound   Upper bound
------ ------------    ------------- ------------- -------------
     1 var01.teas-windfarm-1.output
                               40000             0
     2 var02.teas-windfarm-1.source-out
                               40000             0
     3 var03.teas-source-oxid-1.output
                         9.25926e-05             0
     4 var04.teas-source-oxid-1.source-out
                         9.25926e-05             0
     5 var05.teas-oxid-to-elec-1.factor
                         9.25926e-05             0
     6 var06.teas-oxid-to-elec-1.output
                                   0             0
     7 vab07.teas-oxid-to-elec-1.trip-if-zero
                    *              0             0             1
     8 var08.teas-oxid-to-elec-1.block-io-in
                         9.25926e-05             0
     9 var09.teas-oxid-to-elec-1.block-io-out
                                   0             0
    10 var10.teas-load-elec-ts-1.factor
                               40000             0
    11 var11.teas-load-elec-ts-1.sink-in
                               40000             0
    12 var12.junc-demand-2-split-elec-1.socket
                               40000             0
    13 var13.junc-demand-2-split-elec-1.cable-1
                                   0             0
    14 var14.junc-demand-2-split-elec-1.cable-2
                               40000             0

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 = 4.30e+03 on row 3
        max.rel.err = 1.20e-01 on row 3
        SOLUTION IS INFEASIBLE

End of output

  return  : 0
  elapsed : 0

-----------------------------------------

p mip min 20 14 35
n p pro-00010.dc-1
n z obj.tsolve-srfin
n i 1 con01.teas-windfarm-1.output-bal
i 2 l 0
n i 2 con02.teas-windfarm-1.lo-bound
i 3 u 35702.8395230523
n i 3 con03.teas-windfarm-1.hi-bound
n i 4 con04.teas-source-oxid-1.output-bal
i 5 l 0
n i 5 con05.teas-source-oxid-1.lo-bound
i 6 u 0.01
n i 6 con06.teas-source-oxid-1.hi-bound
n i 7 con07.teas-oxid-to-elec-1.factor-bal
n i 8 con08.teas-oxid-to-elec-1.output-bal
i 9 s 9.25925925925926e-05
n i 9 con09.teas-oxid-to-elec-1.scaled-efficiency
i 10 l 0
n i 10 con10.teas-oxid-to-elec-1.lo-bound
i 11 u 0
n i 11 con11.teas-oxid-to-elec-1.hi-bound
i 12 l -0.06
n i 12 con12.teas-oxid-to-elec-1.lo-ramp-restraint
i 13 u 0.06
n i 13 con13.teas-oxid-to-elec-1.hi-ramp-restraint
n i 14 con14.iface-bal
n i 15 con15.teas-load-elec-ts-1.factor-bal
i 16 s 40000
n i 16 con16.teas-load-elec-ts-1.fixed-bound
n i 17 con17.junc-demand-2-split-elec-1.junction-bal
n i 18 con18.iface-bal
n i 19 con19.iface-bal
n i 20 con20.iface-bal
j 1 c l 0
n j 1 var01.teas-windfarm-1.output
j 2 c l 0
n j 2 var02.teas-windfarm-1.source-out
j 3 c l 0
n j 3 var03.teas-source-oxid-1.output
j 4 c l 0
n j 4 var04.teas-source-oxid-1.source-out
j 5 c l 0
n j 5 var05.teas-oxid-to-elec-1.factor
j 6 c l 0
n j 6 var06.teas-oxid-to-elec-1.output
n j 7 vab07.teas-oxid-to-elec-1.trip-if-zero
j 8 c l 0
n j 8 var08.teas-oxid-to-elec-1.block-io-in
j 9 c l 0
n j 9 var09.teas-oxid-to-elec-1.block-io-out
j 10 c l 0
n j 10 var10.teas-load-elec-ts-1.factor
j 11 c l 0
n j 11 var11.teas-load-elec-ts-1.sink-in
j 12 c l 0
n j 12 var12.junc-demand-2-split-elec-1.socket
j 13 c l 0
n j 13 var13.junc-demand-2-split-elec-1.cable-1
j 14 c l 0
n j 14 var14.junc-demand-2-split-elec-1.cable-2
a 0 0 760001202.005
a 0 3 100
a 0 5 100
a 0 10 100
a 1 2 1
a 1 1 -1
a 2 2 1
a 3 2 1
a 4 4 1
a 4 3 -1
a 5 4 1
a 6 4 1
a 7 8 -1
a 7 5 1
a 8 9 10000000
a 8 6 -1
a 9 7 -0.000185185185185185
a 9 9 -0.925925925925926
a 9 8 1
a 10 9 1
a 10 7 -0.001
a 11 9 1
a 11 7 -0.02
a 12 9 1
a 13 9 1
a 14 5 -1
a 14 3 1
a 15 11 1
a 15 10 -1
a 16 11 1
a 17 14 -1
a 17 13 -1
a 17 12 1
a 18 13 -1
a 18 6 1
a 19 14 -1
a 19 1 1
a 20 12 -1
a 20 10 1
e o f

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