mpq_lp.c

Go to the documentation of this file.
00001 /****************************************************************************/
00002 /*                                                                          */
00003 /*  This file is part of QSopt_ex.                                          */
00004 /*                                                                          */
00005 /*  (c) Copyright 2006 by David Applegate, William Cook, Sanjeeb Dash,      */
00006 /*  and Daniel Espinoza                                                     */
00007 /*                                                                          */
00008 /*  Sanjeeb Dash ownership of copyright in QSopt_ex is derived from his     */
00009 /*  copyright in QSopt.                                                     */
00010 /*                                                                          */
00011 /*  This code may be used under the terms of the GNU General Public License */
00012 /*  (Version 2.1 or later) as published by the Free Software Foundation.    */
00013 /*                                                                          */
00014 /*  Alternatively, use is granted for research purposes only.               */
00015 /*                                                                          */
00016 /*  It is your choice of which of these two licenses you are operating      */
00017 /*  under.                                                                  */
00018 /*                                                                          */
00019 /*  We make no guarantees about the correctness or usefulness of this code. */
00020 /*                                                                          */
00021 /****************************************************************************/
00022 
00023 /* RCS_INFO = "$RCSfile: mpq_lp.c,v $ $Revision: 1.2 $ $Date: 2003/11/05 16:49:52 $"; */
00024 
00025 /****************************************************************************/
00026 /*                                                                          */
00027 /*               Routines for Reading and Writing LP Files                  */
00028 /*                                                                          */
00029 /*  EXPORTED FUNCTIONS                                                      */
00030 /*                                                                          */
00031 /*        int mpq_ILLwrite_lp (EGioFile_t *out, mpq_ILLlpdata *lp)                  */
00032 /*        int mpq_ILLread_lp (mpq_qsline_reader f, const char *mpq_fname, mpq_rawlpdata *lp)*/
00033 /*        int mpq_ILLis_lp_name_char (char c, int pos)                          */
00034 /*        int mpq_ILLread_constraint_expr(mpq_ILLread_lp_state *state,              */
00035 /*          mpq_rawlpdata *lp, int rowind, int allowNew)                        */
00036 /*        int mpq_ILLread_constraint_name (mpq_ILLread_lp_state *state,             */
00037 /*          char **rowname)                                                 */
00038 /*        int mpq_ILLread_one_constraint (mpq_ILLread_lp_state *state,              */
00039 /*          const char *rowname, mpq_rawlpdata *lp, int allowNewCols)           */
00040 /*                                                                          */
00041 /****************************************************************************/
00042 
00043 #include <stdio.h>
00044 #include "qs_config.h"
00045 /* from the cplex manual: 
00046  
00047     not exceed 16 characters, all of which must be alphanumeric
00048     (a-z, A-Z, 0-9) or one of these symbols: ! " # $ % & ( ) / ,
00049     . ; ? @ _ ` ' { } | ~. Longer names will be truncated to 16
00050     characters. A variable name can not begin with a number or a
00051     period. 
00052 
00053     The letter E or e, alone or followed by other valid symbols,
00054     or followed by another E or e, should be avoided as this
00055     notation is reserved for exponential entries. Thus, variables
00056     can not be named e9, E-24, E8cats, or other names that could
00057     be interpreted as an exponent. Even variable names such as
00058     eels or example can cause a read error, depending on their
00059     placement in an input line. 
00060 
00061     Also, the following characters are not valid in variable
00062     names (in order to allow for quadratic objective
00063     information): ^, *, [ and ]. 
00064 */
00065 /* OUR DEFINTION:
00066  * -) variables consist of a-z A-Z 0-9 !"#$%(),;.?@_`'{}|~ 
00067  *    don't start with a digit or '.'
00068  * return  0 for variable 
00069  * return -1 for keyword 
00070  * return  1 otherwise 
00071  */
00072 
00073 
00074 int mpq_ILLis_lp_name_char (
00075   int c,
00076   int pos)
00077 {
00078   return ((('a' <= c) && (c <= 'z')) ||
00079           (('A' <= c) && (c <= 'Z')) ||
00080           ((pos > 0) && ('0' <= c) && (c <= '9')) ||
00081           ((pos > 0) && (c == '.')) ||
00082           (strchr ("!\"#$%&()/,;?@_`'{}|~", c) != NULL));
00083 }
00084 
00085 
00086 /* 
00087  * -) anything after '\' is comment 
00088  * -) Problem is optional and comes first
00089  * -) Minimize, Maximize, ... comes after Problem
00090  * -) variables consist of a-z A-Z 0-9!"#$%(),;.?@_`'{}|~ 
00091  */
00092 
00093 /*  NOTES                                                                   */
00094 /*   
00095  *    don't start with a digit or '.'
00096  */
00097 
00098 static const int mpq_LINE_LEN = 256;
00099 
00100 #include "mpq_iqsutil.h"
00101 #include "mpq_lp.h"
00102 #include "mpq_rawlp.h"
00103 #include "mpq_read_lp.h"
00104 #include "mpq_write_lp.h"
00105 #ifdef USEDMALLOC
00106 #include "dmalloc.h"
00107 #endif
00108 //extern mpq_t mpq_SZERO_TOLER;
00109 static int TRACE = 0;
00110 
00111 static int mpq_read_problem_name (
00112   mpq_ILLread_lp_state * state,
00113   mpq_rawlpdata * lp);
00114 static int mpq_read_minmax (
00115   mpq_ILLread_lp_state * state,
00116   mpq_rawlpdata * lp);
00117 static int mpq_read_objective (
00118   mpq_ILLread_lp_state * state,
00119   mpq_rawlpdata * lp);
00120 static int mpq_read_objective (
00121   mpq_ILLread_lp_state * state,
00122   mpq_rawlpdata * lp);
00123 static int mpq_read_constraints (
00124   mpq_ILLread_lp_state * state,
00125   mpq_rawlpdata * lp,
00126   int allowNewCols);
00127 static int mpq_read_colname (
00128   mpq_ILLread_lp_state * state,
00129   ILLsymboltab * coltab,
00130   int mustHave);
00131 static int mpq_read_integer (
00132   mpq_ILLread_lp_state * state,
00133   mpq_rawlpdata * lp);
00134 static int mpq_read_bounds (
00135   mpq_ILLread_lp_state * state,
00136   mpq_rawlpdata * lp);
00137 static int mpq_add_var (
00138   mpq_rawlpdata * lp,
00139   mpq_ILLread_lp_state * state,
00140   mpq_t coef,
00141   int row,
00142   int allowNew);
00143 
00144 /*------------------------------------------------------------------------ 
00145  * mpq_ILLwrite_lp and support routines
00146  */
00147 static int mpq_fix_names (
00148   mpq_qserror_collector * collector,
00149   char **names,
00150   int nnames,
00151   const char *extra,
00152   int prefix,
00153   char ***newnames);
00154 static void mpq_write_objective (
00155   mpq_ILLlpdata * lp,
00156   const char *objname,
00157   char **colnames);
00158 static int mpq_write_row (
00159   mpq_ILLlpdata * lp,
00160   mpq_ILLlp_rows * lprows,
00161   int i,
00162   char **rownames,
00163   char **colnames,
00164   int *colInRow,
00165   mpq_t * colCoef);
00166 static int mpq_write_bounds (
00167   mpq_ILLlpdata * lp,
00168   char **colnames);
00169 static void mpq_write_intvars (
00170   mpq_ILLlpdata * lp,
00171   char **colnames);
00172 
00173 int mpq_ILLwrite_lp (
00174   mpq_ILLlpdata * lp,
00175   mpq_qserror_collector * collector)
00176 {
00177   int rval = 0;
00178   int i;
00179   mpq_ILLlp_rows lp_rows, *lprows = NULL;
00180   char **colnames = (char **) NULL;
00181   char **rownames = (char **) NULL;
00182   mpq_t *colCoef = NULL;
00183   int *colInRow = NULL;
00184   const char *objname;
00185 
00186   ILL_FAILfalse (lp, "called without data\n");
00187   if (lp->nstruct == 0 || lp->nrows == 0)
00188   {
00189     EG_RETURN (rval);
00190   }
00191   ILL_FAILfalse (lp->colnames != NULL, "lp->colnames != NULL");
00192   ILL_FAILfalse (lp->rownames != NULL, "lp->rownames != NULL");
00193   ILL_FAILfalse (lp->nstruct == lp->coltab.tablesize,
00194                  "lp coltab has nstruct entries");
00195   if (lp->objname == (char *) NULL)
00196   {
00197     ILL_FAILfalse (lp->nrows == lp->rowtab.tablesize,
00198                    "lp rowtab should have nrows entries");
00199   }
00200   else
00201   {
00202     ILL_FAILfalse (lp->nrows + 1 == lp->rowtab.tablesize,
00203                    "lp rowtab should have nrows+1 entries");
00204     ILL_FAILfalse (ILLsymboltab_contains (&lp->rowtab, lp->objname),
00205                    "rowtab must contain objname");
00206   }
00207 
00208   rval = mpq_fix_names (collector, lp->colnames, lp->nstruct, NULL, 'x', &colnames);
00209   CHECKRVALG (rval, CLEANUP);
00210 
00211   rval = mpq_fix_names (collector, lp->rownames, lp->nrows,
00212                     (lp->objname) ? lp->objname : "obj", 'c', &rownames);
00213   CHECKRVALG (rval, CLEANUP);
00214   objname = rownames[lp->nrows];
00215 
00216   ILL_FAILtrue (objname == NULL, "OOps, that should never happen");
00217   CHECKRVALG (rval, CLEANUP);
00218 
00219   if (lp->sos.matcols > 0)
00220   {
00221     rval +=
00222       mpq_ILLdata_error (collector, "Can't express SOS information in LP format.");
00223   }
00224 
00225   mpq_write_objective (lp, objname, colnames);
00226 
00227   /* Note, mpq_ILLlp_rows_init returns cols ordered by structmap, so we may use 
00228    * colnames[i] when pulling i from the matrix data.  */
00229 
00230   lprows = &lp_rows;
00231   if (mpq_ILLlp_rows_init (lprows, lp, 0) != 0)
00232   {
00233     rval += 1;
00234     ILL_FAILtrue (rval, "mpq_ILLlp_rows_init failed\n");
00235   }
00236 
00237   colCoef = mpq_EGlpNumAllocArray (lp->nstruct);
00238   ILL_SAFE_MALLOC (colInRow, lp->nstruct, int);
00239 
00240   for (i = 0; i < lp->nstruct; i++)
00241   {
00242     colInRow[i] = -1;
00243   }
00244 
00245   mpq_ILLprint_report (lp, "Subject To\n");
00246   for (i = 0; i < lp->nrows; i++)
00247   {
00248     if (lprows->rowcnt[i] == 0)
00249     {
00250       /*
00251        * mpq_ILLdata_warn (collector, "Not printing  empty row \"%s\".", rownames[i]);
00252        */
00253       continue;
00254     }
00255     rval += mpq_write_row (lp, lprows, i, rownames, colnames, colInRow, colCoef);
00256   }
00257 
00258   rval += mpq_write_bounds (lp, colnames);
00259 
00260   if (lp->intmarker != NULL)
00261   {
00262     mpq_write_intvars (lp, colnames);
00263   }
00264 
00265   mpq_ILLprint_report (lp, "End\n");
00266 CLEANUP:
00267   if (lprows != NULL)
00268   {
00269     mpq_ILLlp_rows_clear (lprows);
00270   }
00271   ILLfree_names (colnames, lp->nstruct);
00272   ILLfree_names (rownames, lp->nrows + 1);
00273   mpq_EGlpNumFreeArray (colCoef);
00274   ILL_IFFREE (colInRow, int);
00275 
00276   EG_RETURN (rval);
00277 }
00278 
00279 static void mpq_write_objective (
00280   mpq_ILLlpdata * lp,
00281   const char *objname,
00282   char **colnames)
00283 {
00284   int ri, i, k, var;
00285   mpq_ILLwrite_lp_state ln, *line = &ln;
00286 
00287   if (lp->probname != NULL)
00288   {
00289     mpq_ILLprint_report (lp, "Problem\n %s\n", lp->probname);
00290   }
00291   if (lp->objsense == mpq_ILL_MIN)
00292   {
00293     mpq_ILLprint_report (lp, "Minimize\n");
00294   }
00295   else
00296   {
00297     mpq_ILLprint_report (lp, "Maximize\n");
00298   }
00299   mpq_ILLwrite_lp_state_init (line, NULL);
00300   mpq_ILLwrite_lp_state_append (line, " ");
00301   mpq_ILLwrite_lp_state_append (line, objname);
00302   mpq_ILLwrite_lp_state_append (line, ": ");
00303   mpq_ILLwrite_lp_state_save_start (line);
00304 
00305   for (ri = 0, var = 0; ri < lp->nstruct; ri++)
00306   {
00307     i = lp->structmap[ri];
00308     if (mpq_EGlpNumIsNeqqZero (lp->obj[i]))
00309     {
00310       mpq_ILLwrite_lp_state_append_coef (line, lp->obj[i], var);
00311       mpq_ILLwrite_lp_state_append (line, " ");
00312       mpq_ILLwrite_lp_state_append (line, colnames[ri]);
00313       var++;
00314 
00315       /* we put a least 4 terms on a line 
00316        * and then we stop after mpq_LINE_LEN or more characters 
00317        */
00318       if ((line->total >= mpq_LINE_LEN) && (var >= 4))
00319       {
00320         /* see whether there is another term 
00321          * if so append a '+' and print line */
00322         k = ri + 1;
00323         while (k < lp->nstruct)
00324         {
00325           if (mpq_EGlpNumIsLessZero (lp->obj[lp->structmap[k]]))
00326           {
00327             break;
00328           }
00329           else
00330           {
00331             if (mpq_EGlpNumIsGreatZero (lp->obj[lp->structmap[k]]))
00332             {
00333               mpq_ILLwrite_lp_state_append (line, " +");
00334               break;
00335             }
00336           }
00337           k++;
00338         }
00339         var = 0;                /* next line does not need to prefix coef with '+' */
00340         mpq_ILLprint_report (lp, "%s\n", line->buf);
00341         mpq_ILLwrite_lp_state_start (line);
00342       }
00343     }
00344   }
00345   if (var > 0)
00346   {
00347     mpq_ILLprint_report (lp, "%s\n", line->buf);
00348   }
00349 }
00350 
00351 static void mpq_write_the_expr (
00352   mpq_ILLlpdata * lp,
00353   mpq_ILLwrite_lp_state * line,
00354   char *rowname,
00355   mpq_ILLlp_rows * lprows,
00356   int row,
00357   char **colnames,
00358   int *colInRow,
00359   mpq_t * colCoef,
00360   int ncols)
00361 {
00362   int var, firstVar, k, i;
00363   mpq_t *coef;
00364 
00365   mpq_ILLwrite_lp_state_init (line, NULL);
00366   if (rowname != NULL)
00367   {
00368     mpq_ILLwrite_lp_state_append (line, " ");
00369     mpq_ILLwrite_lp_state_append (line, rowname);
00370     mpq_ILLwrite_lp_state_append (line, ": ");
00371   }
00372   else
00373   {
00374     mpq_ILLwrite_lp_state_append (line, "   ");
00375   }
00376   mpq_ILLwrite_lp_state_save_start (line);
00377 
00378   for (k = lprows->rowbeg[row];
00379        k < lprows->rowbeg[row] + lprows->rowcnt[row]; k++)
00380   {
00381     i = lprows->rowind[k];
00382     colInRow[i] = row;
00383     mpq_EGlpNumCopy (colCoef[i], lprows->rowval[k]);
00384   }
00385   var = 0;
00386   firstVar = 1;
00387   for (i = 0; i < ncols; i++)
00388   {
00389     if (colInRow[i] == row)
00390     {
00391       if (mpq_EGlpNumIsNeqqZero (colCoef[i]))
00392       {
00393         coef = &(colCoef[i]);
00394         if (line->total >= mpq_LINE_LEN)
00395         {
00396           mpq_ILLprint_report (lp, "%s\n", line->buf);
00397           mpq_ILLwrite_lp_state_start (line);
00398           if ((!firstVar) && !mpq_EGlpNumIsLessZero (*coef))
00399           {
00400             mpq_ILLwrite_lp_state_append (line, " +");
00401           }
00402           var = 0;
00403         }
00404 
00405         mpq_ILLwrite_lp_state_append_coef (line, *coef, var);
00406         mpq_ILLwrite_lp_state_append (line, " ");
00407         mpq_ILLwrite_lp_state_append (line, colnames[i]);
00408         var++;
00409         firstVar = 0;
00410       }
00411     }
00412   }
00413 }
00414 
00415 static int mpq_write_row (
00416   mpq_ILLlpdata * lp,
00417   mpq_ILLlp_rows * lprows,
00418   int i,
00419   char **rownames,
00420   char **colnames,
00421   int *colInRow,
00422   mpq_t * colCoef)
00423 {
00424   mpq_ILLwrite_lp_state ln, *line = &ln;
00425   int rval = 0;
00426   mpq_t ntmp;
00427 
00428   mpq_write_the_expr (lp, line, rownames[i], lprows, i, colnames,
00429                   colInRow, colCoef, lp->nstruct);
00430 
00431   switch (lp->sense[i])
00432   {
00433   case 'G':
00434     mpq_ILLwrite_lp_state_append (line, " >= ");
00435     mpq_ILLwrite_lp_state_append_number (line, lp->rhs[i]);
00436     break;
00437   case 'L':
00438     mpq_ILLwrite_lp_state_append (line, " <= ");
00439     mpq_ILLwrite_lp_state_append_number (line, lp->rhs[i]);
00440     break;
00441   case 'E':
00442     mpq_ILLwrite_lp_state_append (line, " = ");
00443     mpq_ILLwrite_lp_state_append_number (line, lp->rhs[i]);
00444     break;
00445   case 'R':
00446     ILL_FAILtrue (!lp->rangeval, "RANGE constraints without values\n");
00447     mpq_EGlpNumInitVar (ntmp);
00448     mpq_ILLwrite_lp_state_append (line, " >= ");
00449     mpq_ILLwrite_lp_state_append_number (line, lp->rhs[i]);
00450 
00451     mpq_ILLwrite_lp_state_append (line, " \t\\ RANGE (");
00452     mpq_ILLwrite_lp_state_append_number (line, lp->rhs[i]);
00453     mpq_ILLwrite_lp_state_append (line, ", ");
00454     mpq_EGlpNumCopySum (ntmp, lp->rhs[i], lp->rangeval[i]);
00455     mpq_ILLwrite_lp_state_append_number (line, ntmp);
00456     mpq_ILLwrite_lp_state_append (line, ")");
00457     mpq_ILLprint_report (lp, "%s\n", line->buf);
00458 
00459     mpq_write_the_expr (lp, line, NULL, lprows, i,
00460                     colnames, colInRow, colCoef, lp->nstruct);
00461     mpq_ILLwrite_lp_state_append (line, " <= ");
00462     mpq_ILLwrite_lp_state_append_number (line, ntmp);
00463     mpq_EGlpNumClearVar (ntmp);
00464     break;
00465   default:
00466     ILL_FAILtrue (1, "Unknown row sense\n");
00467   }
00468 
00469   mpq_ILLprint_report (lp, "%s\n", line->buf);
00470 CLEANUP:
00471   EG_RETURN (rval);
00472 }
00473 
00474 static int mpq_write_bounds (
00475   mpq_ILLlpdata * lp,
00476   char **colnames)
00477 {
00478   int ri, i, rval = 0;
00479   int prtLower, prtUpper;
00480   mpq_ILLwrite_lp_state l, *line = &l;
00481 
00482   ILL_FAILtrue (lp->lower == NULL || lp->upper == NULL,
00483                 "Should not call mpq_write_bounds when lower or upper are NULL");
00484   ri = mpq_ILLraw_first_nondefault_bound (lp);
00485   if (ri != lp->nstruct)
00486   {
00487     mpq_ILLprint_report (lp, "Bounds\n");
00488     mpq_ILLwrite_lp_state_init (line, " ");
00489     mpq_ILLwrite_lp_state_save_start (line);
00490 
00491     for (ri = ri; ri < lp->nstruct; ri++)
00492     {
00493       mpq_ILLwrite_lp_state_start (line);
00494       i = lp->structmap[ri];
00495       if (mpq_EGlpNumIsEqqual (lp->lower[i], lp->upper[i]))
00496       {
00497         mpq_ILLwrite_lp_state_append (line, " ");
00498         mpq_ILLwrite_lp_state_append (line, colnames[ri]);
00499         mpq_ILLwrite_lp_state_append (line, " = ");
00500         mpq_ILLwrite_lp_state_append_number (line, lp->upper[i]);
00501         mpq_ILLprint_report (lp, "%s\n", line->buf);
00502         continue;
00503       }
00504       if ((mpq_EGlpNumIsEqqual (lp->lower[i], mpq_ILL_MINDOUBLE)) &&
00505           (mpq_EGlpNumIsEqqual (lp->upper[i], mpq_ILL_MAXDOUBLE)))
00506       {
00507         mpq_ILLwrite_lp_state_append (line, colnames[ri]);
00508         mpq_ILLwrite_lp_state_append (line, " free");
00509         mpq_ILLprint_report (lp, "%s\n", line->buf);
00510         continue;
00511       }
00512       prtLower = !mpq_ILLraw_default_lower (lp, i);
00513       prtUpper = !mpq_ILLraw_default_upper (lp, i, ri);
00514       if (prtLower || prtUpper)
00515       {
00516         if (prtLower)
00517         {
00518           mpq_ILLwrite_lp_state_append_number (line, lp->lower[i]);
00519           mpq_ILLwrite_lp_state_append (line, " <= ");
00520         }
00521         if (prtLower || prtUpper)
00522         {
00523           mpq_ILLwrite_lp_state_append (line, colnames[ri]);
00524         }
00525         if (prtUpper)
00526         {
00527           mpq_ILLwrite_lp_state_append (line, " <= ");
00528           mpq_ILLwrite_lp_state_append_number (line, lp->upper[i]);
00529         }
00530         mpq_ILLprint_report (lp, "%s\n", line->buf);
00531       }
00532     }
00533   }
00534 CLEANUP:
00535   EG_RETURN (rval);
00536 }
00537 
00538 static void mpq_write_intvars (
00539   mpq_ILLlpdata * lp,
00540   char **colnames)
00541 {
00542   mpq_ILLwrite_lp_state ln, *line = &ln;
00543   int var, j;
00544 
00545   mpq_ILLprint_report (lp, "Integer\n");
00546   mpq_ILLwrite_lp_state_init (line, " ");
00547   mpq_ILLwrite_lp_state_save_start (line);
00548 
00549   for (j = 0, var = 0; j < lp->nstruct; j++)
00550   {
00551     if (lp->intmarker[j])
00552     {
00553       if (var > 0)
00554       {
00555         mpq_ILLwrite_lp_state_append (line, " ");
00556       }
00557       mpq_ILLwrite_lp_state_append (line, colnames[j]);
00558       var++;
00559       if (line->total >= mpq_LINE_LEN)
00560       {
00561         mpq_ILLprint_report (lp, "%s\n", line->buf);
00562         mpq_ILLwrite_lp_state_init (line, " ");
00563         var = 0;
00564       }
00565     }
00566   }
00567   if (var > 0)
00568   {
00569     mpq_ILLprint_report (lp, "%s\n", line->buf);
00570   }
00571 }
00572 
00573 /* ------------------------------------------------------------ */
00574 /* fix up names that are numbers, i.e. prefix with x X x_ or X_ */
00575 
00576 /* 
00577  * redefine names that start with [0-9]; i.e. give a prefix of 
00578  *         "x" | "X" | "x_" | "X_"  
00579  *         or if all these are already taken prefix with "X"<number>
00580  *         make sure names contain solely the characters: 
00581  *            [a-zA-Z0-9] and ! " # $ % & ( ) / , . ; ? @ _ ` ' { } | ~
00582  *         rename names with 'bad' chars to <x X x_ X_><number>
00583  */
00584 static int mpq_fix_names (
00585   mpq_qserror_collector * collector,
00586   char **names,
00587   int nnames,
00588   const char *extra,
00589   int pref,
00590   char ***newnames)
00591 {
00592   ILLsymboltab symt, *symtab = NULL;
00593   int rval = 0, i, j, n, ind, hit;
00594   char **n_names = NULL;
00595   const char *old_name;
00596   char buf[ILL_namebufsize];
00597   char p1[2], p2[3];
00598 
00599   p1[0] = pref;
00600   p1[1] = '\0';
00601   p2[0] = pref;
00602   p2[1] = '_';
00603   p2[2] = '\0';
00604 
00605   ILL_SAFE_MALLOC (n_names, nnames + 1, char *);
00606 
00607   for (i = 0; i < nnames; i++)
00608   {
00609     n_names[i] = (char *) NULL;
00610   }
00611 
00612   for (i = 0; i <= nnames; i++)
00613   {
00614     if (i == nnames)
00615     {
00616       if (extra == NULL)
00617         break;
00618       old_name = extra;
00619     }
00620     else
00621       old_name = names[i];
00622 
00623     n = strlen (old_name);
00624     strcpy (buf, old_name);
00625     if (!mpq_ILLis_lp_name_char (buf[0], 1))
00626     {
00627       sprintf (buf, "%d", i);
00628     }
00629     else
00630     {
00631       for (j = 1; j < n; j++)
00632       {
00633         if (!mpq_ILLis_lp_name_char (buf[j], j))
00634         {
00635           sprintf (buf, "%d", i);
00636           break;
00637         }
00638       }
00639     }
00640 
00641     if (!mpq_ILLis_lp_name_char (buf[0], 0))
00642     {
00643       if (symtab == NULL)
00644       {
00645         symtab = &symt;
00646         ILLsymboltab_init (symtab);
00647         ILLsymboltab_create (symtab, nnames + 1);
00648         for (j = 0; j < nnames; j++)
00649         {
00650           ILLsymboltab_register (symtab, names[j], -1, &ind, &hit);
00651           ILL_FAILfalse (ind == j, "ind == j");
00652         }
00653         if (extra != NULL)
00654           ILLsymboltab_register (symtab, extra, -1, &ind, &hit);
00655       }
00656       rval = ILLsymboltab_uname (symtab, buf, p1, p2);
00657       CHECKRVALG (rval, CLEANUP);
00658       rval = ILLsymboltab_rename (symtab, i, buf);
00659       CHECKRVALG (rval, CLEANUP);
00660 
00661       mpq_ILL_UTIL_STR (n_names[i], buf);
00662       mpq_ILLdata_warn (collector,
00663                     "\"%s\" is not a valid name in LP format; %s\"%s\".",
00664                     old_name, "renaiming to ", buf);
00665     }
00666     else
00667     {
00668       mpq_ILL_UTIL_STR (n_names[i], old_name);
00669     }
00670   }
00671 
00672 CLEANUP:
00673   if (symtab != NULL)
00674   {
00675     ILLsymboltab_free (symtab);
00676   }
00677   *newnames = n_names;
00678   EG_RETURN (rval);
00679 }
00680 
00681 /* 
00682  * end ILLlpdata_lpwrite 
00683  * ---------------------------------------------------------------------- */
00684 
00685 int mpq_ILLread_lp (
00686   mpq_qsline_reader * file,
00687   const char *mpq_fname,
00688   mpq_rawlpdata * lp)
00689 {
00690 /* file format: 
00691  *     optional problem name (this is in addition to the bix format) 
00692  *     min or max 
00693  *     objective fct 
00694  *     constraints (mandatory !) 
00695  *     optional bounds 
00696  *     optional integer (also new) 
00697  *
00698  * as opposed to the official bix-format: 
00699  *     no blanks in variable names 
00700  *     there may be several bound defs on the same line; 
00701  *     bound definitions may cross line boundaries
00702  *     constraints that have no name get generated names:
00703  *             if constraint i has not name we take the first name from the 
00704  *             following list that is not in use:
00705  *                  c<i>,  C<i>, or c<i>_0, c<i>_1, c<i>_2, ...
00706  */
00707   int rval = 0;
00708   mpq_ILLread_lp_state lpstate, *state = &lpstate;
00709 
00710   const char *bnds[3], *integer[3], *end[2];
00711 
00712   bnds[0] = "BOUNDS";
00713   bnds[1] = "BOUND";
00714   bnds[2] = NULL;
00715   integer[0] = "INTEGER";
00716   integer[1] = "INT";
00717   integer[2] = NULL;
00718   end[0] = "END";
00719   end[1] = NULL;
00720 
00721   rval = mpq_ILLread_lp_state_init (state, file, mpq_fname, 0);
00722   CHECKRVALG (rval, CLEANUP);
00723 
00724   mpq_ILLinit_rawlpdata (lp, file->error_collector);
00725   rval = ILLsymboltab_create (&lp->rowtab, 100) ||
00726     ILLsymboltab_create (&lp->coltab, 100);
00727   CHECKRVALG (rval, CLEANUP);
00728 
00729   if (mpq_ILLread_lp_state_next_field (state))
00730   {
00731     rval = mpq_ILLlp_error (state, "Empty file.\n");
00732   }
00733   if (rval == 0)
00734     rval = mpq_read_problem_name (state, lp);
00735   if (rval == 0)
00736     rval = mpq_read_minmax (state, lp);
00737   if (rval == 0)
00738     rval = mpq_read_objective (state, lp);
00739   if (rval == 0)
00740     rval = mpq_read_constraints (state, lp, 1);
00741   if ((rval == 0) && (lp->ncols == 0 || lp->nrows == 0))
00742   {
00743     rval = mpq_ILLlp_error (state,
00744                         "Problem must contain at least one %s.\n",
00745                         "non empty constraint");
00746   }
00747   CHECKRVALG (rval, CLEANUP);
00748 
00749   if (mpq_ILLread_lp_state_keyword (state, bnds) == 0)
00750   {
00751     rval = mpq_read_bounds (state, lp);
00752   }
00753   CHECKRVALG (rval, CLEANUP);
00754 
00755   if (mpq_ILLread_lp_state_keyword (state, integer) == 0)
00756   {
00757     rval = mpq_read_integer (state, lp);
00758   }
00759   CHECKRVALG (rval, CLEANUP);
00760 
00761   rval = mpq_ILLread_lp_state_keyword (state, end);
00762   if (rval != 0)
00763   {
00764     if (state->eof)
00765     {
00766       rval = mpq_ILLlp_error (state, "Missing \"End\" at end of file.\n");
00767     }
00768     else
00769     {
00770       rval = mpq_ILLlp_error (state, "\"%s\" unknown keyword\n", state->field);
00771     }
00772   }
00773   if (rval == 0)
00774   {
00775     rval = mpq_ILLraw_fill_in_rownames (lp) || mpq_ILLraw_fill_in_bounds (lp);
00776   }
00777 
00778 CLEANUP:
00779   mpq_EGlpNumClearVar (lpstate.bound_val);
00780   EG_RETURN (rval);
00781 }
00782 
00783 static int mpq_read_problem_name (
00784   mpq_ILLread_lp_state * state,
00785   mpq_rawlpdata * lp)
00786 {
00787   int rval = 0;
00788 
00789   if (!state->fieldOnFirstCol)
00790   {
00791     rval = mpq_ILLlp_error (state,
00792                         "Keyword \"%s\" not at beginning of line.\n",
00793                         state->field);
00794   }
00795   if (!mpq_ILLutil_strcasecmp (state->field, "PROBLEM") ||
00796       !mpq_ILLutil_strcasecmp (state->field, "PROB"))
00797   {
00798     if (mpq_ILLread_lp_state_next_field (state) != 0)
00799     {
00800       rval = mpq_ILLlp_error (state, "No Problem name field.\n");
00801     }
00802     else
00803     {
00804       ILL_IFFREE (lp->name, char);
00805 
00806       mpq_ILL_UTIL_STR (lp->name, state->field);
00807       ILL_IFTRACE ("ProblemName: %s\n", state->field);
00808       (void) mpq_ILLread_lp_state_next_field (state);
00809     }
00810   }
00811 CLEANUP:
00812   EG_RETURN (rval);
00813 }
00814 
00815 static int mpq_read_minmax (
00816   mpq_ILLread_lp_state * state,
00817   mpq_rawlpdata * lp)
00818 {
00819   int rval = 0;
00820 
00821   if (!state->fieldOnFirstCol)
00822   {
00823     rval = mpq_ILLlp_error (state,
00824                         "Keyword \"%s\" not at beginning of line.\n",
00825                         state->field);
00826   }
00827   if (!mpq_ILLutil_strcasecmp (state->field, "MAX") ||
00828       !mpq_ILLutil_strcasecmp (state->field, "MAXIMUM") ||
00829       !mpq_ILLutil_strcasecmp (state->field, "MAXIMIZE"))
00830   {
00831     lp->objsense = mpq_ILL_MAX;
00832   }
00833   else
00834   {
00835     if (!mpq_ILLutil_strcasecmp (state->field, "MIN") ||
00836         !mpq_ILLutil_strcasecmp (state->field, "MINIMUM") ||
00837         !mpq_ILLutil_strcasecmp (state->field, "MINIMIZE"))
00838     {
00839       lp->objsense = mpq_ILL_MIN;
00840     }
00841     else
00842     {
00843       mpq_ILLread_lp_state_prev_field (state);
00844       rval = mpq_ILLlp_error (state, "Expecting \"%s\" or \"%s\" keyword.\n",
00845                           "Minimize", "Maximize");
00846     }
00847   }
00848   EG_RETURN (rval);
00849 }
00850 
00851 int mpq_ILLread_constraint_expr (
00852   mpq_ILLread_lp_state * state,
00853   mpq_rawlpdata * lp,
00854   int rowind,
00855   int allowNew)
00856 {
00857   int rval = 0;
00858   char firstTerm, haveCoef;
00859   const char *name;
00860   mpq_t sign, coef;
00861   mpq_t ntmp;
00862 
00863   mpq_EGlpNumInitVar (ntmp);
00864   mpq_EGlpNumInitVar (sign);
00865   mpq_EGlpNumInitVar (coef);
00866 
00867   firstTerm = 1;
00868   while (1)
00869   {
00870     if (mpq_ILLread_lp_state_sign (state, &sign) != 0)
00871     {
00872       if (!firstTerm)
00873       {
00874         break;                  /* we've ssen at least one term, 
00875                                  * this is the constraint's end */
00876       }
00877     }
00878     haveCoef = mpq_ILLread_lp_state_possible_coef (state, &coef, mpq_oneLpNum);
00879     if (mpq_ILLread_lp_state_next_var (state) == 0)
00880     {
00881       mpq_EGlpNumCopy (ntmp, coef);
00882       mpq_EGlpNumMultTo (ntmp, sign);
00883       rval = mpq_add_var (lp, state, ntmp, rowind, allowNew);
00884       CHECKRVALG (rval, CLEANUP);
00885     }
00886     else
00887     {
00888       if (haveCoef == 0)
00889       {
00890         return mpq_ILLlp_error (state, "Coefficient without variable.\n");
00891       }
00892       else
00893       {
00894         break;
00895       }
00896     }
00897     firstTerm = 0;
00898   }
00899 CLEANUP:
00900   if ((rval == 0) && firstTerm)
00901   {
00902     name = mpq_ILLraw_rowname (lp, rowind);
00903     if (name != NULL)
00904     {
00905       mpq_ILLlp_warn (state,
00906                   "No terms in constraint expression for \"%s\".\n", name);
00907     }
00908     else
00909     {
00910       mpq_ILLlp_warn (state, "No terms in constraint expression.\n");
00911     }
00912   }
00913   mpq_EGlpNumClearVar (ntmp);
00914   mpq_EGlpNumClearVar (sign);
00915   mpq_EGlpNumClearVar (coef);
00916   EG_RETURN (rval);
00917 }
00918 
00919 static int mpq_read_objective (
00920   mpq_ILLread_lp_state * state,
00921   mpq_rawlpdata * lp)
00922 {
00923   int rval = 0;
00924   char objname[ILL_namebufsize];
00925   char *name;
00926 
00927   ILL_FAILfalse (lp->nrows == 0, "objective should be first row");
00928   mpq_ILLread_lp_state_skip_blanks (state, 1);
00929   if (mpq_ILLread_lp_state_has_colon (state))
00930   {
00931     if (mpq_ILLread_lp_state_next_var (state) != 0)
00932     {
00933       rval = mpq_ILLlp_error (state, "Bad objective function name.\n");
00934     }
00935     name = state->field;
00936     if (rval == 0)
00937     {
00938       if (mpq_ILLread_lp_state_colon (state) != 0)
00939       {
00940         rval = mpq_ILLlp_error (state, "':' must follow constraint row name.\n");
00941       }
00942     }
00943   }
00944   else
00945   {
00946     name = NULL;
00947   }
00948 
00949   if (rval == 0)
00950   {
00951     ILL_FAILfalse (lp->rowtab.tablesize == 0,
00952                    "objective row is first in symbol tab");
00953     if (name == NULL)
00954     {
00955       strcpy (objname, "obj");
00956       mpq_ILLlp_warn (state, "Empty obj name; using \"%s\".\n", objname);
00957     }
00958     else
00959     {
00960       strcpy (objname, name);
00961     }
00962     rval = mpq_ILLraw_add_row (lp, objname, 'N', mpq_zeroLpNum);
00963     lp->objindex = lp->nrows - 1;
00964     CHECKRVALG (rval, CLEANUP);
00965     rval = mpq_ILLread_constraint_expr (state, lp, lp->objindex, 1);
00966   }
00967 CLEANUP:
00968   EG_RETURN (rval);
00969 }
00970 
00971 int mpq_ILLread_constraint_name (
00972   mpq_ILLread_lp_state * state,
00973   char **rowname)
00974 {
00975   int rval = 0;
00976 
00977   *rowname = NULL;
00978 
00979   /* if there is a ':' on the line: look for constraint row name */
00980   if (mpq_ILLread_lp_state_has_colon (state))
00981   {
00982     if (mpq_ILLread_lp_state_next_var (state) != 0)
00983     {
00984       rval = mpq_ILLlp_error (state, "Bad constraint row name.\n");
00985     }
00986     else
00987     {
00988       *rowname = state->field;
00989       if (mpq_ILLread_lp_state_colon (state) != 0)
00990       {
00991         rval = mpq_ILLlp_error (state, "':' must follow constraint row name.\n");
00992       }
00993     }
00994   }
00995   return rval;
00996 }
00997 
00998 int mpq_ILLread_one_constraint (
00999   mpq_ILLread_lp_state * state,
01000   const char *rowname,
01001   mpq_rawlpdata * lp,
01002   int allowNewCols)
01003 {
01004   int rval = 0;
01005   int rowind;
01006   char sense;
01007   mpq_t d;
01008 
01009   mpq_EGlpNumInitVar (d);
01010 
01011   if ((rowname != NULL) &&
01012       (ILLsymboltab_lookup (&lp->rowtab, rowname, &rowind) == 0))
01013   {
01014     rval = mpq_ILLlp_error (state, "Repeated row name \"%s\".\n", rowname);
01015     CHECKRVALG (rval, CLEANUP);
01016   }
01017   rowind = lp->nrows;
01018   rval = rval || mpq_ILLraw_add_row (lp, rowname, 'N', mpq_zeroLpNum);
01019 
01020   rval = rval || mpq_ILLread_constraint_expr (state, lp, rowind, allowNewCols);
01021   rval = rval || mpq_ILLread_lp_state_sense (state);
01022   sense = state->sense_val;
01023   if (rval == 0)
01024   {
01025     rval = mpq_ILLread_lp_state_value (state, &d);
01026     if (rval)
01027     {
01028       (void) mpq_ILLlp_error (state, "No right hand side value in constraint.\n");
01029     }
01030   }
01031   if (rval == 0)
01032   {
01033     lp->rowsense[rowind] = sense;
01034     mpq_EGlpNumCopy (lp->rhs[rowind], d);
01035     ILL_IFTRACE ("SENSE \"%s\": %c %f\n",
01036                  mpq_ILLraw_rowname (lp, rowind), sense, mpq_EGlpNumToLf (d));
01037   }
01038 CLEANUP:
01039   mpq_EGlpNumClearVar (d);
01040   EG_RETURN (rval);
01041 }
01042 
01043 static int mpq_read_constraints (
01044   mpq_ILLread_lp_state * state,
01045   mpq_rawlpdata * lp,
01046   int allowNewCols)
01047 {
01048   int rval = 0;
01049   char *rowname = NULL;
01050 
01051   if (mpq_ILLcheck_subject_to (state) != 0)
01052   {
01053     return mpq_ILLlp_error (state, "Constraint section expected.\n");
01054   }
01055   while (rval == 0)
01056   {
01057     rval = mpq_ILLread_constraint_name (state, &rowname);
01058     if (rval == 0)
01059     {
01060       rval = mpq_ILLread_one_constraint (state, rowname, lp, allowNewCols);
01061     }
01062     if (rval == 0)
01063     {
01064       if (mpq_ILLread_lp_state_next_constraint (state) != 0)
01065       {
01066         break;
01067       }
01068     }
01069   }
01070   mpq_ILLread_lp_state_next_field (state);
01071   EG_RETURN (rval);
01072 }
01073 
01074 /* 
01075  * return -2 iff next is not a variable and not a keyword
01076  * return -1 iff next is a keyword and !mustHave 
01077  * return 1  iff unknown column name or mustHave and keyword 
01078  * return 0  for success
01079  */
01080 static int mpq_read_colname (
01081   mpq_ILLread_lp_state * state,
01082   ILLsymboltab * coltab,
01083   int mustHave)
01084 {
01085   int rval = 0;
01086   int colind = ILL_SYM_NOINDEX;
01087 
01088   rval = mpq_ILLread_lp_state_next_var (state);
01089   if (mustHave && (rval != 0))
01090   {
01091     return mpq_ILLlp_error (state, "Expecting a column name.\n");
01092   }
01093   if (rval != 0)
01094   {
01095     return (rval == -1) ? rval : -2;
01096   }
01097   if (ILLsymboltab_lookup (coltab, state->field, &colind))
01098   {
01099     mpq_ILLread_lp_state_prev_field (state);
01100     return mpq_ILLlp_error (state, "\"%s\" is not a column name.\n", state->field);
01101   }
01102   state->column_index = colind;
01103   return 0;
01104 }
01105 
01106 static int mpq_read_integer (
01107   mpq_ILLread_lp_state * state,
01108   mpq_rawlpdata * lp)
01109 {
01110   int rval = 0;
01111   ILLsymboltab *coltab = &lp->coltab;
01112 
01113   ILL_FAILfalse (lp->intmarker, "Programming error");
01114 
01115   while ((rval = mpq_read_colname (state, coltab, 0)) == 0)
01116   {
01117     ILL_FAILtrue (state->column_index == ILL_SYM_NOINDEX, "Programming error");
01118     lp->intmarker[state->column_index] = 1;
01119   }
01120 CLEANUP:
01121   if (rval == -1)
01122   {                             /* last try for a colname gave us a keyword */
01123     rval = 0;
01124   }
01125   else
01126   {
01127     rval = mpq_ILLlp_error (state, "Expecting a column name.");
01128   }
01129   mpq_ILLread_lp_state_next_field (state);
01130   EG_RETURN (rval);
01131 }
01132 
01133 static int mpq_read_bounds (
01134   mpq_ILLread_lp_state * state,
01135   mpq_rawlpdata * lp)
01136 {
01137   int rval = 0;
01138   int colind, haveBound;
01139   char sense;
01140   const char *msg;
01141   ILLsymboltab *coltab;
01142 
01143   mpq_ILLraw_init_bounds (lp);
01144   coltab = &lp->coltab;
01145 
01146   while (1)
01147   {
01148     colind = -1;
01149     haveBound = 0;
01150     if (mpq_ILLread_lp_state_possible_bound_value (state))
01151     {
01152       /* this must be for a lower bound */
01153       mpq_ILLtest_lp_state_bound_sense (state);
01154       if (state->sense_val != 'L')
01155       {
01156         rval = mpq_ILLlp_error (state, "Expecting \"<=\".\n");
01157         break;
01158       }
01159       rval = mpq_read_colname (state, coltab, 1);
01160       if (rval != 0)
01161       {
01162         break;
01163       }
01164       colind = state->column_index;
01165       /* add lower bound value */
01166       msg = mpq_ILLraw_set_lowerBound (lp, colind, state->bound_val);
01167       mpq_ILLlp_warn (state, msg);
01168       haveBound = 1;
01169     }
01170     if (colind == -1)
01171     {
01172       rval = mpq_read_colname (state, coltab, 0);
01173       colind = state->column_index;
01174       if (rval != 0)
01175       {
01176         if (rval == -1)
01177         {
01178           rval = 0;             /* found a keyword and that's OK */
01179         }
01180         else if (rval == -2)
01181         {
01182           rval = mpq_ILLlp_error (state, "Expecting a column name.\n");
01183         }
01184         break;
01185       }
01186     }
01187     ILL_FAILtrue (colind == -1, "must have a valid colname");
01188     mpq_ILLtest_lp_state_bound_sense (state);
01189     if (state->sense_val != ' ')
01190     {
01191       sense = state->sense_val;
01192       if ((sense != 'L') && (sense != 'E'))
01193       {
01194         rval = mpq_ILLlp_error (state, "Expecting \"<=\" or \"=\".\n");
01195         break;
01196       }
01197       if (mpq_ILLread_lp_state_possible_bound_value (state))
01198       {
01199         if (sense == 'E')
01200         {
01201           msg = mpq_ILLraw_set_fixedBound (lp, colind, state->bound_val);
01202         }
01203         else
01204         {
01205           msg = mpq_ILLraw_set_upperBound (lp, colind, state->bound_val);
01206         }
01207         mpq_ILLlp_warn (state, msg);
01208         haveBound = 1;
01209       }
01210       else
01211       {
01212         rval = mpq_ILLlp_error (state, "Expecting bound value.\n");
01213         break;
01214       }
01215     }
01216     else
01217     {
01218       if (mpq_ILLtest_lp_state_next_is (state, "FREE"))
01219       {
01220         msg = mpq_ILLraw_set_unbound (lp, colind);
01221         mpq_ILLlp_warn (state, msg);
01222         haveBound = 1;
01223       }
01224       else
01225       {
01226         if (!haveBound)
01227         {
01228           rval = mpq_ILLlp_error (state, "Not a bound expression.\n");
01229           break;
01230         }
01231       }
01232     }
01233     ILL_IFTRACE ("BOUNDS: %f <= %s <= %f\n", mpq_EGlpNumToLf (lp->lower[colind]),
01234                  mpq_ILLraw_colname (lp, colind), mpq_EGlpNumToLf (lp->upper[colind]));
01235   }
01236   mpq_ILLread_lp_state_next_field (state);
01237 CLEANUP:
01238   EG_RETURN (rval);
01239 }
01240 
01241 static int mpq_add_var (
01242   mpq_rawlpdata * lp,
01243   mpq_ILLread_lp_state * state,
01244   mpq_t coef,
01245   int row,
01246   int allowNew)
01247 {
01248   char *var = state->field;
01249   int rval = 0;
01250   int colind;
01251 
01252   if (ILLsymboltab_lookup (&lp->coltab, var, &colind) != 0)
01253   {
01254     if (!allowNew)
01255     {
01256       rval = mpq_ILLlp_error (state, "Unknown col name \"%s\".\n", var);
01257     }
01258     CHECKRVALG (rval, CLEANUP);
01259     rval = mpq_ILLraw_add_col (lp, var, 0 /* not an integer var */ );
01260     colind = lp->ncols - 1;
01261     CHECKRVALG (rval, CLEANUP);
01262   }
01263   ILL_IFTRACE ("mpq_add_var: \"%s\" coef=%f row=%s\n",
01264                var, mpq_EGlpNumToLf (coef), mpq_ILLraw_rowname (lp, row));
01265   rval = mpq_ILLraw_add_col_coef (lp, colind, row, coef);
01266 CLEANUP:
01267   EG_RETURN (rval);
01268 }

Generated on Thu Mar 29 09:32:32 2012 for QSopt_ex by  doxygen 1.4.7