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: lpdefs.h,v 1.3 2003/11/05 16:57:39 meven Exp $ */ 00024 #ifndef __QS_LPDEFS_H 00025 #define __QS_LPDEFS_H 00026 00027 #include "qsopt.h" 00028 #include "lpdata.h" 00029 #include "factor.h" 00030 00031 /* infinity and negative infinity */ 00032 #define INFTY ILL_MAXDOUBLE 00033 #define NINFTY ILL_MINDOUBLE 00034 00035 #include "basicdefs.h" 00036 /* tolerances, these are initialized in ILLstart, file lpdata.c */ 00037 //#if EGLPNUM_TYPE != DBL_TYPE && EGLPNUM_TYPE != LDBL_TYPE 00038 /* these three constants are defined in lpdata.c */ 00039 extern EGlpNum_t PARAM_IBASIS_RPIVOT; /* 0.98 */ 00040 extern EGlpNum_t PARAM_IBASIS_RTRIANG;/* 0.01 */ 00041 extern EGlpNum_t PARAM_MIN_DNORM; /* 1e-24 */ 00042 extern EGlpNum_t PFEAS_TOLER; /* 1e-6 */ 00043 extern EGlpNum_t BD_TOLER; /* 1e-7 */ 00044 extern EGlpNum_t DFEAS_TOLER; /* 1e-6 */ 00045 extern EGlpNum_t PIVOT_TOLER; /* 1e-10 */ 00046 extern EGlpNum_t SZERO_TOLER; /* 1e-15 */ 00047 extern EGlpNum_t PIVZ_TOLER; /* 1e-12 */ 00048 extern EGlpNum_t OBJBND_TOLER; /* 1e-2 */ 00049 extern EGlpNum_t DBNDPIV_TOLER; /* 1e-3 */ 00050 extern EGlpNum_t DBNDPIV_RATIO; /* 1e-2 */ 00051 extern EGlpNum_t ALTPIV_TOLER; /* 1e-8 */ 00052 //extern EGlpNum_t DJZERO_TOLER;/* 1e-8 */ 00053 extern EGlpNum_t PROGRESS_ZERO; /* 1e-7 */ 00054 extern EGlpNum_t PROGRESS_THRESH; /* 1e-5 */ 00055 extern EGlpNum_t CB_EPS; /* 0.001 */ 00056 extern EGlpNum_t CB_INF_RATIO; /* 10.0 */ 00057 extern EGlpNum_t 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 EGlpNum_t 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 EGlpNum_t z_ravg; /* weighted avg. of current & prior z */ 00068 int zanz_cnt; /* nz in z^TA */ 00069 int num_za; 00070 EGlpNum_t 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 count_struct; 00099 00100 /* structure for tolerances */ 00101 typedef struct 00102 { 00103 EGlpNum_t pfeas_tol; 00104 EGlpNum_t dfeas_tol; 00105 EGlpNum_t pivot_tol; 00106 EGlpNum_t szero_tol; 00107 EGlpNum_t ip_tol; /* inner primal & dual feas toler */ 00108 EGlpNum_t id_tol; 00109 } 00110 tol_struct; 00111 00112 /* bound information */ 00113 typedef struct bndinfo 00114 { 00115 EGlpNum_t pbound; 00116 EGlpNum_t cbound; 00117 int btype; 00118 int varnum; 00119 struct bndinfo *next; 00120 } 00121 bndinfo; 00122 00123 /* bound information */ 00124 typedef struct coefinfo 00125 { 00126 EGlpNum_t pcoef; 00127 EGlpNum_t ccoef; 00128 int varnum; 00129 struct coefinfo *next; 00130 } 00131 coefinfo; 00132 00133 /* feasibility info */ 00134 typedef struct feas_info 00135 { 00136 int pstatus; 00137 int dstatus; 00138 EGlpNum_t totinfeas; 00139 } 00140 feas_info; 00141 00142 typedef struct 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 lp_status_info; 00154 00155 typedef struct pI_uinfo 00156 { 00157 int tctr; 00158 int i; 00159 int *perm; 00160 int *ix; 00161 int fs; 00162 EGlpNum_t piv; 00163 EGlpNum_t *t; 00164 EGlpNum_t dty; 00165 EGlpNum_t c_obj; 00166 EGlpNum_t tz; 00167 } 00168 pI_uinfo; 00169 00170 extern void ILLlp_status_info_init ( 00171 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 lpinfo 00179 { 00180 00181 EGlpNum_t objval; /* obj info */ 00182 EGlpNum_t pobjval; /* intermediate status info */ 00183 EGlpNum_t dobjval; 00184 EGlpNum_t pinfeas; 00185 EGlpNum_t dinfeas; 00186 EGlpNum_t objbound; 00187 lp_status_info probstat; /* final status */ 00188 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 EGlpNum_t *matval; 00195 int matfree; 00196 int matsize; 00197 EGlpNum_t *bz; 00198 EGlpNum_t *lz; 00199 EGlpNum_t *uz; 00200 EGlpNum_t *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 EGlpNum_t *rowval; 00206 00207 EGlpNum_t *xbz; /* output info x, pi, reduced cost */ 00208 EGlpNum_t *piz; 00209 EGlpNum_t *dz; 00210 EGlpNum_t *pIxbz; /* output info (phase I) x, pi, reduced cost */ 00211 EGlpNum_t *pIpiz; 00212 EGlpNum_t *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 factor_work *f; 00225 int *vtype; /* internal var info */ 00226 char *vclass; /* structural or logical */ 00227 00228 svector zz; /* local ILLfactor_update vectors z, yj, za */ 00229 svector yjz; 00230 svector zA; 00231 svector work; /* local work vector */ 00232 svector srhs; /* local vectors for lin. eq. solves */ 00233 svector ssoln; 00234 int *iwork; /* local work vector */ 00235 pI_uinfo upd; /* phase I update info */ 00236 int *bfeas; /* primal and dual infeasibility info */ 00237 int *dfeas; 00238 00239 tol_struct *tol; /* tolerances */ 00240 count_struct *cnts; /* counts */ 00241 int nbchange; /* # bound shifts */ 00242 int ncchange; /* # obj coef shifts */ 00243 bndinfo *bchanges; /* list of bound shifts */ 00244 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 ILLlpdata *O; 00255 ILLrandstate rstate; 00256 00257 } 00258 lpinfo; 00259 00260 /* pricing structures */ 00261 typedef struct 00262 { 00263 int ninit; 00264 EGlpNum_t *norms; 00265 int *refframe; 00266 } 00267 p_devex_info; 00268 00269 typedef struct 00270 { 00271 EGlpNum_t *norms; 00272 } 00273 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 EGlpNum_t *infeas; 00287 } 00288 mpart_info; 00289 00290 typedef struct 00291 { 00292 int ninit; 00293 EGlpNum_t *norms; 00294 int *refframe; 00295 } 00296 d_devex_info; 00297 00298 typedef struct 00299 { 00300 EGlpNum_t *norms; 00301 } 00302 d_steep_info; 00303 00304 /* pricing information */ 00305 typedef struct 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 EGlpNum_t *p_scaleinf; 00315 EGlpNum_t *d_scaleinf; 00316 p_devex_info pdinfo; 00317 p_steep_info psinfo; 00318 mpart_info pmpinfo; 00319 d_devex_info ddinfo; 00320 d_steep_info dsinfo; 00321 mpart_info dmpinfo; 00322 heap h; 00323 EGlpNum_t htrigger; 00324 int hineff; 00325 char init; 00326 } 00327 price_info; 00328 00329 #endif /* __QS_LPDEFS_H */
1.4.7