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 */
1.5.2