Scippy

SoPlex

Sequential object-oriented simPlex

spxshift.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-2019 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 "soplex/spxdefines.h"
20 #include "soplex/spxsolver.h"
21 #include "soplex/spxout.h"
22 
23 namespace soplex
24 {
25 void SPxSolver::shiftFvec()
26 {
27 
28  /* the allowed tolerance is (rep() == COLUMN) ? feastol() : opttol() because theFvec is the primal vector in COLUMN
29  * and the dual vector in ROW representation; this is equivalent to entertol()
30  */
31  Real minrandom = 10.0 * entertol();
32  Real maxrandom = 100.0 * entertol();
33  Real allow = entertol() - epsilon();
34 
35  assert(type() == ENTER);
36  assert(allow > 0);
37 
38  for(int i = dim() - 1; i >= 0; --i)
39  {
40  if(theUBbound[i] + allow < (*theFvec)[i])
41  {
42  MSG_DEBUG(std::cout << "DSHIFT08 theUBbound[" << i << "] violated by " <<
43  (*theFvec)[i] - theUBbound[i] - allow << std::endl);
44 
45  if(theUBbound[i] != theLBbound[i])
46  shiftUBbound(i, (*theFvec)[i] + random.next(minrandom, maxrandom));
47  else
48  {
49  shiftUBbound(i, (*theFvec)[i]);
50  theLBbound[i] = theUBbound[i];
51  }
52  }
53  else if((*theFvec)[i] < theLBbound[i] - allow)
54  {
55  MSG_DEBUG(std::cout << "DSHIFT08 theLBbound[" << i << "] violated by " << theLBbound[i] -
56  (*theFvec)[i] - allow << std::endl);
57 
58  if(theUBbound[i] != theLBbound[i])
59  shiftLBbound(i, (*theFvec)[i] - random.next(minrandom, maxrandom));
60  else
61  {
62  shiftLBbound(i, (*theFvec)[i]);
63  theUBbound[i] = theLBbound[i];
64  }
65  }
66  }
67 
68 #ifndef NDEBUG
69  testBounds();
70  MSG_DEBUG(std::cout << "DSHIFT01 shiftFvec: OK" << std::endl;)
71 #endif
72 }
73 
74 // -----------------------------------------------------------------
75 
76 /*
77  This methods assumes correctly setup vectors |pVec| and |coPvec| and bound
78  vectors for leaving simplex. Then it checks all values of |pVec| and
79  |coPvec| to obey these bounds and enlarges them if neccessary.
80  */
81 void SPxSolver::shiftPvec()
82 {
83 
84  /* the allowed tolerance is (rep() == ROW) ? feastol() : opttol() because thePvec is the primal vector in ROW and the
85  * dual vector in COLUMN representation; this is equivalent to leavetol()
86  */
87  Real minrandom = 10.0 * leavetol();
88  Real maxrandom = 100.0 * leavetol();
89  Real allow = leavetol() - epsilon();
90  bool tmp;
91  int i;
92 
93  assert(type() == LEAVE);
94  assert(allow > 0.0);
95 
96  for(i = dim() - 1; i >= 0; --i)
97  {
98  tmp = !isBasic(coId(i));
99 
100  if((*theCoUbound)[i] + allow <= (*theCoPvec)[i] && tmp)
101  {
102  if((*theCoUbound)[i] != (*theCoLbound)[i])
103  shiftUCbound(i, (*theCoPvec)[i] + random.next(minrandom, maxrandom));
104  else
105  {
106  shiftUCbound(i, (*theCoPvec)[i]);
107  (*theCoLbound)[i] = (*theCoUbound)[i];
108  }
109  }
110  else if((*theCoLbound)[i] - allow >= (*theCoPvec)[i] && tmp)
111  {
112  if((*theCoUbound)[i] != (*theCoLbound)[i])
113  shiftLCbound(i, (*theCoPvec)[i] - random.next(minrandom, maxrandom));
114  else
115  {
116  shiftLCbound(i, (*theCoPvec)[i]);
117  (*theCoUbound)[i] = (*theCoLbound)[i];
118  }
119  }
120  }
121 
122  for(i = coDim() - 1; i >= 0; --i)
123  {
124  tmp = !isBasic(id(i));
125 
126  if((*theUbound)[i] + allow <= (*thePvec)[i] && tmp)
127  {
128  if((*theUbound)[i] != (*theLbound)[i])
129  shiftUPbound(i, (*thePvec)[i] + random.next(minrandom, maxrandom));
130  else
131  {
132  shiftUPbound(i, (*thePvec)[i]);
133  (*theLbound)[i] = (*theUbound)[i];
134  }
135  }
136  else if((*theLbound)[i] - allow >= (*thePvec)[i] && tmp)
137  {
138  if((*theUbound)[i] != (*theLbound)[i])
139  shiftLPbound(i, (*thePvec)[i] - random.next(minrandom, maxrandom));
140  else
141  {
142  shiftLPbound(i, (*thePvec)[i]);
143  (*theUbound)[i] = (*theLbound)[i];
144  }
145  }
146  }
147 
148 #ifndef NDEBUG
149  testBounds();
150  MSG_DEBUG(std::cout << "DSHIFT02 shiftPvec: OK" << std::endl;)
151 #endif
152 }
153 // -----------------------------------------------------------------
154 void SPxSolver::perturbMin(
155  const UpdateVector& uvec,
156  Vector& p_low,
157  Vector& p_up,
158  Real eps,
159  Real p_delta,
160  int start,
161  int incr)
162 {
163  assert(uvec.dim() == p_low.dim());
164  assert(uvec.dim() == p_up.dim());
165 
166  const Real* vec = uvec.get_const_ptr();
167  Real minrandom = 10.0 * p_delta;
168  Real maxrandom = 100.0 * p_delta;
169  Real x, l, u;
170  int i;
171 
172  if(fullPerturbation)
173  {
174  eps = p_delta;
175 
176  for(i = uvec.dim() - start - 1; i >= 0; i -= incr)
177  {
178  u = p_up[i];
179  l = p_low[i];
180  x = vec[i];
181 
182  if(LT(u, infinity) && NE(l, u) && u <= x + eps)
183  {
184  p_up[i] = x + random.next(minrandom, maxrandom);
185  theShift += p_up[i] - u;
186  }
187 
188  if(GT(l, -infinity) && NE(l, u) && l >= x - eps)
189  {
190  p_low[i] = x - random.next(minrandom, maxrandom);
191  theShift -= p_low[i] - l;
192  }
193  }
194  }
195  else
196  {
197  const Real* upd = uvec.delta().values();
198  const IdxSet& idx = uvec.delta().indices();
199 
200  for(int j = uvec.delta().size() - start - 1; j >= 0; j -= incr)
201  {
202  i = idx.index(j);
203  x = upd[i];
204  u = p_up[i];
205  l = p_low[i];
206 
207  // do not permute these bounds! c.f. with computeFrhs2() in spxvecs.cpp
208  if(dualStatus(baseId(i)) == SPxBasis::Desc::D_ON_BOTH)
209  {
210  continue;
211  }
212 
213  if(x < -eps)
214  {
215  if(LT(u, infinity) && NE(l, u) && vec[i] >= u - eps)
216  {
217  p_up[i] = vec[i] + random.next(minrandom, maxrandom);
218  theShift += p_up[i] - u;
219  }
220  }
221  else if(x > eps)
222  {
223  if(GT(l, -infinity) && NE(l, u) && vec[i] <= l + eps)
224  {
225  p_low[i] = vec[i] - random.next(minrandom, maxrandom);
226  theShift -= p_low[i] - l;
227  }
228  }
229  }
230  }
231 }
232 // -----------------------------------------------------------------
233 void SPxSolver::perturbMax(
234  const UpdateVector& uvec,
235  Vector& p_low,
236  Vector& p_up,
237  Real eps,
238  Real p_delta,
239  int start,
240  int incr)
241 {
242  assert(uvec.dim() == p_low.dim());
243  assert(uvec.dim() == p_up.dim());
244 
245  const Real* vec = uvec.get_const_ptr();
246  Real minrandom = 10.0 * p_delta;
247  Real maxrandom = 100.0 * p_delta;
248  Real x, l, u;
249  int i;
250 
251  if(fullPerturbation)
252  {
253  eps = p_delta;
254 
255  for(i = uvec.dim() - start - 1; i >= 0; i -= incr)
256  {
257  u = p_up[i];
258  l = p_low[i];
259  x = vec[i];
260 
261  if(LT(u, infinity) && NE(l, u) && u <= x + eps)
262  {
263  p_up[i] = x + random.next(minrandom, maxrandom);
264  theShift += p_up[i] - u;
265  }
266 
267  if(GT(l, -infinity) && NE(l, u) && l >= x - eps)
268  {
269  p_low[i] = x - random.next(minrandom, maxrandom);
270  theShift -= p_low[i] - l;
271  }
272  }
273  }
274  else
275  {
276  const Real* upd = uvec.delta().values();
277  const IdxSet& idx = uvec.delta().indices();
278 
279  for(int j = uvec.delta().size() - start - 1; j >= 0; j -= incr)
280  {
281  i = idx.index(j);
282  x = upd[i];
283  u = p_up[i];
284  l = p_low[i];
285 
286  // do not permute these bounds! c.f. computeFrhs2() in spxvecs.cpp
287  if(dualStatus(baseId(i)) == SPxBasis::Desc::D_ON_BOTH)
288  {
289  continue;
290  }
291 
292  if(x > eps)
293  {
294  if(LT(u, infinity) && NE(l, u) && vec[i] >= u - eps)
295  {
296  p_up[i] = vec[i] + random.next(minrandom, maxrandom);
297  theShift += p_up[i] - u;
298  }
299  }
300  else if(x < -eps)
301  {
302  if(GT(l, -infinity) && NE(l, u) && vec[i] <= l + eps)
303  {
304  p_low[i] = vec[i] - random.next(minrandom, maxrandom);
305  theShift -= p_low[i] - l;
306  }
307  }
308  }
309  }
310 }
311 
312 void SPxSolver::perturbMinEnter(void)
313 {
314  MSG_DEBUG(std::cout << "DSHIFT03 iteration= " << iteration() << ": perturbing " << shift();)
315  fVec().delta().setup();
316  perturbMin(fVec(), lbBound(), ubBound(), epsilon(), entertol());
317  MSG_DEBUG(std::cout << "\t->" << shift() << std::endl;)
318 }
319 
320 
321 void SPxSolver::perturbMaxEnter(void)
322 {
323  MSG_DEBUG(std::cout << "DSHIFT04 iteration= " << iteration() << ": perturbing " << shift();)
324  fVec().delta().setup();
325  perturbMax(fVec(), lbBound(), ubBound(), epsilon(), entertol());
326  MSG_DEBUG(std::cout << "\t->" << shift() << std::endl;)
327 }
328 
329 
330 Real SPxSolver::perturbMin(
331  const UpdateVector& uvec,
332  Vector& p_low,
333  Vector& p_up,
334  Real eps,
335  Real p_delta,
336  const SPxBasis::Desc::Status* stat,
337  int start,
338  int incr)
339 {
340  assert(uvec.dim() == p_low.dim());
341  assert(uvec.dim() == p_up.dim());
342 
343  const Real* vec = uvec.get_const_ptr();
344  Real minrandom = 10.0 * p_delta;
345  Real maxrandom = 100.0 * p_delta;
346  Real x, l, u;
347  int i;
348  Real l_theShift = 0;
349 
350  if(fullPerturbation)
351  {
352  eps = p_delta;
353 
354  for(i = uvec.dim() - start - 1; i >= 0; i -= incr)
355  {
356  u = p_up[i];
357  l = p_low[i];
358  x = vec[i];
359 
360  if(LT(u, infinity) && NE(l, u) && u <= x + eps && rep() * stat[i] < 0)
361  {
362  p_up[i] = vec[i] + random.next(minrandom, maxrandom);
363  l_theShift += p_up[i] - u;
364  }
365 
366  if(GT(l, -infinity) && NE(l, u) && l >= x - eps && rep() * stat[i] < 0)
367  {
368  p_low[i] = vec[i] - random.next(minrandom, maxrandom);
369  l_theShift -= p_low[i] - l;
370  }
371  }
372  }
373  else
374  {
375  const Real* upd = uvec.delta().values();
376  const IdxSet& idx = uvec.delta().indices();
377 
378  for(int j = uvec.delta().size() - start - 1; j >= 0; j -= incr)
379  {
380  i = idx.index(j);
381  x = upd[i];
382  u = p_up[i];
383  l = p_low[i];
384 
385  if(x < -eps)
386  {
387  if(LT(u, infinity) && NE(l, u) && vec[i] >= u - eps && rep() * stat[i] < 0)
388  {
389  p_up[i] = vec[i] + random.next(minrandom, maxrandom);
390  l_theShift += p_up[i] - u;
391  }
392  }
393  else if(x > eps)
394  {
395  if(GT(l, -infinity) && NE(l, u) && vec[i] <= l + eps && rep() * stat[i] < 0)
396  {
397  p_low[i] = vec[i] - random.next(minrandom, maxrandom);
398  l_theShift -= p_low[i] - l;
399  }
400  }
401  }
402  }
403 
404  return l_theShift;
405 }
406 
407 Real SPxSolver::perturbMax(
408  const UpdateVector& uvec,
409  Vector& p_low,
410  Vector& p_up,
411  Real eps,
412  Real p_delta,
413  const SPxBasis::Desc::Status* stat,
414  int start,
415  int incr)
416 {
417  assert(uvec.dim() == p_low.dim());
418  assert(uvec.dim() == p_up.dim());
419 
420  const Real* vec = uvec.get_const_ptr();
421  Real minrandom = 10.0 * p_delta;
422  Real maxrandom = 100.0 * p_delta;
423  Real x, l, u;
424  int i;
425  Real l_theShift = 0;
426 
427  if(fullPerturbation)
428  {
429  eps = p_delta;
430 
431  for(i = uvec.dim() - start - 1; i >= 0; i -= incr)
432  {
433  u = p_up[i];
434  l = p_low[i];
435  x = vec[i];
436 
437  if(LT(u, infinity) && NE(l, u) && u <= x + eps && rep() * stat[i] < 0)
438  {
439  p_up[i] = vec[i] + random.next(minrandom, maxrandom);
440  l_theShift += p_up[i] - u;
441  }
442 
443  if(GT(l, -infinity) && NE(l, u) && l >= x - eps && rep() * stat[i] < 0)
444  {
445  p_low[i] = vec[i] - random.next(minrandom, maxrandom);
446  l_theShift -= p_low[i] - l;
447  }
448  }
449  }
450  else
451  {
452  const Real* upd = uvec.delta().values();
453  const IdxSet& idx = uvec.delta().indices();
454 
455  for(int j = uvec.delta().size() - start - 1; j >= 0; j -= incr)
456  {
457  i = idx.index(j);
458  x = upd[i];
459  u = p_up[i];
460  l = p_low[i];
461 
462  if(x > eps)
463  {
464  if(LT(u, infinity) && NE(l, u) && vec[i] >= u - eps && rep() * stat[i] < 0)
465  {
466  p_up[i] = vec[i] + random.next(minrandom, maxrandom);
467  l_theShift += p_up[i] - u;
468  }
469  }
470  else if(x < -eps)
471  {
472  if(GT(l, -infinity) && NE(l, u) && vec[i] <= l + eps && rep() * stat[i] < 0)
473  {
474  p_low[i] = vec[i] - random.next(minrandom, maxrandom);
475  l_theShift -= p_low[i] - l;
476  }
477  }
478  }
479  }
480 
481  return l_theShift;
482 }
483 
484 
485 void SPxSolver::perturbMinLeave(void)
486 {
487  MSG_DEBUG(std::cout << "DSHIFT05 iteration= " << iteration() << ": perturbing " << shift();)
488  pVec().delta().setup();
489  coPvec().delta().setup();
490  theShift += perturbMin(pVec(), lpBound(), upBound(), epsilon(), leavetol(),
491  desc().status(), 0, 1);
492  theShift += perturbMin(coPvec(), lcBound(), ucBound(), epsilon(), leavetol(),
493  desc().coStatus(), 0, 1);
494  MSG_DEBUG(std::cout << "\t->" << shift() << std::endl;)
495 }
496 
497 
498 void SPxSolver::perturbMaxLeave(void)
499 {
500  MSG_DEBUG(std::cout << "DSHIFT06 iteration= " << iteration() << ": perturbing " << shift();)
501  pVec().delta().setup();
502  coPvec().delta().setup();
503  theShift += perturbMax(pVec(), lpBound(), upBound(), epsilon(), leavetol(),
504  desc().status(), 0, 1);
505  theShift += perturbMax(coPvec(), lcBound(), ucBound(), epsilon(), leavetol(),
506  desc().coStatus(), 0, 1);
507  MSG_DEBUG(std::cout << "\t->" << shift() << std::endl;)
508 }
509 
510 
511 void SPxSolver::unShift(void)
512 {
513  MSG_INFO3((*spxout), (*spxout) << "DSHIFT07 = " << "unshifting ..." << std::endl;);
514 
515  if(isInitialized())
516  {
517  int i;
518  Real t_up, t_low;
519  const SPxBasis::Desc& ds = desc();
520 
521  theShift = 0;
522 
523  if(type() == ENTER)
524  {
525  Real eps = entertol();
526 
527  if(rep() == COLUMN)
528  {
529  for(i = dim(); i-- > 0;)
530  {
531  SPxId l_id = baseId(i);
532  int l_num = number(l_id);
533 
534  if(l_id.type() == SPxId::ROW_ID)
535  {
536  t_up = -lhs(l_num);
537  t_low = -rhs(l_num);
538  }
539  else
540  {
541  assert(l_id.type() == SPxId::COL_ID);
542  t_up = upper(l_num);
543  t_low = lower(l_num);
544  }
545 
546  if(t_up != t_low)
547  {
548  if((*theFvec)[i] < t_up + eps) // check allowed violation
549  theUBbound[i] = t_up; // reset shifted bound to original
550  else if((*theFvec)[i] > t_up) // shifted bound is required for feasibility
551  theShift += theUBbound[i] - t_up;
552 
553  if((*theFvec)[i] > t_low - eps) // check allowed violation
554  theLBbound[i] = t_low; // reset shifted bound to original
555  else if((*theFvec)[i] < t_low) // shifted bound is required for feasibility
556  theShift -= theLBbound[i] - t_low;
557  }
558  else
559  {
560  if(theUBbound[i] > t_up)
561  theShift += theUBbound[i] - t_up;
562  else if(theLBbound[i] < t_low)
563  theShift += t_low - theLBbound[i];
564  }
565  }
566 
567  for(i = nRows(); i-- > 0;)
568  {
569  if(!isBasic(ds.rowStatus(i)))
570  {
571  t_up = -lhs(i);
572  t_low = -rhs(i);
573 
574  if(theURbound[i] > t_up) // what about t_up == t_low ?
575  theShift += theURbound[i] - t_up;
576 
577  if(t_low > theLRbound[i]) // what about t_up == t_low ?
578  theShift += t_low - theLRbound[i];
579  }
580  }
581 
582  for(i = nCols(); i-- > 0;)
583  {
584  if(!isBasic(ds.colStatus(i)))
585  {
586  t_up = upper(i);
587  t_low = lower(i);
588 
589  if(theUCbound[i] > t_up) // what about t_up == t_low ?
590  theShift += theUCbound[i] - t_up;
591 
592  if(t_low > theLCbound[i]) // what about t_up == t_low ?
593  theShift += t_low - theLCbound[i];
594  }
595  }
596  }
597  else
598  {
599  assert(rep() == ROW);
600 
601  for(i = dim(); i-- > 0;)
602  {
603  SPxId l_id = baseId(i);
604  int l_num = number(l_id);
605  t_up = t_low = 0;
606 
607  if(l_id.type() == SPxId::ROW_ID)
608  clearDualBounds(ds.rowStatus(l_num), t_up, t_low);
609  else
610  clearDualBounds(ds.colStatus(l_num), t_up, t_low);
611 
612  if(theUBbound[i] != theLBbound[i])
613  {
614  if(theUBbound[i] > t_up)
615  theShift += theUBbound[i] - t_up;
616  else
617  theShift -= theUBbound[i] - t_up;
618  }
619  else
620  {
621  /* if the basic (primal or dual) variable is fixed (e.g., basis status P_FREE in row representation)
622  * then shiftFvec() and shiftPvec() do not relax the bounds, but shift both, hence they may be outside
623  * of [t_low,t_up] */
624  assert(theLBbound[i] == theUBbound[i] || theUBbound[i] >= t_up);
625  assert(theLBbound[i] == theUBbound[i] || theLBbound[i] <= t_low);
626 
627  if((*theFvec)[i] < t_up - eps)
628  theUBbound[i] = t_up;
629  else if((*theFvec)[i] > t_up)
630  theShift += theUBbound[i] - t_up;
631 
632  if((*theFvec)[i] > t_low + eps)
633  theLBbound[i] = t_low;
634  else if((*theFvec)[i] < t_low)
635  theShift -= theLBbound[i] - t_low;
636  }
637  }
638 
639  for(i = nRows(); i-- > 0;)
640  {
641  if(!isBasic(ds.rowStatus(i)))
642  {
643  t_up = t_low = 0;
644  clearDualBounds(ds.rowStatus(i), t_up, t_low);
645 
646  if(theURbound[i] > t_up) // what about t_up == t_low ?
647  theShift += theURbound[i] - t_up;
648 
649  if(t_low > theLRbound[i]) // what about t_up == t_low ?
650  theShift += t_low - theLRbound[i];
651  }
652  }
653 
654  for(i = nCols(); i-- > 0;)
655  {
656  if(!isBasic(ds.colStatus(i)))
657  {
658  t_up = t_low = 0;
659  clearDualBounds(ds.colStatus(i), t_up, t_low);
660 
661  if(theUCbound[i] > t_up) // what about t_up == t_low ?
662  theShift += theUCbound[i] - t_up;
663 
664  if(t_low > theLCbound[i]) // what about t_up == t_low ?
665  theShift += t_low - theLCbound[i];
666  }
667  }
668  }
669  }
670  else
671  {
672  assert(type() == LEAVE);
673 
674  Real eps = leavetol();
675 
676  if(rep() == COLUMN)
677  {
678  for(i = nRows(); i-- > 0;)
679  {
680  t_up = t_low = maxRowObj(i);
681  clearDualBounds(ds.rowStatus(i), t_up, t_low);
682 
683  if(!isBasic(ds.rowStatus(i)))
684  {
685  if((*theCoPvec)[i] < t_up + eps)
686  {
687  theURbound[i] = t_up; // reset bound to original value
688 
689  if(t_up == t_low)
690  theLRbound[i] = t_low; // for fixed rows we change both bounds
691  }
692  else
693  theShift += theURbound[i] - t_up;
694 
695  if((*theCoPvec)[i] > t_low - eps)
696  {
697  theLRbound[i] = t_low; // reset bound to original value
698 
699  if(t_up == t_low)
700  theURbound[i] = t_up; // for fixed rows we change both bounds
701  }
702  else
703  theShift += t_low - theLRbound[i];
704  }
705  else if(theURbound[i] > t_up)
706  theShift += theURbound[i] - t_up;
707  else if(theLRbound[i] < t_low)
708  theShift += t_low - theLRbound[i];
709  }
710 
711  for(i = nCols(); i-- > 0;)
712  {
713  t_up = t_low = -maxObj(i);
714  clearDualBounds(ds.colStatus(i), t_low, t_up);
715 
716  if(!isBasic(ds.colStatus(i)))
717  {
718  if((*thePvec)[i] < -t_up + eps)
719  {
720  theUCbound[i] = -t_up; // reset bound to original value
721 
722  if(t_up == t_low)
723  theLCbound[i] = -t_low; // for fixed variables we change both bounds
724  }
725  else
726  theShift += theUCbound[i] - (-t_up);
727 
728  if((*thePvec)[i] > -t_low - eps)
729  {
730  theLCbound[i] = -t_low; // reset bound to original value
731 
732  if(t_up == t_low)
733  theUCbound[i] = -t_up; // for fixed variables we change both bounds
734  }
735  else
736  theShift += (-t_low) - theLCbound[i];
737  }
738  else if(theUCbound[i] > -t_up)
739  theShift += theUCbound[i] - (-t_up);
740  else if(theLCbound[i] < -t_low)
741  theShift += (-t_low) - theLCbound[i];
742  }
743  }
744  else
745  {
746  assert(rep() == ROW);
747 
748  for(i = nRows(); i-- > 0;)
749  {
750  t_up = rhs(i);
751  t_low = lhs(i);
752 
753  if(t_up == t_low)
754  {
755  if(theURbound[i] > t_up)
756  theShift += theURbound[i] - t_up;
757  else
758  theShift += t_low - theLRbound[i];
759  }
760  else if(!isBasic(ds.rowStatus(i)))
761  {
762  if((*thePvec)[i] < t_up + eps)
763  theURbound[i] = t_up; // reset bound to original value
764  else
765  theShift += theURbound[i] - t_up;
766 
767  if((*thePvec)[i] > t_low - eps)
768  theLRbound[i] = t_low; // reset bound to original value
769  else
770  theShift += t_low - theLRbound[i];
771  }
772  else if(theURbound[i] > t_up)
773  theShift += theURbound[i] - t_up;
774  else if(theLRbound[i] < t_low)
775  theShift += t_low - theLRbound[i];
776  }
777 
778  for(i = nCols(); i-- > 0;)
779  {
780  t_up = upper(i);
781  t_low = lower(i);
782 
783  if(t_up == t_low)
784  {
785  if(theUCbound[i] > t_up)
786  theShift += theUCbound[i] - t_up;
787  else
788  theShift += t_low - theLCbound[i];
789  }
790  else if(!isBasic(ds.colStatus(i)))
791  {
792  if((*theCoPvec)[i] < t_up + eps)
793  theUCbound[i] = t_up; // reset bound to original value
794  else
795  theShift += theUCbound[i] - t_up;
796 
797  if((*theCoPvec)[i] > t_low - eps)
798  theLCbound[i] = t_low; // reset bound to original value
799  else
800  theShift += t_low - theLCbound[i];
801  }
802  else if(theUCbound[i] > t_up)
803  theShift += theUCbound[i] - t_up;
804  else if(theLCbound[i] < t_low)
805  theShift += t_low - theLCbound[i];
806  }
807  }
808  }
809  }
810 }
811 } // namespace soplex
soplex::SPxSolver::unShift
virtual void unShift(void)
remove shift as much as possible.
Definition: spxshift.cpp:511
soplex::SPxLPBase::rhs
const VectorBase< R > & rhs() const
Returns right hand side vector.
Definition: spxlpbase.h:221
soplex::SPxSolver::coId
SPxId coId(int i) const
id of i &#39;th covector.
Definition: spxsolver.h:1117
soplex::SPxSolver::ucBound
const Vector & ucBound() const
Definition: spxsolver.h:1417
soplex::SPxBasis::iteration
int iteration() const
returns number of basis changes since last load().
Definition: spxbasis.h:546
soplex::SPxSolver::shift
virtual Real shift() const
total current shift amount.
Definition: spxsolver.h:1627
soplex::SPxLPBase::upper
const VectorBase< R > & upper() const
Returns upper bound vector.
Definition: spxlpbase.h:461
soplex::SPxSolver::spxout
SPxOut * spxout
message handler
Definition: spxsolver.h:463
soplex::infinity
THREADLOCAL const Real infinity
Definition: spxdefines.cpp:26
soplex::SPxSolver::theUbound
DVector * theUbound
Upper bound for vars.
Definition: spxsolver.h:375
soplex::SPxSolver::testBounds
void testBounds() const
Definition: spxbounds.cpp:328
soplex::SPxSolver::leavetol
Real leavetol() const
feasibility tolerance maintained by ratio test during LEAVE algorithm.
Definition: spxsolver.h:796
soplex::SPxSolver::theCoUbound
DVector * theCoUbound
Upper bound for covars.
Definition: spxsolver.h:377
soplex::SPxBasis::Desc::rowStatus
Status & rowStatus(int i)
Definition: spxbasis.h:239
soplex::LT
bool LT(Real a, Real b, Real eps=Param::epsilon())
returns true iff a < b + eps
Definition: spxdefines.h:388
soplex::SPxSolver::clearDualBounds
void clearDualBounds(SPxBasis::Desc::Status, Real &, Real &) const
Definition: spxbounds.cpp:76
soplex::SPxSolver::perturbMaxLeave
virtual void perturbMaxLeave(void)
perturb nonbasic bounds.
Definition: spxshift.cpp:498
soplex::NE
bool NE(Real a, Real b, Real eps=Param::epsilon())
returns true iff |a-b| > eps
Definition: spxdefines.h:382
soplex::SPxLPBase::number
int number(const SPxRowId &id) const
Returns the row number of the row with identifier id.
Definition: spxlpbase.h:527
soplex::SPxSolver::lcBound
const Vector & lcBound() const
Definition: spxsolver.h:1438
soplex::SPxSolver::perturbMinEnter
virtual void perturbMinEnter(void)
Definition: spxshift.cpp:312
soplex::SPxSolver::dim
int dim() const
dimension of basis matrix.
Definition: spxsolver.h:1075
soplex::SPxSolver::shiftLBbound
void shiftLBbound(int i, Real to)
shift i &#39;th lbBound to to.
Definition: spxsolver.h:1584
soplex::SPxSolver::perturbMaxEnter
virtual void perturbMaxEnter(void)
perturb basis bounds.
Definition: spxshift.cpp:321
soplex::SPxBasis::dualStatus
Desc::Status dualStatus(const SPxColId &id) const
dual Status for the column variable with ID id of the loaded LP.
Definition: spxbasis.cpp:34
soplex::SPxSolver::ROW
rowwise representation.
Definition: spxsolver.h:107
soplex::VectorBase::get_const_ptr
const R * get_const_ptr() const
Conversion to C-style pointer.
Definition: vectorbase.h:455
spxout.h
Wrapper for different output streams and verbosity levels.
soplex::SPxLPBase::nRows
int nRows() const
Returns number of rows in LP.
Definition: spxlpbase.h:152
soplex::SPxSolver::ubBound
const Vector & ubBound() const
upper bound for fVec.
Definition: spxsolver.h:1341
soplex::SPxSolver::ENTER
Entering Simplex.
Definition: spxsolver.h:134
soplex::SPxId
Generic Ids for LP rows or columns.Both SPxColIds and SPxRowIds may be treated uniformly as SPxIds: ...
Definition: spxid.h:85
soplex::SPxSolver::coPvec
UpdateVector & coPvec() const
copricing vector.
Definition: spxsolver.h:1398
soplex::SPxSolver::LEAVE
Leaving Simplex.
Definition: spxsolver.h:143
soplex::Real
double Real
Definition: spxdefines.h:218
soplex::SSVectorBase::values
const R * values() const
Returns array values.
Definition: ssvectorbase.h:300
MSG_DEBUG
#define MSG_DEBUG(x)
Definition: spxdefines.h:132
soplex::SPxSolver::status
Status status() const
Status of solution process.
Definition: spxsolve.cpp:2213
soplex::SPxSolver::shiftLPbound
void shiftLPbound(int i, Real to)
shift i &#39;th lpBound to to.
Definition: spxsolver.h:1600
soplex::GT
bool GT(Real a, Real b, Real eps=Param::epsilon())
returns true iff a > b + eps
Definition: spxdefines.h:400
soplex::SPxSolver::theLbound
DVector * theLbound
Lower bound for vars.
Definition: spxsolver.h:376
soplex::SPxSolver::entertol
Real entertol() const
feasibility tolerance maintained by ratio test during ENTER algorithm.
Definition: spxsolver.h:789
soplex::SPxSolver::thePvec
UpdateVector * thePvec
Definition: spxsolver.h:368
soplex::SPxSolver::lbBound
const Vector & lbBound() const
lower bound for fVec.
Definition: spxsolver.h:1359
soplex::SSVectorBase::indices
const IdxSet & indices() const
Returns indices.
Definition: ssvectorbase.h:306
soplex::SPxSolver::fVec
UpdateVector & fVec() const
feasibility vector.
Definition: spxsolver.h:1323
soplex::SPxSolver::theLBbound
DVector theLBbound
Lower Basic Feasibility bound.
Definition: spxsolver.h:357
spxsolver.h
main LP solver class
soplex::SPxSolver::isBasic
bool isBasic(SPxBasis::Desc::Status stat) const
does stat describe a basic index ?
Definition: spxsolver.h:1263
soplex::Random::next
Real next(Real minimum=0.0, Real maximum=1.0)
returns next random number.
Definition: random.h:102
soplex::SPxLPBase::lhs
const VectorBase< R > & lhs() const
Returns left hand side vector.
Definition: spxlpbase.h:255
soplex::SPxSolver::shiftPvec
void shiftPvec()
Perform initial shifting to optain an feasible or pricable basis.
Definition: spxshift.cpp:81
soplex::UpdateVector
Dense vector with semi-sparse vector for updatesIn many algorithms vectors are updated in every itera...
Definition: updatevector.h:53
soplex::SPxSolver::shiftUCbound
void shiftUCbound(int i, Real to)
shift i &#39;th ucBound to to.
Definition: spxsolver.h:1608
soplex::SPxBasis::Desc
Basis descriptor.
Definition: spxbasis.h:104
soplex::SPxSolver::theURbound
DVector theURbound
Upper Row Feasibility bound.
Definition: spxsolver.h:346
soplex::SPxId::ROW_ID
row identifier.
Definition: spxid.h:97
soplex::SPxId::COL_ID
column identifier.
Definition: spxid.h:99
soplex::SPxLPBase::maxRowObj
const VectorBase< R > & maxRowObj() const
Definition: spxlpbase.h:300
soplex::SPxSolver::shiftUBbound
void shiftUBbound(int i, Real to)
shift i &#39;th ubBound to to.
Definition: spxsolver.h:1576
soplex::SPxBasis::Desc::colStatus
Status & colStatus(int i)
Definition: spxbasis.h:254
soplex::SPxBasis::baseId
SPxId & baseId(int i)
Definition: spxbasis.h:504
soplex::SPxSolver::theUBbound
DVector theUBbound
Upper Basic Feasibility bound.
Definition: spxsolver.h:356
MSG_INFO3
#define MSG_INFO3(spxout, x)
Prints out message x if the verbosity level is at least SPxOut::INFO3.
Definition: spxdefines.h:122
soplex::SPxSolver::theCoLbound
DVector * theCoLbound
Lower bound for covars.
Definition: spxsolver.h:378
soplex::SPxSolver::epsilon
Real epsilon() const
values are considered to be 0.
Definition: spxsolver.h:784
spxdefines.h
Debugging, floating point type and parameter definitions.
soplex::SPxSolver::pVec
UpdateVector & pVec() const
pricing vector.
Definition: spxsolver.h:1478
soplex::SPxSolver::fullPerturbation
bool fullPerturbation
whether to perturb the entire problem or just the bounds relevant for the current pivot ...
Definition: spxsolver.h:325
soplex::SPxSolver::lpBound
const Vector & lpBound() const
Definition: spxsolver.h:1504
soplex::SPxSolver::theLRbound
DVector theLRbound
Lower Row Feasibility bound.
Definition: spxsolver.h:347
soplex::SPxSolver::perturbMin
void perturbMin(const UpdateVector &vec, Vector &low, Vector &up, Real eps, Real delta, int start=0, int incr=1)
Definition: spxshift.cpp:154
soplex::SPxSolver::theUCbound
DVector theUCbound
Upper Column Feasibility bound.
Definition: spxsolver.h:348
soplex::SPxSolver::isInitialized
bool isInitialized() const
has the internal data been initialized?
Definition: spxsolver.h:1850
soplex::VectorBase::dim
int dim() const
Dimension of vector.
Definition: vectorbase.h:217
soplex::SSVectorBase::size
int size() const
Returns the number of nonzeros.
Definition: ssvectorbase.h:200
soplex
Everything should be within this namespace.
soplex::SPxSolver::shiftUPbound
void shiftUPbound(int i, Real to)
shift i &#39;th upBound to to.
Definition: spxsolver.h:1592
soplex::SPxSolver::shiftLCbound
void shiftLCbound(int i, Real to)
shift i &#39;th lcBound to to.
Definition: spxsolver.h:1616
soplex::SPxSolver::theFvec
UpdateVector * theFvec
Definition: spxsolver.h:362
soplex::SPxLPBase::maxObj
const VectorBase< R > & maxObj() const
Returns objective vector for maximization problem.
Definition: spxlpbase.h:434
soplex::SSVectorBase::setup
void setup()
Initializes nonzero indices for elements with absolute values above epsilon and sets all other elemen...
Definition: ssvectorbase.h:133
soplex::SPxSolver::theLCbound
DVector theLCbound
Lower Column Feasibility bound.
Definition: spxsolver.h:349
soplex::SPxSolver::upBound
const Vector & upBound() const
Definition: spxsolver.h:1483
soplex::SPxSolver::perturbMinLeave
virtual void perturbMinLeave(void)
Definition: spxshift.cpp:485
soplex::SPxSolver::shiftFvec
void shiftFvec()
Perform initial shifting to optain an feasible or pricable basis.
Definition: spxshift.cpp:25
soplex::SPxId::type
Type type() const
returns the type of the id.
Definition: spxid.h:146
soplex::SPxSolver::type
Type type() const
return current Type.
Definition: spxsolver.h:512
soplex::SPxSolver::theShift
Real theShift
sum of all shifts applied to any bound.
Definition: spxsolver.h:268
soplex::SPxSolver::coDim
int coDim() const
codimension.
Definition: spxsolver.h:1080
soplex::SPxSolver::random
Random random
The random number generator used throughout the whole computation. Its seed can be modified...
Definition: spxsolver.h:424
soplex::SPxLPBase::nCols
int nCols() const
Returns number of columns in LP.
Definition: spxlpbase.h:158
soplex::SPxBasis::Desc::D_ON_BOTH
dual variable has two bounds
Definition: spxbasis.h:194
soplex::SPxSolver::perturbMax
void perturbMax(const UpdateVector &vec, Vector &low, Vector &up, Real eps, Real delta, int start=0, int incr=1)
Definition: spxshift.cpp:233
soplex::UpdateVector::delta
SSVector & delta()
update vector , writeable
Definition: updatevector.h:122
soplex::IdxSet::index
int index(int n) const
access n &#39;th index.
Definition: idxset.h:118
soplex::SPxSolver::theCoPvec
UpdateVector * theCoPvec
Definition: spxsolver.h:366
soplex::SPxBasis::Desc::Status
Status
Status of a variable.
Definition: spxbasis.h:185
soplex::SPxLPBase::lower
const VectorBase< R > & lower() const
Returns (internal and possibly scaled) lower bound vector.
Definition: spxlpbase.h:488
soplex::SPxBasis::desc
const Desc & desc() const
Definition: spxbasis.h:464
soplex::SPxSolver::rep
Representation rep() const
return the current basis representation.
Definition: spxsolver.h:506
soplex::IdxSet
Set of indices.Class IdxSet provides a set of indices. At construction it must be given an array of i...
Definition: idxset.h:56
soplex::SPxSolver::COLUMN
columnwise representation.
Definition: spxsolver.h:108