Scippy

SoPlex

Sequential object-oriented simPlex

spxmainsm.h
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 /**@file spxmainsm.h
17  * @brief General methods in LP preprocessing.
18  */
19 #ifndef _SPXMAINSM_H_
20 #define _SPXMAINSM_H_
21 
22 #include <assert.h>
23 
24 #include "spxdefines.h"
25 #include "spxsimplifier.h"
26 #include "array.h"
27 #include "exceptions.h"
28 
29 namespace soplex
30 {
31 //---------------------------------------------------------------------
32 // class SPxMainSM
33 //---------------------------------------------------------------------
34 
35 /**@brief LP simplifier for removing uneccessary row/columns.
36  @ingroup Algo
37 
38  This #SPxSimplifier is mainly based on the paper "Presolving in
39  linear programming" by E. Andersen and K. Andersen (Mathematical
40  Programming, 1995). It implements all proposed methods and some
41  other preprocessing techniques for removing redundant rows and
42  columns and bounds. Also infeasibility and unboundedness may be
43  detected.
44 
45  Removed are:
46  - empty rows / columns
47  - unconstraint rows
48  - row singletons
49  - forcing rows
50  - zero objective column singletons
51  - (implied) free column singletons
52  - doubleton equations combined with a column singleton
53  - (implicitly) fixed columns
54  - redundant lhs / rhs
55  - redundant variable bounds
56  - variables that are free in one direction
57  - (weakly) dominated columns
58  - duplicate rows / columns
59 */
60 class SPxMainSM : public SPxSimplifier
61 {
62 private:
63  //---------------------------------------------------------------------
64  // class PostsolveStep
65  //---------------------------------------------------------------------
66 
67  /**@brief Base class for postsolving operations.
68  @ingroup Algo
69 
70  Class #PostStep is an abstract base class providing the
71  interface for operations in the postsolving process.
72  */
73  class PostStep
74  {
75  private:
76  /// name of the simplifier
77  const char* m_name;
78  /// number of cols
79  int nCols;
80  /// number of rows
81  int nRows;
82 
83  public:
84  /// constructor.
85  PostStep(const char* p_name, int nR = 0, int nC = 0)
86  : m_name(p_name)
87  , nCols(nC)
88  , nRows(nR)
89  {}
90  /// copy constructor.
91  PostStep(const PostStep& old)
92  : m_name(old.m_name)
93  , nCols(old.nCols)
94  , nRows(old.nRows)
95  {}
96  /// assignment operator
97  PostStep& operator=(const PostStep& /*rhs*/)
98  {
99  return *this;
100  }
101  /// destructor.
102  virtual ~PostStep()
103  {
104  m_name = 0;
105  }
106  /// get name of simplifying step.
107  virtual const char* getName() const
108  {
109  return m_name;
110  }
111  /// clone function for polymorphism
112  virtual PostStep* clone() const = 0;
113  /// executes the postsolving.
114  virtual void execute(DVector& x, DVector& y, DVector& s, DVector& r,
115  DataArray<SPxSolver::VarStatus>& cBasis, DataArray<SPxSolver::VarStatus>& rBasis, bool isOptimal) const = 0;
116 
118 
119  static Real eps()
120  {
121  return 1e-6;
122  }
123  };
124 
125  /**@brief Postsolves row objectives.
126  @ingroup Algo
127  */
128  class RowObjPS : public PostStep
129  {
130  private:
131  int m_i; ///< row index
132  int m_j; ///< slack column index
133 
134  public:
135  ///
136  RowObjPS(const SPxLP& lp, int _i, int _j)
137  : PostStep("RowObj", lp.nRows(), lp.nCols())
138  , m_i(_i)
139  , m_j(_j)
140  {}
141  /// copy constructor
142  RowObjPS(const RowObjPS& old)
143  : PostStep(old)
144  , m_i(old.m_i)
145  , m_j(old.m_j)
146  {}
147  /// assignment operator
149  {
150  if(this != &rhs)
151  {
152  m_i = rhs.m_i;
153  m_j = rhs.m_j;
154  }
155 
156  return *this;
157  }
158  ///
159  virtual void execute(DVector& x, DVector& y, DVector& s, DVector& r,
160  DataArray<SPxSolver::VarStatus>& cBasis, DataArray<SPxSolver::VarStatus>& rBasis, bool isOptimal) const;
161  /// clone function for polymorphism
162  inline virtual PostStep* clone() const
163  {
164  return new RowObjPS(*this);
165  }
166  };
167 
168  /**@brief Postsolves unconstraint constraints.
169  @ingroup Algo
170  */
171  class FreeConstraintPS : public PostStep
172  {
173  private:
174  int m_i;
175  int m_old_i;
178 
179  public:
180  ///
181  FreeConstraintPS(const SPxLP& lp, int _i)
182  : PostStep("FreeConstraint", lp.nRows(), lp.nCols())
183  , m_i(_i)
184  , m_old_i(lp.nRows()-1)
185  , m_row(lp.rowVector(_i))
186  , m_row_obj(lp.rowObj(_i))
187  {}
188  /// copy constructor
190  : PostStep(old)
191  , m_i(old.m_i)
192  , m_old_i(old.m_old_i)
193  , m_row(old.m_row)
194  , m_row_obj(old.m_row_obj)
195  {}
196  /// assignment operator
198  {
199  if(this != &rhs)
200  {
201  m_i = rhs.m_i;
202  m_old_i = rhs.m_old_i;
203  m_row = rhs.m_row;
204  m_row_obj = rhs.m_row_obj;
205  }
206 
207  return *this;
208  }
209  ///
210  virtual void execute(DVector& x, DVector& y, DVector& s, DVector& r,
211  DataArray<SPxSolver::VarStatus>& cBasis, DataArray<SPxSolver::VarStatus>& rBasis, bool isOptimal) const;
212  /// clone function for polymorphism
213  inline virtual PostStep* clone() const
214  {
215  return new FreeConstraintPS(*this);
216  }
217  };
218 
219  /**@brief Postsolves empty constraints.
220  @ingroup Algo
221  */
223  {
224  private:
225  int m_i;
226  int m_old_i;
228 
229  public:
230  ///
231  EmptyConstraintPS(const SPxLP& lp, int _i)
232  : PostStep("EmptyConstraint", lp.nRows(), lp.nCols())
233  , m_i(_i)
234  , m_old_i(lp.nRows()-1)
235  , m_row_obj(lp.rowObj(_i))
236  {}
237  /// copy constructor
239  : PostStep(old)
240  , m_i(old.m_i)
241  , m_old_i(old.m_old_i)
242  , m_row_obj(old.m_row_obj)
243  {}
244  /// assignment operator
246  {
247  if(this != &rhs)
248  {
249  m_i = rhs.m_i;
250  m_old_i = rhs.m_old_i;
251  m_row_obj = rhs.m_row_obj;
252  }
253 
254  return *this;
255  }
256  ///
257  virtual void execute(DVector& x, DVector& y, DVector& s, DVector& r,
258  DataArray<SPxSolver::VarStatus>& cBasis, DataArray<SPxSolver::VarStatus>& rBasis, bool isOptimal) const;
259  /// clone function for polymorphism
260  inline virtual PostStep* clone() const
261  {
262  return new EmptyConstraintPS(*this);
263  }
264  };
265 
266  /**@brief Postsolves row singletons.
267  @ingroup Algo
268  */
269  class RowSingletonPS : public PostStep
270  {
271  private:
272  const int m_i;
273  const int m_old_i;
274  const int m_j;
275  const Real m_lhs;
276  const Real m_rhs;
277  const bool m_strictLo;
278  const bool m_strictUp;
279  const bool m_maxSense;
280  const Real m_obj;
282  const Real m_newLo;
283  const Real m_newUp;
284  const Real m_oldLo;
285  const Real m_oldUp;
287 
288  public:
289  ///
290  RowSingletonPS(const SPxLP& lp, int _i, int _j, bool strictLo, bool strictUp,
291  Real newLo, Real newUp, Real oldLo, Real oldUp)
292  : PostStep("RowSingleton", lp.nRows(), lp.nCols())
293  , m_i(_i)
294  , m_old_i(lp.nRows()-1)
295  , m_j(_j)
296  , m_lhs(lp.lhs(_i))
297  , m_rhs(lp.rhs(_i))
298  , m_strictLo(strictLo)
299  , m_strictUp(strictUp)
300  , m_maxSense(lp.spxSense() == SPxLP::MAXIMIZE)
301  , m_obj(lp.spxSense() == SPxLP::MINIMIZE ? lp.obj(_j) : -lp.obj(_j))
302  , m_col(lp.colVector(_j))
303  , m_newLo(newLo)
304  , m_newUp(newUp)
305  , m_oldLo(oldLo)
306  , m_oldUp(oldUp)
307  , m_row_obj(lp.rowObj(_i))
308  {}
309  /// copy constructor
311  : PostStep(old)
312  , m_i(old.m_i)
313  , m_old_i(old.m_old_i)
314  , m_j(old.m_j)
315  , m_lhs(old.m_lhs)
316  , m_rhs(old.m_rhs)
317  , m_strictLo(old.m_strictLo)
318  , m_strictUp(old.m_strictUp)
319  , m_maxSense(old.m_maxSense)
320  , m_obj(old.m_obj)
321  , m_col(old.m_col)
322  , m_newLo(old.m_newLo)
323  , m_newUp(old.m_newUp)
324  , m_oldLo(old.m_oldLo)
325  , m_oldUp(old.m_oldUp)
326  , m_row_obj(old.m_row_obj)
327  {}
328  /// assignment operator
330  {
331  if(this != &rhs)
332  {
333  PostStep::operator=(rhs);
334  m_col = rhs.m_col;
335  }
336 
337  return *this;
338  }
339  /// clone function for polymorphism
340  inline virtual PostStep* clone() const
341  {
342  return new RowSingletonPS(*this);
343  }
344  ///
345  virtual void execute(DVector& x, DVector& y, DVector& s, DVector& r,
346  DataArray<SPxSolver::VarStatus>& cBasis, DataArray<SPxSolver::VarStatus>& rBasis, bool isOptimal) const;
347  };
348 
349  /**@brief Postsolves forcing constraints.
350  @ingroup Algo
351  */
353  {
354  private:
355  const int m_i;
356  const int m_old_i;
357  const Real m_lRhs;
362  const bool m_lhsFixed;
363  const bool m_maxSense;
366  const Real m_lhs;
367  const Real m_rhs;
368  const Real m_rowobj;
369 
370  public:
371  ///
372  ForceConstraintPS(const SPxLP& lp, int _i, bool lhsFixed, DataArray<bool>& fixCols, DataArray<Real>& lo, DataArray<Real>& up)
373  : PostStep("ForceConstraint", lp.nRows(), lp.nCols())
374  , m_i(_i)
375  , m_old_i(lp.nRows()-1)
376  , m_lRhs(lhsFixed ? lp.lhs(_i) : lp.rhs(_i))
377  , m_row(lp.rowVector(_i))
378  , m_objs(lp.rowVector(_i).size())
379  , m_fixed(fixCols)
380  , m_cols(lp.rowVector(_i).size())
381  , m_lhsFixed(lhsFixed)
382  , m_maxSense(lp.spxSense() == SPxLP::MAXIMIZE)
383  , m_oldLowers(lo)
384  , m_oldUppers(up)
385  , m_lhs(lp.lhs(_i))
386  , m_rhs(lp.rhs(_i))
387  , m_rowobj(lp.rowObj(_i))
388  {
389  for(int k = 0; k < m_row.size(); ++k)
390  {
391  m_objs[k] = (lp.spxSense() == SPxLP::MINIMIZE ? lp.obj(m_row.index(k)) : -lp.obj(m_row.index(k)));
392  m_cols[k] = lp.colVector(m_row.index(k));
393  }
394  }
395  /// copy constructor
397  : PostStep(old)
398  , m_i(old.m_i)
399  , m_old_i(old.m_old_i)
400  , m_lRhs(old.m_lRhs)
401  , m_row(old.m_row)
402  , m_objs(old.m_objs)
403  , m_fixed(old.m_fixed)
404  , m_cols(old.m_cols)
405  , m_lhsFixed(old.m_lhsFixed)
406  , m_maxSense(old.m_maxSense)
407  , m_oldLowers(old.m_oldLowers)
408  , m_oldUppers(old.m_oldUppers)
409  , m_lhs(old.m_lhs)
410  , m_rhs(old.m_rhs)
411  , m_rowobj(old.m_rowobj)
412  {}
413  /// assignment operator
415  {
416  if(this != &rhs)
417  {
418  PostStep::operator=(rhs);
419  m_row = rhs.m_row;
420  m_objs = rhs.m_objs;
421  m_fixed = rhs.m_fixed;
422  m_cols = rhs.m_cols;
423  m_oldLowers = rhs.m_oldLowers;
424  m_oldUppers = rhs.m_oldUppers;
425  }
426 
427  return *this;
428  }
429  /// clone function for polymorphism
430  inline virtual PostStep* clone() const
431  {
432  return new ForceConstraintPS(*this);
433  }
434  ///
435  virtual void execute(DVector& x, DVector& y, DVector& s, DVector& r,
436  DataArray<SPxSolver::VarStatus>& cBasis, DataArray<SPxSolver::VarStatus>& rBasis, bool isOptimal) const;
437  };
438 
439  /**@brief Postsolves variable fixing.
440  @ingroup Algo
441  */
442  class FixVariablePS : public PostStep
443  {
444  private:
445  const int m_j;
446  const int m_old_j;
447  const Real m_val;
448  const Real m_obj;
449  const Real m_lower;
450  const Real m_upper;
451  const bool m_correctIdx; /// does the index mapping have to be updated in postsolving?
453 
454  public:
455  ///
456  FixVariablePS(const SPxLP& lp, SPxMainSM& simplifier, int _j, const Real val, bool correctIdx = true)
457  : PostStep("FixVariable", lp.nRows(), lp.nCols())
458  , m_j(_j)
459  , m_old_j(lp.nCols()-1)
460  , m_val(val)
461  , m_obj(lp.spxSense() == SPxLP::MINIMIZE ? lp.obj(_j) : -lp.obj(_j))
462  , m_lower(lp.lower(_j))
463  , m_upper(lp.upper(_j))
464  , m_correctIdx(correctIdx)
465  , m_col(lp.colVector(_j))
466  {
467  simplifier.addObjoffset(m_val*lp.obj(m_j));
468  }
469  /// copy constructor
471  : PostStep(old)
472  , m_j(old.m_j)
473  , m_old_j(old.m_old_j)
474  , m_val(old.m_val)
475  , m_obj(old.m_obj)
476  , m_lower(old.m_lower)
477  , m_upper(old.m_upper)
478  , m_correctIdx(old.m_correctIdx)
479  , m_col(old.m_col)
480  {}
481  /// assignment operator
483  {
484  if(this != &rhs)
485  {
486  PostStep::operator=(rhs);
487  m_col = rhs.m_col;
488  }
489 
490  return *this;
491  }
492  /// clone function for polymorphism
493  inline virtual PostStep* clone() const
494  {
495  return new FixVariablePS(*this);
496  }
497  ///
498  virtual void execute(DVector& x, DVector& y, DVector& s, DVector& r,
499  DataArray<SPxSolver::VarStatus>& cBasis, DataArray<SPxSolver::VarStatus>& rBasis, bool isOptimal) const;
500  };
501 
502  /**@brief Postsolves variable bound fixing.
503  @ingroup Algo
504  */
505  class FixBoundsPS : public PostStep
506  {
507  private:
508  const int m_j;
510 
511  public:
512  ///
513  FixBoundsPS(const SPxLP& lp, int j, Real val)
514  : PostStep("FixBounds", lp.nRows(), lp.nCols())
515  , m_j(j)
516  {
517  if (EQrel(lp.lower(j), lp.upper(j), eps()))
518  m_status = SPxSolver::FIXED;
519  else if (EQrel(val, lp.lower(j), eps()))
520  m_status = SPxSolver::ON_LOWER;
521  else if (EQrel(val, lp.upper(j), eps()))
522  m_status = SPxSolver::ON_UPPER;
523  else if (lp.lower(j) <= -infinity && lp.upper(j) >= infinity)
524  m_status = SPxSolver::ZERO;
525  else
526  {
527  throw SPxInternalCodeException("XMAISM14 This should never happen.");
528  }
529  }
530  /// copy constructor
532  : PostStep(old)
533  , m_j(old.m_j)
534  , m_status(old.m_status)
535  {}
536  /// assignment operator
538  {
539  if(this != &rhs)
540  {
541  PostStep::operator=(rhs);
542  m_status = rhs.m_status;
543  }
544 
545  return *this;
546  }
547  /// clone function for polymorphism
548  inline virtual PostStep* clone() const
549  {
550  FixBoundsPS* FixBoundsPSptr = 0;
551  spx_alloc(FixBoundsPSptr);
552  return new (FixBoundsPSptr) FixBoundsPS(*this);
553  }
554  ///
555  virtual void execute(DVector& x, DVector& y, DVector& s, DVector& r,
556  DataArray<SPxSolver::VarStatus>& cBasis, DataArray<SPxSolver::VarStatus>& rBasis, bool isOptimal) const;
557  };
558 
559  /**@brief Postsolves the case when constraints are removed due to a
560  variable with zero objective that is free in one direction.
561  @ingroup Algo
562  */
564  {
565  private:
566  const int m_j;
567  const int m_old_j;
568  const int m_old_i;
569  const Real m_bnd;
574  const bool m_loFree;
575 
576  public:
577  ///
578  FreeZeroObjVariablePS(const SPxLP& lp, int _j, bool loFree, SVector col_idx_sorted)
579  : PostStep("FreeZeroObjVariable", lp.nRows(), lp.nCols())
580  , m_j(_j)
581  , m_old_j(lp.nCols()-1)
582  , m_old_i(lp.nRows()-1)
583  , m_bnd(loFree ? lp.upper(_j) : lp.lower(_j))
584  , m_col(col_idx_sorted)
585  , m_lRhs(lp.colVector(_j).size())
586  , m_rowObj(lp.colVector(_j).size())
587  , m_rows(lp.colVector(_j).size())
588  , m_loFree(loFree)
589  {
590  for(int k = 0; k < m_col.size(); ++k)
591  {
592  assert(isNotZero(m_col.value(k)));
593 
594  int r = m_col.index(k);
595  if ((m_loFree && m_col.value(k) > 0) ||
596  (!m_loFree && m_col.value(k) < 0))
597  m_lRhs.add(k, lp.rhs(r));
598  else
599  m_lRhs.add(k, lp.lhs(r));
600 
601  m_rows[k] = lp.rowVector(r);
602  m_rowObj.add(k, lp.rowObj(r));
603  }
604  }
605  /// copy constructor
607  : PostStep(old)
608  , m_j(old.m_j)
609  , m_old_j(old.m_old_j)
610  , m_old_i(old.m_old_i)
611  , m_bnd(old.m_bnd)
612  , m_col(old.m_col)
613  , m_lRhs(old.m_lRhs)
614  , m_rowObj(old.m_rowObj)
615  , m_rows(old.m_rows)
616  , m_loFree(old.m_loFree)
617  {}
618  /// assignment operator
620  {
621  if(this != &rhs)
622  {
623  PostStep::operator=(rhs);
624  m_col = rhs.m_col;
625  m_lRhs = rhs.m_lRhs;
626  m_rowObj = rhs.m_rowObj;
627  m_rows = rhs.m_rows;
628  }
629 
630  return *this;
631  }
632  /// clone function for polymorphism
633  inline virtual PostStep* clone() const
634  {
635  FreeZeroObjVariablePS* FreeZeroObjVariablePSptr = 0;
636  spx_alloc(FreeZeroObjVariablePSptr);
637  return new (FreeZeroObjVariablePSptr) FreeZeroObjVariablePS(*this);
638  }
639  ///
640  virtual void execute(DVector& x, DVector& y, DVector& s, DVector& r,
641  DataArray<SPxSolver::VarStatus>& cBasis, DataArray<SPxSolver::VarStatus>& rBasis, bool isOptimal) const;
642  };
643 
644  /**@brief Postsolves column singletons with zero objective.
645  @ingroup Algo
646  */
648  {
649  private:
650  const int m_j;
651  const int m_i;
652  const int m_old_j;
653  const Real m_lhs;
654  const Real m_rhs;
655  const Real m_lower;
656  const Real m_upper;
658 
659  public:
660  ///
661  ZeroObjColSingletonPS(const SPxLP& lp, const SPxMainSM& , int _j, int _i)
662  : PostStep("ZeroObjColSingleton", lp.nRows(), lp.nCols())
663  , m_j(_j)
664  , m_i(_i)
665  , m_old_j(lp.nCols()-1)
666  , m_lhs(lp.lhs(_i))
667  , m_rhs(lp.rhs(_i))
668  , m_lower(lp.lower(_j))
669  , m_upper(lp.upper(_j))
670  , m_row(lp.rowVector(_i))
671  {}
672  /// copy constructor
674  : PostStep(old)
675  , m_j(old.m_j)
676  , m_i(old.m_i)
677  , m_old_j(old.m_old_j)
678  , m_lhs(old.m_lhs)
679  , m_rhs(old.m_rhs)
680  , m_lower(old.m_lower)
681  , m_upper(old.m_upper)
682  , m_row(old.m_row)
683  {}
684  /// assignment operator
686  {
687  if(this != &rhs)
688  {
689  PostStep::operator=(rhs);
690  m_row = rhs.m_row;
691  }
692 
693  return *this;
694  }
695  /// clone function for polymorphism
696  inline virtual PostStep* clone() const
697  {
698  ZeroObjColSingletonPS* ZeroObjColSingletonPSptr = 0;
699  spx_alloc(ZeroObjColSingletonPSptr);
700  return new (ZeroObjColSingletonPSptr) ZeroObjColSingletonPS(*this);
701  }
702  ///
703  virtual void execute(DVector& x, DVector& y, DVector& s, DVector& r,
704  DataArray<SPxSolver::VarStatus>& cBasis, DataArray<SPxSolver::VarStatus>& rBasis, bool isOptimal) const;
705  };
706 
707  /**@brief Postsolves free column singletons.
708  @ingroup Algo
709  */
711  {
712  private:
713  const int m_j;
714  const int m_i;
715  const int m_old_j;
716  const int m_old_i;
717  const Real m_obj;
718  const Real m_lRhs;
719  const bool m_onLhs;
720  const bool m_eqCons;
722 
723  public:
724  ///
725  FreeColSingletonPS(const SPxLP& lp, SPxMainSM& simplifier, int _j, int _i, Real slackVal)
726  : PostStep("FreeColSingleton", lp.nRows(), lp.nCols())
727  , m_j(_j)
728  , m_i(_i)
729  , m_old_j(lp.nCols()-1)
730  , m_old_i(lp.nRows()-1)
731  , m_obj(lp.spxSense() == SPxLP::MINIMIZE ? lp.obj(_j) : -lp.obj(_j))
732  , m_lRhs(slackVal)
733  , m_onLhs(EQ(slackVal, lp.lhs(_i)))
734  , m_eqCons(EQ(lp.lhs(_i), lp.rhs(_i)))
735  , m_row(lp.rowVector(_i))
736  {
737  assert(m_row[m_j] != 0.0);
738  simplifier.addObjoffset(m_lRhs*(lp.obj(m_j)/m_row[m_j]));
739  }
740  /// copy constructor
742  : PostStep(old)
743  , m_j(old.m_j)
744  , m_i(old.m_i)
745  , m_old_j(old.m_old_j)
746  , m_old_i(old.m_old_i)
747  , m_obj(old.m_obj)
748  , m_lRhs(old.m_lRhs)
749  , m_onLhs(old.m_onLhs)
750  , m_eqCons(old.m_eqCons)
751  , m_row(old.m_row)
752  {}
753  /// assignment operator
755  {
756  if(this != &rhs)
757  {
758  PostStep::operator=(rhs);
759  m_row = rhs.m_row;
760  }
761 
762  return *this;
763  }
764  /// clone function for polymorphism
765  inline virtual PostStep* clone() const
766  {
767  FreeColSingletonPS* FreeColSingletonPSptr = 0;
768  spx_alloc(FreeColSingletonPSptr);
769  return new (FreeColSingletonPSptr) FreeColSingletonPS(*this);
770  }
771  ///
772  virtual void execute(DVector& x, DVector& y, DVector& s, DVector& r,
773  DataArray<SPxSolver::VarStatus>& cBasis, DataArray<SPxSolver::VarStatus>& rBasis, bool isOptimal) const;
774  };
775 
776  /**@brief Postsolves doubleton equations combined with a column singleton.
777  @ingroup Algo
778  */
780  {
781  private:
782  const int m_j;
783  const int m_k;
784  const int m_i;
785  const bool m_maxSense;
786  const bool m_jFixed;
787  const Real m_jObj;
788  const Real m_kObj;
789  const Real m_aij;
790  const bool m_strictLo;
791  const bool m_strictUp;
792  const Real m_newLo;
793  const Real m_newUp;
794  const Real m_oldLo;
795  const Real m_oldUp;
796  const Real m_Lo_j;
797  const Real m_Up_j;
798  const Real m_lhs;
799  const Real m_rhs;
801 
802  public:
803  ///
804  DoubletonEquationPS(const SPxLP& lp, int _j, int _k, int _i, Real oldLo, Real oldUp)
805  : PostStep("DoubletonEquation", lp.nRows(), lp.nCols())
806  , m_j(_j)
807  , m_k(_k)
808  , m_i(_i)
809  , m_maxSense(lp.spxSense() == SPxLP::MAXIMIZE)
810  , m_jFixed(EQ(lp.lower(_j), lp.upper(_j)))
811  , m_jObj(lp.spxSense() == SPxLP::MINIMIZE ? lp.obj(_j) : -lp.obj(_j))
812  , m_kObj(lp.spxSense() == SPxLP::MINIMIZE ? lp.obj(_k) : -lp.obj(_k))
813  , m_aij(lp.colVector(_j).value(0))
814  , m_strictLo(lp.lower(_k) > oldLo)
815  , m_strictUp(lp.upper(_k) < oldUp)
816  , m_newLo(lp.lower(_k))
817  , m_newUp(lp.upper(_k))
818  , m_oldLo(oldLo)
819  , m_oldUp(oldUp)
820  , m_Lo_j(lp.lower(_j))
821  , m_Up_j(lp.upper(_j))
822  , m_lhs(lp.lhs(_i))
823  , m_rhs(lp.rhs(_i))
824  , m_col(lp.colVector(_k))
825  {}
826  /// copy constructor
828  : PostStep(old)
829  , m_j(old.m_j)
830  , m_k(old.m_k)
831  , m_i(old.m_i)
832  , m_maxSense(old.m_maxSense)
833  , m_jFixed(old.m_jFixed)
834  , m_jObj(old.m_jObj)
835  , m_kObj(old.m_kObj)
836  , m_aij(old.m_aij)
837  , m_strictLo(old.m_strictLo)
838  , m_strictUp(old.m_strictUp)
839  , m_newLo(old.m_newLo)
840  , m_newUp(old.m_newUp)
841  , m_oldLo(old.m_oldLo)
842  , m_oldUp(old.m_oldUp)
843  , m_Lo_j(old.m_Lo_j)
844  , m_Up_j(old.m_Up_j)
845  , m_lhs(old.m_lhs)
846  , m_rhs(old.m_rhs)
847  , m_col(old.m_col)
848  {}
849  /// assignment operator
851  {
852  if(this != &rhs)
853  {
854  PostStep::operator=(rhs);
855  m_col = rhs.m_col;
856  }
857 
858  return *this;
859  }
860  /// clone function for polymorphism
861  inline virtual PostStep* clone() const
862  {
863  DoubletonEquationPS* DoubletonEquationPSptr = 0;
864  spx_alloc(DoubletonEquationPSptr);
865  return new (DoubletonEquationPSptr) DoubletonEquationPS(*this);
866  }
867  ///
868  virtual void execute(DVector& x, DVector& y, DVector& s, DVector& r,
869  DataArray<SPxSolver::VarStatus>& cBasis, DataArray<SPxSolver::VarStatus>& rBasis, bool isOptimal) const;
870  };
871 
872  /**@brief Postsolves duplicate rows.
873  @ingroup Algo
874  */
875  class DuplicateRowsPS : public PostStep
876  {
877  private:
878  const int m_i;
880  const int m_maxLhsIdx;
881  const int m_minRhsIdx;
882  const bool m_maxSense;
883  const bool m_isFirst;
884  const bool m_isLast;
885  const bool m_fixed;
886  const int m_nCols;
892 
893  public:
894  DuplicateRowsPS(const SPxLP& lp, int _i,
895  int maxLhsIdx, int minRhsIdx, const DSVector& dupRows,
896  const DataArray<Real> scale, const DataArray<int> perm, const DataArray<bool> isLhsEqualRhs,
897  bool isTheLast, bool isFixedRow, bool isFirst = false)
898  : PostStep("DuplicateRows", lp.nRows(), lp.nCols())
899  , m_i(_i)
900  , m_i_rowObj(lp.rowObj(_i))
901  , m_maxLhsIdx((maxLhsIdx == -1) ? -1 : maxLhsIdx)
902  , m_minRhsIdx((minRhsIdx == -1) ? -1 : minRhsIdx)
903  , m_maxSense(lp.spxSense() == SPxLP::MAXIMIZE)
904  , m_isFirst(isFirst)
905  , m_isLast(isTheLast)
906  , m_fixed(isFixedRow)
907  , m_nCols(lp.nCols())
908  , m_scale(dupRows.size())
909  , m_rowObj(dupRows.size())
910  , m_rIdxLocalOld(dupRows.size())
911  , m_perm(perm)
912  , m_isLhsEqualRhs(isLhsEqualRhs)
913  {
914  Real rowScale = scale[_i];
915 
916  for(int k = 0; k < dupRows.size(); ++k)
917  {
918  m_scale.add(dupRows.index(k), rowScale / scale[dupRows.index(k)]);
919  m_rowObj.add(dupRows.index(k), lp.rowObj(dupRows.index(k)));
920  m_rIdxLocalOld[k] = dupRows.index(k);
921  }
922  }
923  /// copy constructor
925  : PostStep(old)
926  , m_i(old.m_i)
927  , m_i_rowObj(old.m_i_rowObj)
928  , m_maxLhsIdx(old.m_maxLhsIdx)
929  , m_minRhsIdx(old.m_minRhsIdx)
930  , m_maxSense(old.m_maxSense)
931  , m_isFirst(old.m_isFirst)
932  , m_isLast(old.m_isLast)
933  , m_fixed(old.m_fixed)
934  , m_nCols(old.m_nCols)
935  , m_scale(old.m_scale)
936  , m_rowObj(old.m_rowObj)
937  , m_rIdxLocalOld(old.m_rIdxLocalOld)
938  , m_perm(old.m_perm)
939  , m_isLhsEqualRhs(old.m_isLhsEqualRhs)
940  {}
941  /// assignment operator
943  {
944  if(this != &rhs)
945  {
946  PostStep::operator=(rhs);
947  m_scale = rhs.m_scale;
948  m_rowObj = rhs.m_rowObj;
949  m_rIdxLocalOld = rhs.m_rIdxLocalOld;
950  m_perm = rhs.m_perm;
951  m_isLhsEqualRhs = rhs.m_isLhsEqualRhs;
952  }
953 
954  return *this;
955  }
956  /// clone function for polymorphism
957  inline virtual PostStep* clone() const
958  {
959  DuplicateRowsPS* DuplicateRowsPSptr = 0;
960  spx_alloc(DuplicateRowsPSptr);
961  return new (DuplicateRowsPSptr) DuplicateRowsPS(*this);
962  }
963  virtual void execute(DVector& x, DVector& y, DVector& s, DVector& r,
964  DataArray<SPxSolver::VarStatus>& cBasis, DataArray<SPxSolver::VarStatus>& rBasis, bool isOptimal) const;
965  };
966 
967  /**@brief Postsolves duplicate columns.
968  @ingroup Algo
969  */
970  class DuplicateColsPS : public PostStep
971  {
972  private:
973  const int m_j;
974  const int m_k;
975  const Real m_loJ;
976  const Real m_upJ;
977  const Real m_loK;
978  const Real m_upK;
979  const Real m_scale;
980  const bool m_isFirst;
981  const bool m_isLast;
983 
984  public:
985  DuplicateColsPS(const SPxLP& lp, int _j, int _k, Real scale, DataArray<int> perm, bool isFirst = false, bool isTheLast = false)
986  : PostStep("DuplicateCols", lp.nRows(), lp.nCols())
987  , m_j(_j)
988  , m_k(_k)
989  , m_loJ(lp.lower(_j))
990  , m_upJ(lp.upper(_j))
991  , m_loK(lp.lower(_k))
992  , m_upK(lp.upper(_k))
993  , m_scale(scale)
994  , m_isFirst(isFirst)
995  , m_isLast(isTheLast)
996  , m_perm(perm)
997  {}
998  /// copy constructor
1000  : PostStep(old)
1001  , m_j(old.m_j)
1002  , m_k(old.m_k)
1003  , m_loJ(old.m_loJ)
1004  , m_upJ(old.m_upJ)
1005  , m_loK(old.m_loK)
1006  , m_upK (old.m_upK)
1007  , m_scale (old.m_scale)
1008  , m_isFirst(old.m_isFirst)
1009  , m_isLast(old.m_isLast)
1010  , m_perm(old.m_perm)
1011  {}
1012  /// assignment operator
1014  {
1015  if(this != &rhs)
1016  {
1017  PostStep::operator=(rhs);
1018  }
1019 
1020  return *this;
1021  }
1022  /// clone function for polymorphism
1023  inline virtual PostStep* clone() const
1024  {
1025  DuplicateColsPS* DuplicateColsPSptr = 0;
1026  spx_alloc(DuplicateColsPSptr);
1027  return new (DuplicateColsPSptr) DuplicateColsPS(*this);
1028  }
1029  virtual void execute(DVector& x, DVector& y, DVector& s, DVector& r,
1030  DataArray<SPxSolver::VarStatus>& cBasis, DataArray<SPxSolver::VarStatus>& rBasis, bool isOptimal) const;
1031  };
1032 
1033  /**@brief Postsolves multi aggregation.
1034  @ingroup Algo
1035  */
1037  {
1038  private:
1039  const int m_j;
1040  const int m_i;
1041  const int m_old_j;
1042  const int m_old_i;
1043  const Real m_upper;
1044  const Real m_lower;
1045  const Real m_obj;
1046  const Real m_const;
1047  const bool m_onLhs;
1048  const bool m_eqCons;
1051 
1052  public:
1053  ///
1054  MultiAggregationPS(const SPxLP& lp, SPxMainSM& simplifier, int _i, int _j, Real constant)
1055  : PostStep("MultiAggregation", lp.nRows(), lp.nCols())
1056  , m_j(_j)
1057  , m_i(_i)
1058  , m_old_j(lp.nCols()-1)
1059  , m_old_i(lp.nRows()-1)
1060  , m_upper(lp.upper(_j))
1061  , m_lower(lp.lower(_j))
1062  , m_obj(lp.spxSense() == SPxLP::MINIMIZE ? lp.obj(_j) : -lp.obj(_j))
1063  , m_const(constant)
1064  , m_onLhs(EQ(constant, lp.lhs(_i)))
1065  , m_eqCons(EQ(lp.lhs(_i), lp.rhs(_i)))
1066  , m_row(lp.rowVector(_i))
1067  , m_col(lp.colVector(_j))
1068  {
1069  assert(m_row[m_j] != 0.0);
1070  simplifier.addObjoffset(m_obj*m_const/m_row[m_j]);
1071  }
1072  /// copy constructor
1074  : PostStep(old)
1075  , m_j(old.m_j)
1076  , m_i(old.m_i)
1077  , m_old_j(old.m_old_j)
1078  , m_old_i(old.m_old_i)
1079  , m_upper(old.m_upper)
1080  , m_lower(old.m_lower)
1081  , m_obj(old.m_obj)
1082  , m_const(old.m_const)
1083  , m_onLhs(old.m_onLhs)
1084  , m_eqCons(old.m_eqCons)
1085  , m_row(old.m_row)
1086  , m_col(old.m_col)
1087  {}
1088  /// assignment operator
1090  {
1091  if(this != &rhs)
1092  {
1093  PostStep::operator=(rhs);
1094  m_row = rhs.m_row;
1095  m_col = rhs.m_col;
1096  }
1097 
1098  return *this;
1099  }
1100  /// clone function for polymorphism
1101  inline virtual PostStep* clone() const
1102  {
1103  MultiAggregationPS* MultiAggregationPSptr = 0;
1104  spx_alloc(MultiAggregationPSptr);
1105  return new (MultiAggregationPSptr) MultiAggregationPS(*this);
1106  }
1107  ///
1108  virtual void execute(DVector& x, DVector& y, DVector& s, DVector& r,
1109  DataArray<SPxSolver::VarStatus>& cBasis, DataArray<SPxSolver::VarStatus>& rBasis, bool isOptimal) const;
1110  };
1111 
1112  /**@brief Postsolves variable bound tightening from pseudo objective propagation.
1113  @ingroup Algo
1114  */
1115  class TightenBoundsPS : public PostStep
1116  {
1117  private:
1118  const int m_j;
1121 
1122  public:
1123  ///
1124  TightenBoundsPS(const SPxLP& lp, int j, Real origupper, Real origlower)
1125  : PostStep("TightenBounds", lp.nRows(), lp.nCols())
1126  , m_j(j)
1127  , m_origupper(origupper)
1128  , m_origlower(origlower)
1129  {
1130  }
1131  /// copy constructor
1133  : PostStep(old)
1134  , m_j(old.m_j)
1135  , m_origupper(old.m_origupper)
1136  , m_origlower(old.m_origlower)
1137  {}
1138  /// assignment operator
1140  {
1141  return *this;
1142  }
1143  /// clone function for polymorphism
1144  inline virtual PostStep* clone() const
1145  {
1146  TightenBoundsPS* TightenBoundsPSptr = 0;
1147  spx_alloc(TightenBoundsPSptr);
1148  return new (TightenBoundsPSptr) TightenBoundsPS(*this);
1149  }
1150  ///
1151  virtual void execute(DVector& x, DVector& y, DVector& s, DVector& r,
1152  DataArray<SPxSolver::VarStatus>& cBasis, DataArray<SPxSolver::VarStatus>& rBasis, bool isOptimal) const;
1153  };
1154  // friends
1155  friend class FreeConstraintPS;
1156  friend class EmptyConstraintPS;
1157  friend class RowSingletonPS;
1158  friend class ForceConstraintPS;
1159  friend class FixVariablePS;
1160  friend class FixBoundsPS;
1163  friend class FreeColSingletonPS;
1164  friend class DoubletonEquationPS;
1165  friend class DuplicateRowsPS;
1166  friend class DuplicateColsPS;
1167 
1168 private:
1169  //------------------------------------
1170  //**@name Types */
1171  //@{
1172  /// Different simplification steps.
1174  {
1180  FIX_COL = 5,
1191  };
1192  //@}
1193 
1194  //------------------------------------
1195  //**@name Data */
1196  //@{
1197  ///
1198  DVector m_prim; ///< unsimplified primal solution vector.
1199  DVector m_slack; ///< unsimplified slack vector.
1200  DVector m_dual; ///< unsimplified dual solution vector.
1201  DVector m_redCost; ///< unsimplified reduced cost vector.
1202  DataArray<SPxSolver::VarStatus> m_cBasisStat; ///< basis status of columns.
1203  DataArray<SPxSolver::VarStatus> m_rBasisStat; ///< basis status of rows.
1204  DataArray<int> m_cIdx; ///< column index vector in original LP.
1205  DataArray<int> m_rIdx; ///< row index vector in original LP.
1206  DataArray<PostStep*> m_hist; ///< vector of presolve history.
1207  Array<DSVector> m_classSetRows; ///< stores parallel classes with non-zero colum entry
1208  Array<DSVector> m_classSetCols; ///< stores parallel classes with non-zero row entry
1209  Array<DSVector> m_dupRows; ///< arrange duplicate rows using bucket sort w.r.t. their pClass values
1210  Array<DSVector> m_dupCols; ///< arrange duplicate columns w.r.t. their pClass values
1211  bool m_postsolved; ///< status of postsolving.
1212  Real m_epsilon; ///< epsilon zero.
1213  Real m_feastol; ///< primal feasibility tolerance.
1214  Real m_opttol; ///< dual feasibility tolerance.
1215  DataArray<int> m_stat; ///< preprocessing history.
1216  SPxLP::SPxSense m_thesense; ///< optimization sense.
1217  bool m_keepbounds; ///< keep some bounds (for boundflipping)
1218  int m_addedcols; ///< columns added by handleRowObjectives()
1219  Result m_result; ///< result of the simplification.
1220  Real m_cutoffbound; ///< the cutoff bound that is found by heuristics
1221  Real m_pseudoobj; ///< the pseudo objective function value
1222  //@}
1223 
1224 private:
1225  //------------------------------------
1226  //**@name Private helpers */
1227  //@{
1228  /// handle row objectives
1229  void handleRowObjectives(SPxLP& lp);
1230 
1231  /// handles extreme values by setting them to zero or infinity.
1232  void handleExtremes(SPxLP& lp);
1233 
1234  /// computes the minimum and maximum residual activity for a given row and column. If colNumber is set to -1, then
1235  // the activity of the row is returned.
1236  void computeMinMaxResidualActivity(SPxLP& lp, int rowNumber, int colNumber, Real& minAct, Real& maxAct);
1237 
1238  /// calculate min/max value for the multi aggregated variables
1239  void computeMinMaxValues(SPxLP& lp, Real side, Real val, Real minRes, Real maxRes, Real& minVal, Real& maxVal);
1240 
1241  /// tries to find good lower bound solutions by applying some trivial heuristics
1242  void trivialHeuristic(SPxLP& lp);
1243 
1244  /// checks a solution for feasibility
1245  bool checkSolution(SPxLP& lp, DVector sol);
1246 
1247  /// tightens variable bounds by propagating the pseudo objective function value.
1248  void propagatePseudoobj(SPxLP& lp);
1249 
1250  /// removed empty rows and empty columns.
1251  Result removeEmpty(SPxLP& lp);
1252 
1253  /// remove row singletons.
1254  Result removeRowSingleton(SPxLP& lp, const SVector& row, int& i);
1255 
1256  /// performs simplification steps on the rows of the LP.
1257  Result simplifyRows(SPxLP& lp, bool& again);
1258 
1259  /// performs simplification steps on the columns of the LP.
1260  Result simplifyCols(SPxLP& lp, bool& again);
1261 
1262  /// performs simplification steps on the LP based on dual concepts.
1263  Result simplifyDual(SPxLP& lp, bool& again);
1264 
1265  /// performs multi-aggregations of variable based upon constraint activitu.
1266  Result multiaggregation(SPxLP& lp, bool& again);
1267 
1268  /// removes duplicate rows.
1269  Result duplicateRows(SPxLP& lp, bool& again);
1270 
1271  /// removes duplicate columns
1272  Result duplicateCols(SPxLP& lp, bool& again);
1273 
1274  /// handles the fixing of a variable. correctIdx is true iff the index mapping has to be updated.
1275  void fixColumn(SPxLP& lp, int i, bool correctIdx = true);
1276 
1277  /// removes a row in the LP.
1278  void removeRow(SPxLP& lp, int i)
1279  {
1280  m_rIdx[i] = m_rIdx[lp.nRows()-1];
1281  lp.removeRow(i);
1282  }
1283  /// removes a column in the LP.
1284  void removeCol(SPxLP& lp, int j)
1285  {
1286  m_cIdx[j] = m_cIdx[lp.nCols()-1];
1287  lp.removeCol(j);
1288  }
1289  /// returns for a given row index of the (reduced) LP the corresponding row index in the unsimplified LP.
1290  int rIdx(int i) const
1291  {
1292  return m_rIdx[i];
1293  }
1294  /// returns for a given column index of the (reduced) LP the corresponding column index in the unsimplified LP.
1295  int cIdx(int j) const
1296  {
1297  return m_cIdx[j];
1298  }
1299  ///
1300  Real epsZero() const
1301  {
1302  return m_epsilon;
1303  }
1304  ///
1305  Real feastol() const
1306  {
1307  return m_feastol;
1308  }
1309  ///
1310  Real opttol() const
1311  {
1312  return m_opttol;
1313  }
1314  //@}
1315 
1316 public:
1317 
1318  //------------------------------------
1319  //**@name Constructors / destructors */
1320  //@{
1321  /// default constructor.
1323  : SPxSimplifier("MainSM", ttype)
1324  , m_postsolved(0)
1325  , m_epsilon(DEFAULT_EPS_ZERO)
1326  , m_feastol(DEFAULT_BND_VIOL)
1327  , m_opttol(DEFAULT_BND_VIOL)
1328  , m_stat(16)
1329  , m_thesense(SPxLP::MAXIMIZE)
1330  , m_keepbounds(false)
1331  , m_addedcols(0)
1332  , m_result(OKAY)
1333  , m_cutoffbound(-infinity)
1334  , m_pseudoobj(-infinity)
1335  {}
1336  /// copy constructor.
1337  SPxMainSM(const SPxMainSM& old)
1338  : SPxSimplifier(old)
1339  , m_prim(old.m_prim)
1340  , m_slack(old.m_slack)
1341  , m_dual(old.m_dual)
1342  , m_redCost(old.m_redCost)
1343  , m_cBasisStat(old.m_cBasisStat)
1344  , m_rBasisStat(old.m_rBasisStat)
1345  , m_cIdx(old.m_cIdx)
1346  , m_rIdx(old.m_rIdx)
1347  , m_postsolved(old.m_postsolved)
1348  , m_epsilon(old.m_epsilon)
1349  , m_feastol(old.m_feastol)
1350  , m_opttol(old.m_opttol)
1351  , m_stat(old.m_stat)
1352  , m_thesense(old.m_thesense)
1353  , m_keepbounds(old.m_keepbounds)
1354  , m_addedcols(old.m_addedcols)
1355  , m_result(old.m_result)
1356  , m_cutoffbound(old.m_cutoffbound)
1357  , m_pseudoobj(old.m_pseudoobj)
1358  {
1359  // copy pointers in m_hist
1360  m_hist.reSize(0);
1361  for(int k = 0; k < old.m_hist.size(); ++k)
1362  {
1363  if(old.m_hist[k] != 0)
1364  m_hist.append(old.m_hist[k]->clone());
1365  else
1366  m_hist.append(0);
1367  }
1368  }
1369  /// assignment operator
1371  {
1372  if(this != &rhs)
1373  {
1375  m_prim = rhs.m_prim;
1376  m_slack = rhs.m_slack;
1377  m_dual = rhs.m_dual;
1378  m_redCost = rhs.m_redCost;
1379  m_cBasisStat = rhs.m_cBasisStat;
1380  m_rBasisStat = rhs.m_rBasisStat;
1381  m_cIdx = rhs.m_cIdx;
1382  m_rIdx = rhs.m_rIdx;
1383  m_postsolved = rhs.m_postsolved;
1384  m_epsilon = rhs.m_epsilon;
1385  m_feastol = rhs.m_feastol;
1386  m_opttol = rhs.m_opttol;
1387  m_stat = rhs.m_stat;
1388  m_thesense = rhs.m_thesense;
1389  m_keepbounds = rhs.m_keepbounds;
1390  m_addedcols = rhs.m_addedcols;
1391  m_result = rhs.m_result;
1392  m_cutoffbound = rhs.m_cutoffbound;
1393  m_pseudoobj = rhs.m_pseudoobj;
1394 
1395  // delete pointers in m_hist
1396  for(int k = 0; k < m_hist.size(); ++k)
1397  {
1398  m_hist[k]->~PostStep();
1399  spx_free(m_hist[k]);
1400  }
1401 
1402  m_hist.clear();
1403 
1404  // copy pointers in m_hist
1405  for(int k = 0; k < rhs.m_hist.size(); ++k)
1406  {
1407  if(rhs.m_hist[k] != 0)
1408  m_hist.append(rhs.m_hist[k]->clone());
1409  else
1410  m_hist.append(0);
1411  }
1412  }
1413 
1414  return *this;
1415  }
1416  /// destructor.
1417  virtual ~SPxMainSM()
1418  {
1419  // delete pointers in m_hist
1420  for(int k = 0; k < m_hist.size(); ++k)
1421  {
1422  if( m_hist[k] != 0 )
1423  {
1424  m_hist[k]->~PostStep();
1425  spx_free(m_hist[k]);
1426  }
1427  }
1428  }
1429  /// clone function for polymorphism
1430  inline virtual SPxSimplifier* clone() const
1431  {
1432  return new SPxMainSM(*this);
1433  }
1434  //@}
1435 
1436  //------------------------------------
1437  //**@name LP simplification */
1438  //@{
1439  /// simplify SPxLP \p lp with identical primal and dual feasibility tolerance.
1440  virtual Result simplify(SPxLP& lp, Real eps, Real delta)
1441  {
1442  return simplify(lp, eps, delta, delta);
1443  }
1444  /// simplify SPxLP \p lp with independent primal and dual feasibility tolerance.
1445  virtual Result simplify(SPxLP& lp, Real eps, Real ftol, Real otol, bool keepbounds = false);
1446 
1447  /// reconstructs an optimal solution for the unsimplified LP.
1448  virtual void unsimplify(const Vector& x, const Vector& y, const Vector& s, const Vector& r,
1449  const SPxSolver::VarStatus rows[], const SPxSolver::VarStatus cols[], bool isOptimal = true);
1450 
1451  /// returns result status of the simplification
1452  virtual Result result() const
1453  {
1454  return m_result;
1455  }
1456 
1457  /// specifies whether an optimal solution has already been unsimplified.
1458  virtual bool isUnsimplified() const
1459  {
1460  return m_postsolved;
1461  }
1462  /// returns a reference to the unsimplified primal solution.
1463  virtual const Vector& unsimplifiedPrimal()
1464  {
1465  assert(m_postsolved);
1466  return m_prim;
1467  }
1468  /// returns a reference to the unsimplified dual solution.
1469  virtual const Vector& unsimplifiedDual()
1470  {
1471  assert(m_postsolved);
1472  return m_dual;
1473  }
1474  /// returns a reference to the unsimplified slack values.
1475  virtual const Vector& unsimplifiedSlacks()
1476  {
1477  assert(m_postsolved);
1478  return m_slack;
1479  }
1480  /// returns a reference to the unsimplified reduced costs.
1481  virtual const Vector& unsimplifiedRedCost()
1482  {
1483  assert(m_postsolved);
1484  return m_redCost;
1485  }
1486  /// gets basis status for a single row.
1488  {
1489  assert(m_postsolved);
1490  return m_rBasisStat[i];
1491  }
1492  /// gets basis status for a single column.
1494  {
1495  assert(m_postsolved);
1496  return m_cBasisStat[j];
1497  }
1498  /// get optimal basis.
1499  virtual void getBasis(SPxSolver::VarStatus rows[], SPxSolver::VarStatus cols[], const int rowsSize = -1, const int colsSize = -1) const
1500  {
1501  assert(m_postsolved);
1502  assert(rowsSize < 0 || rowsSize >= m_rBasisStat.size());
1503  assert(colsSize < 0 || colsSize >= m_cBasisStat.size());
1504 
1505  for(int i = 0; i < m_rBasisStat.size(); ++i)
1506  rows[i] = m_rBasisStat[i];
1507 
1508  for(int j = 0; j < m_cBasisStat.size(); ++j)
1509  cols[j] = m_cBasisStat[j];
1510  }
1511  //@}
1512 
1513 private:
1514  //------------------------------------
1515  //**@name Types */
1516  //@{
1517  /// comparator for class SVector::Element: compare nonzeros according to value
1519  {
1520  public:
1522 
1523  int operator()(const SVector::Element& e1, const SVector::Element& e2) const
1524  {
1525  if (EQ(e1.val, e2.val))
1526  return 0;
1527  if (e1.val < e2.val)
1528  return -1;
1529  else // (e1.val > e2.val)
1530  return 1;
1531  }
1532  };
1533  /// comparator for class SVector::Element: compare nonzeros according to index
1534  struct IdxCompare
1535  {
1536  public:
1538 
1539  int operator()(const SVector::Element& e1, const SVector::Element& e2) const
1540  {
1541  if (EQ(e1.idx, e2.idx))
1542  return 0;
1543  if (e1.idx < e2.idx)
1544  return -1;
1545  else // (e1.idx > e2.idx)
1546  return 1;
1547  }
1548  };
1549  //@}
1550 };
1551 
1552 } // namespace soplex
1553 #endif // _SPXMAINSM_H_
const VectorBase< R > & rhs() const
Returns right hand side vector.
Definition: spxlpbase.h:219
DVector m_prim
unsimplified primal solution vector.
Definition: spxmainsm.h:1198
bool isNotZero(Real a, Real eps=Param::epsilon())
returns true iff |a| > eps
Definition: spxdefines.h:417
Real m_opttol
dual feasibility tolerance.
Definition: spxmainsm.h:1214
virtual bool isUnsimplified() const
specifies whether an optimal solution has already been unsimplified.
Definition: spxmainsm.h:1458
DataArray< PostStep * > m_hist
vector of presolve history.
Definition: spxmainsm.h:1206
Postsolves multi aggregation.
Definition: spxmainsm.h:1036
Exception class for things that should NEVER happen.This class is derived from the SoPlex exception b...
Definition: exceptions.h:109
RowObjPS & operator=(const RowObjPS &rhs)
assignment operator
Definition: spxmainsm.h:148
virtual void removeRow(int i)
Removes i &#39;th row.
Definition: spxlpbase.h:884
MultiAggregationPS(const MultiAggregationPS &old)
copy constructor
Definition: spxmainsm.h:1073
free variable fixed to zero.
Definition: spxsolver.h:194
friend class FreeConstraintPS
Definition: spxmainsm.h:1155
Result removeRowSingleton(SPxLP &lp, const SVector &row, int &i)
remove row singletons.
Definition: spxmainsm.cpp:1983
DataArray< int > m_stat
preprocessing history.
Definition: spxmainsm.h:1215
EmptyConstraintPS(const SPxLP &lp, int _i)
Definition: spxmainsm.h:231
ZeroObjColSingletonPS & operator=(const ZeroObjColSingletonPS &rhs)
assignment operator
Definition: spxmainsm.h:685
PostStep & operator=(const PostStep &)
assignment operator
Definition: spxmainsm.h:97
SPxMainSM(Timer::TYPE ttype=Timer::USER_TIME)
default constructor.
Definition: spxmainsm.h:1322
const VectorBase< R > & upper() const
Returns upper bound vector.
Definition: spxlpbase.h:456
#define DEFAULT_BND_VIOL
default allowed bound violation
Definition: spxdefines.h:223
Real m_epsilon
epsilon zero.
Definition: spxmainsm.h:1212
THREADLOCAL const Real infinity
Definition: spxdefines.cpp:26
Postsolves variable bound fixing.
Definition: spxmainsm.h:505
Result
Result of the simplification.
Definition: spxsimplifier.h:81
Postsolves duplicate rows.
Definition: spxmainsm.h:875
int size() const
Number of used indices.
Definition: svectorbase.h:152
const char * m_name
name of the simplifier
Definition: spxmainsm.h:77
FixVariablePS(const FixVariablePS &old)
copy constructor
Definition: spxmainsm.h:470
void computeMinMaxResidualActivity(SPxLP &lp, int rowNumber, int colNumber, Real &minAct, Real &maxAct)
computes the minimum and maximum residual activity for a given row and column. If colNumber is set to...
Definition: spxmainsm.cpp:1583
Real m_feastol
primal feasibility tolerance.
Definition: spxmainsm.h:1213
virtual PostStep * clone() const
clone function for polymorphism
Definition: spxmainsm.h:260
DataArray< SPxSolver::VarStatus > m_rBasisStat
basis status of rows.
Definition: spxmainsm.h:1203
Exception classes for SoPlex.
SPxMainSM & operator=(const SPxMainSM &rhs)
assignment operator
Definition: spxmainsm.h:1370
virtual PostStep * clone() const
clone function for polymorphism
Definition: spxmainsm.h:162
FreeZeroObjVariablePS(const SPxLP &lp, int _j, bool loFree, SVector col_idx_sorted)
Definition: spxmainsm.h:578
Real opttol() const
Definition: spxmainsm.h:1310
SPxLP::SPxSense m_thesense
optimization sense.
Definition: spxmainsm.h:1216
virtual void execute(DVector &x, DVector &y, DVector &s, DVector &r, DataArray< SPxSolver::VarStatus > &cBasis, DataArray< SPxSolver::VarStatus > &rBasis, bool isOptimal) const =0
executes the postsolving.
Safe arrays of arbitrary types.Class Array provides safe arrays of arbitrary type. Array elements are accessed just like ordinary C++ array elements by means of the index operator[](). Safety is provided by.
Definition: array.h:62
virtual Result simplify(SPxLP &lp, Real eps, Real delta)
simplify SPxLP lp with identical primal and dual feasibility tolerance.
Definition: spxmainsm.h:1440
friend class DuplicateRowsPS
Definition: spxmainsm.h:1165
PostStep(const PostStep &old)
copy constructor.
Definition: spxmainsm.h:91
FixVariablePS(const SPxLP &lp, SPxMainSM &simplifier, int _j, const Real val, bool correctIdx=true)
Definition: spxmainsm.h:456
int cIdx(int j) const
returns for a given column index of the (reduced) LP the corresponding column index in the unsimplifi...
Definition: spxmainsm.h:1295
void clear()
remove all elements.
Definition: dataarray.h:205
FixBoundsPS & operator=(const FixBoundsPS &rhs)
assignment operator
Definition: spxmainsm.h:537
variable fixed to identical bounds.
Definition: spxsolver.h:193
RowSingletonPS & operator=(const RowSingletonPS &rhs)
assignment operator
Definition: spxmainsm.h:329
Base class for postsolving operations.Class PostStep is an abstract base class providing the interfac...
Definition: spxmainsm.h:73
DVector m_dual
unsimplified dual solution vector.
Definition: spxmainsm.h:1200
virtual const Vector & unsimplifiedDual()
returns a reference to the unsimplified dual solution.
Definition: spxmainsm.h:1469
FreeConstraintPS(const FreeConstraintPS &old)
copy constructor
Definition: spxmainsm.h:189
virtual void removeCol(int i)
Removes i &#39;th column.
Definition: spxlpbase.h:981
R & value(int n)
Reference to value of n &#39;th nonzero.
Definition: svectorbase.h:254
DuplicateRowsPS & operator=(const DuplicateRowsPS &rhs)
assignment operator
Definition: spxmainsm.h:942
Postsolves empty constraints.
Definition: spxmainsm.h:222
PostStep(const char *p_name, int nR=0, int nC=0)
constructor.
Definition: spxmainsm.h:85
FreeColSingletonPS(const FreeColSingletonPS &old)
copy constructor
Definition: spxmainsm.h:741
Real feastol() const
Definition: spxmainsm.h:1305
void handleExtremes(SPxLP &lp)
handles extreme values by setting them to zero or infinity.
Definition: spxmainsm.cpp:1387
bool m_postsolved
status of postsolving.
Definition: spxmainsm.h:1211
virtual SPxSolver::VarStatus getBasisRowStatus(int i) const
gets basis status for a single row.
Definition: spxmainsm.h:1487
int rIdx(int i) const
returns for a given row index of the (reduced) LP the corresponding row index in the unsimplified LP...
Definition: spxmainsm.h:1290
virtual void unsimplify(const Vector &x, const Vector &y, const Vector &s, const Vector &r, const SPxSolver::VarStatus rows[], const SPxSolver::VarStatus cols[], bool isOptimal=true)
reconstructs an optimal solution for the unsimplified LP.
Definition: spxmainsm.cpp:4659
virtual PostStep * clone() const
clone function for polymorphism
Definition: spxmainsm.h:1101
FreeColSingletonPS(const SPxLP &lp, SPxMainSM &simplifier, int _j, int _i, Real slackVal)
Definition: spxmainsm.h:725
ZeroObjColSingletonPS(const SPxLP &lp, const SPxMainSM &, int _j, int _i)
Definition: spxmainsm.h:661
int idx
Index of nonzero element.
Definition: svectorbase.h:40
LP simplification base class.
void fixColumn(SPxLP &lp, int i, bool correctIdx=true)
handles the fixing of a variable. correctIdx is true iff the index mapping has to be updated...
Definition: spxmainsm.cpp:4353
FreeZeroObjVariablePS & operator=(const FreeZeroObjVariablePS &rhs)
assignment operator
Definition: spxmainsm.h:619
virtual void addObjoffset(const Real val)
add objective offset.
int nRows() const
Returns number of rows in LP.
Definition: spxlpbase.h:151
void add(const SVectorBase< S > &vec)
Append nonzeros of sv.
Definition: dsvectorbase.h:216
void spx_alloc(T &p, int n=1)
Allocate memory.
Definition: spxalloc.h:48
simplification could be done
Definition: spxsimplifier.h:83
virtual PostStep * clone() const
clone function for polymorphism
Definition: spxmainsm.h:548
MultiAggregationPS(const SPxLP &lp, SPxMainSM &simplifier, int _i, int _j, Real constant)
Definition: spxmainsm.h:1054
Postsolves the case when constraints are removed due to a variable with zero objective that is free i...
Definition: spxmainsm.h:563
virtual const char * getName() const
get name of simplifying step.
Definition: spxmainsm.h:107
virtual PostStep * clone() const
clone function for polymorphism
Definition: spxmainsm.h:633
friend class RowSingletonPS
Definition: spxmainsm.h:1157
EmptyConstraintPS(const EmptyConstraintPS &old)
copy constructor
Definition: spxmainsm.h:238
SPxSimplifier & operator=(const SPxSimplifier &rhs)
assignment operator
SPxSense
Optimization sense.
Definition: spxlpbase.h:97
TightenBoundsPS & operator=(const TightenBoundsPS &rhs)
assignment operator
Definition: spxmainsm.h:1139
virtual ~PostStep()
destructor.
Definition: spxmainsm.h:102
virtual PostStep * clone() const
clone function for polymorphism
Definition: spxmainsm.h:493
virtual PostStep * clone() const
clone function for polymorphism
Definition: spxmainsm.h:861
double Real
Definition: spxdefines.h:215
SPxSolver::VarStatus m_status
Definition: spxmainsm.h:509
Array< DSVector > m_classSetCols
stores parallel classes with non-zero row entry
Definition: spxmainsm.h:1208
RowSingletonPS(const RowSingletonPS &old)
copy constructor
Definition: spxmainsm.h:310
FreeConstraintPS(const SPxLP &lp, int _i)
Definition: spxmainsm.h:181
Result duplicateCols(SPxLP &lp, bool &again)
removes duplicate columns
Definition: spxmainsm.cpp:3977
void removeCol(SPxLP &lp, int j)
removes a column in the LP.
Definition: spxmainsm.h:1284
int nRows
number of rows
Definition: spxmainsm.h:81
TightenBoundsPS(const SPxLP &lp, int j, Real origupper, Real origlower)
Definition: spxmainsm.h:1124
SPxSense spxSense() const
Returns the optimization sense.
Definition: spxlpbase.h:510
int & index(int n)
Reference to index of n &#39;th nonzero.
Definition: svectorbase.h:236
Postsolves row singletons.
Definition: spxmainsm.h:269
MultiAggregationPS & operator=(const MultiAggregationPS &rhs)
assignment operator
Definition: spxmainsm.h:1089
virtual PostStep * clone() const
clone function for polymorphism
Definition: spxmainsm.h:696
Result simplifyRows(SPxLP &lp, bool &again)
performs simplification steps on the rows of the LP.
Definition: spxmainsm.cpp:2056
virtual void getBasis(SPxSolver::VarStatus rows[], SPxSolver::VarStatus cols[], const int rowsSize=-1, const int colsSize=-1) const
get optimal basis.
Definition: spxmainsm.h:1499
DuplicateColsPS & operator=(const DuplicateColsPS &rhs)
assignment operator
Definition: spxmainsm.h:1013
LP simplification abstract base class.Instances of classes derived from SPxSimplifier may be loaded t...
Definition: spxsimplifier.h:41
bool checkSolution(SPxLP &lp, DVector sol)
checks a solution for feasibility
Definition: spxmainsm.cpp:1793
virtual PostStep * clone() const
clone function for polymorphism
Definition: spxmainsm.h:213
DuplicateColsPS(const SPxLP &lp, int _j, int _k, Real scale, DataArray< int > perm, bool isFirst=false, bool isTheLast=false)
Definition: spxmainsm.h:985
R rowObj(int i) const
Definition: spxlpbase.h:279
void append(const T &t)
append element t.
Definition: dataarray.h:121
friend class DoubletonEquationPS
Definition: spxmainsm.h:1164
SPxMainSM(const SPxMainSM &old)
copy constructor.
Definition: spxmainsm.h:1337
FixVariablePS & operator=(const FixVariablePS &rhs)
assignment operator
Definition: spxmainsm.h:482
ForceConstraintPS(const SPxLP &lp, int _i, bool lhsFixed, DataArray< bool > &fixCols, DataArray< Real > &lo, DataArray< Real > &up)
Definition: spxmainsm.h:372
Postsolves doubleton equations combined with a column singleton.
Definition: spxmainsm.h:779
Postsolves free column singletons.
Definition: spxmainsm.h:710
ForceConstraintPS & operator=(const ForceConstraintPS &rhs)
assignment operator
Definition: spxmainsm.h:414
#define DEFAULT_EPS_ZERO
default allowed additive zero: 1.0 + EPS_ZERO == 1.0
Definition: spxdefines.h:227
comparator for class SVector::Element: compare nonzeros according to value
Definition: spxmainsm.h:1518
R obj(int i) const
Returns objective value of column i.
Definition: spxlpbase.h:403
virtual PostStep * clone() const
clone function for polymorphism
Definition: spxmainsm.h:1144
const VectorBase< R > & lhs() const
Returns left hand side vector.
Definition: spxlpbase.h:253
friend class FixBoundsPS
Definition: spxmainsm.h:1160
DataArray< int > m_cIdx
column index vector in original LP.
Definition: spxmainsm.h:1204
Result m_result
result of the simplification.
Definition: spxmainsm.h:1219
FixBoundsPS(const FixBoundsPS &old)
copy constructor
Definition: spxmainsm.h:531
DuplicateColsPS(const DuplicateColsPS &old)
copy constructor
Definition: spxmainsm.h:999
virtual Result result() const
returns result status of the simplification
Definition: spxmainsm.h:1452
variable set to its upper bound.
Definition: spxsolver.h:191
DoubletonEquationPS(const SPxLP &lp, int _j, int _k, int _i, Real oldLo, Real oldUp)
Definition: spxmainsm.h:804
virtual PostStep * clone() const
clone function for polymorphism
Definition: spxmainsm.h:340
DuplicateRowsPS(const DuplicateRowsPS &old)
copy constructor
Definition: spxmainsm.h:924
DoubletonEquationPS(const DoubletonEquationPS &old)
copy constructor
Definition: spxmainsm.h:827
variable set to its lower bound.
Definition: spxsolver.h:192
Array< DSVector > m_dupCols
arrange duplicate columns w.r.t. their pClass values
Definition: spxmainsm.h:1210
virtual PostStep * clone() const =0
clone function for polymorphism
Debugging, floating point type and parameter definitions.
Postsolves row objectives.
Definition: spxmainsm.h:128
bool EQ(Real a, Real b, Real eps=Param::epsilon())
returns true iff |a-b| <= eps
Definition: spxdefines.h:375
DataArray< int > m_rIdx
row index vector in original LP.
Definition: spxmainsm.h:1205
Postsolves column singletons with zero objective.
Definition: spxmainsm.h:647
TightenBoundsPS(const TightenBoundsPS &old)
copy constructor
Definition: spxmainsm.h:1132
bool m_keepbounds
keep some bounds (for boundflipping)
Definition: spxmainsm.h:1217
Everything should be within this namespace.
TYPE
types of timers
Definition: timer.h:99
bool EQrel(Real a, Real b, Real eps=Param::epsilon())
returns true iff |relDiff(a,b)| <= eps
Definition: spxdefines.h:423
virtual bool checkBasisDim(DataArray< SPxSolver::VarStatus > rows, DataArray< SPxSolver::VarStatus > cols) const
Definition: spxmainsm.cpp:66
friend class ForceConstraintPS
Definition: spxmainsm.h:1158
void handleRowObjectives(SPxLP &lp)
handle row objectives
Definition: spxmainsm.cpp:1370
RowSingletonPS(const SPxLP &lp, int _i, int _j, bool strictLo, bool strictUp, Real newLo, Real newUp, Real oldLo, Real oldUp)
Definition: spxmainsm.h:290
DuplicateRowsPS(const SPxLP &lp, int _i, int maxLhsIdx, int minRhsIdx, const DSVector &dupRows, const DataArray< Real > scale, const DataArray< int > perm, const DataArray< bool > isLhsEqualRhs, bool isTheLast, bool isFixedRow, bool isFirst=false)
Definition: spxmainsm.h:894
virtual ~SPxMainSM()
destructor.
Definition: spxmainsm.h:1417
Result duplicateRows(SPxLP &lp, bool &again)
removes duplicate rows.
Definition: spxmainsm.cpp:3623
Real m_cutoffbound
the cutoff bound that is found by heuristics
Definition: spxmainsm.h:1220
DSVector m_col
does the index mapping have to be updated in postsolving?
Definition: spxmainsm.h:452
Result multiaggregation(SPxLP &lp, bool &again)
performs multi-aggregations of variable based upon constraint activitu.
Definition: spxmainsm.cpp:3379
Save arrays of arbitrary types.
friend class DuplicateColsPS
Definition: spxmainsm.h:1166
FreeZeroObjVariablePS(const FreeZeroObjVariablePS &old)
copy constructor
Definition: spxmainsm.h:606
const SVectorBase< R > & rowVector(int i) const
Gets row vector of row i.
Definition: spxlpbase.h:204
comparator for class SVector::Element: compare nonzeros according to index
Definition: spxmainsm.h:1534
virtual const Vector & unsimplifiedPrimal()
returns a reference to the unsimplified primal solution.
Definition: spxmainsm.h:1463
FreeColSingletonPS & operator=(const FreeColSingletonPS &rhs)
assignment operator
Definition: spxmainsm.h:754
virtual const Vector & unsimplifiedRedCost()
returns a reference to the unsimplified reduced costs.
Definition: spxmainsm.h:1481
void trivialHeuristic(SPxLP &lp)
tries to find good lower bound solutions by applying some trivial heuristics
Definition: spxmainsm.cpp:1674
int m_j
slack column index
Definition: spxmainsm.h:132
virtual PostStep * clone() const
clone function for polymorphism
Definition: spxmainsm.h:430
Postsolves duplicate columns.
Definition: spxmainsm.h:970
DataArray< bool > m_isLhsEqualRhs
Definition: spxmainsm.h:891
virtual SPxSimplifier * clone() const
clone function for polymorphism
Definition: spxmainsm.h:1430
SimpleStep
Different simplification steps.
Definition: spxmainsm.h:1173
Result removeEmpty(SPxLP &lp)
removed empty rows and empty columns.
Definition: spxmainsm.cpp:1875
int size() const
return nr. of elements.
Definition: dataarray.h:211
Postsolves forcing constraints.
Definition: spxmainsm.h:352
virtual PostStep * clone() const
clone function for polymorphism
Definition: spxmainsm.h:957
FixBoundsPS(const SPxLP &lp, int j, Real val)
Definition: spxmainsm.h:513
Result simplifyDual(SPxLP &lp, bool &again)
performs simplification steps on the LP based on dual concepts.
Definition: spxmainsm.cpp:3121
Postsolves unconstraint constraints.
Definition: spxmainsm.h:171
R val
Value of nonzero element.
Definition: svectorbase.h:39
Postsolves variable bound tightening from pseudo objective propagation.
Definition: spxmainsm.h:1115
const SVectorBase< R > & colVector(int i) const
Returns column vector of column i.
Definition: spxlpbase.h:373
Postsolves variable fixing.
Definition: spxmainsm.h:442
int nCols() const
Returns number of columns in LP.
Definition: spxlpbase.h:157
friend class FreeColSingletonPS
Definition: spxmainsm.h:1163
Real m_pseudoobj
the pseudo objective function value
Definition: spxmainsm.h:1221
friend class FreeZeroObjVariablePS
Definition: spxmainsm.h:1161
void computeMinMaxValues(SPxLP &lp, Real side, Real val, Real minRes, Real maxRes, Real &minVal, Real &maxVal)
calculate min/max value for the multi aggregated variables
Definition: spxmainsm.cpp:1641
virtual PostStep * clone() const
clone function for polymorphism
Definition: spxmainsm.h:1023
int m_addedcols
columns added by handleRowObjectives()
Definition: spxmainsm.h:1218
virtual const Vector & unsimplifiedSlacks()
returns a reference to the unsimplified slack values.
Definition: spxmainsm.h:1475
friend class ZeroObjColSingletonPS
Definition: spxmainsm.h:1162
int operator()(const SVector::Element &e1, const SVector::Element &e2) const
Definition: spxmainsm.h:1539
void removeRow(SPxLP &lp, int i)
removes a row in the LP.
Definition: spxmainsm.h:1278
friend class EmptyConstraintPS
Definition: spxmainsm.h:1156
FreeConstraintPS & operator=(const FreeConstraintPS &rhs)
assignment operator
Definition: spxmainsm.h:197
int nCols
number of cols
Definition: spxmainsm.h:79
RowObjPS(const RowObjPS &old)
copy constructor
Definition: spxmainsm.h:142
RowObjPS(const SPxLP &lp, int _i, int _j)
Definition: spxmainsm.h:136
Result simplifyCols(SPxLP &lp, bool &again)
performs simplification steps on the columns of the LP.
Definition: spxmainsm.cpp:2592
Array< DSVector > m_dupRows
arrange duplicate rows using bucket sort w.r.t. their pClass values
Definition: spxmainsm.h:1209
EmptyConstraintPS & operator=(const EmptyConstraintPS &rhs)
assignment operator
Definition: spxmainsm.h:245
void reSize(int newsize)
reset size to newsize.
Definition: dataarray.h:223
ZeroObjColSingletonPS(const ZeroObjColSingletonPS &old)
copy constructor
Definition: spxmainsm.h:673
DVector m_slack
unsimplified slack vector.
Definition: spxmainsm.h:1199
const VectorBase< R > & lower() const
Returns (internal and possibly scaled) lower bound vector.
Definition: spxlpbase.h:483
void spx_free(T &p)
Release memory.
Definition: spxalloc.h:109
virtual SPxSolver::VarStatus getBasisColStatus(int j) const
gets basis status for a single column.
Definition: spxmainsm.h:1493
DoubletonEquationPS & operator=(const DoubletonEquationPS &rhs)
assignment operator
Definition: spxmainsm.h:850
DataArray< SPxSolver::VarStatus > m_cBasisStat
basis status of columns.
Definition: spxmainsm.h:1202
void propagatePseudoobj(SPxLP &lp)
tightens variable bounds by propagating the pseudo objective function value.
Definition: spxmainsm.cpp:1813
LP simplifier for removing uneccessary row/columns.This SPxSimplifier is mainly based on the paper "P...
Definition: spxmainsm.h:60
Array< DSVector > m_classSetRows
stores parallel classes with non-zero colum entry
Definition: spxmainsm.h:1207
friend class FixVariablePS
Definition: spxmainsm.h:1159
Real epsZero() const
Definition: spxmainsm.h:1300
int operator()(const SVector::Element &e1, const SVector::Element &e2) const
Definition: spxmainsm.h:1523
DVector m_redCost
unsimplified reduced cost vector.
Definition: spxmainsm.h:1201
ForceConstraintPS(const ForceConstraintPS &old)
copy constructor
Definition: spxmainsm.h:396
virtual PostStep * clone() const
clone function for polymorphism
Definition: spxmainsm.h:765