[Bug-glpk] OPB output file anomaly

[Joey Rios]

This is a follow-up from our OPB thread in the help section 
(http://lists.gnu.org/archive/html/help-glpk/2008-02/msg00105.html)...




> > So it does look like these constraints are trivially satisfied if I
> > am interpreting the output correctly.
> 
> In cplex format there is the same picture, i.e. it does not permit
> empty left-hand side, so the output routine uses a first variable
> with zero coefficient to make a fake lhs. I do not know whether opb
> format allows zero coefficients or not.
> 

I don't think I've found a definitive format for opb problems and at least two 
of them conflict on the point of zero coefficients:

http://www.cril.univ-artois.fr/PB07/solver_req.html (doesn't restrict 
coefficients)
http://www.mpi-inf.mpg.de/departments/d2/software/opbdp/README  (doesn't allow 
0-value coeffs)

The first link is the one noted by the opb documentation provided with GLPK, 
and is the basis of a large PB Solver competition, so it probably makes sense 
to follow that one.  Thus, we could add something like the cplex formatter 
does: dummy variable with zero coefficient for empty LHS.

> There should be a check for infeasible empty rows, i.e. rows like
> 0 <= -3 or 0 >= +3. If such rows are removed, the routine must issue
> at least a warning message that the original instance is infeasible.

I understand what you mean regarding infeasible rows, but I don't know enough 
about the internals of GLPK to know how those rows might end up with empty LHS. 
 Is there a field on the row data structure that would indicate infeasibility? 

One final note.  I've gotten the solution from minisat+ using the 
GLPK-generated OPB file to agree with the solution from GLPK.  The difference 
comes from the constant term in the objective function (if present).  So, 
before glpk solves the given model we get the following output:

lpx_read_model: row Delay_Costs; constant term -240720 ignored
lpx_write_pb: writing problem in OPB format to `mono.opb'...

It turns out the the difference in solution between the OPB solver and glpk is 
actually this constant.  I found this by noticing the same discrepancy when I 
generate an MPS and provide the resulting MPS file to various solvers.  The 
objective constant is not translated to the resulting OPB or MPS files.  Is 
this a feature or bug?  If it's a feature, could you explain the logic... it 
isn't clear to me why this happens.

With all of these considerations, I've made some changes to glplpx19.c which 
writes the OPB file so that now I get agreement from glpk and the PB solver 
without any manual manipulation of the OPB file.  All of the changes fit my 
needs perfectly and may or may not be appropriate for inclusion to the main 
GLPK branch.  I've included a patch below if it is useful.  For my purposes I 
leave KEEP_EMPTY_LHS_CONSTRAINTS undefined, thus not printing any constraints 
with empty LHS, but I left the option of doing a cplex-like fake LHS.

--- ../glpk-4.22/src/glplpx19.c 2007-09-19 01:00:00.000000000 -0700
+++ src/glplpx19.c      2008-03-05 10:45:01.000000000 -0800
@@ -25,6 +25,7 @@
 
 #include "glpapi.h"
 #define print xprint1
+/*#define KEEP_EMPTY_LHS_CONSTRAINTS*/
 
 /*----------------------------------------------------------------------
 -- lpx_write_pb - write problem data in (normalized) OPB format.
@@ -51,6 +52,9 @@
    FILE* fp;
    int m,n,i,j,k,o,nonfree=0, obj_dir, dbl, *ndx, row_type;
    double coeff, *val, bound;
+   int warning_flag = 0;
+   int obj_has_const_term = 0;
+   char* dummy_var = "__DUMMY_VAR";
 
    fp = xfopen(fname, "w");
 
@@ -83,6 +87,15 @@
        /* Objective function */
        obj_dir = glp_get_obj_dir(lp);
        fprintf(fp,"min: ");
+       /* Check for constant term ("shift") */
+       coeff = glp_get_obj_coef(lp,0);
+       if(coeff != 0.0) {
+          obj_has_const_term = 1;
+          if(normalized)
+                  fprintf(fp, " %d x0", (int)coeff);
+          else
+                  fprintf(fp, " %d*%s", (int)coeff, dummy_var);           
+       }
        for(i=1;i<=n;i++)
         {
           coeff = glp_get_obj_coef(lp,i);
@@ -102,6 +115,9 @@
        if(normalized)  /* Name substitution */
         {
           fprintf(fp,"* Variable name substitution:\n");
+          if(obj_has_const_term) {
+                 fprintf(fp, "* x0 = %s\n", j, dummy_var);
+          }
           for(j=1;j<=n;j++)
             {
               fprintf(fp, "* x%d = %s\n", j, glp_get_col_name(lp,j));
@@ -127,12 +143,31 @@
                   dbl=1;
                 }
               k=glp_get_mat_row(lp, j, ndx, val);
+#ifndef KEEP_EMPTY_LHS_CONSTRAINTS
+              if( k == 0) { /* If k is zero, we'd get an empty LHS */
+                 warning_flag = 1;
+                 continue;
+              }
+#endif
               for(o=1;o<=dbl;o++)
                 {
                   if(o==2)
                      {
                       row_type = GLP_LO;
-                     }
+                     }  
+#ifdef KEEP_EMPTY_LHS_CONSTRAINTS
+                  if(k == 0) { /* If k is zero, we'd get an empty LHS */
+                         warning_flag = 1;
+                         if(normalized)
+                         {
+                                 fprintf(fp, "0 x1 ");
+                         }
+                         else
+                         {
+                                 fprintf(fp, "0*%s ", 
glp_get_col_name(lp,ndx[1]));
+                         }
+                  }
+#endif
                   for(i=1;i<=k;i++)
                      {
                        if(val[i] != 0.0)
@@ -188,6 +223,9 @@
        xfree(val);
 
      }
+   if (warning_flag) {
+          print("Warning: there were some empty LHSs.");
+   }
    else
      {
        print("Problems opening file for writing: %s", fname);





Climb to the top of the charts! Play the word scramble challenge with star 
power. Play now!

This is a follow-up from our OPB thread in the help section (http://lists.gnu.org/archive/html/help-glpk/2008-02/msg00105.html)...

> > So it does look like these constraints are trivially satisfied if I
> > am interpreting the output correctly.
>
> In cplex format there is the same picture, i.e. it does not permit
> empty left-hand side, so the output routine uses a first variable
> with zero coefficient to make a fake lhs. I do not know whether opb
> format allows zero coefficients or not.
>

I don't think I've found a definitive format for opb problems and at least two of them conflict on the point of zero coefficients:

http://www.cril.univ-artois.fr/PB07/solver_req.html (doesn't restrict coefficients)
http://www.mpi-inf.mpg.de/departments/d2/software/opbdp/README  (doesn't allow 0-value coeffs)

The first link is the one noted by the opb documentation provided with GLPK, and is the basis of a large PB Solver competition, so it probably makes sense to follow that one.  Thus, we could add something like the cplex formatter does: dummy variable with zero coefficient for empty LHS.

> There should be a check for infeasible empty rows, i.e. rows like
> 0 <= -3 or 0 >= +3. If such rows are removed, the routine must issue
> at least a warning message that the original instance is infeasible.

I understand what you mean regarding infeasible rows, but I don't know enough about the internals of GLPK to know how those rows might end up with empty LHS.  Is there a field on the row data structure that would indicate infeasibility?

One final note.  I've gotten the solution from minisat+ using the GLPK-generated OPB file to agree with the solution from GLPK.  The difference comes from the constant term in the objective function (if present).  So, before glpk solves the given model we get the following output:

lpx_read_model: row Delay_Costs; constant term -240720 ignored
lpx_write_pb: writing problem in OPB format to `mono.opb'...

It turns out the the difference in solution between the OPB solver and glpk is actually this constant.  I found this by noticing the same discrepancy when I generate an MPS and provide the resulting MPS file to various solvers.  The objective constant is not translated to the resulting OPB or MPS files.  Is this a feature or bug?  If it's a feature, could you explain the logic... it isn't clear to me why this happens.

With all of these considerations, I've made some changes to glplpx19.c which writes the OPB file so that now I get agreement from glpk and the PB solver without any manual manipulation of the OPB file.  All of the changes fit my needs perfectly and may or may not be appropriate for inclusion to the main GLPK branch.  I've included a patch below if it is useful.  For my purposes I leave KEEP_EMPTY_LHS_CONSTRAINTS undefined, thus not printing any constraints with empty LHS, but I left the option of doing a cplex-like fake LHS.

--- ../glpk-4.22/src/glplpx19.c 2007-09-19 01:00:00.000000000 -0700
+++ src/glplpx19.c      2008-03-05 10:45:01.000000000 -0800
@@ -25,6 +25,7 @@
 
 #include "glpapi.h"
 #define print xprint1
+/*#define KEEP_EMPTY_LHS_CONSTRAINTS*/
 
 /*----------------------------------------------------------------------
 -- lpx_write_pb - write problem data in (normalized) OPB format.
@@ -51,6 +52,9 @@
    FILE* fp;
    int m,n,i,j,k,o,nonfree=0, obj_dir, dbl, *ndx, row_type;
    double coeff, *val, bound;
+   int warning_flag = 0;
+   int obj_has_const_term = 0;
+   char* dummy_var = "__DUMMY_VAR";
 
    fp = xfopen(fname, "w");
 
@@ -83,6 +87,15 @@
        /* Objective function */
        obj_dir = glp_get_obj_dir(lp);
        fprintf(fp,"min: ");
+       /* Check for constant term ("shift") */
+       coeff = glp_get_obj_coef(lp,0);
+       if(coeff != 0.0) {
+          obj_has_const_term = 1;
+          if(normalized)
+                  fprintf(fp, " %d x0", (int)coeff);
+          else
+                  fprintf(fp, " %d*%s", (int)coeff, dummy_var);          
+       }
        for(i=1;i<=n;i++)
         {
           coeff = glp_get_obj_coef(lp,i);
@@ -102,6 +115,9 @@
        if(normalized)  /* Name substitution */
         {
           fprintf(fp,"* Variable name substitution:\n");
+          if(obj_has_const_term) {
+                 fprintf(fp, "* x0 = %s\n", j, dummy_var);
+          }
           for(j=1;j<=n;j++)
             {
               fprintf(fp, "* x%d = %s\n", j, glp_get_col_name(lp,j));
@@ -127,12 +143,31 @@
                   dbl=1;
                 }
               k=glp_get_mat_row(lp, j, ndx, val);
+#ifndef KEEP_EMPTY_LHS_CONSTRAINTS
+              if( k == 0) { /* If k is zero, we'd get an empty LHS */
+                 warning_flag = 1;
+                 continue;
+              }
+#endif
               for(o=1;o<=dbl;o++)
                 {
                   if(o==2)
                      {
                       row_type = GLP_LO;
-                     }
+                     } 
+#ifdef KEEP_EMPTY_LHS_CONSTRAINTS
+                  if(k == 0) { /* If k is zero, we'd get an empty LHS */
+                         warning_flag = 1;
+                         if(normalized)
+                         {
+                                 fprintf(fp, "0 x1 ");
+                         }
+                         else
+                         {
+                                 fprintf(fp, "0*%s ", glp_get_col_name(lp,ndx[1]));
+                         }
+                  }
+#endif
                   for(i=1;i<=k;i++)
                      {
                        if(val[i] != 0.0)
@@ -188,6 +223,9 @@
        xfree(val);
 
      }
+   if (warning_flag) {
+          print("Warning: there were some empty LHSs.");
+   }
    else
      {
        print("Problems opening file for writing: %s", fname);

---

Climb to the top of the charts! Play the word scramble challenge with star power. Play now!