simplex_clp.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 <float.h>
7 #include <math.h>
8 #include <string.h>
9 
22 void SimplexCreate(double epsilon,unsigned int ncols,TSimplex *s)
23 {
24  double ct;
25  unsigned int i;
26 
27  /*Create the problem*/
28  s->lp=Clp_newModel();
29 
30  /*Set the number of columns*/
31  Clp_resize(s->lp,0,ncols);
32 
33  {
34  /*We add a fake row to properly initialize the whole matrix*/
35  double *v;
36  unsigned int *e;
37 
38  double rl[1]={-INF};
39  double ru[1]={ INF};
40  int rs[2]={0,ncols};
41 
42  NEW(v,ncols,double);
43  NEW(e,ncols,unsigned int);
44  for(i=0;i<ncols;i++)
45  {
46  e[i]=i;
47  v[i]=0;
48  }
49 
50  Clp_addRows(s->lp,1,rl,ru,rs,(signed int *)e,v);
51 
52  free(v);
53  free(e);
54 
55  s->fakeRows=1; /* number of fake rows in the tableau */
56  }
57 
58  NEW(s->lower,ncols,double);
59  NEW(s->upper,ncols,double);
60  NEW(s->obj,ncols,double);
61  for(i=0;i<ncols;i++)
62  {
63  s->lower[i]=-INF;
64  s->upper[i]=+INF;
65  s->obj[i]=0;
66  }
67 
68  /*Set the verbosity level*/
69  #if (_DEBUG<5)
70  Clp_setLogLevel(s->lp,0);
71  #endif
72 
73  /* LP: Adjust LP internal parameters */
74  Clp_scaling(s->lp,0);
75 
76  ct=Clp_primalTolerance(s->lp);
77  if (ct>(epsilon*1e-3))
78  Clp_setPrimalTolerance(s->lp,epsilon*1e-3);
79 
80  ct=Clp_dualTolerance(s->lp);
81  if (ct>(epsilon*1e-3))
82  Clp_setDualTolerance(s->lp,epsilon*1e-3);
83 
84  ct=Clp_getSmallElementValue(s->lp);
85  if (ct>epsilon)
86  Clp_setSmallElementValue(s->lp,epsilon);
87 
88  /* LP: Minimize */
89  Clp_setOptimizationDirection(s->lp,1);
90 
91  /* LP: Timeout in seconds*/
92  Clp_setMaximumSeconds(s->lp,ncols*SIMPLEX_TIMEOUT);
93 }
94 
95 /* LP: Reset the LP internal information */
97 {
98  /* An empty ResetSimplex functions means that SAFE_SIMPLEX levels
99  1,2,and 3 are equivalent */
100 }
101 
102 unsigned int SimplexNColumns(TSimplex *s)
103 {
104  return((unsigned int)Clp_numberColumns(s->lp));
105 }
106 
107 unsigned int SimplexNRows(TSimplex *s)
108 {
109  return((unsigned int)Clp_numberRows(s->lp)-s->fakeRows);
110 }
111 
112 /* LP: set bounds for a given column */
113 void SimplexSetColBounds(unsigned int ncol,Tinterval *i,TSimplex *s)
114 {
115  s->lower[ncol]=LowerLimit(i);
116  s->upper[ncol]=UpperLimit(i);
117 
118  Clp_chgColumnLower(s->lp,s->lower);
119  Clp_chgColumnUpper(s->lp,s->upper);
120 }
121 
122 /* LP: get bounds for a given column */
123 void SimplexGetColBounds(unsigned int ncol,Tinterval *i,TSimplex *s)
124 {
125  double *colUpper,*colLower;
126 
127  colLower=Clp_columnLower(s->lp);
128  colUpper=Clp_columnUpper(s->lp);
129 
130  NewInterval(colLower[ncol],colUpper[ncol],i);
131 }
132 
133 void SimplexGetColConstraint(unsigned int ncol,TLinearConstraint *lc,TSimplex *s)
134 {
135  Tinterval error;
136  const double *elements;
137  const int *rowIndices;
138  const int *columnLengths;
139  const CoinBigIndex *columnStarts;
140  CoinBigIndex a,b,i;
141 
142  rowIndices=Clp_getIndices(s->lp);
143  elements=Clp_getElements(s->lp);
144 
145  columnLengths=Clp_getVectorLengths(s->lp);
146  columnStarts=Clp_getVectorStarts(s->lp);
147 
148  a=columnStarts[ncol];
149  b=a+columnLengths[ncol];
150 
152  for(i=a;i<b;++i)
153  AddTerm2LinearConstraint((unsigned int)rowIndices[i],elements[i],lc);
154 
155  SimplexGetColBounds(ncol,&error,s);
156  SetLinearConstraintError(&error,lc);
157 }
158 
159 boolean SimplexColEmpty(unsigned int ncol,TSimplex *s)
160 {
161  const int *columnLengths;
162 
163  columnLengths=Clp_getVectorLengths(s->lp);
164 
165  return(columnLengths[ncol]==0);
166 }
167 
168 double SimplexGetColPrimal(unsigned int ncol,TSimplex *s)
169 {
170  double *obj;
171 
172  obj=Clp_primalColumnSolution(s->lp);
173 
174  return(obj[ncol]);
175 }
176 
177 double SimplexGetColDual(unsigned int ncol,TSimplex *s)
178 {
179  double *obj;
180 
181  obj=Clp_dualColumnSolution(s->lp);
182 
183  return(obj[ncol]);
184 }
185 
186 /* LP: set bounds for a given row */
187 void SimplexSetRowBounds(unsigned int nrow,Tinterval *i,TSimplex *s)
188 {
189  Error("SimplexSetRowBounds is not implemented with CLP");
190 }
191 
192 /* LP: get bounds for a given row */
193 void SimplexGetRowBounds(unsigned int nrow,Tinterval *i,TSimplex *s)
194 {
195  double *rowUpper,*rowLower;
196 
197  rowLower=Clp_rowLower(s->lp);
198  rowUpper=Clp_rowUpper(s->lp);
199 
200  NewInterval(rowLower[nrow+s->fakeRows],rowUpper[nrow+s->fakeRows],i);
201 }
202 
203 void SimplexGetRowConstraint(unsigned int nrow,TLinearConstraint *lc,TSimplex *s)
204 {
205 
206  Tinterval error;
207  const double *elements;
208  const int *rowIndices;
209  const int *columnLengths;
210  const CoinBigIndex *columnStarts;
211  CoinBigIndex a,b,i;
212  unsigned int j,m,n;
213 
214  m=SimplexNColumns(s);
215 
216  rowIndices=Clp_getIndices(s->lp);
217  elements=Clp_getElements(s->lp);
218 
219  columnLengths=Clp_getVectorLengths(s->lp);
220  columnStarts=Clp_getVectorStarts(s->lp);
221 
222  n=nrow+s->fakeRows;
223 
225  for(j=0;j<m;j++)
226  {
227  a=columnStarts[j];
228  b=a+columnLengths[j];
229  for(i=a;i<b;++i)
230  {
231  if (rowIndices[i]==n)
232  AddTerm2LinearConstraint(j,elements[i],lc);
233  }
234  }
235 
236  SimplexGetRowBounds(nrow,&error,s);
237  SetLinearConstraintError(&error,lc);
238 }
239 
240 
241 double SimplexGetRowPrimal(unsigned int nrow,TSimplex *s)
242 {
243  double *obj;
244 
245  obj=Clp_primalRowSolution(s->lp);
246 
247  return(obj[nrow+s->fakeRows]);
248 }
249 
250 double SimplexGetRowDual(unsigned int nrow,TSimplex *s)
251 {
252  double *obj;
253 
254  obj=Clp_dualRowSolution(s->lp);
255 
256  return(obj[nrow+s->fakeRows]);
257 }
258 
260 {
261  Tinterval bounds;
262  double rl[1];
263  double ru[1];
264  int rs[2]; /*row starts*/
265 
266  GetLinearConstraintError(&bounds,lc);
267 
268  rl[0]=LowerLimit(&bounds);
269  ru[0]=UpperLimit(&bounds);
270 
271  rs[0]=0;
273 
274  Clp_addRows(s->lp,1,rl,ru,rs,
275  (signed int *)GetLinearConstraintVariables(lc),
277 
278  #if (_DEBUG>4)
279  printf(" Setting Row %u with range ",SimplexNRows(s));
280  PrintInterval(stdout,&bounds);
281  printf(" [%g %g]\n ",rl[0],ru[0]);
282  PrintLinearConstraint(stdout,TRUE,NULL,lc);
283  #endif
284 }
285 
287 {
288  unsigned int i,n;
289 
290  n=SimplexNColumns(s);
291 
292  for(i=0;i<n;i++)
293  s->obj[i]=0.0;
294 
296  for(i=0;i<n;i++)
297  {
298  #if (_DEBUG>4)
299  printf("+%f*v[%u]",
302  #endif
303 
305  }
306  #if (_DEBUG>4)
307  printf("\n");
308  #endif
309  Clp_chgObjCoefficients(s->lp,s->obj);
310 }
311 
313 {
314  unsigned int i,n;
315  double *obj_c;
316 
317  obj_c=Clp_objective(s->lp);
318 
320 
321  n=SimplexNColumns(s);
322 
323  for(i=0;i<n;i++)
324  AddTerm2LinearConstraint(i,obj_c[i],obj);
325 }
326 
328 {
329  return(Clp_objectiveValue(s->lp));
330 }
331 
332 unsigned int SimplexSolve(TSimplex *s)
333 {
334  int status;
335  unsigned int e;
336 
337  if (s->fakeRows>0)
338  {
339  const int w[1]={0};
340 
341  Clp_deleteRows(s->lp,1,w);//Remove the initial fake row
342 
343  s->fakeRows=0;
344  }
345 
346  Clp_primal(s->lp,1); /* 1 => something changed in the problem!*/
347 
348  status=Clp_status(s->lp);
349 
350  switch(status)
351  {
352  case 0: /* optimal */
353  e=REDUCED_BOX;
354  break;
355  case 1: /* primal infeasible*/
356  e=EMPTY_BOX;
357  break;
358  case 2: /* dual infeasible*/
359  e=UNBOUNDED_BOX;
360  break;
361  default:
363  }
364  return(e);
365 }
366 
368 {
369  if (SimplexNRows(s)>0)
370  Clp_deleteModel(s->lp);
371 
372  free(s->lower);
373  free(s->upper);
374  free(s->obj);
375 }
376 
377 
unsigned int SimplexNColumns(TSimplex *s)
Gets the number of columns (i.e., variables) of the simplex structure.
Definition: simplex_clp.c:102
void SimplexSetRowBounds(unsigned int nrow, Tinterval *i, TSimplex *s)
Sets the bounds for a given row (i.e., constraint).
Definition: simplex_clp.c:187
#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.
#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.
boolean SimplexColEmpty(unsigned int ncol, TSimplex *s)
Checks if a simplex column is empty.
Definition: simplex_clp.c:159
unsigned int SimplexSolve(TSimplex *s)
Determines an optimal value.
Definition: simplex_clp.c:332
void InitLinearConstraint(TLinearConstraint *lc)
Constructor.
#define EMPTY_BOX
One of the possible results of reducing a box.
Definition: box.h:25
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
double SimplexGetOptimalValueRaw(TSimplex *s)
Gets the optimal value after optimizing the problem.
Definition: simplex_clp.c:327
void Error(const char *s)
General error function.
Definition: error.c:80
SimplexType * lp
Definition: simplex.h:75
void SimplexAddNewConstraintRaw(TLinearConstraint *lc, TSimplex *s)
Adds a row (i.e., a constraint) to the simplex.
Definition: simplex_clp.c:259
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 fakeRows
Definition: simplex.h:78
Error and warning functions.
void SimplexCreate(double epsilon, unsigned int ncols, TSimplex *s)
Constructor.
Definition: simplex_clp.c:22
double LowerLimit(Tinterval *i)
Gets the lower limit.
Definition: interval.c:79
#define SIMPLEX_TIMEOUT
Simplex timeout.
Definition: simplex.h:63
Definitions of constants and macros used in several parts of the cuik library.
double * upper
Definition: simplex.h:81
void SimplexGetColConstraint(unsigned int ncol, TLinearConstraint *lc, TSimplex *s)
Gets a column from the simplex in the form of a linear constraint.
Definition: simplex_clp.c:133
void SimplexSetColBounds(unsigned int ncol, Tinterval *i, TSimplex *s)
Sets the bounds for a given column (i.e., variable).
Definition: simplex_clp.c:113
double UpperLimit(Tinterval *i)
Gets the uppser limit.
Definition: interval.c:87
unsigned int SimplexNRows(TSimplex *s)
Gets the number of rows (i.e., constraints) of the simplex structure.
Definition: simplex_clp.c:107
void SimplexGetColBounds(unsigned int ncol, Tinterval *i, TSimplex *s)
Gets the bounds for a given column (i.e., variable).
Definition: simplex_clp.c:123
void SimplexDelete(TSimplex *s)
Destructor.
Definition: simplex_clp.c:367
unsigned int * GetLinearConstraintVariables(TLinearConstraint *lc)
Gets the linear constraint variables.
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
double SimplexGetRowPrimal(unsigned int nrow, TSimplex *s)
Gets a row primal value after solving the simplex.
Definition: simplex_clp.c:241
void SetLinearConstraintError(Tinterval *error, TLinearConstraint *lc)
Sets a new righ-hand side error of the linear constraint.
void NewInterval(double lower, double upper, Tinterval *i)
Constructor.
Definition: interval.c:47
double SimplexGetColPrimal(unsigned int ncol, TSimplex *s)
Gets a column primal value after solving the simplex.
Definition: simplex_clp.c:168
#define INF
Infinite.
Definition: defines.h:70
double GetLinearConstraintCoefficient(unsigned int i, TLinearConstraint *lc)
Gets the a particular linear constraint coefficient.
double * obj
Definition: simplex.h:82
#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.
Definition: simplex_clp.c:312
void SimplexGetRowConstraint(unsigned int nrow, TLinearConstraint *lc, TSimplex *s)
Gets a row constraint from the simplex.
Definition: simplex_clp.c:203
double SimplexGetColDual(unsigned int ncol, TSimplex *s)
Gets a column dual value after solving the simplex.
Definition: simplex_clp.c:177
double SimplexGetRowDual(unsigned int nrow, TSimplex *s)
Gets a row dual value after solving the simplex.
Definition: simplex_clp.c:250
double * lower
Definition: simplex.h:80
Defines a interval.
Definition: interval.h:33
void SimplexGetRowBounds(unsigned int nrow, Tinterval *i, TSimplex *s)
Gets the bounds for a given row (i.e., constraint).
Definition: simplex_clp.c:193
void SimplexSetOptimizationFunction(TLinearConstraint *obj, TSimplex *s)
Sets a new objective function.
Definition: simplex_clp.c:286
void ResetSimplex(TSimplex *s)
Resets the simplex structure.
Definition: simplex_clp.c:96