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