Re: [Help-glpk] OPB output file anomaly

[Andrew Makhorin]

Oscar,

Could you please give comments for the proposal below?

It seems to me that including dummy variables in the output .opb file
could resolve the following two problems:

- processing empty left-hand side; corresponding constraint can be
  represented as "dummy_zero >= rhs" or "dummy_zero <= rhs", where
  dummy_zero is a dummy variable fixed at 0;

- processing the constant term of the objective function by adding
  "c0 * dummy_one", where dummy_one is a dummy variable fixed at 1.

Regards,

Andrew Makhorin
   

> 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);