Re: RE: [Help-glpk] Getting more info from presolver

[glpk xypron]

Hello Joey,

I have tested the suggestion concerning glpsol -o for a trivial example with 
glpk-4.28:

var x;
var y;
minimize obj : x + y;
s.t. c0 : x + 3 * y >= 0;
s.t. c4 : y <= 10;
s.t. c1 : x + 4 <= 0;
s.t. c2 : x + 3 >= 0;

A line "KKT.PB" was not issued. The output file gave me no clue which 
inequalities (c1, c2) render the problem solution infeasible:

Problem:    test
Rows:       5
Columns:    2
Non-zeros:  7
Status:     UNDEFINED
Objective:  obj = 0 (MINimum)

   No.   Row name   St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 obj          B              0
     2 c0           B              0            -0
     3 c4           B              0                          10
     4 c1           B              0                          -4
     5 c2           B              0            -3

   No. Column name  St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 x            NF             0                                     < eps
     2 y            NF             0                                     < eps

I agree providing one of the (in)equalities leading to infeasibility would be a 
nice feature to see in GLPK. It is the same kind of information to be ssen in 
commercial solvers.

Obviously the indicated inequality in your output is only one of the 
inequalities that constitutes the infeasibility. The improvement you suggest 
would be even more valuable if all inequalities involved in the infeasibility 
would be listed.

Could you, please, mail your coding suggestion to the mail list.

Best regards

Xypron

-------- Original-Nachricht --------
> Datum: Wed, 18 Jun 2008 11:29:38 -0700
> Von: Joey Rios
> An: "address@hidden"
> Betreff: RE: [Help-glpk] Getting more info from presolver

> > You may look at the output listing produced by either glpsol (with
> > -o option) or the api routine lpx_print_sol. 
> 
> It was actually more economical for me to go to the source code on this. 
> In the time it would take glpsol to provide the KKT info (several hours), I
> threw some lines into glpk and got the info I needed.  Of course, I have
> no idea if what I added will break other things or will work for all cases,
> it just gave me what I needed.  For completeness of this discussion thread,
> here is the message I was receiving originally:
> 
> lpx_read_cpxlp: reading problem data from `dw_monolithic.cplex'...
> lpx_read_cpxlp: 440350 rows, 299500 columns, 969398 non-zeros
> lpx_read_cpxlp: 299500 integer columns, all of which are binary
> lpx_read_cpxlp: 1089422 lines were read
> glp_simplex: original LP has 440350 rows, 299500 columns, 969398 non-zeros
> PROBLEM HAS NO PRIMAL FEASIBLE SOLUTION
> glp_intopt: optimal basis to initial LP relaxation not provided
> Time used:   1.0 secs
> Memory used: 211.3 Mb (221541952 bytes)
> 
> 
> And with less than 10-20 lines of additional code I could get this:
> 
> 
> lpx_read_cpxlp: reading problem data from `dw_monolithic.cplex'...
> lpx_read_cpxlp: 440350 rows, 299500 columns, 969398 non-zeros
> lpx_read_cpxlp: 299500 integer columns, all of which are binary
> lpx_read_cpxlp: 1089422 lines were read
> glp_simplex: original LP has 440350 rows, 299500 columns, 969398 non-zeros
> General Row Analysis.  Row 437495.
> PROBLEM HAS NO PRIMAL FEASIBLE SOLUTION
> The problem row was 437495, DepartCap(CLE,2).
> glp_intopt: optimal basis to initial LP relaxation not provided
> Time used:   0.0 secs
> Memory used: 211.3 Mb (221541956 bytes)
> 
> 
> This is going to help me debug my code for generating my input file to
> glpsol.  I'd be happy to send you my changes, Andrew, if you thought it would
> be helpful.  They seem very minor, but again, I can't say I've considered
> every implication of their inclusion.
> 
> Joey
> 
> _________________________________________________________________
> The other season of giving begins 6/24/08. Check out the i’m Talkathon.
> http://www.imtalkathon.com?source=TXT_EML_WLH_SeasonOfGiving

-- 
Der GMX SmartSurfer hilft bis zu 70% Ihrer Onlinekosten zu sparen! 
Ideal für Modem und ISDN: http://www.gmx.net/de/go/smartsurfer