simplex_lpsolve.c
Go to the documentation of this file.
1 #include "simplex.h"
2 #include "error.h"
3 #include "geom.h"
4 #include "defines.h"
5 
6 #include <math.h>
7 #include <string.h>
8 
23 void SimplexCreate(double epsilon,unsigned int ncols,TSimplex *s)
24 {
25  double ct;
26 
27  /* LP: Create an empty LP problem */
28  s->lp=make_lp(0,ncols);
29  if (s->lp==NULL)
30  Error("Error creating the simplex (simplex_lpsolve)");
31 
32  /* LP: Adjust the verbosity of the LP problem */
33  #if (_DEBUG<5)
34  set_verbose(s->lp,NEUTRAL);
35  #endif
36 
37  s->inf=get_infinite(s->lp);
38 
39  /* LP: Adjust LP internal parameters */
40  set_presolve(s->lp,PRESOLVE_NONE,0);
41  set_scaling(s->lp,SCALE_NONE);
42 
43  ct=get_epsb(s->lp);
44  if (ct>(epsilon*1e-2))
45  set_epsb(s->lp,ct*1e-2);
46 
47  ct=get_epsd(s->lp);
48  if (ct>(epsilon*1e-2))
49  set_epsd(s->lp,ct*1e-2);
50 
51  ct=get_epsel(s->lp);
52  if (ct>(epsilon*1e-2))
53  set_epsel(s->lp,ct*1e-2);
54 
55  ct=get_epspivot(s->lp);
56  if (ct>(epsilon*1e-4))
57  set_epspivot(s->lp,ct*1e-4);
58 
59  /* LP: Minimize */
60  set_minim(s->lp);
61 
62  /* LP: Timeout in seconds*/
63  set_timeout(s->lp,ncols*SIMPLEX_TIMEOUT);
64 }
65 
66 /* LP: Reset the LP internal information */
68 {
69  default_basis(s->lp);
70 }
71 
72 unsigned int SimplexNColumns(TSimplex *s)
73 {
74  return(get_Ncolumns(s->lp));
75 }
76 
77 unsigned int SimplexNRows(TSimplex *s)
78 {
79  return(get_Nrows(s->lp));
80 }
81 
82 /* LP: set bounds for a given column */
83 void SimplexSetColBounds(unsigned int ncol,Tinterval *i,TSimplex *s)
84 {
85  double l,u;
86  unsigned int ncolInt;
87 
88  ncolInt=ncol+1;
89 
90  l=LowerLimit(i);
91  u=UpperLimit(i);
92 
93  if (l==-INF) l=-s->inf;
94  if (l== INF) l= s->inf;
95  if (u==-INF) u=-s->inf;
96  if (u== INF) u= s->inf;
97 
98  set_lowbo(s->lp,ncolInt,l);
99  set_upbo(s->lp,ncolInt,u);
100 }
101 
102 /* LP: get bounds for a given column */
103 void SimplexGetColBounds(unsigned int ncol,Tinterval *i,TSimplex *s)
104 {
105  double l,u;
106  unsigned int ncolInt;
107 
108  ncolInt=ncol+1;
109 
110  l=get_lowbo(s->lp,ncolInt);
111  u=get_upbo(s->lp,ncolInt);
112 
113  if (l==-s->inf) l=-INF;
114  if (l== s->inf) l= INF;
115  if (u==-s->inf) u=-INF;
116  if (u== s->inf) u= INF;
117 
118  NewInterval(l,u,i);
119 }
120 
121 void SimplexGetColConstraint(unsigned int ncol,TLinearConstraint *lc,TSimplex *s)
122 {
123  unsigned int m,i,k;
124  double *val;
125  signed int *ind;
126  Tinterval error;
127 
128  m=SimplexNRows(s);
129 
130  NEW(val,m+1,double);
131  NEW(ind,m+1,signed int);
132 
133  k=get_columnex(s->lp,ncol+1,val,ind);
134 
136  for(i=0;i<k;i++)
137  AddTerm2LinearConstraint(ind[i]-1,val[i],lc);
138 
139  SimplexGetColBounds(ncol,&error,s);
140  SetLinearConstraintError(&error,lc);
141 
142  free(val);
143  free(ind);
144 }
145 
146 boolean SimplexColEmpty(unsigned int ncol,TSimplex *s)
147 {
148  unsigned int m;
149  double *val;
150  signed int *ind;
151  signed int k;
152 
153  m=SimplexNRows(s);
154 
155  NEW(val,m+1,double);
156  NEW(ind,m+1,signed int);
157 
158  k=get_columnex(s->lp,ncol+1,val,ind);
159 
160  free(val);
161  free(ind);
162 
163  return(k==0);
164 }
165 
166 double SimplexGetColPrimal(unsigned int ncol,TSimplex *s)
167 {
168  return(get_var_primalresult(s->lp,1+SimplexNRows(s)+ncol));
169 }
170 
171 double SimplexGetColDual(unsigned int ncol,TSimplex *s)
172 {
173  return(get_var_dualresult(s->lp,1+SimplexNRows(s)+ncol));
174 }
175 
176 /* LP: set bounds for a given row */
177 void SimplexSetRowBounds(unsigned int nrow,Tinterval *i,TSimplex *s)
178 {
179  double l,u;
180  int t;
181  unsigned int nrowInt;
182 
183  nrowInt=nrow+1;
184 
185  t=get_constr_type(s->lp,nrowInt);
186 
187  l=LowerLimit(i);
188  u=UpperLimit(i);
189 
190  if (l==-INF)
191  {
192  if (u==INF)
193  {
194  set_constr_type(s->lp,nrowInt,GE);
195  set_rh(s->lp,nrowInt,-s->inf);
196  set_rh_range(s->lp,nrowInt,s->inf);
197  }
198  else
199  {
200  set_constr_type(s->lp,nrowInt,LE);
201  set_rh(s->lp,nrowInt,u);
202  }
203  }
204  else
205  {
206  if (u==INF)
207  {
208  set_constr_type(s->lp,nrowInt,GE);
209  set_rh(s->lp,nrowInt,l);
210  }
211  else
212  {
213  if (u==l)
214  {
215  set_constr_type(s->lp,nrowInt,EQ);
216  set_rh(s->lp,nrowInt,l);
217  }
218  else
219  {
220  set_constr_type(s->lp,nrowInt,GE);
221  set_rh(s->lp,nrowInt,l);
222  set_rh_range(s->lp,nrowInt,IntervalSize(i));
223  }
224  }
225  }
226 }
227 
228 /* LP: get bounds for a given row */
229 void SimplexGetRowBounds(unsigned int nrow,Tinterval *i,TSimplex *s)
230 {
231  signed int t;
232  double r,g;
233  unsigned int nrowInt;
234 
235  nrowInt=nrow+1;
236 
237  t=get_constr_type(s->lp,nrowInt);
238  r=get_rh(s->lp,nrowInt);
239  g=get_rh_range(s->lp,nrowInt);
240 
241  switch(t)
242  {
243  case LE:
244  if (g==s->inf)
245  NewInterval(-INF,r,i);
246  else
247  NewInterval(r-g,r,i);
248  break;
249  case GE:
250  if (g==s->inf)
251  {
252  if (r==-s->inf)
253  NewInterval(-INF,INF,i);
254  else
255  NewInterval(r,INF,i);
256  }
257  else
258  NewInterval(r,r+g,i);
259  break;
260  case EQ:
261  if (g==s->inf)
262  NewInterval(r,r,i);
263  else
264  NewInterval(r,r+g,i);
265  break;
266  }
267 }
268 
269 void SimplexGetRowConstraint(unsigned int nrow,TLinearConstraint *lc,TSimplex *s)
270 {
271  unsigned int i,n,m;
272  unsigned int nrowInt;
273  double *val;
274  Tinterval error;
275 
276  nrowInt=nrow+1;
277 
279 
280  n=SimplexNColumns(s);
281  m=SimplexNRows(s);
282 
283  NEW(val,m+1,double);
284 
285  for(i=1;i<=n;i++)
286  {
287  get_column(s->lp,i,val);
288  AddTerm2LinearConstraint(i-1,val[nrowInt],lc);
289  }
290  free(val);
291 
292  SimplexGetRowBounds(nrow,&error,s);
293  SetLinearConstraintError(&error,lc);
294 }
295 
296 
297 double SimplexGetRowPrimal(unsigned int nrow,TSimplex *s)
298 {
299  return(get_var_primalresult(s->lp,1+nrow));
300 }
301 
302 double SimplexGetRowDual(unsigned int nrow,TSimplex *s)
303 {
304  return(get_var_dualresult(s->lp,1+nrow));
305 }
306 
308 {
309  Tinterval bounds;
310  unsigned int nrow;
311  unsigned int i;
312  signed int *ind;
313 
314  /* LP: Add a row to the tableau */
315  nrow=SimplexNRows(s); /* number of the row to be added next */
316 
317  NEW(ind,n,signed int);
318  for(i=0;i<n;i++)
319  ind[i]=(signed int)GetLinearConstraintVariable(i,lc)+1;
320 
321  /* LP: set the row information */
322  add_constraintex(s->lp,n,
324  ind,
325  EQ,0);
326 
327  free(ind);
328 
329  GetLinearConstraintError(&bounds,lc);
330  SimplexSetRowBounds(nrow,&bounds,s);
331 
332 #if (_DEBUG>4)
333  printf(" Setting Row %u with range ",nrow);
334  PrintInterval(stdout,&bounds);
335  printf("\n ");
336  PrintLinearConstraint(stdout,TRUE,NULL,lc);
337 #endif
338 }
339 
341 {
342  unsigned int i,n;
343  signed int *ind;
344 
345  #if (_DEBUG>4)
346  printf("Setting cost function: ");
347  #endif
348 
350 
351  #if (_DEBUG>4)
352  for(i=0;i<n;i++)
353  {
354  printf("+%f*v[%u]",
357  }
358  #endif
359 
360  NEW(ind,n,signed int);
361  for(i=0;i<n;i++)
362  ind[i]=(signed int)GetLinearConstraintVariable(i,obj)+1;
363 
364  set_obj_fnex(s->lp,n,
366  ind);
367  free(ind);
368 
369  #if (_DEBUG>4)
370  printf("\n");
371  #endif
372 }
373 
375 {
376  unsigned int i,n,m;
377  double *val;
378 
380 
381  n=SimplexNColumns(s);
382  m=SimplexNRows(s);
383 
384  NEW(val,m+1,double);
385 
386  for(i=1;i<=n;i++)
387  {
388  get_column(s->lp,i,val);
389  AddTerm2LinearConstraint(0,i-1,val[0],obj);
390  }
391  free(val);
392 }
393 
395 {
396  return(get_objective(s->lp));
397 }
398 
399 unsigned int SimplexSolve(TSimplex *s)
400 {
401  unsigned int r;
402 
403  /*print_lp(s->lp); exit(0);*/
404 
405  r=solve(s->lp);
406 
407  if (r==OPTIMAL)
408  return(REDUCED_BOX);
409  else
410  {
411  if (r==INFEASIBLE)
412  return(EMPTY_BOX);
413  else
414  {
415  if (r==UNBOUNDED)
416  return(UNBOUNDED_BOX);
417  else
418  return(ERROR_IN_PROCESS);
419  }
420  }
421 }
422 
424 {
425  delete_lp(s->lp);
426 }
427 
428 
double SimplexGetColPrimal(unsigned int ncol, TSimplex *s)
Gets a column primal value after solving the simplex.
void SimplexSetColBounds(unsigned int ncol, Tinterval *i, TSimplex *s)
Sets the bounds for a given column (i.e., variable).
void SimplexAddNewConstraintRaw(TLinearConstraint *lc, TSimplex *s)
Adds a row (i.e., a constraint) to the simplex.
void SimplexSetRowBounds(unsigned int nrow, Tinterval *i, TSimplex *s)
Sets the bounds for a given row (i.e., constraint).
double inf
Definition: simplex.h:86
#define ERROR_IN_PROCESS
One of the possible results of reducing a box.
Definition: box.h:32
Definition of basic functions.
double * GetLinearConstraintCoefficients(TLinearConstraint *lc)
Gets the linear constraint coefficients.
void SimplexGetColBounds(unsigned int ncol, Tinterval *i, TSimplex *s)
Gets the bounds for a given column (i.e., variable).
#define UNBOUNDED_BOX
One of the possible results of reducing a box.
Definition: box.h:45
#define NEW(_var, _n, _type)
Allocates memory space.
Definition: defines.h:385
A linear constraint with an associated error.
void InitLinearConstraint(TLinearConstraint *lc)
Constructor.
#define EMPTY_BOX
One of the possible results of reducing a box.
Definition: box.h:25
void ResetSimplex(TSimplex *s)
Resets the simplex structure.
unsigned int GetLinearConstraintVariable(unsigned int i, TLinearConstraint *lc)
Gets the a particular variable index.
void PrintLinearConstraint(FILE *f, boolean eq, char **varName, TLinearConstraint *lc)
Prints a linear constraint.
#define TRUE
TRUE.
Definition: boolean.h:21
unsigned int SimplexNColumns(TSimplex *s)
Gets the number of columns (i.e., variables) of the simplex structure.
void Error(const char *s)
General error function.
Definition: error.c:80
SimplexType * lp
Definition: simplex.h:75
A simplex tableau structure.
Definition: simplex.h:73
void AddTerm2LinearConstraint(unsigned int ind, double val, TLinearConstraint *lc)
Adds a scaled variable to the linear constraint.
unsigned int SimplexNRows(TSimplex *s)
Gets the number of rows (i.e., constraints) of the simplex structure.
double SimplexGetOptimalValueRaw(TSimplex *s)
Gets the optimal value after optimizing the problem.
Error and warning functions.
double SimplexGetRowDual(unsigned int nrow, TSimplex *s)
Gets a row dual value after solving the simplex.
void SimplexGetColConstraint(unsigned int ncol, TLinearConstraint *lc, TSimplex *s)
Gets a column from the simplex in the form of a linear constraint.
double LowerLimit(Tinterval *i)
Gets the lower limit.
Definition: interval.c:79
#define SIMPLEX_TIMEOUT
Simplex timeout.
Definition: simplex.h:63
void SimplexGetRowBounds(unsigned int nrow, Tinterval *i, TSimplex *s)
Gets the bounds for a given row (i.e., constraint).
Definitions of constants and macros used in several parts of the cuik library.
void SimplexGetRowConstraint(unsigned int nrow, TLinearConstraint *lc, TSimplex *s)
Gets a row constraint from the simplex.
double UpperLimit(Tinterval *i)
Gets the uppser limit.
Definition: interval.c:87
void SimplexCreate(double epsilon, unsigned int ncols, TSimplex *s)
Constructor.
double SimplexGetColDual(unsigned int ncol, TSimplex *s)
Gets a column dual value after solving the simplex.
double SimplexGetRowPrimal(unsigned int nrow, TSimplex *s)
Gets a row primal value after solving the simplex.
unsigned int GetNumTermsInLinearConstraint(TLinearConstraint *lc)
Number of variables in a linear constraint.
void GetLinearConstraintError(Tinterval *error, TLinearConstraint *lc)
Gets the right-hand side interval for the linear constraint.
Definition of the TSimplex type and the associated functions.
void PrintInterval(FILE *f, Tinterval *i)
Prints an interval.
Definition: interval.c:1006
void SetLinearConstraintError(Tinterval *error, TLinearConstraint *lc)
Sets a new righ-hand side error of the linear constraint.
boolean SimplexColEmpty(unsigned int ncol, TSimplex *s)
Checks if a simplex column is empty.
void NewInterval(double lower, double upper, Tinterval *i)
Constructor.
Definition: interval.c:47
#define INF
Infinite.
Definition: defines.h:70
double GetLinearConstraintCoefficient(unsigned int i, TLinearConstraint *lc)
Gets the a particular linear constraint coefficient.
#define REDUCED_BOX
One of the possible results of reducing a box.
Definition: box.h:38
void SimplexGetOptimizationFunction(TLinearConstraint *obj, TSimplex *s)
Gets a current objective function.
Defines a interval.
Definition: interval.h:33
double IntervalSize(Tinterval *i)
Gets the uppser limit.
Definition: interval.c:96
void SimplexDelete(TSimplex *s)
Destructor.
unsigned int SimplexSolve(TSimplex *s)
Determines an optimal value.
void SimplexSetOptimizationFunction(TLinearConstraint *obj, TSimplex *s)
Sets a new objective function.