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
00023 void SimplexCreate(double epsilon,unsigned int ncols,TSimplex *s)
00024 {
00025 double ct;
00026
00027
00028 s->lp=make_lp(0,ncols);
00029 if (s->lp==NULL)
00030 Error("Error creating the simplex (simplex_lpsolve)");
00031
00032
00033 #if (_DEBUG<5)
00034 set_verbose(s->lp,NEUTRAL);
00035 #endif
00036
00037 s->inf=get_infinite(s->lp);
00038
00039
00040 set_presolve(s->lp,PRESOLVE_NONE,0);
00041 set_scaling(s->lp,SCALE_NONE);
00042
00043 ct=get_epsb(s->lp);
00044 if (ct>(epsilon*1e-2))
00045 set_epsb(s->lp,ct*1e-2);
00046
00047 ct=get_epsd(s->lp);
00048 if (ct>(epsilon*1e-2))
00049 set_epsd(s->lp,ct*1e-2);
00050
00051 ct=get_epsel(s->lp);
00052 if (ct>(epsilon*1e-2))
00053 set_epsel(s->lp,ct*1e-2);
00054
00055 ct=get_epspivot(s->lp);
00056 if (ct>(epsilon*1e-4))
00057 set_epspivot(s->lp,ct*1e-4);
00058
00059
00060 set_minim(s->lp);
00061
00062
00063 set_timeout(s->lp,ncols*SIMPLEX_TIMEOUT);
00064 }
00065
00066
00067 void ResetSimplex(TSimplex *s)
00068 {
00069 default_basis(s->lp);
00070 }
00071
00072 unsigned int SimplexNColumns(TSimplex *s)
00073 {
00074 return(get_Ncolumns(s->lp));
00075 }
00076
00077 unsigned int SimplexNRows(TSimplex *s)
00078 {
00079 return(get_Nrows(s->lp));
00080 }
00081
00082
00083 void SimplexSetColBounds(unsigned int ncol,Tinterval *i,TSimplex *s)
00084 {
00085 double l,u;
00086 unsigned int ncolInt;
00087
00088 ncolInt=ncol+1;
00089
00090 l=LowerLimit(i);
00091 u=UpperLimit(i);
00092
00093 if (l==-INF) l=-s->inf;
00094 if (l== INF) l= s->inf;
00095 if (u==-INF) u=-s->inf;
00096 if (u== INF) u= s->inf;
00097
00098 set_lowbo(s->lp,ncolInt,l);
00099 set_upbo(s->lp,ncolInt,u);
00100 }
00101
00102
00103 void SimplexGetColBounds(unsigned int ncol,Tinterval *i,TSimplex *s)
00104 {
00105 double l,u;
00106 unsigned int ncolInt;
00107
00108 ncolInt=ncol+1;
00109
00110 l=get_lowbo(s->lp,ncolInt);
00111 u=get_upbo(s->lp,ncolInt);
00112
00113 if (l==-s->inf) l=-INF;
00114 if (l== s->inf) l= INF;
00115 if (u==-s->inf) u=-INF;
00116 if (u== s->inf) u= INF;
00117
00118 NewInterval(l,u,i);
00119 }
00120
00121 void SimplexGetColConstraint(unsigned int ncol,TLinearConstraint *lc,TSimplex *s)
00122 {
00123 unsigned int m,i,k;
00124 double *val;
00125 signed int *ind;
00126 Tinterval error;
00127
00128 m=SimplexNRows(s);
00129
00130 NEW(val,m+1,double);
00131 NEW(ind,m+1,signed int);
00132
00133 k=get_columnex(s->lp,ncol+1,val,ind);
00134
00135 InitLinearConstraint(lc);
00136 for(i=0;i<k;i++)
00137 AddTerm2LinearConstraint(ind[i]-1,val[i],lc);
00138
00139 SimplexGetColBounds(ncol,&error,s);
00140 SetLinearConstraintError(&error,lc);
00141
00142 free(val);
00143 free(ind);
00144 }
00145
00146 boolean SimplexColEmpty(unsigned int ncol,TSimplex *s)
00147 {
00148 unsigned int m;
00149 double *val;
00150 signed int *ind;
00151 signed int k;
00152
00153 m=SimplexNRows(s);
00154
00155 NEW(val,m+1,double);
00156 NEW(ind,m+1,signed int);
00157
00158 k=get_columnex(s->lp,ncol+1,val,ind);
00159
00160 free(val);
00161 free(ind);
00162
00163 return(k==0);
00164 }
00165
00166 double SimplexGetColPrimal(unsigned int ncol,TSimplex *s)
00167 {
00168 return(get_var_primalresult(s->lp,1+SimplexNRows(s)+ncol));
00169 }
00170
00171 double SimplexGetColDual(unsigned int ncol,TSimplex *s)
00172 {
00173 return(get_var_dualresult(s->lp,1+SimplexNRows(s)+ncol));
00174 }
00175
00176
00177 void SimplexSetRowBounds(unsigned int nrow,Tinterval *i,TSimplex *s)
00178 {
00179 double l,u;
00180 int t;
00181 unsigned int nrowInt;
00182
00183 nrowInt=nrow+1;
00184
00185 t=get_constr_type(s->lp,nrowInt);
00186
00187 l=LowerLimit(i);
00188 u=UpperLimit(i);
00189
00190 if (l==-INF)
00191 {
00192 if (u==INF)
00193 {
00194 set_constr_type(s->lp,nrowInt,GE);
00195 set_rh(s->lp,nrowInt,-s->inf);
00196 set_rh_range(s->lp,nrowInt,s->inf);
00197 }
00198 else
00199 {
00200 set_constr_type(s->lp,nrowInt,LE);
00201 set_rh(s->lp,nrowInt,u);
00202 }
00203 }
00204 else
00205 {
00206 if (u==INF)
00207 {
00208 set_constr_type(s->lp,nrowInt,GE);
00209 set_rh(s->lp,nrowInt,l);
00210 }
00211 else
00212 {
00213 if (u==l)
00214 {
00215 set_constr_type(s->lp,nrowInt,EQ);
00216 set_rh(s->lp,nrowInt,l);
00217 }
00218 else
00219 {
00220 set_constr_type(s->lp,nrowInt,GE);
00221 set_rh(s->lp,nrowInt,l);
00222 set_rh_range(s->lp,nrowInt,IntervalSize(i));
00223 }
00224 }
00225 }
00226 }
00227
00228
00229 void SimplexGetRowBounds(unsigned int nrow,Tinterval *i,TSimplex *s)
00230 {
00231 signed int t;
00232 double r,g;
00233 unsigned int nrowInt;
00234
00235 nrowInt=nrow+1;
00236
00237 t=get_constr_type(s->lp,nrowInt);
00238 r=get_rh(s->lp,nrowInt);
00239 g=get_rh_range(s->lp,nrowInt);
00240
00241 switch(t)
00242 {
00243 case LE:
00244 if (g==s->inf)
00245 NewInterval(-INF,r,i);
00246 else
00247 NewInterval(r-g,r,i);
00248 break;
00249 case GE:
00250 if (g==s->inf)
00251 {
00252 if (r==-s->inf)
00253 NewInterval(-INF,INF,i);
00254 else
00255 NewInterval(r,INF,i);
00256 }
00257 else
00258 NewInterval(r,r+g,i);
00259 break;
00260 case EQ:
00261 if (g==s->inf)
00262 NewInterval(r,r,i);
00263 else
00264 NewInterval(r,r+g,i);
00265 break;
00266 }
00267 }
00268
00269 void SimplexGetRowConstraint(unsigned int nrow,TLinearConstraint *lc,TSimplex *s)
00270 {
00271 unsigned int i,n,m;
00272 unsigned int nrowInt;
00273 double *val;
00274 Tinterval error;
00275
00276 nrowInt=nrow+1;
00277
00278 InitLinearConstraint(lc);
00279
00280 n=SimplexNColumns(s);
00281 m=SimplexNRows(s);
00282
00283 NEW(val,m+1,double);
00284
00285 for(i=1;i<=n;i++)
00286 {
00287 get_column(s->lp,i,val);
00288 AddTerm2LinearConstraint(i-1,val[nrowInt],lc);
00289 }
00290 free(val);
00291
00292 SimplexGetRowBounds(nrow,&error,s);
00293 SetLinearConstraintError(&error,lc);
00294 }
00295
00296
00297 double SimplexGetRowPrimal(unsigned int nrow,TSimplex *s)
00298 {
00299 return(get_var_primalresult(s->lp,1+nrow));
00300 }
00301
00302 double SimplexGetRowDual(unsigned int nrow,TSimplex *s)
00303 {
00304 return(get_var_dualresult(s->lp,1+nrow));
00305 }
00306
00307 void SimplexAddNewConstraintRaw(TLinearConstraint *lc,TSimplex *s)
00308 {
00309 Tinterval bounds;
00310 unsigned int nrow;
00311 unsigned int i;
00312 signed int *ind;
00313
00314
00315 nrow=SimplexNRows(s);
00316
00317 NEW(ind,n,signed int);
00318 for(i=0;i<n;i++)
00319 ind[i]=(signed int)GetLinearConstraintVariable(i,lc)+1;
00320
00321
00322 add_constraintex(s->lp,n,
00323 GetLinearConstraintCoefficients(lc),
00324 ind,
00325 EQ,0);
00326
00327 free(ind);
00328
00329 GetLinearConstraintError(&bounds,lc);
00330 SimplexSetRowBounds(nrow,&bounds,s);
00331
00332 #if (_DEBUG>4)
00333 printf(" Setting Row %u with range ",nrow);
00334 PrintInterval(stdout,&bounds);
00335 printf("\n ");
00336 PrintLinearConstraint(stdout,TRUE,NULL,lc);
00337 #endif
00338 }
00339
00340 void SimplexSetOptimizationFunction(TLinearConstraint *obj,TSimplex *s)
00341 {
00342 unsigned int i,n;
00343 signed int *ind;
00344
00345 #if (_DEBUG>4)
00346 printf("Setting cost function: ");
00347 #endif
00348
00349 n=GetNumTermsInLinearConstraint(obj);
00350
00351 #if (_DEBUG>4)
00352 for(i=0;i<n;i++)
00353 {
00354 printf("+%f*v[%u]",
00355 GetLinearConstraintCoefficient(i,obj),
00356 GetLinearConstraintVariable(i,obj));
00357 }
00358 #endif
00359
00360 NEW(ind,n,signed int);
00361 for(i=0;i<n;i++)
00362 ind[i]=(signed int)GetLinearConstraintVariable(i,obj)+1;
00363
00364 set_obj_fnex(s->lp,n,
00365 GetLinearConstraintCoefficients(obj),
00366 ind);
00367 free(ind);
00368
00369 #if (_DEBUG>4)
00370 printf("\n");
00371 #endif
00372 }
00373
00374 void SimplexGetOptimizationFunction(TLinearConstraint *obj,TSimplex *s)
00375 {
00376 unsigned int i,n,m;
00377 double *val;
00378
00379 InitLinearConstraint(obj);
00380
00381 n=SimplexNColumns(s);
00382 m=SimplexNRows(s);
00383
00384 NEW(val,m+1,double);
00385
00386 for(i=1;i<=n;i++)
00387 {
00388 get_column(s->lp,i,val);
00389 AddTerm2LinearConstraint(0,i-1,val[0],obj);
00390 }
00391 free(val);
00392 }
00393
00394 double SimplexGetOptimalValueRaw(TSimplex *s)
00395 {
00396 return(get_objective(s->lp));
00397 }
00398
00399 unsigned int SimplexSolve(TSimplex *s)
00400 {
00401 unsigned int r;
00402
00403
00404
00405 r=solve(s->lp);
00406
00407 if (r==OPTIMAL)
00408 return(REDUCED_BOX);
00409 else
00410 {
00411 if (r==INFEASIBLE)
00412 return(EMPTY_BOX);
00413 else
00414 {
00415 if (r==UNBOUNDED)
00416 return(UNBOUNDED_BOX);
00417 else
00418 return(ERROR_IN_PROCESS);
00419 }
00420 }
00421 }
00422
00423 void SimplexDelete(TSimplex *s)
00424 {
00425 delete_lp(s->lp);
00426 }
00427
00428