Scippy

SoPlex

Sequential object-oriented simPlex

spxdevexpr.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 "spxdefines.h"
17 #include "spxdevexpr.h"
18 
19 #define DEVEX_REFINETOL 2.0
20 
21 namespace soplex
22 {
23 
25 {
26  thesolver = base;
27  setRep(base->rep());
28  assert(isConsistent());
29 }
30 
32 {
33 #ifdef ENABLE_CONSISTENCY_CHECKS
34  if (thesolver != 0)
35  if (weights.dim() != thesolver->coDim()
36  || coWeights.dim() != thesolver->dim())
37  return MSGinconsistent("SPxDevexPR");
38 #endif
39 
40  return true;
41 }
42 
44 {
45  int i;
46  if (tp == SPxSolver::ENTER)
47  {
48  for (i = weights.dim(); --i >= 0;)
49  weights[i] = 2;
50  for (i = coWeights.dim(); --i >= 0;)
51  coWeights[i] = 2;
53  {
55  {
56  bestPrices.clear();
59  }
61  {
65  }
66  }
67  }
68  else
69  {
70  for (i = coWeights.dim(); --i >= 0;)
71  coWeights[i] = 1;
73  {
74  bestPrices.clear();
77  }
78  }
79  weightsAreSetup = true;
80  assert(isConsistent());
81 }
82 
84 {
85  init(tp);
86  refined = false;
87 }
88 
89 /**@todo suspicious: Shouldn't the relation between dim, coDim, Vecs,
90  * and CoVecs be influenced by the representation ?
91  */
93 {
94  if (thesolver != 0)
95  {
98  assert(isConsistent());
99  }
100 }
101 
103 {
104  int idx;
105  int nsorted;
106  Real fTesti;
107  const Real* fTest = thesolver->fTest().get_const_ptr();
108  const Real* cpen = coWeights.get_const_ptr();
109  IdxElement price;
110  prices.clear();
111  bestPrices.clear();
112 
113  // TODO we should check infeasiblities for duplicates or loop over dimension
114  // bestPrices may then also contain duplicates!
115  // construct vector of all prices
116  for (int i = thesolver->infeasibilities.size() - 1; i >= 0; --i)
117  {
118  idx = thesolver->infeasibilities.index(i);
119  fTesti = fTest[idx];
120  if (fTesti < -feastol)
121  {
123  price.idx = idx;
124  price.val = fTesti * fTesti / cpen[idx];
125  prices.append(price);
126  }
127  }
128  // set up structures for the quicksort implementation
130  // do a partial sort to move the best ones to the front
131  // TODO this can be done more efficiently, since we only need the indices
133  // copy indices of best values to bestPrices
134  for( int i = 0; i < nsorted; ++i )
135  {
136  bestPrices.addIdx(prices[i].idx);
138  }
139 
140  if( nsorted > 0 )
141  return prices[0].idx;
142  else
143  return -1;
144 }
145 
147 {
148  int retid;
149 
151  {
152  if ( bestPrices.size() < 2 || thesolver->basis().lastUpdate() == 0 )
153  {
154  // call init method to build up price-vector and return index of largest price
156  }
157  else
158  retid = selectLeaveHyper(theeps);
159  }
160  else if (thesolver->sparsePricingLeave)
161  retid = selectLeaveSparse(theeps);
162  else
163  retid = selectLeaveX(theeps);
164 
165  if ( retid < 0 && !refined )
166  {
167  refined = true;
168  MSG_INFO3( (*thesolver->spxout), (*thesolver->spxout) << "WDEVEX02 trying refinement step..\n"; )
170  }
171 
172  assert(retid < thesolver->dim());
173 
174  return retid;
175 }
176 
177 int SPxDevexPR::selectLeaveX(Real feastol, int start, int incr)
178 {
179  Real x;
180 
181  const Real* fTest = thesolver->fTest().get_const_ptr();
182  const Real* cpen = coWeights.get_const_ptr();
183  Real best = 0;
184  int bstI = -1;
185  int end = coWeights.dim();
186 
187  for (; start < end; start += incr)
188  {
189  if (fTest[start] < -feastol)
190  {
191  x = fTest[start] * fTest[start] / cpen[start];
192  if (x > best)
193  {
194  best = x;
195  bstI = start;
196  last = cpen[start];
197  }
198  }
199  }
200  return bstI;
201 }
202 
204 {
205  Real x;
206 
207  const Real* fTest = thesolver->fTest().get_const_ptr();
208  const Real* cpen = coWeights.get_const_ptr();
209  Real best = 0;
210  int bstI = -1;
211  int idx = -1;
212  Real fTesti;
213  Real coPeni;
214 
215  for (int i = thesolver->infeasibilities.size() - 1; i >= 0; --i)
216  {
217  idx = thesolver->infeasibilities.index(i);
218  fTesti = fTest[idx];
219  if (fTesti < -feastol)
220  {
221  coPeni = cpen[idx];
222  x = fTesti * fTesti / coPeni;
223  if (x > best)
224  {
225  best = x;
226  bstI = idx;
227  last = coPeni;
228  }
229  }
230  else
231  {
235  }
236  }
237  return bstI;
238 }
239 
241 {
242  Real x;
243 
244  const Real* fTest = thesolver->fTest().get_const_ptr();
245  const Real* cpen = coWeights.get_const_ptr();
246  Real best = 0;
247  Real leastBest = infinity;
248  int bstI = -1;
249  int idx = -1;
250  Real fTesti;
251  Real coPeni;
252 
253  // find the best price from the short candidate list
254  for( int i = bestPrices.size() - 1; i >= 0; --i )
255  {
256  idx = bestPrices.index(i);
257  fTesti = fTest[idx];
258  if( fTesti < -feastol )
259  {
260  coPeni = cpen[idx];
261  x = fTesti * fTesti / coPeni;
262  if( x > best )
263  {
264  best = x;
265  bstI = idx;
266  last = coPeni;
267  }
268  // get the smallest price of candidate list
269  if( x < leastBest )
270  leastBest = x;
271  }
272  else
273  {
274  bestPrices.remove(i);
276  }
277  }
278 
279  // make sure we do not skip potential candidates due to a high leastBest value
280  if( leastBest == infinity )
281  {
282  assert(bestPrices.size() == 0);
283  leastBest = 0;
284  }
285 
286  // scan the updated indices for a better price
287  for( int i = thesolver->updateViols.size() - 1; i >= 0; --i )
288  {
289  idx = thesolver->updateViols.index(i);
290  // only look at indeces that were not checked already
291  if( thesolver->isInfeasible[idx] == VIOLATED )
292  {
293  fTesti = fTest[idx];
294  assert(fTesti < -feastol);
295  coPeni = cpen[idx];
296  x = fTesti * fTesti / coPeni;
297  if( x > leastBest )
298  {
299  if( x > best )
300  {
301  best = x;
302  bstI = idx;
303  last = coPeni;
304  }
305  // put index into candidate list
307  bestPrices.addIdx(idx);
308  }
309  }
310  }
311 
312  return bstI;
313 }
314 
315 void SPxDevexPR::left4(int n, SPxId id)
316 {
317  if (id.isValid())
318  {
319  int i, j;
320  Real x;
321  const Real* rhoVec = thesolver->fVec().delta().values();
322  Real rhov_1 = 1 / rhoVec[n];
323  Real beta_q = thesolver->coPvec().delta().length2() * rhov_1 * rhov_1;
324 
325 #ifndef NDEBUG
326  if (spxAbs(rhoVec[n]) < theeps)
327  {
328  MSG_ERROR( std::cerr << "WDEVEX01: rhoVec = "
329  << rhoVec[n] << " with smaller absolute value than theeps = " << theeps << std::endl; )
330  }
331 #endif // NDEBUG
332 
333  // Update #coPenalty# vector
334  const IdxSet& rhoIdx = thesolver->fVec().idx();
335  int len = thesolver->fVec().idx().size();
336  for (i = len - 1; i >= 0; --i)
337  {
338  j = rhoIdx.index(i);
339  x = rhoVec[j] * rhoVec[j] * beta_q;
340  // if(x > coPenalty[j])
341  coWeights[j] += x;
342  }
343 
344  coWeights[n] = beta_q;
345  }
346 }
347 
349 {
350  int idx;
351  int nsorted;
352  Real x;
353  const Real* coTest = thesolver->coTest().get_const_ptr();
354  const Real* cpen = coWeights.get_const_ptr();
355  IdxElement price;
356  prices.clear();
357  bestPrices.clear();
358 
359  // construct vector of all prices
360  for (int i = thesolver->infeasibilities.size() - 1; i >= 0; --i)
361  {
362  idx = thesolver->infeasibilities.index(i);
363  x = coTest[idx];
364  if ( x < -feastol)
365  {
367  price.idx = idx;
368  price.val = x * x / cpen[idx];
369  prices.append(price);
370  }
371  else
372  {
375  }
376  }
377  // set up structures for the quicksort implementation
379  // do a partial sort to move the best ones to the front
380  // TODO this can be done more efficiently, since we only need the indices
382  // copy indices of best values to bestPrices
383  for( int i = 0; i < nsorted; ++i )
384  {
385  bestPrices.addIdx(prices[i].idx);
387  }
388 
389  if( nsorted > 0 )
390  {
391  best = prices[0].val;
392  return thesolver->coId(prices[0].idx);
393  }
394  else
395  return SPxId();
396 }
397 
399 {
400  int idx;
401  int nsorted;
402  Real x;
403  const Real* test = thesolver->test().get_const_ptr();
404  const Real* pen = weights.get_const_ptr();
405  IdxElement price;
406  pricesCo.clear();
408 
409  // construct vector of all prices
410  for (int i = thesolver->infeasibilitiesCo.size() - 1; i >= 0; --i)
411  {
413  x = test[idx];
414  if ( x < -feastol)
415  {
417  price.idx = idx;
418  price.val = x * x / pen[idx];
419  pricesCo.append(price);
420  }
421  else
422  {
425  }
426  }
427  // set up structures for the quicksort implementation
429  // do a partial sort to move the best ones to the front
430  // TODO this can be done more efficiently, since we only need the indices
432  // copy indices of best values to bestPrices
433  for( int i = 0; i < nsorted; ++i )
434  {
435  bestPricesCo.addIdx(pricesCo[i].idx);
437  }
438 
439  if( nsorted > 0 )
440  {
441  best = pricesCo[0].val;
442  return thesolver->id(pricesCo[0].idx);
443  }
444  else
445  return SPxId();
446 }
447 
449 {
450  assert(thesolver != 0);
451 
452  SPxId enterId;
453 
454  enterId = selectEnterX(theeps);
455 
456  if( !enterId.isValid() && !refined )
457  {
458  refined = true;
459  MSG_INFO3( (*thesolver->spxout), (*thesolver->spxout) << "WDEVEX02 trying refinement step..\n"; )
461  }
462 
463  return enterId;
464 }
465 
466 // choose the best entering index among columns and rows but prefer sparsity
468 {
469  SPxId enterId;
470  SPxId enterCoId;
471  Real best;
472  Real bestCo;
473 
474  best = 0;
475  bestCo = 0;
476  last = 1.0;
477 
478  // avoid uninitialized value later on in entered4X()
479  last = 1.0;
480 
481  if( thesolver->hyperPricingEnter && !refined )
482  {
483  if( bestPrices.size() < 2 || thesolver->basis().lastUpdate() == 0 )
484  enterCoId = (thesolver->sparsePricingEnter) ? buildBestPriceVectorEnterDim(best, tol) : selectEnterDenseDim(best, tol);
485  else
486  enterCoId = (thesolver->sparsePricingEnter) ? selectEnterHyperDim(best, tol) : selectEnterDenseDim(best, tol);
487 
488  if( bestPricesCo.size() < 2 || thesolver->basis().lastUpdate() == 0 )
489  enterId = (thesolver->sparsePricingEnterCo) ? buildBestPriceVectorEnterCoDim(bestCo, tol) : selectEnterDenseCoDim(bestCo, tol);
490  else
491  enterId = (thesolver->sparsePricingEnterCo) ? selectEnterHyperCoDim(bestCo, tol) : selectEnterDenseCoDim(bestCo, tol);
492  }
493  else
494  {
495  enterCoId = (thesolver->sparsePricingEnter && !refined) ? selectEnterSparseDim(best, tol) : selectEnterDenseDim(best, tol);
496  enterId = (thesolver->sparsePricingEnterCo && !refined) ? selectEnterSparseCoDim(bestCo, tol) : selectEnterDenseCoDim(bestCo, tol);
497  }
498 
499  // prefer coIds to increase the number of unit vectors in the basis matrix, i.e., rows in colrep and cols in rowrep
500  if( enterCoId.isValid() && (best > SPARSITY_TRADEOFF * bestCo || !enterId.isValid()) )
501  return enterCoId;
502  else
503  return enterId;
504 }
505 
507 {
508  const Real* cTest = thesolver->coTest().get_const_ptr();
509  const Real* cpen = coWeights.get_const_ptr();
510  Real leastBest = infinity;
511  Real coTesti;
512  Real coPeni;
513  Real x;
514  int enterIdx = -1;
515  int idx;
516 
517  // find the best price from short candidate list
518  for( int i = bestPrices.size() - 1; i >= 0; --i )
519  {
520  idx = bestPrices.index(i);
521  coTesti = cTest[idx];
522  if( coTesti < -feastol )
523  {
524  coPeni = cpen[idx];
525  x = coTesti * coTesti / coPeni;
526  if( x > best )
527  {
528  best = x;
529  enterIdx = idx;
530  last = coPeni;
531  }
532  if( x < leastBest )
533  leastBest = x;
534  }
535  else
536  {
537  bestPrices.remove(i);
539  }
540  }
541 
542  // make sure we do not skip potential candidates due to a high leastBest value
543  if( leastBest == infinity )
544  {
545  assert(bestPrices.size() == 0);
546  leastBest = 0;
547  }
548 
549  // scan the updated indeces for a better price
550  for( int i = thesolver->updateViols.size() -1; i >= 0; --i )
551  {
552  idx = thesolver->updateViols.index(i);
553  // only look at indeces that were not checked already
554  if( thesolver->isInfeasible[idx] == VIOLATED )
555  {
556  coTesti = cTest[idx];
557  if( coTesti < -feastol )
558  {
559  coPeni = cpen[idx];
560  x = coTesti * coTesti / coPeni;
561  if(x > leastBest)
562  {
563  if( x > best )
564  {
565  best = x;
566  enterIdx = idx;
567  last = cpen[idx];
568  }
569  // put index into candidate list
571  bestPrices.addIdx(idx);
572  }
573  }
574  else
575  {
577  }
578  }
579  }
580 
581  if (enterIdx >= 0)
582  return thesolver->coId(enterIdx);
583  else
584  return SPxId();
585 }
586 
587 
589 {
590  const Real* test = thesolver->test().get_const_ptr();
591  const Real* pen = weights.get_const_ptr();
592  Real leastBest = infinity;
593  Real testi;
594  Real peni;
595  Real x;
596  int enterIdx = -1;
597  int idx;
598 
599  // find the best price from short candidate list
600  for( int i = bestPricesCo.size() - 1; i >= 0; --i )
601  {
602  idx = bestPricesCo.index(i);
603  testi = test[idx];
604  if( testi < -feastol )
605  {
606  peni = pen[idx];
607  x = testi * testi / peni;
608  if( x > best )
609  {
610  best = x;
611  enterIdx = idx;
612  last = peni;
613  }
614  if( x < leastBest )
615  leastBest = x;
616  }
617  else
618  {
619  bestPricesCo.remove(i);
621  }
622  }
623  // make sure we do not skip potential candidates due to a high leastBest value
624  if( leastBest == infinity )
625  {
626  assert(bestPricesCo.size() == 0);
627  leastBest = 0;
628  }
629 
630  //scan the updated indeces for a better price
631  for( int i = thesolver->updateViolsCo.size() -1; i >= 0; --i )
632  {
633  idx = thesolver->updateViolsCo.index(i);
634  // only look at indeces that were not checked already
635  if( thesolver->isInfeasibleCo[idx] == VIOLATED )
636  {
637  testi = test[idx];
638  if( testi < -feastol )
639  {
640  peni = pen[idx];
641  x = testi * testi / peni;
642  if(x > leastBest)
643  {
644  if( x > best )
645  {
646  best = x;
647  enterIdx = idx;
648  last = pen[idx];
649  }
650  // put index into candidate list
652  bestPricesCo.addIdx(idx);
653  }
654  }
655  else
656  {
658  }
659  }
660  }
661 
662  if (enterIdx >= 0)
663  return thesolver->id(enterIdx);
664  else
665  return SPxId();
666 }
667 
668 
670 {
671  const Real* cTest = thesolver->coTest().get_const_ptr();
672  const Real* cpen = coWeights.get_const_ptr();
673  int enterIdx = -1;
674  int idx;
675  Real coTesti;
676  Real coPeni;
677  Real x;
678 
679  assert(coWeights.dim() == thesolver->coTest().dim());
680  for(int i = thesolver->infeasibilities.size() -1; i >= 0; --i)
681  {
682  idx = thesolver->infeasibilities.index(i);
683  coTesti = cTest[idx];
684  if (coTesti < -feastol)
685  {
686  coPeni = cpen[idx];
687  x = coTesti * coTesti / coPeni;
688  if (x > best)
689  {
690  best = x;
691  enterIdx = idx;
692  last = cpen[idx];
693  }
694  }
695  else
696  {
699  }
700  }
701  if (enterIdx >= 0)
702  return thesolver->coId(enterIdx);
703 
704  return SPxId();
705 }
706 
707 
709 {
710  const Real* test = thesolver->test().get_const_ptr();
711  const Real* pen = weights.get_const_ptr();
712  int enterIdx = -1;
713  int idx;
714  Real testi;
715  Real peni;
716  Real x;
717 
718  assert(weights.dim() == thesolver->test().dim());
719  for (int i = thesolver->infeasibilitiesCo.size() -1; i >= 0; --i)
720  {
722  testi = test[idx];
723  if (testi < -feastol)
724  {
725  peni = pen[idx];
726  x = testi * testi / peni;
727  if (x > best)
728  {
729  best = x;
730  enterIdx = idx;
731  last = pen[idx];
732  }
733  }
734  else
735  {
738  }
739  }
740 
741  if (enterIdx >= 0)
742  return thesolver->id(enterIdx);
743 
744  return SPxId();
745 }
746 
747 
748 SPxId SPxDevexPR::selectEnterDenseDim(Real& best, Real feastol, int start, int incr)
749 {
750  const Real* cTest = thesolver->coTest().get_const_ptr();
751  const Real* cpen = coWeights.get_const_ptr();
752  int end = coWeights.dim();
753  int enterIdx = -1;
754  Real x;
755 
756  assert(end == thesolver->coTest().dim());
757  for (; start < end; start += incr)
758  {
759  if (cTest[start] < -feastol)
760  {
761  x = cTest[start] * cTest[start] / cpen[start];
762  if (x > best)
763  {
764  best = x;
765  enterIdx = start;
766  last = cpen[start];
767  }
768  }
769  }
770 
771  if (enterIdx >= 0)
772  return thesolver->coId(enterIdx);
773 
774  return SPxId();
775 }
776 
777 
778 SPxId SPxDevexPR::selectEnterDenseCoDim(Real& best, Real feastol, int start, int incr)
779 {
780  const Real* test = thesolver->test().get_const_ptr();
781  const Real* pen = weights.get_const_ptr();
782  int end = weights.dim();
783  int enterIdx = -1;
784  Real x;
785 
786  assert(end == thesolver->test().dim());
787  for (; start < end; start += incr)
788  {
789  if (test[start] < -feastol)
790  {
791  x = test[start] * test[start] / pen[start];
792  if (x > best)
793  {
794  best = x;
795  enterIdx = start;
796  last = pen[start];
797  }
798  }
799  }
800 
801  if (enterIdx >= 0)
802  return thesolver->id(enterIdx);
803 
804  return SPxId();
805 }
806 
807 
808 /**@todo suspicious: the pricer should be informed, that variable id
809  has entered the basis at position n, but the id is not used here
810  (this is true for all pricers)
811 */
812 void SPxDevexPR::entered4(SPxId /*id*/, int n)
813 {
814  if (n >= 0 && n < thesolver->dim())
815  {
816  const Real* pVec = thesolver->pVec().delta().values();
817  const IdxSet& pIdx = thesolver->pVec().idx();
818  const Real* coPvec = thesolver->coPvec().delta().values();
819  const IdxSet& coPidx = thesolver->coPvec().idx();
820  Real xi_p = 1 / thesolver->fVec().delta()[n];
821  int i, j;
822 
823  assert(thesolver->fVec().delta()[n] > thesolver->epsilon()
824  || thesolver->fVec().delta()[n] < -thesolver->epsilon());
825 
826  xi_p = xi_p * xi_p * last;
827 
828  for (j = coPidx.size() - 1; j >= 0; --j)
829  {
830  i = coPidx.index(j);
831  coWeights[i] += xi_p * coPvec[i] * coPvec[i];
832  if (coWeights[i] <= 1 || coWeights[i] > 1e+6)
833  {
835  return;
836  }
837  }
838 
839  for (j = pIdx.size() - 1; j >= 0; --j)
840  {
841  i = pIdx.index(j);
842  weights[i] += xi_p * pVec[i] * pVec[i];
843  if (weights[i] <= 1 || weights[i] > 1e+6)
844  {
846  return;
847  }
848  }
849  }
850 }
851 
853 {
854  int initval = (thesolver->type() == SPxSolver::ENTER) ? 2 : 1;
855  n = weights.dim();
857  for (int i = weights.dim()-1; i >= n; --i )
858  weights[i] = initval;
859 }
860 
862 {
863  int initval = (thesolver->type() == SPxSolver::ENTER) ? 2 : 1;
864  n = coWeights.dim();
866  for (int i = coWeights.dim()-1; i >= n; --i)
867  coWeights[i] = initval;
868 }
869 
870 } // namespace soplex
Rational spxAbs(const Rational &r)
Absolute.
Definition: rational.cpp:3925
int dim() const
dimension of basis matrix.
Definition: spxsolver.h:936
int coDim() const
codimension.
Definition: spxsolver.h:941
virtual SPxId selectEnter()
Definition: spxdevexpr.cpp:448
const R * values() const
Returns array values.
Definition: ssvectorbase.h:288
DIdxSet bestPricesCo
set of best pricing candidates
Definition: spxdevexpr.h:54
Representation rep() const
return the current basis representation.
Definition: spxsolver.h:406
void reDim(int newdim, const bool setZero=true)
Resets DVectorBase&#39;s dimension to newdim.
Definition: dvectorbase.h:249
const IdxSet & idx() const
nonzero indices of update vector
Definition: updatevector.h:133
SPxId buildBestPriceVectorEnterCoDim(Real &best, Real feastol)
Definition: spxdevexpr.cpp:398
DIdxSet updateViols
store indices that were changed in the previous iteration and must be checked in hyper pricing ...
Definition: spxsolver.h:363
SPxOut * spxout
message handler
Definition: spxsolver.h:384
bool sparsePricingLeave
These values enable or disable sparse pricing.
Definition: spxsolver.h:374
Type
Algorithmic type.
Definition: spxsolver.h:124
DataArray< IdxElement > pricesCo
temporary array of precomputed pricing values
Definition: spxdevexpr.h:52
bool isValid() const
returns TRUE iff the id is a valid column or row identifier.
Definition: spxid.h:150
const Vector & fTest() const
Violations of fVec.
Definition: spxsolver.h:1246
#define DEVEX_REFINETOL
Definition: spxdevexpr.cpp:19
T * get_ptr()
get a C pointer to the data.
Definition: dataarray.h:110
Representation
LP basis representation.
Definition: spxsolver.h:105
bool sparsePricingEnterCo
true if sparsePricing is turned on in the entering Simplex
Definition: spxsolver.h:376
DVector weights
vector to store pricing weights or norms
Definition: spxpricer.h:60
DataArray< int > isInfeasible
0: index not violated, 1: index violated, 2: index violated and among candidate list ...
Definition: spxsolver.h:370
virtual void left4(int n, SPxId id)
Definition: spxdevexpr.cpp:315
SPxId selectEnterDenseCoDim(Real &best, Real feastol, int start=0, int incr=1)
SPxPricer::selectEnter() in dense case.
Definition: spxdevexpr.cpp:778
void clear()
removes all indices.
Definition: idxset.h:184
void init(SPxSolver::Type)
set entering/leaving algorithm
Definition: spxdevexpr.cpp:43
const R * get_const_ptr() const
Conversion to C-style pointer.
Definition: vectorbase.h:412
UpdateVector & fVec() const
feasibility vector.
Definition: spxsolver.h:1184
UpdateVector & pVec() const
pricing vector.
Definition: spxsolver.h:1339
void clear()
remove all elements.
Definition: dataarray.h:205
SPxId coId(int i) const
id of i &#39;th covector.
Definition: spxsolver.h:978
SPxId buildBestPriceVectorEnterDim(Real &best, Real feastol)
build up vector of pricing values for later use
Definition: spxdevexpr.cpp:348
Devex pricer.
Real last
penalty, selected at last iteration.
Definition: spxdevexpr.h:50
SPxId selectEnterSparseCoDim(Real &best, Real feastol)
implementation of sparse pricing in the entering Simplex
Definition: spxdevexpr.cpp:708
bool weightsAreSetup
are the weights already set up?
Definition: spxpricer.h:63
int buildBestPriceVectorLeave(Real feastol)
build up vector of pricing values for later use
Definition: spxdevexpr.cpp:102
int index(int n) const
access n &#39;th index.
Definition: idxset.h:118
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
void remove(int n, int m)
removes indices at position numbers n through m.
Definition: idxset.cpp:49
DataArray< IdxElement > prices
temporary array of precomputed pricing values
Definition: spxdevexpr.h:51
UpdateVector & coPvec() const
copricing vector.
Definition: spxsolver.h:1259
double Real
SOPLEX_DEBUG.
Definition: spxdefines.h:200
int selectLeaveSparse(Real feastol)
implementation of sparse pricing in the leaving Simplex
Definition: spxdevexpr.cpp:203
const Vector & test() const
Violations of pVec.
Definition: spxsolver.h:1392
virtual void setType(SPxSolver::Type)
set entering/leaving algorithm
Definition: spxdevexpr.cpp:83
virtual void setRep(SPxSolver::Representation)
set row/column representation
Definition: spxdevexpr.cpp:92
#define HYPERPRICINGSIZE
Definition: spxsolver.h:38
const T * get_const_ptr() const
get a const C pointer to the data.
Definition: dataarray.h:115
int size() const
returns the number of used indices.
Definition: idxset.h:124
void append(const T &t)
append element t.
Definition: dataarray.h:121
const SPxBasis & basis() const
Return current basis.
Definition: spxsolver.h:1616
void addIdx(int i)
adds index i to the index set
Definition: didxset.h:75
int size() const
return nr. of elements.
Definition: dataarray.h:211
SPxSolver * thesolver
the solver
Definition: spxpricer.h:56
#define MSG_ERROR(x)
Prints out message x if the verbosity level is at least SPxOut::ERROR.
Definition: spxdefines.h:109
SPxId selectEnterHyperCoDim(Real &best, Real feastol)
implementation of hyper sparse pricing in the entering Simplex
Definition: spxdevexpr.cpp:588
int dim() const
Dimension of vector.
Definition: vectorbase.h:174
bool sparsePricingEnter
true if sparsePricing is turned on in the entering Simplex for slack variables
Definition: spxsolver.h:375
Type type() const
return current Type.
Definition: spxsolver.h:412
DIdxSet bestPrices
set of best pricing candidates
Definition: spxdevexpr.h:53
const Vector & coTest() const
violations of coPvec.
Definition: spxsolver.h:1326
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
DIdxSet infeasibilities
Definition: spxsolver.h:357
Everything should be within this namespace.
IdxCompare compare
Definition: spxpricer.h:93
int lastUpdate() const
returns number of basis changes since last refactorization.
Definition: spxbasis.h:533
int selectLeaveHyper(Real feastol)
implementation of hyper sparse pricing in the leaving Simplex
Definition: spxdevexpr.cpp:240
virtual int selectLeave()
Definition: spxdevexpr.cpp:146
DVector coWeights
Definition: spxpricer.h:61
#define SPARSITY_TRADEOFF
Definition: spxsolver.h:41
int SPxQuicksortPart(T *keys, COMPARATOR &compare, int start, int end, int size, int start2=0, int end2=0, bool type=true)
Generic implementation of Partial QuickSort.
Definition: sorter.h:219
SPxId selectEnterHyperDim(Real &best, Real feastol)
implementation of hyper sparse pricing in the entering Simplex
Definition: spxdevexpr.cpp:506
Real theeps
violation bound
Definition: spxpricer.h:58
SPxId id(int i) const
id of i &#39;th vector.
Definition: spxsolver.h:959
int selectLeaveX(Real feastol, int start=0, int incr=1)
internal implementation of SPxPricer::selectLeave()
Definition: spxdevexpr.cpp:177
Real epsilon() const
values are considered to be 0.
Definition: spxsolver.h:670
virtual void entered4(SPxId id, int n)
Definition: spxdevexpr.cpp:812
DataArray< int > isInfeasibleCo
0: index not violated, 1: index violated, 2: index violated and among candidate list ...
Definition: spxsolver.h:371
R length2() const
Squared euclidian norm.
Definition: ssvectorbase.h:504
const Real infinity
Definition: spxdefines.cpp:26
bool hyperPricingEnter
true if hyper sparse pricing is turned on in the entering Simplex
Definition: spxsolver.h:378
virtual void addedCoVecs(int n)
n covectors have been added to loaded LP.
Definition: spxdevexpr.cpp:861
#define MSGinconsistent(name)
Definition: spxdefines.h:121
virtual void load(SPxSolver *base)
sets the solver
Definition: spxdevexpr.cpp:24
SSVector & delta()
update vector , writeable
Definition: updatevector.h:122
DIdxSet updateViolsCo
Definition: spxsolver.h:364
#define MSG_INFO3(spxout, x)
Prints out message x if the verbosity level is at least SPxOut::INFO3.
Definition: spxdefines.h:117
void reMax(int newMax=1, int newSize=-1)
reset maximum number of elements.
Definition: dataarray.h:254
SPxId selectEnterSparseDim(Real &best, Real feastol)
implementation of sparse pricing in the entering Simplex (slack variables)
Definition: spxdevexpr.cpp:669
SPxId selectEnterDenseDim(Real &best, Real feastol, int start=0, int incr=1)
SPxPricer::selectEnter() in dense case (slack variabels)
Definition: spxdevexpr.cpp:748
void setMax(int newmax=1)
sets the maximum number of indices.
Definition: didxset.cpp:22
DIdxSet infeasibilitiesCo
Definition: spxsolver.h:360
bool hyperPricingLeave
true if hyper sparse pricing is turned on in the leaving Simplex
Definition: spxsolver.h:377
const IdxElement * elements
Definition: spxpricer.h:82
Set of indices.Class IdxSet provides a set of indices. At construction it must be given an array of i...
Definition: idxset.h:56
virtual void addedVecs(int n)
n vectors have been added to loaded LP.
Definition: spxdevexpr.cpp:852
SPxId selectEnterX(Real tol)
choose the best entering index among columns and rows but prefer sparsity
Definition: spxdevexpr.cpp:467
virtual bool isConsistent() const
consistency check
Definition: spxdevexpr.cpp:31