mpf_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: mpf_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 mpf_ILLwrite_lp (EGioFile_t *out, mpf_ILLlpdata *lp)                  */
00032 /*        int mpf_ILLread_lp (mpf_qsline_reader f, const char *mpf_fname, mpf_rawlpdata *lp)*/
00033 /*        int mpf_ILLis_lp_name_char (char c, int pos)                          */
00034 /*        int mpf_ILLread_constraint_expr(mpf_ILLread_lp_state *state,              */
00035 /*          mpf_rawlpdata *lp, int rowind, int allowNew)                        */
00036 /*        int mpf_ILLread_constraint_name (mpf_ILLread_lp_state *state,             */
00037 /*          char **rowname)                                                 */
00038 /*        int mpf_ILLread_one_constraint (mpf_ILLread_lp_state *state,              */
00039 /*          const char *rowname, mpf_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 mpf_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 mpf_LINE_LEN = 256;
00099 
00100 #include "mpf_iqsutil.h"
00101 #include "mpf_lp.h"
00102 #include "mpf_rawlp.h"
00103 #include "mpf_read_lp.h"
00104 #include "mpf_write_lp.h"
00105 #ifdef USEDMALLOC
00106 #include "dmalloc.h"
00107 #endif
00108 //extern mpf_t mpf_SZERO_TOLER;
00109 static int TRACE = 0;
00110 
00111 static int mpf_read_problem_name (
00112   mpf_ILLread_lp_state * state,
00113   mpf_rawlpdata * lp);
00114 static int mpf_read_minmax (
00115   mpf_ILLread_lp_state * state,
00116   mpf_rawlpdata * lp);
00117 static int mpf_read_objective (
00118   mpf_ILLread_lp_state * state,
00119   mpf_rawlpdata * lp);
00120 static int mpf_read_objective (
00121   mpf_ILLread_lp_state * state,
00122   mpf_rawlpdata * lp);
00123 static int mpf_read_constraints (
00124   mpf_ILLread_lp_state * state,
00125   mpf_rawlpdata * lp,
00126   int allowNewCols);
00127 static int mpf_read_colname (
00128   mpf_ILLread_lp_state * state,
00129   ILLsymboltab * coltab,
00130   int mustHave);
00131 static int mpf_read_integer (
00132   mpf_ILLread_lp_state * state,
00133   mpf_rawlpdata * lp);
00134 static int mpf_read_bounds (
00135   mpf_ILLread_lp_state * state,
00136   mpf_rawlpdata * lp);
00137 static int mpf_add_var (
00138   mpf_rawlpdata * lp,
00139   mpf_ILLread_lp_state * state,
00140   mpf_t coef,
00141   int row,
00142   int allowNew);
00143 
00144 /*------------------------------------------------------------------------ 
00145  * mpf_ILLwrite_lp and support routines
00146  */
00147 static int mpf_fix_names (
00148   mpf_qserror_collector * collector,
00149   char **names,
00150   int nnames,
00151   const char *extra,
00152   int prefix,
00153   char ***newnames);
00154 static void mpf_write_objective (
00155   mpf_ILLlpdata * lp,
00156   const char *objname,
00157   char **colnames);
00158 static int mpf_write_row (
00159   mpf_ILLlpdata * lp,
00160   mpf_ILLlp_rows * lprows,
00161   int i,
00162   char **rownames,
00163   char **colnames,
00164   int *colInRow,
00165   mpf_t * colCoef);
00166 static int mpf_write_bounds (
00167   mpf_ILLlpdata * lp,
00168   char **colnames);
00169 static void mpf_write_intvars (
00170   mpf_ILLlpdata * lp,
00171   char **colnames);
00172 
00173 int mpf_ILLwrite_lp (
00174   mpf_ILLlpdata * lp,
00175   mpf_qserror_collector * collector)
00176 {
00177   int rval = 0;
00178   int i;
00179   mpf_ILLlp_rows lp_rows, *lprows = NULL;
00180   char **colnames = (char **) NULL;
00181   char **rownames = (char **) NULL;
00182   mpf_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 = mpf_fix_names (collector, lp->colnames, lp->nstruct, NULL, 'x', &colnames);
00209   CHECKRVALG (rval, CLEANUP);
00210 
00211   rval = mpf_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       mpf_ILLdata_error (collector, "Can't express SOS information in LP format.");
00223   }
00224 
00225   mpf_write_objective (lp, objname, colnames);
00226 
00227   /* Note, mpf_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 (mpf_ILLlp_rows_init (lprows, lp, 0) != 0)
00232   {
00233     rval += 1;
00234     ILL_FAILtrue (rval, "mpf_ILLlp_rows_init failed\n");
00235   }
00236 
00237   colCoef = mpf_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   mpf_ILLprint_report (lp, "Subject To\n");
00246   for (i = 0; i < lp->nrows; i++)
00247   {
00248     if (lprows->rowcnt[i] == 0)
00249     {
00250       /*
00251        * mpf_ILLdata_warn (collector, "Not printing  empty row \"%s\".", rownames[i]);
00252        */
00253       continue;
00254     }
00255     rval += mpf_write_row (lp, lprows, i, rownames, colnames, colInRow, colCoef);
00256   }
00257 
00258   rval += mpf_write_bounds (lp, colnames);
00259 
00260   if (lp->intmarker != NULL)
00261   {
00262     mpf_write_intvars (lp, colnames);
00263   }
00264 
00265   mpf_ILLprint_report (lp, "End\n");
00266 CLEANUP:
00267   if (lprows != NULL)
00268   {
00269     mpf_ILLlp_rows_clear (lprows);
00270   }
00271   ILLfree_names (colnames, lp->nstruct);
00272   ILLfree_names (rownames, lp->nrows + 1);
00273   mpf_EGlpNumFreeArray (colCoef);
00274   ILL_IFFREE (colInRow, int);
00275 
00276   EG_RETURN (rval);
00277 }
00278 
00279 static void mpf_write_objective (
00280   mpf_ILLlpdata * lp,
00281   const char *objname,
00282   char **colnames)
00283 {
00284   int ri, i, k, var;
00285   mpf_ILLwrite_lp_state ln, *line = &ln;
00286 
00287   if (lp->probname != NULL)
00288   {
00289     mpf_ILLprint_report (lp, "Problem\n %s\n", lp->probname);
00290   }
00291   if (lp->objsense == mpf_ILL_MIN)
00292   {
00293     mpf_ILLprint_report (lp, "Minimize\n");
00294   }
00295   else
00296   {
00297     mpf_ILLprint_report (lp, "Maximize\n");
00298   }
00299   mpf_ILLwrite_lp_state_init (line, NULL);
00300   mpf_ILLwrite_lp_state_append (line, " ");
00301   mpf_ILLwrite_lp_state_append (line, objname);
00302   mpf_ILLwrite_lp_state_append (line, ": ");
00303   mpf_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 (mpf_EGlpNumIsNeqqZero (lp->obj[i]))
00309     {
00310       mpf_ILLwrite_lp_state_append_coef (line, lp->obj[i], var);
00311       mpf_ILLwrite_lp_state_append (line, " ");
00312       mpf_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 mpf_LINE_LEN or more characters 
00317        */
00318       if ((line->total >= mpf_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 (mpf_EGlpNumIsLessZero (lp->obj[lp->structmap[k]]))
00326           {
00327             break;
00328           }
00329           else
00330           {
00331             if (mpf_EGlpNumIsGreatZero (lp->obj[lp->structmap[k]]))
00332             {
00333               mpf_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         mpf_ILLprint_report (lp, "%s\n", line->buf);
00341         mpf_ILLwrite_lp_state_start (line);
00342       }
00343     }
00344   }
00345   if (var > 0)
00346   {
00347     mpf_ILLprint_report (lp, "%s\n", line->buf);
00348   }
00349 }
00350 
00351 static void mpf_write_the_expr (
00352   mpf_ILLlpdata * lp,
00353   mpf_ILLwrite_lp_state * line,
00354   char *rowname,
00355   mpf_ILLlp_rows * lprows,
00356   int row,
00357   char **colnames,
00358   int *colInRow,
00359   mpf_t * colCoef,
00360   int ncols)
00361 {
00362   int var, firstVar, k, i;
00363   mpf_t *coef;
00364 
00365   mpf_ILLwrite_lp_state_init (line, NULL);
00366   if (rowname != NULL)
00367   {
00368     mpf_ILLwrite_lp_state_append (line, " ");
00369     mpf_ILLwrite_lp_state_append (line, rowname);
00370     mpf_ILLwrite_lp_state_append (line, ": ");
00371   }
00372   else
00373   {
00374     mpf_ILLwrite_lp_state_append (line, "   ");
00375   }
00376   mpf_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     mpf_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 (mpf_EGlpNumIsNeqqZero (colCoef[i]))
00392       {
00393         coef = &(colCoef[i]);
00394         if (line->total >= mpf_LINE_LEN)
00395         {
00396           mpf_ILLprint_report (lp, "%s\n", line->buf);
00397           mpf_ILLwrite_lp_state_start (line);
00398           if ((!firstVar) && !mpf_EGlpNumIsLessZero (*coef))
00399           {
00400             mpf_ILLwrite_lp_state_append (line, " +");
00401           }
00402           var = 0;
00403         }
00404 
00405         mpf_ILLwrite_lp_state_append_coef (line, *coef, var);
00406         mpf_ILLwrite_lp_state_append (line, " ");
00407         mpf_ILLwrite_lp_state_append (line, colnames[i]);
00408         var++;
00409         firstVar = 0;
00410       }
00411     }
00412   }
00413 }
00414 
00415 static int mpf_write_row (
00416   mpf_ILLlpdata * lp,
00417   mpf_ILLlp_rows * lprows,
00418   int i,
00419   char **rownames,
00420   char **colnames,
00421   int *colInRow,
00422   mpf_t * colCoef)
00423 {
00424   mpf_ILLwrite_lp_state ln, *line = &ln;
00425   int rval = 0;
00426   mpf_t ntmp;
00427 
00428   mpf_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     mpf_ILLwrite_lp_state_append (line, " >= ");
00435     mpf_ILLwrite_lp_state_append_number (line, lp->rhs[i]);
00436     break;
00437   case 'L':
00438     mpf_ILLwrite_lp_state_append (line, " <= ");
00439     mpf_ILLwrite_lp_state_append_number (line, lp->rhs[i]);
00440     break;
00441   case 'E':
00442     mpf_ILLwrite_lp_state_append (line, " = ");
00443     mpf_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     mpf_EGlpNumInitVar (ntmp);
00448     mpf_ILLwrite_lp_state_append (line, " >= ");
00449     mpf_ILLwrite_lp_state_append_number (line, lp->rhs[i]);
00450 
00451     mpf_ILLwrite_lp_state_append (line, " \t\\ RANGE (");
00452     mpf_ILLwrite_lp_state_append_number (line, lp->rhs[i]);
00453     mpf_ILLwrite_lp_state_append (line, ", ");
00454     mpf_EGlpNumCopySum (ntmp, lp->rhs[i], lp->rangeval[i]);
00455     mpf_ILLwrite_lp_state_append_number (line, ntmp);
00456     mpf_ILLwrite_lp_state_append (line, ")");
00457     mpf_ILLprint_report (lp, "%s\n", line->buf);
00458 
00459     mpf_write_the_expr (lp, line, NULL, lprows, i,
00460                     colnames, colInRow, colCoef, lp->nstruct);
00461     mpf_ILLwrite_lp_state_append (line, " <= ");
00462     mpf_ILLwrite_lp_state_append_number (line, ntmp);
00463     mpf_EGlpNumClearVar (ntmp);
00464     break;
00465   default:
00466     ILL_FAILtrue (1, "Unknown row sense\n");
00467   }
00468 
00469   mpf_ILLprint_report (lp, "%s\n", line->buf);
00470 CLEANUP:
00471   EG_RETURN (rval);
00472 }
00473 
00474 static int mpf_write_bounds (
00475   mpf_ILLlpdata * lp,
00476   char **colnames)
00477 {
00478   int ri, i, rval = 0;
00479   int prtLower, prtUpper;
00480   mpf_ILLwrite_lp_state l, *line = &l;
00481 
00482   ILL_FAILtrue (lp->lower == NULL || lp->upper == NULL,
00483                 "Should not call mpf_write_bounds when lower or upper are NULL");
00484   ri = mpf_ILLraw_first_nondefault_bound (lp);
00485   if (ri != lp->nstruct)
00486   {
00487     mpf_ILLprint_report (lp, "Bounds\n");
00488     mpf_ILLwrite_lp_state_init (line, " ");
00489     mpf_ILLwrite_lp_state_save_start (line);
00490 
00491     for (ri = ri; ri < lp->nstruct; ri++)
00492     {
00493       mpf_ILLwrite_lp_state_start (line);
00494       i = lp->structmap[ri];
00495       if (mpf_EGlpNumIsEqqual (lp->lower[i], lp->upper[i]))
00496       {
00497         mpf_ILLwrite_lp_state_append (line, " ");
00498         mpf_ILLwrite_lp_state_append (line, colnames[ri]);
00499         mpf_ILLwrite_lp_state_append (line, " = ");
00500         mpf_ILLwrite_lp_state_append_number (line, lp->upper[i]);
00501         mpf_ILLprint_report (lp, "%s\n", line->buf);
00502         continue;
00503       }
00504       if ((mpf_EGlpNumIsEqqual (lp->lower[i], mpf_ILL_MINDOUBLE)) &&
00505           (mpf_EGlpNumIsEqqual (lp->upper[i], mpf_ILL_MAXDOUBLE)))
00506       {
00507         mpf_ILLwrite_lp_state_append (line, colnames[ri]);
00508         mpf_ILLwrite_lp_state_append (line, " free");
00509         mpf_ILLprint_report (lp, "%s\n", line->buf);
00510         continue;
00511       }
00512       prtLower = !mpf_ILLraw_default_lower (lp, i);
00513       prtUpper = !mpf_ILLraw_default_upper (lp, i, ri);
00514       if (prtLower || prtUpper)
00515       {
00516         if (prtLower)
00517         {
00518           mpf_ILLwrite_lp_state_append_number (line, lp->lower[i]);
00519           mpf_ILLwrite_lp_state_append (line, " <= ");
00520         }
00521         if (prtLower || prtUpper)
00522         {
00523           mpf_ILLwrite_lp_state_append (line, colnames[ri]);
00524         }
00525         if (prtUpper)
00526         {
00527           mpf_ILLwrite_lp_state_append (line, " <= ");
00528           mpf_ILLwrite_lp_state_append_number (line, lp->upper[i]);
00529         }
00530         mpf_ILLprint_report (lp, "%s\n", line->buf);
00531       }
00532     }
00533   }
00534 CLEANUP:
00535   EG_RETURN (rval);
00536 }
00537 
00538 static void mpf_write_intvars (
00539   mpf_ILLlpdata * lp,
00540   char **colnames)
00541 {
00542   mpf_ILLwrite_lp_state ln, *line = &ln;
00543   int var, j;
00544 
00545   mpf_ILLprint_report (lp, "Integer\n");
00546   mpf_ILLwrite_lp_state_init (line, " ");
00547   mpf_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         mpf_ILLwrite_lp_state_append (line, " ");
00556       }
00557       mpf_ILLwrite_lp_state_append (line, colnames[j]);
00558       var++;
00559       if (line->total >= mpf_LINE_LEN)
00560       {
00561         mpf_ILLprint_report (lp, "%s\n", line->buf);
00562         mpf_ILLwrite_lp_state_init (line, " ");
00563         var = 0;
00564       }
00565     }
00566   }
00567   if (var > 0)
00568   {
00569     mpf_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 mpf_fix_names (
00585   mpf_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 (!mpf_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 (!mpf_ILLis_lp_name_char (buf[j], j))
00634         {
00635           sprintf (buf, "%d", i);
00636           break;
00637         }
00638       }
00639     }
00640 
00641     if (!mpf_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       mpf_ILL_UTIL_STR (n_names[i], buf);
00662       mpf_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       mpf_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 mpf_ILLread_lp (
00686   mpf_qsline_reader * file,
00687   const char *mpf_fname,
00688   mpf_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   mpf_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 = mpf_ILLread_lp_state_init (state, file, mpf_fname, 0);
00722   CHECKRVALG (rval, CLEANUP);
00723 
00724   mpf_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 (mpf_ILLread_lp_state_next_field (state))
00730   {
00731     rval = mpf_ILLlp_error (state, "Empty file.\n");
00732   }
00733   if (rval == 0)
00734     rval = mpf_read_problem_name (state, lp);
00735   if (rval == 0)
00736     rval = mpf_read_minmax (state, lp);
00737   if (rval == 0)
00738     rval = mpf_read_objective (state, lp);
00739   if (rval == 0)
00740     rval = mpf_read_constraints (state, lp, 1);
00741   if ((rval == 0) && (lp->ncols == 0 || lp->nrows == 0))
00742   {
00743     rval = mpf_ILLlp_error (state,
00744                         "Problem must contain at least one %s.\n",
00745                         "non empty constraint");
00746   }
00747   CHECKRVALG (rval, CLEANUP);
00748 
00749   if (mpf_ILLread_lp_state_keyword (state, bnds) == 0)
00750   {
00751     rval = mpf_read_bounds (state, lp);
00752   }
00753   CHECKRVALG (rval, CLEANUP);
00754 
00755   if (mpf_ILLread_lp_state_keyword (state, integer) == 0)
00756   {
00757     rval = mpf_read_integer (state, lp);
00758   }
00759   CHECKRVALG (rval, CLEANUP);
00760 
00761   rval = mpf_ILLread_lp_state_keyword (state, end);
00762   if (rval != 0)
00763   {
00764     if (state->eof)
00765     {
00766       rval = mpf_ILLlp_error (state, "Missing \"End\" at end of file.\n");
00767     }
00768     else
00769     {
00770       rval = mpf_ILLlp_error (state, "\"%s\" unknown keyword\n", state->field);
00771     }
00772   }
00773   if (rval == 0)
00774   {
00775     rval = mpf_ILLraw_fill_in_rownames (lp) || mpf_ILLraw_fill_in_bounds (lp);
00776   }
00777 
00778 CLEANUP:
00779   mpf_EGlpNumClearVar (lpstate.bound_val);
00780   EG_RETURN (rval);
00781 }
00782 
00783 static int mpf_read_problem_name (
00784   mpf_ILLread_lp_state * state,
00785   mpf_rawlpdata * lp)
00786 {
00787   int rval = 0;
00788 
00789   if (!state->fieldOnFirstCol)
00790   {
00791     rval = mpf_ILLlp_error (state,
00792                         "Keyword \"%s\" not at beginning of line.\n",
00793                         state->field);
00794   }
00795   if (!mpf_ILLutil_strcasecmp (state->field, "PROBLEM") ||
00796       !mpf_ILLutil_strcasecmp (state->field, "PROB"))
00797   {
00798     if (mpf_ILLread_lp_state_next_field (state) != 0)
00799     {
00800       rval = mpf_ILLlp_error (state, "No Problem name field.\n");
00801     }
00802     else
00803     {
00804       ILL_IFFREE (lp->name, char);
00805 
00806       mpf_ILL_UTIL_STR (lp->name, state->field);
00807       ILL_IFTRACE ("ProblemName: %s\n", state->field);
00808       (void) mpf_ILLread_lp_state_next_field (state);
00809     }
00810   }
00811 CLEANUP:
00812   EG_RETURN (rval);
00813 }
00814 
00815 static int mpf_read_minmax (
00816   mpf_ILLread_lp_state * state,
00817   mpf_rawlpdata * lp)
00818 {
00819   int rval = 0;
00820 
00821   if (!state->fieldOnFirstCol)
00822   {
00823     rval = mpf_ILLlp_error (state,
00824                         "Keyword \"%s\" not at beginning of line.\n",
00825                         state->field);
00826   }
00827   if (!mpf_ILLutil_strcasecmp (state->field, "MAX") ||
00828       !mpf_ILLutil_strcasecmp (state->field, "MAXIMUM") ||
00829       !mpf_ILLutil_strcasecmp (state->field, "MAXIMIZE"))
00830   {
00831     lp->objsense = mpf_ILL_MAX;
00832   }
00833   else
00834   {
00835     if (!mpf_ILLutil_strcasecmp (state->field, "MIN") ||
00836         !mpf_ILLutil_strcasecmp (state->field, "MINIMUM") ||
00837         !mpf_ILLutil_strcasecmp (state->field, "MINIMIZE"))
00838     {
00839       lp->objsense = mpf_ILL_MIN;
00840     }
00841     else
00842     {
00843       mpf_ILLread_lp_state_prev_field (state);
00844       rval = mpf_ILLlp_error (state, "Expecting \"%s\" or \"%s\" keyword.\n",
00845                           "Minimize", "Maximize");
00846     }
00847   }
00848   EG_RETURN (rval);
00849 }
00850 
00851 int mpf_ILLread_constraint_expr (
00852   mpf_ILLread_lp_state * state,
00853   mpf_rawlpdata * lp,
00854   int rowind,
00855   int allowNew)
00856 {
00857   int rval = 0;
00858   char firstTerm, haveCoef;
00859   const char *name;
00860   mpf_t sign, coef;
00861   mpf_t ntmp;
00862 
00863   mpf_EGlpNumInitVar (ntmp);
00864   mpf_EGlpNumInitVar (sign);
00865   mpf_EGlpNumInitVar (coef);
00866 
00867   firstTerm = 1;
00868   while (1)
00869   {
00870     if (mpf_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 = mpf_ILLread_lp_state_possible_coef (state, &coef, mpf_oneLpNum);
00879     if (mpf_ILLread_lp_state_next_var (state) == 0)
00880     {
00881       mpf_EGlpNumCopy (ntmp, coef);
00882       mpf_EGlpNumMultTo (ntmp, sign);
00883       rval = mpf_add_var (lp, state, ntmp, rowind, allowNew);
00884       CHECKRVALG (rval, CLEANUP);
00885     }
00886     else
00887     {
00888       if (haveCoef == 0)
00889       {
00890         return mpf_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 = mpf_ILLraw_rowname (lp, rowind);
00903     if (name != NULL)
00904     {
00905       mpf_ILLlp_warn (state,
00906                   "No terms in constraint expression for \"%s\".\n", name);
00907     }
00908     else
00909     {
00910       mpf_ILLlp_warn (state, "No terms in constraint expression.\n");
00911     }
00912   }
00913   mpf_EGlpNumClearVar (ntmp);
00914   mpf_EGlpNumClearVar (sign);
00915   mpf_EGlpNumClearVar (coef);
00916   EG_RETURN (rval);
00917 }
00918 
00919 static int mpf_read_objective (
00920   mpf_ILLread_lp_state * state,
00921   mpf_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   mpf_ILLread_lp_state_skip_blanks (state, 1);
00929   if (mpf_ILLread_lp_state_has_colon (state))
00930   {
00931     if (mpf_ILLread_lp_state_next_var (state) != 0)
00932     {
00933       rval = mpf_ILLlp_error (state, "Bad objective function name.\n");
00934     }
00935     name = state->field;
00936     if (rval == 0)
00937     {
00938       if (mpf_ILLread_lp_state_colon (state) != 0)
00939       {
00940         rval = mpf_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       mpf_ILLlp_warn (state, "Empty obj name; using \"%s\".\n", objname);
00957     }
00958     else
00959     {
00960       strcpy (objname, name);
00961     }
00962     rval = mpf_ILLraw_add_row (lp, objname, 'N', mpf_zeroLpNum);
00963     lp->objindex = lp->nrows - 1;
00964     CHECKRVALG (rval, CLEANUP);
00965     rval = mpf_ILLread_constraint_expr (state, lp, lp->objindex, 1);
00966   }
00967 CLEANUP:
00968   EG_RETURN (rval);
00969 }
00970 
00971 int mpf_ILLread_constraint_name (
00972   mpf_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 (mpf_ILLread_lp_state_has_colon (state))
00981   {
00982     if (mpf_ILLread_lp_state_next_var (state) != 0)
00983     {
00984       rval = mpf_ILLlp_error (state, "Bad constraint row name.\n");
00985     }
00986     else
00987     {
00988       *rowname = state->field;
00989       if (mpf_ILLread_lp_state_colon (state) != 0)
00990       {
00991         rval = mpf_ILLlp_error (state, "':' must follow constraint row name.\n");
00992       }
00993     }
00994   }
00995   return rval;
00996 }
00997 
00998 int mpf_ILLread_one_constraint (
00999   mpf_ILLread_lp_state * state,
01000   const char *rowname,
01001   mpf_rawlpdata * lp,
01002   int allowNewCols)
01003 {
01004   int rval = 0;
01005   int rowind;
01006   char sense;
01007   mpf_t d;
01008 
01009   mpf_EGlpNumInitVar (d);
01010 
01011   if ((rowname != NULL) &&
01012       (ILLsymboltab_lookup (&lp->rowtab, rowname, &rowind) == 0))
01013   {
01014     rval = mpf_ILLlp_error (state, "Repeated row name \"%s\".\n", rowname);
01015     CHECKRVALG (rval, CLEANUP);
01016   }
01017   rowind = lp->nrows;
01018   rval = rval || mpf_ILLraw_add_row (lp, rowname, 'N', mpf_zeroLpNum);
01019 
01020   rval = rval || mpf_ILLread_constraint_expr (state, lp, rowind, allowNewCols);
01021   rval = rval || mpf_ILLread_lp_state_sense (state);
01022   sense = state->sense_val;
01023   if (rval == 0)
01024   {
01025     rval = mpf_ILLread_lp_state_value (state, &d);
01026     if (rval)
01027     {
01028       (void) mpf_ILLlp_error (state, "No right hand side value in constraint.\n");
01029     }
01030   }
01031   if (rval == 0)
01032   {
01033     lp->rowsense[rowind] = sense;
01034     mpf_EGlpNumCopy (lp->rhs[rowind], d);
01035     ILL_IFTRACE ("SENSE \"%s\": %c %f\n",
01036                  mpf_ILLraw_rowname (lp, rowind), sense, mpf_EGlpNumToLf (d));
01037   }
01038 CLEANUP:
01039   mpf_EGlpNumClearVar (d);
01040   EG_RETURN (rval);
01041 }
01042 
01043 static int mpf_read_constraints (
01044   mpf_ILLread_lp_state * state,
01045   mpf_rawlpdata * lp,
01046   int allowNewCols)
01047 {
01048   int rval = 0;
01049   char *rowname = NULL;
01050 
01051   if (mpf_ILLcheck_subject_to (state) != 0)
01052   {
01053     return mpf_ILLlp_error (state, "Constraint section expected.\n");
01054   }
01055   while (rval == 0)
01056   {
01057     rval = mpf_ILLread_constraint_name (state, &rowname);
01058     if (rval == 0)
01059     {
01060       rval = mpf_ILLread_one_constraint (state, rowname, lp, allowNewCols);
01061     }
01062     if (rval == 0)
01063     {
01064       if (mpf_ILLread_lp_state_next_constraint (state) != 0)
01065       {
01066         break;
01067       }
01068     }
01069   }
01070   mpf_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 mpf_read_colname (
01081   mpf_ILLread_lp_state * state,
01082   ILLsymboltab * coltab,
01083   int mustHave)
01084 {
01085   int rval = 0;
01086   int colind = ILL_SYM_NOINDEX;
01087 
01088   rval = mpf_ILLread_lp_state_next_var (state);
01089   if (mustHave && (rval != 0))
01090   {
01091     return mpf_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     mpf_ILLread_lp_state_prev_field (state);
01100     return mpf_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 mpf_read_integer (
01107   mpf_ILLread_lp_state * state,
01108   mpf_rawlpdata * lp)
01109 {
01110   int rval = 0;
01111   ILLsymboltab *coltab = &lp->coltab;
01112 
01113   ILL_FAILfalse (lp->intmarker, "Programming error");
01114 
01115   while ((rval = mpf_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 = mpf_ILLlp_error (state, "Expecting a column name.");
01128   }
01129   mpf_ILLread_lp_state_next_field (state);
01130   EG_RETURN (rval);
01131 }
01132 
01133 static int mpf_read_bounds (
01134   mpf_ILLread_lp_state * state,
01135   mpf_rawlpdata * lp)
01136 {
01137   int rval = 0;
01138   int colind, haveBound;
01139   char sense;
01140   const char *msg;
01141   ILLsymboltab *coltab;
01142 
01143   mpf_ILLraw_init_bounds (lp);
01144   coltab = &lp->coltab;
01145 
01146   while (1)
01147   {
01148     colind = -1;
01149     haveBound = 0;
01150     if (mpf_ILLread_lp_state_possible_bound_value (state))
01151     {
01152       /* this must be for a lower bound */
01153       mpf_ILLtest_lp_state_bound_sense (state);
01154       if (state->sense_val != 'L')
01155       {
01156         rval = mpf_ILLlp_error (state, "Expecting \"<=\".\n");
01157         break;
01158       }
01159       rval = mpf_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 = mpf_ILLraw_set_lowerBound (lp, colind, state->bound_val);
01167       mpf_ILLlp_warn (state, msg);
01168       haveBound = 1;
01169     }
01170     if (colind == -1)
01171     {
01172       rval = mpf_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 = mpf_ILLlp_error (state, "Expecting a column name.\n");
01183         }
01184         break;
01185       }
01186     }
01187     ILL_FAILtrue (colind == -1, "must have a valid colname");
01188     mpf_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 = mpf_ILLlp_error (state, "Expecting \"<=\" or \"=\".\n");
01195         break;
01196       }
01197       if (mpf_ILLread_lp_state_possible_bound_value (state))
01198       {
01199         if (sense == 'E')
01200         {
01201           msg = mpf_ILLraw_set_fixedBound (lp, colind, state->bound_val);
01202         }
01203         else
01204         {
01205           msg = mpf_ILLraw_set_upperBound (lp, colind, state->bound_val);
01206         }
01207         mpf_ILLlp_warn (state, msg);
01208         haveBound = 1;
01209       }
01210       else
01211       {
01212         rval = mpf_ILLlp_error (state, "Expecting bound value.\n");
01213         break;
01214       }
01215     }
01216     else
01217     {
01218       if (mpf_ILLtest_lp_state_next_is (state, "FREE"))
01219       {
01220         msg = mpf_ILLraw_set_unbound (lp, colind);
01221         mpf_ILLlp_warn (state, msg);
01222         haveBound = 1;
01223       }
01224       else
01225       {
01226         if (!haveBound)
01227         {
01228           rval = mpf_ILLlp_error (state, "Not a bound expression.\n");
01229           break;
01230         }
01231       }
01232     }
01233     ILL_IFTRACE ("BOUNDS: %f <= %s <= %f\n", mpf_EGlpNumToLf (lp->lower[colind]),
01234                  mpf_ILLraw_colname (lp, colind), mpf_EGlpNumToLf (lp->upper[colind]));
01235   }
01236   mpf_ILLread_lp_state_next_field (state);
01237 CLEANUP:
01238   EG_RETURN (rval);
01239 }
01240 
01241 static int mpf_add_var (
01242   mpf_rawlpdata * lp,
01243   mpf_ILLread_lp_state * state,
01244   mpf_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 = mpf_ILLlp_error (state, "Unknown col name \"%s\".\n", var);
01257     }
01258     CHECKRVALG (rval, CLEANUP);
01259     rval = mpf_ILLraw_add_col (lp, var, 0 /* not an integer var */ );
01260     colind = lp->ncols - 1;
01261     CHECKRVALG (rval, CLEANUP);
01262   }
01263   ILL_IFTRACE ("mpf_add_var: \"%s\" coef=%f row=%s\n",
01264                var, mpf_EGlpNumToLf (coef), mpf_ILLraw_rowname (lp, row));
01265   rval = mpf_ILLraw_add_col_coef (lp, colind, row, coef);
01266 CLEANUP:
01267   EG_RETURN (rval);
01268 }

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