← Back to branch summary

~ubuntu-branches/ubuntu/saucy/gfan/saucy-proposed

« back to all changes in this revision

Viewing changes to lp.cpp

  • Committer: Package Import Robot
  • Author(s): Cédric Boutillier
  • Date: 2013-07-09 10:44:01 UTC
  • mfrom: (2.1.2 experimental)
  • Revision ID: package-import@ubuntu.com-20130709104401-5q66ozz5j5af0dak
Tags: 0.5+dfsg-3
* Upload to unstable.
* modify remove_failing_tests_on_32bits.patch to replace command of
  0009RenderStairCase test with an empty one instead of deleting it.
* remove lintian override about spelling error

Show diffs side-by-side

added added

removed removed

Lines of Context:
lp.cpp
4
4
#include <math.h>
5
5
#include <string>
6
6
 
 
7
#include "linalg.h"
7
8
#include "timer.h"
8
9
 
9
10
static Timer lpTimer("LP",100);
99
100
  assert(0);
100
101
}
101
102
 
102
 
IntegerVector LpSolver::relativeInteriorPoint(const IntegerVectorList &g, IntegerVector const *equalitySet)
 
103
IntegerVector LpSolver::relativeInteriorPoint(int n, const IntegerVectorList &g, IntegerVector const *equalitySet)
103
104
{
104
105
  fprintf(stderr,"relativeInteriorPoint method not supported in \"%s\" LP class\n",name());
105
106
  assert(0);
116
117
bool LpSolver::hasHomogeneousSolution(int n, const IntegerVectorList &inequalities, const IntegerVectorList &equations)
117
118
{
118
119
  fprintf(stderr,"hasHomogeneousSolution method not supported in \"%s\" LP class\n",name());
119
 
  assert(0);  
 
120
  assert(0);
120
121
}
121
122
 
122
 
static LpSolver *soplex,*huber,*cdd,*cddgmp,*default_;
 
123
static LpSolver *soplex,*soplexCddGmp,*huber,*cdd,*cddgmp,*default_;
123
124
static bool initialized;
124
125
 
125
126
 
126
127
bool lpSetSolver(const char *name)
127
128
{
 
129
  soplexCddGmp=LpSolver::find("SoPlexCddGmp");
128
130
  soplex=LpSolver::find("SoPlex");
129
131
  huber=LpSolver::find("Huber's");
130
132
  cdd=LpSolver::find("cdd");
134
136
  if(soplex)default_=soplex;
135
137
  if(cdd)default_=cdd;
136
138
  if(cddgmp)default_=cddgmp;
 
139
  if(soplexCddGmp)default_=soplexCddGmp;
137
140
  if(selected)default_=selected;
138
141
  initialized=true;
139
142
  assert(default_);
140
 
  //  fprintf(stderr,"LP algorithm being used: \"%s\".\n",default_->name()); //TODO: change to debug printer
 
143
  fprintf(stderr,"LP algorithm being used: \"%s\".\n",default_->name()); //TODO: change to debug printer
 
144
  //if(default_==soplexCddGmp)fprintf(stderr,"USING SoPlexCddGmp\n");
141
145
 
142
146
  return selected;
143
147
}
157
161
  TimerScope ts(&lpTimer);
158
162
  LpInit();
159
163
 
160
 
  return default_->isFacet(g,i); 
 
164
  return default_->isFacet(g,i);
161
165
}
162
166
 
163
167
 
182
186
 
183
187
  if(g.empty())return g.end();
184
188
 
185
 
  return default_->shoot(g); 
 
189
  return default_->shoot(g);
186
190
}
187
191
 
188
192
 
205
209
 
206
210
IntegerVectorList extremeRaysInequalityIndices(const IntegerVectorList &inequalityList)
207
211
{
 
212
  /* If cone is simplicial, then the rays are easy to find...*/
 
213
  if(rankOfMatrix(inequalityList)==inequalityList.size())
 
214
    {
 
215
      IntegerVectorList ret;
 
216
      int m=inequalityList.size();
 
217
      for(int i=0;i<m;i++)
 
218
        {
 
219
          IntegerVector v(m-1);
 
220
          for(int j=0;j<i;j++)
 
221
            v[j]=j;
 
222
          for(int j=i+1;j<m;j++)
 
223
            v[j-1]=j;
 
224
          ret.push_back(v);
 
225
        }
 
226
      return ret;
 
227
    }
 
228
 
 
229
 
208
230
  LpInit();
209
231
 
210
232
  return default_->extremeRaysInequalityIndices(inequalityList);
219
241
}
220
242
 
221
243
 
222
 
IntegerVector relativeInteriorPoint(const IntegerVectorList &g, IntegerVector const *equalitySet)
 
244
IntegerVector relativeInteriorPoint(int n, const IntegerVectorList &g, IntegerVector const *equalitySet)
223
245
{
224
246
  LpInit();
225
247
 
226
 
  return default_->relativeInteriorPoint(g,equalitySet);
 
248
  return default_->relativeInteriorPoint(n,g,equalitySet);
227
249
}
228
250
 
229
251
 
239
261
{
240
262
  LpInit();
241
263
 
 
264
  for(IntegerVectorList::const_iterator i=inequalities.begin();i!=inequalities.end();i++)
 
265
    if(i->size()!=n)
 
266
      {
 
267
        AsciiPrinter(Stderr) << "Inequality length does not match. n="<<n<<" *i="<<*i<<"\n";
 
268
        assert(0);
 
269
      }
 
270
  for(IntegerVectorList::const_iterator i=equations.begin();i!=equations.end();i++)
 
271
    if(i->size()!=n)
 
272
      {
 
273
        AsciiPrinter(Stderr) << "Equation length does not match. n="<<n<<" *i="<<*i<<"\n";
 
274
        assert(0);
 
275
      }
 
276
 
242
277
  return default_->hasHomogeneousSolution(n, inequalities, equations);
243
278
}
 
279
 
 
280
 
 
281
bool isInNonNegativeSpan(IntegerVector const &v, IntegerVectorList const &rays, IntegerVectorList const &linealitySpace)
 
282
{
 
283
  int n=v.size();
 
284
  /*
 
285
  Solve Ax>=0 with A being:
 
286
    0| 1  | 000
 
287
    0|  1 | 000
 
288
    0|   1| 000
 
289
   -v| rrr| lll\
 
290
   -v| aaa| iii \ Added as
 
291
   -v| yyy| nnn / equations
 
292
   -v| sss| eee/
 
293
   */
 
294
 
 
295
  FieldMatrix A1=combineLeftRight(combineLeftRight(FieldMatrix(Q,rays.size(),1),FieldMatrix::identity(Q,rays.size())),FieldMatrix(Q,rays.size(),linealitySpace.size()));
 
296
  FieldMatrix temp=FieldMatrix(Q,1,n);
 
297
  temp[0]=integerVectorToFieldVector(-v,Q);
 
298
  FieldMatrix A2=combineLeftRight(combineLeftRight(temp.transposed(),integerMatrixToFieldMatrix(rowsToIntegerMatrix(rays,n),Q).transposed()),
 
299
                                  integerMatrixToFieldMatrix(rowsToIntegerMatrix(linealitySpace,n),Q).transposed());
 
300
 
 
301
  return hasHomogeneousSolution(1+rays.size()+linealitySpace.size(),fieldMatrixToIntegerMatrixPrimitive(A1).getRows(),fieldMatrixToIntegerMatrixPrimitive(A2).getRows());
 
302
}