Scippy

SoPlex

Sequential object-oriented simPlex

spxdantzigpr.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-2017 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 // #define EQ_PREF 1000
20 
21 #include "spxdefines.h"
22 #include "spxdantzigpr.h"
23 
24 namespace soplex
25 {
26 
28 {
29  assert(thesolver != 0);
30 
32  return selectLeaveSparse();
33 
34  // const Real* up = thesolver->ubBound();
35  // const Real* low = thesolver->lbBound();
36 
37  Real best = -theeps;
38  int n = -1;
39 
40  for(int i = thesolver->dim() - 1; i >= 0; --i)
41  {
42  Real x = thesolver->fTest()[i];
43 
44  if (x < -theeps)
45  {
46  // x *= EQ_PREF * (1 + (up[i] == low[i]));
47  if (x < best)
48  {
49  n = i;
50  best = x;
51  }
52  }
53  }
54  return n;
55 }
56 
58 {
59  assert(thesolver != 0);
60 
61  Real best = -theeps;
62  Real x;
63  int n = -1;
64  int index;
65 
66  for(int i = thesolver->infeasibilities.size() - 1; i >= 0; --i)
67  {
68  index = thesolver->infeasibilities.index(i);
69  x = thesolver->fTest()[index];
70  if (x < -theeps)
71  {
72  if (x < best)
73  {
74  n = index;
75  best = x;
76  }
77  }
78  else
79  {
81  assert(thesolver->isInfeasible[index] > 0);
82  thesolver->isInfeasible[index] = 0;
83  }
84  }
85  return n;
86 }
87 
88 
90 {
91  assert(thesolver != 0);
92 
93  // const SPxBasis::Desc& ds = thesolver->basis().desc();
94 
95  SPxId enterId;
96  enterId = selectEnterX();
97 
98  return enterId;
99 }
100 
102 {
103  SPxId enterId;
104  SPxId enterIdCo;
105  Real best;
106  Real bestCo;
107 
108  best = -theeps;
109  bestCo = -theeps;
110  enterId = (thesolver->sparsePricingEnter) ? selectEnterSparseDim(best,enterId) : selectEnterDenseDim(best,enterId);
111  enterIdCo = (thesolver->sparsePricingEnterCo) ? selectEnterSparseCoDim(bestCo,enterId) : selectEnterDenseCoDim(bestCo,enterId);
112 
113  // prefer slack indices to reduce nonzeros in basis matrix
114  if( enterId.isValid() && (best > SPARSITY_TRADEOFF * bestCo || !enterIdCo.isValid()) )
115  return enterId;
116  else
117  return enterIdCo;
118 }
119 
120 
122 {
123  assert(thesolver != 0);
124 
125  int idx;
126  Real x;
127 
128  for (int i = thesolver->infeasibilities.size() - 1; i >= 0; --i)
129  {
130  idx = thesolver->infeasibilities.index(i);
131  x = thesolver->coTest()[idx];
132 
133  if (x < -theeps)
134  {
135  // x *= EQ_PREF * (1 + (ds.coStatus(i) == SPxBasis::Desc::P_FREE
136  // || ds.coStatus(i) == SPxBasis::Desc::D_FREE));
137  if (x < best)
138  {
139  enterId = thesolver->coId(idx);
140  best = x;
141  }
142  }
143  else
144  {
146 
147  assert(thesolver->isInfeasible[idx]);
148  thesolver->isInfeasible[idx] = 0;
149  }
150  }
151  return enterId;
152 }
153 
155 {
156  assert(thesolver != 0);
157 
158  int idx;
159  Real x;
160 
161  for (int i = thesolver->infeasibilitiesCo.size() - 1; i >= 0; --i)
162  {
164  x = thesolver->test()[idx];
165 
166  if (x < -theeps)
167  {
168  // x *= EQ_PREF * (1 + (ds.coStatus(i) == SPxBasis::Desc::P_FREE
169  // || ds.coStatus(i) == SPxBasis::Desc::D_FREE));
170  if (x < best)
171  {
172  enterId = thesolver->id(idx);
173  best = x;
174  }
175  }
176  else
177  {
179  assert(thesolver->isInfeasibleCo[idx] > 0);
180  thesolver->isInfeasibleCo[idx] = 0;
181  }
182  }
183  return enterId;
184 }
185 
187 {
188  assert(thesolver != 0);
189 
190  Real x;
191 
192  for (int i = thesolver->dim() - 1; i >= 0; --i)
193  {
194  x = thesolver->coTest()[i];
195 
196  if (x < -theeps)
197  {
198  // x *= EQ_PREF * (1 + (ds.coStatus(i) == SPxBasis::Desc::P_FREE
199  // || ds.coStatus(i) == SPxBasis::Desc::D_FREE));
200  if (x < best)
201  {
202  enterId = thesolver->coId(i);
203  best = x;
204  }
205  }
206  }
207  return enterId;
208 }
209 
211 {
212  assert(thesolver != 0);
213 
214  Real x;
215 
216  for (int i = thesolver->coDim() - 1; i >= 0; --i)
217  {
218  x = thesolver->test()[i];
219 
220  if (x < -theeps)
221  {
222  // x *= EQ_PREF * (1 + (ds.status(i) == SPxBasis::Desc::P_FREE
223  // || ds.status(i) == SPxBasis::Desc::D_FREE));
224  if (x < best)
225  {
226  enterId = thesolver->id(i);
227  best = x;
228  }
229  }
230  }
231  return enterId;
232 }
233 
234 } // namespace soplex
virtual int selectLeave()
SPxId coId(int i) const
id of i &#39;th covector.
Definition: spxsolver.h:1089
SPxId selectEnterDenseDim(Real &best, SPxId &id)
const Vector & fTest() const
Violations of fVec.
Definition: spxsolver.h:1357
bool sparsePricingLeave
These values enable or disable sparse pricing.
Definition: spxsolver.h:417
bool sparsePricingEnterCo
true if sparsePricing is turned on in the entering Simplex
Definition: spxsolver.h:419
SPxId selectEnterSparseDim(Real &best, SPxId &id)
DataArray< int > isInfeasible
0: index not violated, 1: index violated, 2: index violated and among candidate list ...
Definition: spxsolver.h:413
int dim() const
dimension of basis matrix.
Definition: spxsolver.h:1047
Dantzig pricer.
Generic Ids for LP rows or columns.Both SPxColIds and SPxRowIds may be treated uniformly as SPxIds: ...
Definition: spxid.h:85
void remove(int n, int m)
removes indices at position numbers n through m.
Definition: idxset.cpp:49
virtual SPxId selectEnter()
double Real
Definition: spxdefines.h:215
int size() const
returns the number of used indices.
Definition: idxset.h:124
SPxId id(int i) const
id of i &#39;th vector.
Definition: spxsolver.h:1070
SPxId selectEnterDenseCoDim(Real &best, SPxId &id)
SPxSolver * thesolver
the solver
Definition: spxpricer.h:56
bool sparsePricingEnter
true if sparsePricing is turned on in the entering Simplex for slack variables
Definition: spxsolver.h:418
const Vector & test() const
Violations of pVec.
Definition: spxsolver.h:1503
Debugging, floating point type and parameter definitions.
DIdxSet infeasibilities
Definition: spxsolver.h:400
Everything should be within this namespace.
#define SPARSITY_TRADEOFF
Definition: spxsolver.h:41
Real theeps
violation bound
Definition: spxpricer.h:58
const Vector & coTest() const
violations of coPvec.
Definition: spxsolver.h:1437
bool isValid() const
returns TRUE iff the id is a valid column or row identifier.
Definition: spxid.h:150
DataArray< int > isInfeasibleCo
0: index not violated, 1: index violated, 2: index violated and among candidate list ...
Definition: spxsolver.h:414
int coDim() const
codimension.
Definition: spxsolver.h:1052
SPxId selectEnterSparseCoDim(Real &best, SPxId &id)
int index(int n) const
access n &#39;th index.
Definition: idxset.h:118
DIdxSet infeasibilitiesCo
Definition: spxsolver.h:403