|
| From: | Joey Rios |
| Subject: | RE: [Help-glpk] Getting more info from presolver |
| Date: | Wed, 18 Jun 2008 17:24:30 -0700 |
|
> 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. > That would be more valuable, but it would take a larger coding effort since currently, the presolver kicks out after the first cause for infeasibility. I just capture the index of the row/column that is causing the infeasibility before that return. I store that index in a new data member of the LPP struct so it is available to the simplex2 function upon return from lpp_presolve. So, I touched three files: glpapi06.c, glplpp02.c, glplpp.h. I don't know how attachments work on the message board, so I'll just include the 3 patch files in the body below. I haven't tested these patches beyond seeing that they provided the clue I needed to do my work. I don't think the changes will affect much else since they mostly consist of print statements and saving an otherwise untouched variable in an established struct. If anyone has a quick way to exercise these, I'd feel better knowing they work. Joey --- glpk-dev-4.23/include/glplpp.h 2008-02-11 18:00:32.000000000 -0800 +++ glpk-4.23/include/glplpp.h 2008-06-18 11:16:20.000000000 -0700 @@ -135,6 +135,9 @@ double *col_dual; /* double col_dual[1+ncols]; */ /* col_dual[0] is not used; col_dual[j] is a dual value of j-th structural variable */ + int bad_apple; + /* the index of a "bad" column/row from the original problem + causing dual/primal infeasibilty */ }; struct LPPROW --- glpk-dev-4.23/src/glpapi06.c 2008-02-11 18:00:31.000000000 -0800 +++ glpk-4.23/src/glpapi06.c 2008-06-18 16:49:16.000000000 -0700 @@ -520,6 +520,7 @@ glp_prob *prob; glp_bfcp bfcp; int orig_m, orig_n, orig_nnz, ret; + char* str = (char*) malloc(sizeof(char)*100); orig_m = glp_get_num_rows(orig); orig_n = glp_get_num_cols(orig); orig_nnz = glp_get_num_nz(orig); @@ -544,14 +545,18 @@ break; case 1: /* the original problem is primal infeasible */ - if (parm->msg_lev >= GLP_MSG_ALL) + if (parm->msg_lev >= GLP_MSG_ALL) { xprintf("PROBLEM HAS NO PRIMAL FEASIBLE SOLUTION\n"); + xprintf("The problem row was %d, %s.\n", lpp->bad_apple, glp_get_row_name(orig, lpp->bad_apple)); + } lpp_delete_wksp(lpp); return GLP_ENOPFS; case 2: /* the original problem is dual infeasible */ - if (parm->msg_lev >= GLP_MSG_ALL) + if (parm->msg_lev >= GLP_MSG_ALL) { xprintf("PROBLEM HAS NO DUAL FEASIBLE SOLUTION\n"); + xprintf("The problem column was %d, %s.\n", lpp->bad_apple, glp_get_col_name(orig, lpp->bad_apple)); + } lpp_delete_wksp(lpp); return GLP_ENODFS; default: --- glpk-dev-4.23/src/glplpp02.c 2008-02-11 18:00:32.000000000 -0800 +++ glpk-4.23/src/glplpp02.c 2008-06-18 16:51:15.000000000 -0700 @@ -1601,7 +1601,11 @@ /* process the row */ if (row->ptr == NULL) { /* remove empty row */ - if (process_empty_row(lpp, row)) return 1; + if (process_empty_row(lpp, row)) { + xprintf("Empty Row. Row %d.\n", row->i); + lpp->bad_apple = row->i; + return 1; + } } else if (row->lb == -DBL_MAX && row->ub == +DBL_MAX) { /* remove free row */ @@ -1610,16 +1614,28 @@ else if (row->ptr != NULL && row->ptr->r_next == NULL && row->lb == row->ub) { /* remove row singleton (equality constraint) */ - if (process_row_sngton1(lpp, row)) return 1; + if (process_row_sngton1(lpp, row)) { + xprintf("Row Singleton, equality constraint. Row %d.\n", row->i); + lpp->bad_apple = row->i; + return 1; + } } else if (row->ptr != NULL && row->ptr->r_next == NULL && row->lb != row->ub) { /* remove row singleton (inequality constraint) */ - if (process_row_sngton2(lpp, row)) return 1; + if (process_row_sngton2(lpp, row)) { + xprintf("Row Singleton, inequality constraint. Row %d.\n", row->i); + lpp->bad_apple = row->i; + return 1; + } } else { /* general row analysis */ - if (analyze_row(lpp, row)) return 1; + if (analyze_row(lpp, row)) { + xprintf("General Row Analysis. Row %d.\n", row->i); + lpp->bad_apple = row->i; + return 1; + } } } /* process active columns */ @@ -1631,7 +1647,11 @@ /* process the column */ if (col->ptr == NULL) { /* remove empty column */ - if (process_empty_col(lpp, col)) return 2; + if (process_empty_col(lpp, col)) { + xprintf("Empty column. Col %d.\n", col->j); + lpp->bad_apple = col->j; + return 2; + } } else if (col->lb == col->ub) { /* remove fixed column */ @@ -1645,7 +1665,11 @@ else if (col->ptr != NULL && col->ptr->c_next == NULL && col->ptr->row->lb != col->ptr->row->ub) { /* remove column singleton (implied free variable) */ - if (process_col_sngton2(lpp, col)) return 2; + if (process_col_sngton2(lpp, col)) { + xprintf("Col Singleton, inequality constraint. Col %d.\n", col->j); + lpp->bad_apple = col->j; + return 2; + } } else { /* general column analysis */ > 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 Earn cashback on your purchases with Live Search - the search that pays you back! Learn More |
| [Prev in Thread] | Current Thread | [Next in Thread] |