Scippy

SoPlex

Sequential object-oriented simPlex

spxparmultpr.cpp
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the class library */
4 /* SoPlex --- the Sequential object-oriented simPlex. */
5 /* */
6 /* Copyright (C) 1996-2016 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SoPlex is distributed under the terms of the ZIB Academic Licence. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SoPlex; see the file COPYING. If not email to soplex@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 #include <assert.h>
17 #include <iostream>
18 
19 #include "spxdefines.h"
20 #include "spxparmultpr.h"
21 
22 namespace soplex
23 {
24 // #define EQ_PREF 1000
25 
27 
29 {
30  if (tp == SPxSolver::ENTER)
31  {
32  used = 0;
34  }
35  else
36  {
38  }
39 
40  last = 0;
41  min = partialSize / 2;
42 }
43 
45 {
46  thesolver = p_solver;
48  pricSet.reSize(10 * partialSize);
49 }
50 
52 {
53  SPxId id;
54  Real x;
55  int i;
56  int best = -1;
57  // const SPxBasis::Desc& ds = thesolver->basis().desc();
58 
59  assert(thesolver != 0);
60  int lastlast = -1;
61 
63  {
64  Real val;
65  Real eps = -theeps;
66  lastlast = last;
67 
68  for (i = used - 1; i >= 0; --i)
69  {
70  int n = thesolver->number(pricSet[i].id);
71  if (thesolver->isId(pricSet[i].id))
72  {
74  pricSet[i].test = val = thesolver->computeTest(n);
75  }
76  else
77  pricSet[i].test = val = thesolver->coTest()[n];
78  if (val >= eps)
79  pricSet[i] = pricSet[--used];
80  }
81 
82  while (pricSet.size() - used < partialSize)
83  {
84  best = 0;
85  for (i = 1; i < used; ++i)
86  {
87  if (pricSet[i].test > pricSet[best].test)
88  best = i;
89  }
90  pricSet[best] = pricSet[--used];
91  }
92 
93  do
94  {
95  last = (last + 1) % multiParts;
96  for (i = thesolver->coDim() - last - 1;
97  i >= 0; i -= multiParts)
98  {
100  x = thesolver->computeTest(i);
101  if (x < eps)
102  {
103  pricSet[used].id = thesolver->id(i);
104  pricSet[used].test = x;
105  used++;
106  }
107  }
108 
109  for (i = thesolver->dim() - last - 1;
110  i >= 0; i -= multiParts)
111  {
112  x = thesolver->coTest()[i];
113  if (x < eps)
114  {
115  pricSet[used].id = thesolver->coId(i);
116  pricSet[used].test = x;
117  used++;
118  }
119  }
120  assert(used < pricSet.size());
121  }
122  while (used < min && last != lastlast);
123 
124  if (used > 0)
125  {
126  min = (used + 1);
127  if (min < 1)
128  min = 1;
129  if (min > partialSize)
130  min = partialSize;
131  best = 0;
132  for (i = 1; i < used; ++i)
133  {
134  if (pricSet[i].test < pricSet[best].test)
135  best = i;
136  }
137  id = pricSet[best].id;
138  }
139  return id;
140  }
141 
142  else
143  {
144  assert(thesolver->pricing() == SPxSolver::FULL);
145  Real bestx = -theeps;
146  for (i = thesolver->dim() - 1; i >= 0; --i)
147  {
148  x = thesolver->coTest()[i];
149  // x *= EQ_PREF * (1 + (ds.coStatus(i) == SPxBasis::Desc::P_FREE
150  // || ds.coStatus(i) == SPxBasis::Desc::D_FREE));
151  if (x < bestx)
152  {
153  id = thesolver->coId(i);
154  bestx = thesolver->coTest()[i];
155  }
156  }
157 
158  for (i = thesolver->coDim() - 1; i >= 0; --i)
159  {
160  x = thesolver->test()[i];
161  // x *= EQ_PREF * (1 + (ds.status(i) == SPxBasis::Desc::P_FREE
162  // || ds.status(i) == SPxBasis::Desc::D_FREE));
163  if (x < bestx)
164  {
165  id = thesolver->id(i);
166  bestx = thesolver->test()[i];
167  }
168  }
169 
170  return id;
171  }
172 }
173 
175 {
176  int i, n;
177  Real x;
178  Real best = -theeps;
179  // const Real* up = thesolver->ubBound();
180  // const Real* low = thesolver->lbBound();
181 
182  assert(thesolver != 0);
183  n = -1;
184  for (i = thesolver->dim() - 1; i >= 0; --i)
185  {
186  x = thesolver->fTest()[i];
187  // x *= EQ_PREF * (1 + (up[i] == low[i]));
188  if (x < best)
189  {
190  n = i;
191  best = thesolver->fTest()[i];
192  }
193  }
194 
195  return n;
196 }
197 } // namespace soplex
int dim() const
dimension of basis matrix.
Definition: spxsolver.h:936
int coDim() const
codimension.
Definition: spxsolver.h:941
Type
Algorithmic type.
Definition: spxsolver.h:124
const Vector & fTest() const
Violations of fVec.
Definition: spxsolver.h:1246
int number(const SPxRowId &id) const
Returns the row number of the row with identifier id.
Definition: spxlpbase.h:450
Pricing pricing() const
return current Pricing.
Definition: spxsolver.h:418
SPxId coId(int i) const
id of i &#39;th covector.
Definition: spxsolver.h:978
bool isId(const SPxId &p_id) const
Is p_id an SPxId ?
Definition: spxsolver.h:996
Entering Simplex.
Definition: spxsolver.h:134
Generic Ids for LP rows or columns.Both SPxColIds and SPxRowIds may be treated uniformly as SPxIds: ...
Definition: spxid.h:85
double Real
SOPLEX_DEBUG.
Definition: spxdefines.h:200
virtual void load(SPxSolver *solver)
set the solver
virtual SPxId selectEnter()
const Vector & test() const
Violations of pVec.
Definition: spxsolver.h:1392
virtual int selectLeave()
SPxSolver * thesolver
the solver
Definition: spxpricer.h:56
const Vector & coTest() const
violations of coPvec.
Definition: spxsolver.h:1326
virtual void setType(SPxSolver::Type tp)
set entering or leaving algorithm
Debugging, floating point type and parameter definitions.
Sequential object-oriented SimPlex.SPxSolver is an LP solver class using the revised Simplex algorith...
Definition: spxsolver.h:84
Full pricing.
Definition: spxsolver.h:160
Everything should be within this namespace.
static int partialSize
Set size for partial pricing.
Definition: spxparmultpr.h:78
Real computePvec(int i)
compute and return pVec()[i].
Definition: enter.cpp:173
Partial multiple pricing.
Real theeps
violation bound
Definition: spxpricer.h:58
SPxId id(int i) const
id of i &#39;th vector.
Definition: spxsolver.h:959
Partial pricing.
Definition: spxsolver.h:174
DataArray< SPxParMultPr_Tmp > pricSet
Definition: spxparmultpr.h:68
Real computeTest(int i)
compute and return test()[i] in ENTERing Simplex.
Definition: enter.cpp:179
void setPricing(Pricing pr)
set FULL or PARTIAL pricing.
Definition: spxsolver.cpp:431