00001 #include "simplex.h"
00002 #include "error.h"
00003 #include "geom.h"
00004 #include "defines.h"
00005
00006 #include <math.h>
00007 #include <string.h>
00008
00022 void SimplexCreate(double epsilon,unsigned int ncols,TSimplex *s)
00023 {
00024 double ct;
00025
00026
00027 s->lp=lpx_create_prob();
00028 if (s->lp==NULL)
00029 Error("Problems creating LP tableau\n");
00030
00031
00032
00033 lpx_add_cols(s->lp,ncols);
00034
00035
00036
00037 #if (_DEBUG<5)
00038 lpx_set_int_parm(s->lp,LPX_K_MSGLEV,0);
00039 #endif
00040
00041
00042
00043 ct=lpx_get_real_parm(s->lp,LPX_K_TOLBND);
00044 if (ct>(epsilon*1e-2))
00045 lpx_set_real_parm(s->lp,LPX_K_TOLBND,epsilon*1e-2);
00046
00047 ct=lpx_get_real_parm(s->lp,LPX_K_TOLDJ);
00048 if (ct>(epsilon*1e-2))
00049 lpx_set_real_parm(s->lp,LPX_K_TOLDJ,epsilon*1e-2);
00050
00051 ct=lpx_get_real_parm(s->lp,LPX_K_TOLPIV);
00052 if (ct>(epsilon*1e-4))
00053 lpx_set_real_parm(s->lp,LPX_K_TOLPIV,epsilon*1e-4);
00054
00055
00056
00057 lpx_set_obj_dir(s->lp,LPX_MIN);
00058
00059
00060
00061 lpx_set_real_parm(s->lp,ncols*LPX_K_TMLIM,SIMPLEX_TIMEOUT);
00062 }
00063
00064
00065 void ResetSimplex(TSimplex *s)
00066 {
00067 lpx_adv_basis(s->lp);
00068 }
00069
00070 unsigned int SimplexNColumns(TSimplex *s)
00071 {
00072 return(lpx_get_num_cols(s->lp));
00073 }
00074
00075 unsigned int SimplexNRows(TSimplex *s)
00076 {
00077 return(lpx_get_num_rows(s->lp));
00078 }
00079
00080
00081 void SimplexSetColBounds(unsigned int ncol,Tinterval *i,TSimplex *s)
00082 {
00083 double l,u;
00084
00085 l=LowerLimit(i);
00086 u=UpperLimit(i);
00087
00088 if (l==-INF)
00089 {
00090 if (u==INF)
00091 lpx_set_col_bnds(s->lp,ncol+1,LPX_FR,0.0,0.0);
00092 else
00093 lpx_set_col_bnds(s->lp,ncol+1,LPX_UP,0.0,u);
00094 }
00095 else
00096 {
00097 if (u==INF)
00098 lpx_set_col_bnds(s->lp,ncol+1,LPX_LO,l,0.0);
00099 else
00100 {
00101 if (u==l)
00102 lpx_set_col_bnds(s->lp,ncol+1,LPX_FX,l,l);
00103 else
00104 lpx_set_col_bnds(s->lp,ncol+1,LPX_DB,l,u);
00105 }
00106 }
00107 }
00108
00109
00110 void SimplexGetColBounds(unsigned int ncol,Tinterval *i,TSimplex *s)
00111 {
00112 unsigned int t;
00113 double l,u;
00114
00115 t=lpx_get_col_type(s->lp,ncol+1);
00116 l=lpx_get_col_lb(s->lp,ncol+1);
00117 u=lpx_get_col_ub(s->lp,ncol+1);
00118
00119 switch(t)
00120 {
00121 case LPX_FR:
00122 NewInterval(-INF,INF,i);
00123 break;
00124 case LPX_LO:
00125 NewInterval(l,INF,i);
00126 break;
00127 case LPX_UP:
00128 NewInterval(-INF,u,i);
00129 break;
00130 case LPX_FX:
00131 case LPX_DB:
00132 NewInterval(l,u,i);
00133 break;
00134 }
00135 }
00136
00137 void SimplexGetColConstraint(unsigned int ncol,TLinearConstraint *lc,TSimplex *s)
00138 {
00139 unsigned int m,k,i;
00140 signed int *ind;
00141 double *val;
00142 Tinterval error;
00143
00144 m=SimplexNRows(s);
00145
00146 NEW(val,m+1,double);
00147 NEW(ind,m+1,signed int);
00148
00149 k=lpx_get_mat_col(s->lp,ncol+1,ind,val);
00150
00151 InitLinearConstraint(lc);
00152 for(i=1;i<=k;i++)
00153 AddTerm2LinearConstraint(ind[i]-1,val[i],lc);
00154
00155 SimplexGetColBounds(ncol,&error,s);
00156 SetLinearConstraintError(&error,lc);
00157
00158 free(ind);
00159 free(val);
00160 }
00161
00162 boolean SimplexColEmpty(unsigned int ncol,TSimplex *s)
00163 {
00164 return((unsigned int)lpx_get_mat_col(s->lp,1+ncol,NULL,NULL)==0);
00165 }
00166
00167 double SimplexGetColPrimal(unsigned int ncol,TSimplex *s)
00168 {
00169 return(lpx_get_col_prim(s->lp,ncol+1));
00170 }
00171
00172 double SimplexGetColDual(unsigned int ncol,TSimplex *s)
00173 {
00174 return(lpx_get_col_dual(s->lp,ncol+1));
00175 }
00176
00177
00178 void SimplexSetRowBounds(unsigned int nrow,Tinterval *i,TSimplex *s)
00179 {
00180 double l,u;
00181
00182 l=LowerLimit(i);
00183 u=UpperLimit(i);
00184
00185 if (l==-INF)
00186 {
00187 if (u==INF)
00188 lpx_set_row_bnds(s->lp,nrow+1,LPX_FR,0.0,0.0);
00189 else
00190 lpx_set_row_bnds(s->lp,nrow+1,LPX_UP,0.0,u);
00191 }
00192 else
00193 {
00194 if (u==INF)
00195 lpx_set_row_bnds(s->lp,nrow+1,LPX_LO,l,0.0);
00196 else
00197 {
00198 if (u==l)
00199 lpx_set_row_bnds(s->lp,nrow+1,LPX_FX,l,l);
00200 else
00201 lpx_set_row_bnds(s->lp,nrow+1,LPX_DB,l,u);
00202 }
00203 }
00204 }
00205
00206
00207 void SimplexGetRowBounds(unsigned int nrow,Tinterval *i,TSimplex *s)
00208 {
00209 unsigned int t;
00210 double l,u;
00211
00212 t=lpx_get_row_type(s->lp,nrow+1);
00213 l=lpx_get_row_lb(s->lp,nrow+1);
00214 u=lpx_get_row_ub(s->lp,nrow+1);
00215
00216 switch(t)
00217 {
00218 case LPX_FR:
00219 NewInterval(-INF,INF,i);
00220 break;
00221 case LPX_LO:
00222 NewInterval(l,INF,i);
00223 break;
00224 case LPX_UP:
00225 NewInterval(-INF,u,i);
00226 break;
00227 case LPX_FX:
00228 case LPX_DB:
00229 NewInterval(l,u,i);
00230 break;
00231 }
00232 }
00233
00234 void SimplexGetRowConstraint(unsigned int nrow,TLinearConstraint *lc,TSimplex *s)
00235 {
00236 unsigned int n,k,i;
00237 signed int *ind;
00238 double *val;
00239 Tinterval error;
00240
00241 n=SimplexNColumns(s);
00242
00243 NEW(val,n+1,double);
00244 NEW(ind,n+1,signed int);
00245
00246 k=lpx_get_mat_row(s->lp,nrow+1,ind,val);
00247
00248 InitLinearConstraint(lc);
00249 for(i=1;i<=k;i++)
00250 AddTerm2LinearConstraint(ind[i]-1,val[i],lc);
00251
00252 SimplexGetRowBounds(nrow,&error,s);
00253 SetLinearConstraintError(&error,lc);
00254
00255 free(ind);
00256 free(val);
00257 }
00258
00259 double SimplexGetRowPrimal(unsigned int nrow,TSimplex *s)
00260 {
00261 return(lpx_get_row_prim(s->lp,nrow+1));
00262 }
00263
00264 double SimplexGetRowDual(unsigned int nrow,TSimplex *s)
00265 {
00266 return(lpx_get_row_dual(s->lp,nrow+1));
00267 }
00268
00269 void SimplexAddNewConstraintRaw(TLinearConstraint *lc,TSimplex *s)
00270 {
00271 Tinterval bounds;
00272 unsigned int nrow;
00273 unsigned int i;
00274 signed int *ind;
00275 double *val;
00276
00277
00278 nrow=lpx_add_rows(s->lp,1);
00279 if (nrow==((unsigned int)(-1)))
00280 Error("Error adding constraint to simplex");
00281
00282 NEW(ind,n+1,signed int);
00283 NEW(val,n+1,double);
00284
00285 for(i=0;i<n;i++)
00286 {
00287 ind[i+1]=GetLinearConstraintVariable(i,lc)+1;
00288 val[i+1]=GetLinearConstraintCoefficient(i,lc);
00289 }
00290
00291
00292 lpx_set_mat_row(s->lp,nrow,n,ind,val);
00293
00294 free(ind);
00295 free(val);
00296
00297 GetLinearConstraintError(&bounds,lc);
00298 SimplexSetRowBounds(nrow-1,&bounds,s);
00299
00300 #if (_DEBUG>4)
00301 printf(" Setting Row %u with range ",nrow-1);
00302 PrintInterval(stdout,&bounds);
00303 printf("\n ");
00304 PrintLinearConstraint(stdout,TRUE,NULL,lc);
00305 #endif
00306 }
00307
00308
00309 void SimplexSetOptimizationFunction(TLinearConstraint *obj,TSimplex *s)
00310 {
00311 unsigned int i,n;
00312
00313 #if (_DEBUG>4)
00314 printf("Setting cost function: ");
00315 #endif
00316
00317 n=SimplexNColumns(s);
00318
00319 for(i=0;i<n;i++)
00320 lpx_set_obj_coef(s->lp,i+1,0.0);
00321
00322 n=GetNumTermsInLinearConstraint(obj);
00323 for(i=0;i<n;i++)
00324 {
00325 #if (_DEBUG>4)
00326 printf("+%f*v[%u]",
00327 GetLinearConstraintCoefficient(i,obj),
00328 GetLinearConstraintVariable(i,obj));
00329 #endif
00330 lpx_set_obj_coef(s->lp,
00331 GetLinearConstraintVariable(i,obj)+1,
00332 GetLinearConstraintCoefficient(i,obj));
00333 }
00334 #if (_DEBUG>4)
00335 printf("\n");
00336 #endif
00337 }
00338
00339
00340 void SimplexGetOptimizationFunction(TLinearConstraint *obj,TSimplex *s)
00341 {
00342 unsigned int i,n;
00343
00344 InitLinearConstraint(obj);
00345
00346 n=SimplexNColumns(s);
00347
00348 for(i=0;i<n;i++)
00349 AddTerm2LinearConstraint(0,i,lpx_get_obj_coef(s->lp,i+1),obj);
00350 }
00351
00352 double SimplexGetOptimalValueRaw(TSimplex *s)
00353 {
00354 return(lpx_get_obj_val(s->lp));
00355 }
00356
00357 unsigned int SimplexSolve(TSimplex *s)
00358 {
00359 unsigned int r;
00360
00361 r=lpx_simplex(s->lp);
00362
00363 if (r==LPX_E_TMLIM)
00364 return(ERROR_IN_PROCESS);
00365 else
00366 {
00367 if (r==LPX_E_OK)
00368 {
00369 r=lpx_get_status(s->lp);
00370
00371 if (r==LPX_OPT)
00372 return(REDUCED_BOX);
00373 else
00374 {
00375 if (r==LPX_NOFEAS)
00376 return(EMPTY_BOX);
00377 else
00378 {
00379 if (r==LPX_UNBND)
00380 return(UNBOUNDED_BOX);
00381 else
00382 return(ERROR_IN_PROCESS);
00383 }
00384 }
00385 }
00386 else
00387 return(ERROR_IN_PROCESS);
00388 }
00389 }
00390
00391 void SimplexDelete(TSimplex *s)
00392 {
00393 lpx_delete_prob(s->lp);
00394 }
00395
00396