> 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: "[email protected]"
> > 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!
http://search.live.com/cashback/?&pkw=form=MIJAAF/publ=HMTGL/crea=earncashback_______________________________________________
Help-glpk mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/help-glpk
