dbl_lpdefs.h

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 /* RCSINFO $Id: dbl_lpdefs.h,v 1.3 2003/11/05 16:57:39 meven Exp $ */
00024 #ifndef dbl___QS_LPDEFS_H
00025 #define dbl___QS_LPDEFS_H
00026 
00027 #include "dbl_qsopt.h"
00028 #include "dbl_lpdata.h"
00029 #include "dbl_factor.h"
00030 
00031 /* infinity and negative infinity */
00032 #define dbl_INFTY  dbl_ILL_MAXDOUBLE
00033 #define dbl_NINFTY dbl_ILL_MINDOUBLE
00034 
00035 #include "basicdefs.h"
00036 /* tolerances, these are initialized in dbl_ILLstart, file dbl_lpdata.c */
00037 //#if EGLPNUM_TYPE != DBL_TYPE && EGLPNUM_TYPE != LDBL_TYPE
00038 /* these three constants are defined in dbl_lpdata.c */
00039 extern double dbl_PARAM_IBASIS_RPIVOT;  /*       0.98 */
00040 extern double dbl_PARAM_IBASIS_RTRIANG;/*       0.01 */
00041 extern double dbl_PARAM_MIN_DNORM;      /*      1e-24 */
00042 extern double dbl_PFEAS_TOLER;          /*       1e-6 */
00043 extern double dbl_BD_TOLER;           /*       1e-7 */
00044 extern double dbl_DFEAS_TOLER;          /*       1e-6 */
00045 extern double dbl_PIVOT_TOLER;          /*      1e-10 */
00046 extern double dbl_SZERO_TOLER;          /*      1e-15 */
00047 extern double dbl_PIVZ_TOLER;         /*      1e-12 */
00048 extern double dbl_OBJBND_TOLER;       /*       1e-2 */
00049 extern double dbl_DBNDPIV_TOLER;        /*       1e-3 */
00050 extern double dbl_DBNDPIV_RATIO;        /*       1e-2 */
00051 extern double dbl_ALTPIV_TOLER;       /*       1e-8 */
00052 //extern double DJZERO_TOLER;/*             1e-8 */
00053 extern double dbl_PROGRESS_ZERO;        /*       1e-7 */
00054 extern double dbl_PROGRESS_THRESH;      /*       1e-5 */
00055 extern double dbl_CB_EPS;             /*      0.001 */
00056 extern double dbl_CB_INF_RATIO;       /*       10.0 */
00057 extern double dbl_CB_PRI_RLIMIT;        /*       0.25 */
00058 
00059 /* structure for statistics */
00060 typedef struct
00061 {
00062   int ynz_cnt;                  /* nz in entering columns */
00063   int num_y;
00064   double y_ravg;              /* weighted avg. of current & prior y */
00065   int znz_cnt;                  /* nz in ith row of B^{-1}, ie z_i */
00066   int num_z;
00067   double z_ravg;              /* weighted avg. of current & prior z */
00068   int zanz_cnt;                 /* nz in z^TA */
00069   int num_za;
00070   double za_ravg;           /* weighted avg. of current & prior za */
00071   int pnorm_cnt;                /* nz in columns for primal norms */
00072   int dnorm_cnt;                /* nz in rows for dual norms */
00073   int pinz_cnt;                 /* nz in phase II pi (solve) */
00074   int num_pi;                   /* # of pi solves */
00075   int pi1nz_cnt;                /* nz in phase I pi (solve) */
00076   int num_pi1;                  /* # of phase I pi solves */
00077   int upnz_cnt;                 /* nz in ftran update vector */
00078   int num_up;                   /* # of ftran_updates */
00079   int pupv_cnt;                 /* nz in primal steep updates */
00080   int dupv_cnt;                 /* nz in dual steep updates */
00081 
00082   int start_slacks;             /* # slacks in beginning */
00083   int final_slacks;             /* # slacks in the end */
00084   int start_art;                /* # arts in beginning */
00085   int final_art;                /* # arts in the end */
00086 
00087   int pI_iter;                  /* primal phase I iterations */
00088   int pII_iter;
00089   int dI_iter;                  /* dual phase I iterations */
00090   int dII_iter;
00091   int tot_iter;
00092 
00093   int pivpI[10];                /* sizes of pivots */
00094   int pivpII[10];
00095   int pivdI[10];
00096   int pivdII[10];
00097 }
00098 dbl_count_struct;
00099 
00100 /* structure for tolerances */
00101 typedef struct
00102 {
00103   double pfeas_tol;
00104   double dfeas_tol;
00105   double pivot_tol;
00106   double szero_tol;
00107   double ip_tol;              /* inner primal & dual feas toler */
00108   double id_tol;
00109 }
00110 dbl_tol_struct;
00111 
00112 /* bound information */
00113 typedef struct dbl_bndinfo
00114 {
00115   double pbound;
00116   double cbound;
00117   int btype;
00118   int varnum;
00119   struct dbl_bndinfo *next;
00120 }
00121 dbl_bndinfo;
00122 
00123 /* bound information */
00124 typedef struct dbl_coefinfo
00125 {
00126   double pcoef;
00127   double ccoef;
00128   int varnum;
00129   struct dbl_coefinfo *next;
00130 }
00131 dbl_coefinfo;
00132 
00133 /* feasibility info */
00134 typedef struct dbl_feas_info
00135 {
00136   int pstatus;
00137   int dstatus;
00138   double totinfeas;
00139 }
00140 dbl_feas_info;
00141 
00142 typedef struct dbl_lp_status_info
00143 {
00144   char optimal;
00145   char primal_feasible;
00146   char primal_infeasible;
00147   char primal_unbounded;
00148   char dual_feasible;
00149   char dual_infeasible;
00150   char dual_unbounded;
00151   char padd;
00152 }
00153 dbl_lp_status_info;
00154 
00155 typedef struct dbl_pI_uinfo
00156 {
00157   int tctr;
00158   int i;
00159   int *perm;
00160   int *ix;
00161   int fs;
00162   double piv;
00163   double *t;
00164   double dty;
00165   double c_obj;
00166   double tz;
00167 }
00168 dbl_pI_uinfo;
00169 
00170 extern void dbl_ILLlp_status_info_init (
00171   dbl_lp_status_info * ls);
00172 
00173 /* structure for local lp information
00174  * contains lp obj values - status - dimensions - input data -
00175  * solution vecs - basis info - update vecs - work vecs - bound changes -
00176  * tolerances - time info - statistics 
00177  */
00178 typedef struct dbl_lpinfo
00179 {
00180 
00181   double objval;              /* obj info */
00182   double pobjval;           /* intermediate status info */
00183   double dobjval;
00184   double pinfeas;
00185   double dinfeas;
00186   double objbound;
00187   dbl_lp_status_info probstat;      /* final status */
00188   dbl_lp_status_info basisstat;     /* final status */
00189   int nrows;                    /* input info follows; given in col format */
00190   int ncols;
00191   int *matcnt;
00192   int *matbeg;
00193   int *matind;
00194   double *matval;
00195   int matfree;
00196   int matsize;
00197   double *bz;
00198   double *lz;
00199   double *uz;
00200   double *cz;
00201   int localrows;                /* set to 1 if these are created locally */
00202   int *rowcnt;                  /* row info follows, copy of col info */
00203   int *rowbeg;
00204   int *rowind;
00205   double *rowval;
00206 
00207   double *xbz;                /* output info x, pi, reduced cost */
00208   double *piz;
00209   double *dz;
00210   double *pIxbz;              /* output info (phase I) x, pi, reduced cost */
00211   double *pIpiz;
00212   double *pIdz;
00213 
00214   int final_phase;              /* final phase, inf & unboundedness info */
00215   int infub_ix;
00216 
00217   int basisid;                  /* basis and variable info follows */
00218   int nnbasic;
00219   int *baz;
00220   int *nbaz;
00221   int *vstat;
00222   int *vindex;
00223   int fbasisid;
00224   dbl_factor_work *f;
00225   int *vtype;                   /* internal var info */
00226   char *vclass;                 /* structural or logical */
00227 
00228   dbl_svector zz;                   /* local dbl_ILLfactor_update vectors z, yj, za */
00229   dbl_svector yjz;
00230   dbl_svector zA;
00231   dbl_svector work;                 /* local work vector */
00232   dbl_svector srhs;                 /* local vectors for lin. eq. solves */
00233   dbl_svector ssoln;
00234   int *iwork;                   /* local work vector */
00235   dbl_pI_uinfo upd;                 /* phase I update info */
00236   int *bfeas;                   /* primal and dual infeasibility info */
00237   int *dfeas;
00238 
00239   dbl_tol_struct *tol;              /* tolerances */
00240   dbl_count_struct *cnts;           /* counts */
00241   int nbchange;                 /* # bound shifts */
00242   int ncchange;                 /* # obj coef shifts */
00243   dbl_bndinfo *bchanges;            /* list of bound shifts */
00244   dbl_coefinfo *cchanges;           /* list of coef shifts */
00245   int pIratio;                  /* ratio tests */
00246   int pIIratio;
00247   int dIratio;
00248   int dIIratio;
00249 
00250   int maxiter;
00251   int iterskip;
00252   double maxtime;
00253   double starttime;
00254   struct dbl_ILLlpdata *O;
00255   ILLrandstate rstate;
00256 
00257 }
00258 dbl_lpinfo;
00259 
00260 /* pricing structures */
00261 typedef struct
00262 {
00263   int ninit;
00264   double *norms;
00265   int *refframe;
00266 }
00267 dbl_p_devex_info;
00268 
00269 typedef struct
00270 {
00271   double *norms;
00272 }
00273 dbl_p_steep_info;
00274 
00275 typedef struct
00276 {
00277   int k;
00278   int cgroup;
00279   int ngroups;
00280   int *gstart;
00281   int *gshift;
00282   int *gsize;
00283   int bsize;
00284   int *bucket;
00285   int *perm;
00286   double *infeas;
00287 }
00288 dbl_mpart_info;
00289 
00290 typedef struct
00291 {
00292   int ninit;
00293   double *norms;
00294   int *refframe;
00295 }
00296 dbl_d_devex_info;
00297 
00298 typedef struct
00299 {
00300   double *norms;
00301 }
00302 dbl_d_steep_info;
00303 
00304 /* pricing information */
00305 typedef struct dbl_price_info
00306 {
00307   int p_strategy;
00308   int d_strategy;
00309   int pI_price;
00310   int pII_price;
00311   int dI_price;
00312   int dII_price;
00313   int cur_price;
00314   double *p_scaleinf;
00315   double *d_scaleinf;
00316   dbl_p_devex_info pdinfo;
00317   dbl_p_steep_info psinfo;
00318   dbl_mpart_info pmpinfo;
00319   dbl_d_devex_info ddinfo;
00320   dbl_d_steep_info dsinfo;
00321   dbl_mpart_info dmpinfo;
00322   dbl_heap h;
00323   double htrigger;
00324   int hineff;
00325   char init;
00326 }
00327 dbl_price_info;
00328 
00329 #endif /* dbl___QS_LPDEFS_H */

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