dbl_solver.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: dbl_solver.c,v $ $Revision: 1.2 $ $Date: 2003/11/05 16:49:52 $"; */
00024 
00025 #include "qs_config.h"
00026 #include "exact.h"
00027 #include "dbl_solver.h"
00028 #include "dbl_iqsutil.h"
00029 #include "dbl_util.h"
00030 #include "dbl_lpdefs.h"             /* for PRIMAL_SIMPLEX */
00031 #include "dbl_qstruct.h"
00032 #include "dbl_qsopt.h"
00033 #include "dbl_binary.h"
00034 #include "dbl_editor.h"
00035 #include "dbl_price.h"
00036 #include "dbl_lib.h"                /* for dbl_ILLmip_binary_dfs */
00037 #ifdef USEDMALLOC
00038 #include "dmalloc.h"
00039 #endif
00040 
00041 static char *dbl_fname = 0;
00042 static int dbl_lpfile = 0;
00043 static int dbl_solvemip = 0;
00044 static int dbl_interactive = 0;
00045 static int dbl_usescaling = 1;
00046 static int dbl_showversion = 0;
00047 static int dbl_simplexalgo = PRIMAL_SIMPLEX;
00048 static int dbl_pstrategy = QS_PRICE_PSTEEP;
00049 static int dbl_dstrategy = QS_PRICE_DSTEEP;
00050 static unsigned dbl_precision = 128;
00051 static int dbl_printsol = 0;
00052 static char *dbl_readbasis = 0;
00053 static char *dbl_writebasis = 0;
00054 
00055 static void dbl_usage (
00056   char *s),
00057   dbl_get_ftype (
00058   char *name,
00059   int *ftype);
00060 
00061 #ifdef TEST_FEEDBACK
00062 static int dbl_feedback (
00063   FILE * dest,
00064   const char *str);
00065 #endif
00066 static int parseargs (
00067   int ac,
00068   char **av);
00069 
00070 #ifndef WIN32
00071 dbl_QSLIB_INTERFACE int main ( int ac, char **av);
00072 int main ( int ac, char **av)
00073 {
00074   int rval;
00075   EGlib_info();
00076   EGlib_version();
00077   QSopt_ex_version();
00078   QSexactStart();
00079   rval = dbl_solver_main (ac, av);
00080   QSexactClear();
00081   return rval;
00082 }
00083 #endif
00084 
00085 dbl_QSLIB_INTERFACE int dbl_solver_main (
00086   int ac,
00087   char **av)
00088 {
00089   int rval = 0;
00090   dbl_QSdata *p = 0;
00091   ILLutil_timer timer_solve;
00092   ILLutil_timer timer_read;
00093   int ftype = 0;                /* 0 mps, 1 lp */
00094   double *x = 0;
00095   double val;
00096   double szeit;
00097 
00098   rval = parseargs (ac, av);
00099   if (rval)
00100     ILL_CLEANUP;
00101 
00102   dbl_QSset_precision (dbl_precision);
00103   dbl_EGlpNumInitVar (val);
00104   if (dbl_showversion)
00105   {
00106     char *buf = 0;
00107 
00108     buf = dbl_QSversion ();
00109     if (buf == 0)
00110     {
00111       ILL_CLEANUP;
00112     }
00113     else
00114     {
00115       printf ("%s\n", buf);
00116       dbl_QSfree ((void *) buf);
00117     }
00118   }
00119 
00120   if (dbl_lpfile)
00121   {
00122     ftype = 1;
00123   }
00124   else
00125   {
00126     dbl_get_ftype (dbl_fname, &ftype);
00127   }
00128 
00129   ILLutil_init_timer (&timer_read, "SOLVER_READ");
00130   ILLutil_start_timer (&timer_read);
00131   if (ftype == 1)
00132   {
00133     p = dbl_QSread_prob ((const char *) dbl_fname, "LP");
00134     if (p == 0)
00135     {
00136       fprintf (stderr, "Could not read lp file.\n");
00137       rval = 1;
00138       ILL_CLEANUP_IF (rval);
00139     }
00140   }
00141   else
00142   {
00143     p = dbl_QSread_prob ((const char *) dbl_fname, "MPS");
00144     if (p == 0)
00145     {
00146       fprintf (stderr, "Could not read mps file.\n");
00147       rval = 1;
00148       ILL_CLEANUP_IF (rval);
00149     }
00150   }
00151 
00152   if (dbl_readbasis)
00153   {
00154     rval = dbl_QSread_and_load_basis (p, (const char *) dbl_readbasis);
00155     ILL_CLEANUP_IF (rval);
00156   }
00157   ILLutil_stop_timer (&timer_read, 1);
00158   rval = dbl_QSset_param (p, QS_PARAM_SIMPLEX_DISPLAY, 1)
00159     || dbl_QSset_param (p, QS_PARAM_PRIMAL_PRICING, dbl_pstrategy)
00160     || dbl_QSset_param (p, QS_PARAM_DUAL_PRICING, dbl_dstrategy)
00161     || dbl_QSset_param (p, QS_PARAM_SIMPLEX_SCALING, dbl_usescaling);
00162   ILL_CLEANUP_IF (rval);
00163 
00164   if (dbl_interactive)
00165   {
00166     dbl_ILLeditor_init ();
00167     dbl_ILLeditor (p);
00168     goto CLEANUP;
00169   }
00170 
00171   szeit = ILLutil_zeit();
00172   ILLutil_init_timer (&timer_solve, "SOLVER");
00173   ILLutil_start_timer (&timer_solve);
00174 
00175 #ifdef TEST_FEEDBACK
00176   dbl_QSset_reporter (p, (void *) dbl_feedback, stdout);
00177 #endif
00178   rval = dbl_ILLeditor_solve (p, dbl_simplexalgo);
00179   ILLutil_stop_timer (&timer_solve, 1);
00180   ILL_CLEANUP_IF (rval);
00181 
00182   printf ("ZZ %s %.2f\n", p->lp->O->probname, ILLutil_zeit () - szeit);
00183   fflush (stdout);
00184 
00185   if (dbl_printsol)
00186     x = dbl_EGlpNumAllocArray (p->lp->O->nstruct);
00187 
00188   if (dbl_solvemip)
00189   {
00190     rval = dbl_ILLmip_bfs (p->lp, &val, x, &(p->itcnt));
00191     ILL_CLEANUP_IF (rval);
00192     printf ("MIP Objective Value: %.6f\n", dbl_EGlpNumToLf (val));
00193     fflush (stdout);
00194     if (dbl_printsol && dbl_EGlpNumIsNeqq (val, dbl_ILL_MAXDOUBLE) &&
00195         dbl_EGlpNumIsNeqq (val, dbl_ILL_MINDOUBLE))
00196     {
00197       EGioFile_t*out = EGioOpenFILE(stdout);
00198       rval = dbl_ILLlib_print_x (out, p->lp, 0, x, 1);
00199       EGioClose(out);
00200       ILL_CLEANUP_IF (rval);
00201     }
00202   }
00203   else
00204   {
00205     if (dbl_writebasis)
00206     {
00207       rval = dbl_QSwrite_basis (p, 0, dbl_writebasis);
00208       ILL_CLEANUP_IF (rval);
00209     }
00210     if (dbl_printsol)
00211     {
00212       EGioFile_t*out = EGioOpenFILE(stdout);
00213       rval = dbl_ILLlib_print_x (out, p->lp, 0, 0, 1);
00214       EGioClose(out);
00215       ILL_CLEANUP_IF (rval);
00216     }
00217   }
00218 
00219 CLEANUP:
00220   dbl_EGlpNumFreeArray (x);
00221   dbl_QSfree_prob (p);
00222   dbl_EGlpNumClearVar (val);
00223   return rval;                  /* main return */
00224 }
00225 
00226 static void dbl_usage (
00227   char *s)
00228 {
00229   char *buf = 0;
00230 
00231   buf = dbl_QSversion ();
00232   if (buf)
00233   {
00234     fprintf (stderr, "%s\n", buf);
00235     dbl_QSfree ((void *) buf);
00236   }
00237 
00238   fprintf (stderr, "Usage: %s [- below -] prob_file\n", s);
00239   fprintf (stderr, "   -b f  write basis to file f\n");
00240   fprintf (stderr, "   -B f  read initial basis from file f\n");
00241 #if 0
00242   fprintf (stderr, "   -I    solve the MIP using BestBound\n");
00243   fprintf (stderr, "   -E    edit problem after solving initial version\n");
00244 #endif
00245   fprintf (stderr, "   -L    input file is in lp format (default: mps)\n");
00246   fprintf (stderr, "   -O    print the final solution\n");
00247   fprintf (stderr, "   -p #  run primal simplex with pricing rule #\n");
00248   fprintf (stderr,
00249            "         (%d-Dantzig, %d-Devex, %d-Steep (default), %d-Partial\n",
00250            QS_PRICE_PDANTZIG, QS_PRICE_PDEVEX, QS_PRICE_PSTEEP,
00251            QS_PRICE_PMULTPARTIAL);
00252   fprintf (stderr, "   -d #  run dual simplex with pricing rule #\n");
00253   fprintf (stderr, "         (%d-Dantzig, %d-Steep, %d-Partial, %d-Devex)\n",
00254            QS_PRICE_DDANTZIG, QS_PRICE_DSTEEP, QS_PRICE_DMULTPARTIAL,
00255            QS_PRICE_DDEVEX);
00256   fprintf (stderr, "   -S    do NOT scale the initial LP\n");
00257   fprintf (stderr, "   -v    print QSopt version number\n");
00258 }
00259 
00260 static int parseargs (
00261   int ac,
00262   char **av)
00263 {
00264   int c;
00265   int boptind = 1;
00266   char *boptarg = 0;
00267 
00268   while ((c =
00269           ILLutil_bix_getopt (ac, av, "b:B:d:p:P:IELOSv", &boptind,
00270                               &boptarg)) != EOF)
00271     switch (c)
00272     {
00273     case 'b':
00274       dbl_writebasis = boptarg;
00275       break;
00276     case 'B':
00277       dbl_readbasis = boptarg;
00278       break;
00279     case 'P':
00280       dbl_precision = atoi (boptarg);
00281       break;
00282     case 'd':
00283       dbl_simplexalgo = DUAL_SIMPLEX;
00284       dbl_dstrategy = atoi (boptarg);
00285       break;
00286 #if 0
00287     case 'E':
00288       dbl_interactive = 1;
00289       break;
00290     case 'I':
00291       dbl_solvemip = 1;
00292       break;
00293 #endif
00294     case 'L':
00295       dbl_lpfile = 1;
00296       break;
00297     case 'O':
00298       dbl_printsol = 1;
00299       break;
00300     case 'p':
00301       dbl_simplexalgo = PRIMAL_SIMPLEX;
00302       dbl_pstrategy = atoi (boptarg);
00303       break;
00304     case 'S':
00305       dbl_usescaling = 0;
00306       break;
00307     case 'v':
00308       dbl_showversion = 1;
00309       break;
00310     case '?':
00311     default:
00312       dbl_usage (av[0]);
00313       return 1;
00314     }
00315   if (boptind != (ac - 1))
00316   {
00317     dbl_usage (av[0]);
00318     return 1;
00319   }
00320 
00321   dbl_fname = av[boptind++];
00322   fprintf (stderr, "Reading problem from %s\n", dbl_fname);
00323   return 0;
00324 }
00325 
00326 static void dbl_get_ftype (
00327   char *name,
00328   int *ftype)
00329 {
00330   char *q;
00331 
00332   q = strrchr (name, '.');
00333   if (q)
00334   {
00335     q++;
00336     if (!strcmp (q, "lp") || !strcmp (q, "LP"))
00337     {
00338       *ftype = 1;
00339     }
00340     else
00341     {
00342       *ftype = 0;
00343     }
00344   }
00345 }
00346 
00347 #ifdef TEST_FEEDBACK
00348 static int dbl_feedback (
00349   FILE * dest,
00350   const char *str)
00351 {
00352   if (str != NULL)
00353   {
00354     int rc = fprintf ((FILE *) dest, "FEEDBACK: %s", str);
00355 
00356     fflush (dest);
00357     return rc;
00358   }
00359   return 0;
00360 }
00361 #endif

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