[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] OPB output file anomaly
From: |
Andrew Makhorin |
Subject: |
Re: [Help-glpk] OPB output file anomaly |
Date: |
Sun, 9 Mar 2008 14:10:01 +0300 |
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);