SoPlex Doxygen Documentation
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-2012 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 unboundness 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) const = 0;
116 
117  virtual bool checkBasisDim(DataArray<SPxSolver::VarStatus> rows, DataArray<SPxSolver::VarStatus> cols) const;
118 
119  static Real eps()
120  {
121  return 1e-6;
122  }
123  };
124 
125  /**@brief Postsolves unconstraint constraints.
126  @ingroup Algo
127  */
128  class FreeConstraintPS : public PostStep
129  {
130  private:
131  const int m_i;
132  const int m_old_i;
133  DSVector m_row;
134 
135  public:
136  ///
137  FreeConstraintPS(const SPxLP& lp, int _i)
138  : PostStep("FreeConstraint", lp.nRows(), lp.nCols())
139  , m_i(_i)
140  , m_old_i(lp.nRows()-1)
141  , m_row(lp.rowVector(_i))
142  {}
143  /// copy constructor
144  FreeConstraintPS(const FreeConstraintPS& old)
145  : PostStep(old)
146  , m_i(old.m_i)
147  , m_old_i(old.m_old_i)
148  , m_row(old.m_row)
149  {}
150  /// assignment operator
151  FreeConstraintPS& operator=( const FreeConstraintPS& rhs)
152  {
153  if(this != &rhs)
154  {
155  PostStep::operator=(rhs);
156  m_row = rhs.m_row;
157  }
158 
159  return *this;
160  }
161  ///
162  virtual void execute(DVector& x, DVector& y, DVector& s, DVector& r,
163  DataArray<SPxSolver::VarStatus>& cBasis, DataArray<SPxSolver::VarStatus>& rBasis) const;
164  /// clone function for polymorphism
165  inline virtual PostStep* clone() const
166  {
167  return new FreeConstraintPS(*this);
168  }
169  };
170 
171  /**@brief Postsolves empty constraints.
172  @ingroup Algo
173  */
174  class EmptyConstraintPS : public PostStep
175  {
176  private:
177  const int m_i;
178  const int m_old_i;
179 
180  public:
181  ///
182  EmptyConstraintPS(const SPxLP& lp, int _i)
183  : PostStep("EmptyConstraint", lp.nRows(), lp.nCols())
184  , m_i(_i)
185  , m_old_i(lp.nRows()-1)
186  {}
187  /// copy constructor
188  EmptyConstraintPS(const EmptyConstraintPS& old)
189  : PostStep(old)
190  , m_i(old.m_i)
191  , m_old_i(old.m_old_i)
192  {}
193  /// assignment operator
194  EmptyConstraintPS& operator=( const EmptyConstraintPS& rhs)
195  {
196  if(this != &rhs)
197  {
198  PostStep::operator=(rhs);
199  }
200 
201  return *this;
202  }
203  ///
204  virtual void execute(DVector& x, DVector& y, DVector& s, DVector& r,
205  DataArray<SPxSolver::VarStatus>& cBasis, DataArray<SPxSolver::VarStatus>& rBasis) const;
206  /// clone function for polymorphism
207  inline virtual PostStep* clone() const
208  {
209  return new EmptyConstraintPS(*this);
210  }
211  };
212 
213  /**@brief Postsolves row singletons.
214  @ingroup Algo
215  */
216  class RowSingletonPS : public PostStep
217  {
218  private:
219  const int m_i;
220  const int m_old_i;
221  const int m_j;
222  const Real m_lhs;
223  const Real m_rhs;
224  const bool m_strictLo;
225  const bool m_strictUp;
226  const bool m_maxSense;
227  const Real m_obj;
228  DSVector m_col;
229  const Real m_newLo;
230  const Real m_newUp;
231  const Real m_oldLo;
232  const Real m_oldUp;
233 
234  public:
235  ///
236  RowSingletonPS(const SPxLP& lp, int _i, int _j, bool strictLo, bool strictUp,
237  Real newLo, Real newUp, Real oldLo, Real oldUp)
238  : PostStep("RowSingleton", lp.nRows(), lp.nCols())
239  , m_i(_i)
240  , m_old_i(lp.nRows()-1)
241  , m_j(_j)
242  , m_lhs(lp.lhs(_i))
243  , m_rhs(lp.rhs(_i))
244  , m_strictLo(strictLo)
245  , m_strictUp(strictUp)
246  , m_maxSense(lp.spxSense() == SPxLP::MAXIMIZE)
247  , m_obj(lp.spxSense() == SPxLP::MINIMIZE ? lp.obj(_j) : -lp.obj(_j))
248  , m_col(lp.colVector(_j))
249  , m_newLo(newLo)
250  , m_newUp(newUp)
251  , m_oldLo(oldLo)
252  , m_oldUp(oldUp)
253  {}
254  /// copy constructor
255  RowSingletonPS(const RowSingletonPS& old)
256  : PostStep(old)
257  , m_i(old.m_i)
258  , m_old_i(old.m_old_i)
259  , m_j(old.m_j)
260  , m_lhs(old.m_lhs)
261  , m_rhs(old.m_rhs)
262  , m_strictLo(old.m_strictLo)
263  , m_strictUp(old.m_strictUp)
264  , m_maxSense(old.m_maxSense)
265  , m_obj(old.m_obj)
266  , m_col(old.m_col)
267  , m_newLo(old.m_newLo)
268  , m_newUp(old.m_newUp)
269  , m_oldLo(old.m_oldLo)
270  , m_oldUp(old.m_oldUp)
271  {}
272  /// assignment operator
273  RowSingletonPS& operator=( const RowSingletonPS& rhs)
274  {
275  if(this != &rhs)
276  {
277  PostStep::operator=(rhs);
278  m_col = rhs.m_col;
279  }
280 
281  return *this;
282  }
283  /// clone function for polymorphism
284  inline virtual PostStep* clone() const
285  {
286  return new RowSingletonPS(*this);
287  }
288  ///
289  virtual void execute(DVector& x, DVector& y, DVector& s, DVector& r,
290  DataArray<SPxSolver::VarStatus>& cBasis, DataArray<SPxSolver::VarStatus>& rBasis) const;
291  };
292 
293  /**@brief Postsolves forcing constraints.
294  @ingroup Algo
295  */
296  class ForceConstraintPS : public PostStep
297  {
298  private:
299  const int m_i;
300  const int m_old_i;
301  const Real m_lRhs;
302  DSVector m_row;
303  DataArray<Real> m_objs;
304  DataArray<bool> m_fixed;
305  Array<DSVector> m_cols;
306  const bool m_lhsFixed;
307  const bool m_maxSense;
308  DataArray<Real> m_oldLowers;
309  DataArray<Real> m_oldUppers;
310  const Real m_lhs;
311  const Real m_rhs;
312 
313  public:
314  ///
315  ForceConstraintPS(const SPxLP& lp, int _i, bool lhsFixed, DataArray<bool>& fixCols, DataArray<Real>& lo, DataArray<Real>& up)
316  : PostStep("ForceConstraint", lp.nRows(), lp.nCols())
317  , m_i(_i)
318  , m_old_i(lp.nRows()-1)
319  , m_lRhs(lhsFixed ? lp.lhs(_i) : lp.rhs(_i))
320  , m_row(lp.rowVector(_i))
321  , m_objs(lp.rowVector(_i).size())
322  , m_fixed(fixCols)
323  , m_cols(lp.rowVector(_i).size())
324  , m_lhsFixed(lhsFixed)
325  , m_maxSense(lp.spxSense() == SPxLP::MAXIMIZE)
326  , m_oldLowers(lo)
327  , m_oldUppers(up)
328  , m_lhs(lp.lhs(_i))
329  , m_rhs(lp.rhs(_i))
330  {
331  for(int k = 0; k < m_row.size(); ++k)
332  {
333  m_objs[k] = (lp.spxSense() == SPxLP::MINIMIZE ? lp.obj(m_row.index(k)) : -lp.obj(m_row.index(k)));
334  m_cols[k] = lp.colVector(m_row.index(k));
335  }
336  }
337  /// copy constructor
338  ForceConstraintPS(const ForceConstraintPS& old)
339  : PostStep(old)
340  , m_i(old.m_i)
341  , m_old_i(old.m_old_i)
342  , m_lRhs(old.m_lRhs)
343  , m_row(old.m_row)
344  , m_objs(old.m_objs)
345  , m_fixed(old.m_fixed)
346  , m_cols(old.m_cols)
347  , m_lhsFixed(old.m_lhsFixed)
348  , m_maxSense(old.m_maxSense)
349  , m_oldLowers(old.m_oldLowers)
350  , m_oldUppers(old.m_oldUppers)
351  , m_lhs(old.m_lhs)
352  , m_rhs(old.m_rhs)
353  {}
354  /// assignment operator
355  ForceConstraintPS& operator=( const ForceConstraintPS& rhs)
356  {
357  if(this != &rhs)
358  {
359  PostStep::operator=(rhs);
360  m_row = rhs.m_row;
361  m_objs = rhs.m_objs;
362  m_fixed = rhs.m_fixed;
363  m_cols = rhs.m_cols;
364  m_oldLowers = rhs.m_oldLowers;
365  m_oldUppers = rhs.m_oldUppers;
366  }
367 
368  return *this;
369  }
370  /// clone function for polymorphism
371  inline virtual PostStep* clone() const
372  {
373  return new ForceConstraintPS(*this);
374  }
375  ///
376  virtual void execute(DVector& x, DVector& y, DVector& s, DVector& r,
377  DataArray<SPxSolver::VarStatus>& cBasis, DataArray<SPxSolver::VarStatus>& rBasis) const;
378  };
379 
380  /**@brief Postsolves variable fixing.
381  @ingroup Algo
382  */
383  class FixVariablePS : public PostStep
384  {
385  private:
386  const int m_j;
387  const int m_old_j;
388  const Real m_val;
389  const Real m_obj;
390  const Real m_lower;
391  const Real m_upper;
392  const bool m_correctIdx; /// does the index mapping have to be updated in postsolving?
393  DSVector m_col;
394 
395  public:
396  ///
397  FixVariablePS(const SPxLP& lp, SPxMainSM& simplifier, int _j, const Real val, bool correctIdx = true)
398  : PostStep("FixVariable", lp.nRows(), lp.nCols())
399  , m_j(_j)
400  , m_old_j(lp.nCols()-1)
401  , m_val(val)
402  , m_obj(lp.spxSense() == SPxLP::MINIMIZE ? lp.obj(_j) : -lp.obj(_j))
403  , m_lower(lp.lower(_j))
404  , m_upper(lp.upper(_j))
405  , m_correctIdx(correctIdx)
406  , m_col(lp.colVector(_j))
407  {
408  simplifier.addObjoffset(m_val*lp.obj(m_j));
409  }
410  /// copy constructor
411  FixVariablePS(const FixVariablePS& old)
412  : PostStep(old)
413  , m_j(old.m_j)
414  , m_old_j(old.m_old_j)
415  , m_val(old.m_val)
416  , m_obj(old.m_obj)
417  , m_lower(old.m_lower)
418  , m_upper(old.m_upper)
419  , m_correctIdx(old.m_correctIdx)
420  , m_col(old.m_col)
421  {}
422  /// assignment operator
423  FixVariablePS& operator=( const FixVariablePS& rhs)
424  {
425  if(this != &rhs)
426  {
427  PostStep::operator=(rhs);
428  m_col = rhs.m_col;
429  }
430 
431  return *this;
432  }
433  /// clone function for polymorphism
434  inline virtual PostStep* clone() const
435  {
436  return new FixVariablePS(*this);
437  }
438  ///
439  virtual void execute(DVector& x, DVector& y, DVector& s, DVector& r,
440  DataArray<SPxSolver::VarStatus>& cBasis, DataArray<SPxSolver::VarStatus>& rBasis) const;
441  };
442 
443  /**@brief Postsolves variable bound fixing.
444  @ingroup Algo
445  */
446  class FixBoundsPS : public PostStep
447  {
448  private:
449  const int m_j;
450  SPxSolver::VarStatus m_status;
451 
452  public:
453  ///
454  FixBoundsPS(const SPxLP& lp, int j, Real val)
455  : PostStep("FixBounds", lp.nRows(), lp.nCols())
456  , m_j(j)
457  {
458  if (EQrel(lp.lower(j), lp.upper(j), eps()))
459  m_status = SPxSolver::FIXED;
460  else if (EQrel(val, lp.lower(j), eps()))
461  m_status = SPxSolver::ON_LOWER;
462  else if (EQrel(val, lp.upper(j), eps()))
463  m_status = SPxSolver::ON_UPPER;
464  else if (lp.lower(j) <= -infinity && lp.upper(j) >= infinity)
465  m_status = SPxSolver::ZERO;
466  else
467  {
468  throw SPxInternalCodeException("XMAISM14 This should never happen.");
469  }
470  }
471  /// copy constructor
472  FixBoundsPS(const FixBoundsPS& old)
473  : PostStep(old)
474  , m_j(old.m_j)
475  , m_status(old.m_status)
476  {}
477  /// assignment operator
478  FixBoundsPS& operator=( const FixBoundsPS& rhs)
479  {
480  if(this != &rhs)
481  {
482  PostStep::operator=(rhs);
483  m_status = rhs.m_status;
484  }
485 
486  return *this;
487  }
488  /// clone function for polymorphism
489  inline virtual PostStep* clone() const
490  {
491  return new FixBoundsPS(*this);
492  }
493  ///
494  virtual void execute(DVector& x, DVector& y, DVector& s, DVector& r,
495  DataArray<SPxSolver::VarStatus>& cBasis, DataArray<SPxSolver::VarStatus>& rBasis) const;
496  };
497 
498  /**@brief Postsolves the case when constraints are removed due to a
499  variable with zero objective that is free in one direction.
500  @ingroup Algo
501  */
502  class FreeZeroObjVariablePS : public PostStep
503  {
504  private:
505  const int m_j;
506  const int m_old_j;
507  const int m_old_i;
508  const Real m_bnd;
509  DSVector m_col;
510  DSVector m_lRhs;
511  Array<DSVector> m_rows;
512  const bool m_loFree;
513 
514  public:
515  ///
516  FreeZeroObjVariablePS(const SPxLP& lp, int _j, bool loFree, SVector col_idx_sorted)
517  : PostStep("FreeZeroObjVariable", lp.nRows(), lp.nCols())
518  , m_j(_j)
519  , m_old_j(lp.nCols()-1)
520  , m_old_i(lp.nRows()-1)
521  , m_bnd(loFree ? lp.upper(_j) : lp.lower(_j))
522  , m_col(col_idx_sorted)
523  , m_lRhs(lp.colVector(_j).size())
524  , m_rows(lp.colVector(_j).size())
525  , m_loFree(loFree)
526  {
527  for(int k = 0; k < m_col.size(); ++k)
528  {
529  assert(isNotZero(m_col.value(k)));
530 
531  if ((m_loFree && m_col.value(k) > 0) ||
532  (!m_loFree && m_col.value(k) < 0))
533  m_lRhs.add(k, lp.rhs(m_col.index(k)));
534  else
535  m_lRhs.add(k, lp.lhs(m_col.index(k)));
536 
537  m_rows[k] = lp.rowVector(m_col.index(k));
538  }
539  }
540  /// copy constructor
541  FreeZeroObjVariablePS(const FreeZeroObjVariablePS& old)
542  : PostStep(old)
543  , m_j(old.m_j)
544  , m_old_j(old.m_old_j)
545  , m_old_i(old.m_old_i)
546  , m_bnd(old.m_bnd)
547  , m_col(old.m_col)
548  , m_lRhs(old.m_lRhs)
549  , m_rows(old.m_rows)
550  , m_loFree(old.m_loFree)
551  {}
552  /// assignment operator
553  FreeZeroObjVariablePS& operator=( const FreeZeroObjVariablePS& rhs)
554  {
555  if(this != &rhs)
556  {
557  PostStep::operator=(rhs);
558  m_col = rhs.m_col;
559  m_lRhs = rhs.m_lRhs;
560  m_rows = rhs.m_rows;
561  }
562 
563  return *this;
564  }
565  /// clone function for polymorphism
566  inline virtual PostStep* clone() const
567  {
568  return new FreeZeroObjVariablePS(*this);
569  }
570  ///
571  virtual void execute(DVector& x, DVector& y, DVector& s, DVector& r,
572  DataArray<SPxSolver::VarStatus>& cBasis, DataArray<SPxSolver::VarStatus>& rBasis) const;
573  };
574 
575  /**@brief Postsolves column singletons with zero objective.
576  @ingroup Algo
577  */
578  class ZeroObjColSingletonPS : public PostStep
579  {
580  private:
581  const int m_j;
582  const int m_i;
583  const int m_old_j;
584  const Real m_lhs;
585  const Real m_rhs;
586  const Real m_lower;
587  const Real m_upper;
588  DSVector m_row;
589 
590  public:
591  ///
592  ZeroObjColSingletonPS(const SPxLP& lp, const SPxMainSM& , int _j, int _i)
593  : PostStep("ZeroObjColSingleton", lp.nRows(), lp.nCols())
594  , m_j(_j)
595  , m_i(_i)
596  , m_old_j(lp.nCols()-1)
597  , m_lhs(lp.lhs(_i))
598  , m_rhs(lp.rhs(_i))
599  , m_lower(lp.lower(_j))
600  , m_upper(lp.upper(_j))
601  , m_row(lp.rowVector(_i))
602  {}
603  /// copy constructor
604  ZeroObjColSingletonPS(const ZeroObjColSingletonPS& old)
605  : PostStep(old)
606  , m_j(old.m_j)
607  , m_i(old.m_i)
608  , m_old_j(old.m_old_j)
609  , m_lhs(old.m_lhs)
610  , m_rhs(old.m_rhs)
611  , m_lower(old.m_lower)
612  , m_upper(old.m_upper)
613  , m_row(old.m_row)
614  {}
615  /// assignment operator
616  ZeroObjColSingletonPS& operator=( const ZeroObjColSingletonPS& rhs)
617  {
618  if(this != &rhs)
619  {
620  PostStep::operator=(rhs);
621  m_row = rhs.m_row;
622  }
623 
624  return *this;
625  }
626  /// clone function for polymorphism
627  inline virtual PostStep* clone() const
628  {
629  return new ZeroObjColSingletonPS(*this);
630  }
631  ///
632  virtual void execute(DVector& x, DVector& y, DVector& s, DVector& r,
633  DataArray<SPxSolver::VarStatus>& cBasis, DataArray<SPxSolver::VarStatus>& rBasis) const;
634  };
635 
636  /**@brief Postsolves free column singletons.
637  @ingroup Algo
638  */
639  class FreeColSingletonPS : public PostStep
640  {
641  private:
642  const int m_j;
643  const int m_i;
644  const int m_old_j;
645  const int m_old_i;
646  const Real m_obj;
647  const Real m_lRhs;
648  const bool m_onLhs;
649  const bool m_eqCons;
650  DSVector m_row;
651 
652  public:
653  ///
654  FreeColSingletonPS(const SPxLP& lp, SPxMainSM& simplifier, int _j, int _i, Real slackVal)
655  : PostStep("FreeColSingleton", lp.nRows(), lp.nCols())
656  , m_j(_j)
657  , m_i(_i)
658  , m_old_j(lp.nCols()-1)
659  , m_old_i(lp.nRows()-1)
660  , m_obj(lp.spxSense() == SPxLP::MINIMIZE ? lp.obj(_j) : -lp.obj(_j))
661  , m_lRhs(slackVal)
662  , m_onLhs(slackVal == lp.lhs(_i))
663  , m_eqCons(EQrel(lp.lhs(_i), lp.rhs(_i)))
664  , m_row(lp.rowVector(_i))
665  {
666  assert(m_row[m_j] != 0.0);
667  simplifier.addObjoffset(m_lRhs*(lp.obj(m_j)/m_row[m_j]));
668  }
669  /// copy constructor
670  FreeColSingletonPS(const FreeColSingletonPS& old)
671  : PostStep(old)
672  , m_j(old.m_j)
673  , m_i(old.m_i)
674  , m_old_j(old.m_old_j)
675  , m_old_i(old.m_old_i)
676  , m_obj(old.m_obj)
677  , m_lRhs(old.m_lRhs)
678  , m_onLhs(old.m_onLhs)
679  , m_eqCons(old.m_eqCons)
680  , m_row(old.m_row)
681  {}
682  /// assignment operator
683  FreeColSingletonPS& operator=( const FreeColSingletonPS& rhs)
684  {
685  if(this != &rhs)
686  {
687  PostStep::operator=(rhs);
688  m_row = rhs.m_row;
689  }
690 
691  return *this;
692  }
693  /// clone function for polymorphism
694  inline virtual PostStep* clone() const
695  {
696  return new FreeColSingletonPS(*this);
697  }
698  ///
699  virtual void execute(DVector& x, DVector& y, DVector& s, DVector& r,
700  DataArray<SPxSolver::VarStatus>& cBasis, DataArray<SPxSolver::VarStatus>& rBasis) const;
701  };
702 
703  /**@brief Postsolves doubleton equations combined with a column singleton.
704  @ingroup Algo
705  */
706  class DoubletonEquationPS : public PostStep
707  {
708  private:
709  const int m_j;
710  const int m_k;
711  const int m_i;
712  const bool m_maxSense;
713  const bool m_jFixed;
714  const Real m_jObj;
715  const Real m_kObj;
716  const Real m_aij;
717  const bool m_strictLo;
718  const bool m_strictUp;
719  const Real m_newLo;
720  const Real m_newUp;
721  const Real m_oldLo;
722  const Real m_oldUp;
723  const Real m_Lo_j;
724  const Real m_Up_j;
725  const Real m_lhs;
726  const Real m_rhs;
727  DSVector m_col;
728 
729  public:
730  ///
731  DoubletonEquationPS(const SPxLP& lp, int _j, int _k, int _i, Real oldLo, Real oldUp)
732  : PostStep("DoubletonEquation", lp.nRows(), lp.nCols())
733  , m_j(_j)
734  , m_k(_k)
735  , m_i(_i)
736  , m_maxSense(lp.spxSense() == SPxLP::MAXIMIZE)
737  , m_jFixed(EQrel(lp.lower(_j), lp.upper(_j)))
738  , m_jObj(lp.spxSense() == SPxLP::MINIMIZE ? lp.obj(_j) : -lp.obj(_j))
739  , m_kObj(lp.spxSense() == SPxLP::MINIMIZE ? lp.obj(_k) : -lp.obj(_k))
740  , m_aij(lp.colVector(_j).value(0))
741  , m_strictLo(lp.lower(_k) > oldLo)
742  , m_strictUp(lp.upper(_k) < oldUp)
743  , m_newLo(lp.lower(_k))
744  , m_newUp(lp.upper(_k))
745  , m_oldLo(oldLo)
746  , m_oldUp(oldUp)
747  , m_Lo_j(lp.lower(_j))
748  , m_Up_j(lp.upper(_j))
749  , m_lhs(lp.lhs(_i))
750  , m_rhs(lp.rhs(_i))
751  , m_col(lp.colVector(_k))
752  {}
753  /// copy constructor
754  DoubletonEquationPS(const DoubletonEquationPS& old)
755  : PostStep(old)
756  , m_j(old.m_j)
757  , m_k(old.m_k)
758  , m_i(old.m_i)
759  , m_maxSense(old.m_maxSense)
760  , m_jFixed(old.m_jFixed)
761  , m_jObj(old.m_jObj)
762  , m_kObj(old.m_kObj)
763  , m_aij(old.m_aij)
764  , m_strictLo(old.m_strictLo)
765  , m_strictUp(old.m_strictUp)
766  , m_newLo(old.m_newLo)
767  , m_newUp(old.m_newUp)
768  , m_oldLo(old.m_oldLo)
769  , m_oldUp(old.m_oldUp)
770  , m_Lo_j(old.m_Lo_j)
771  , m_Up_j(old.m_Up_j)
772  , m_lhs(old.m_lhs)
773  , m_rhs(old.m_rhs)
774  , m_col(old.m_col)
775  {}
776  /// assignment operator
777  DoubletonEquationPS& operator=( const DoubletonEquationPS& rhs)
778  {
779  if(this != &rhs)
780  {
781  PostStep::operator=(rhs);
782  m_col = rhs.m_col;
783  }
784 
785  return *this;
786  }
787  /// clone function for polymorphism
788  inline virtual PostStep* clone() const
789  {
790  return new DoubletonEquationPS(*this);
791  }
792  ///
793  virtual void execute(DVector& x, DVector& y, DVector& s, DVector& r,
794  DataArray<SPxSolver::VarStatus>& cBasis, DataArray<SPxSolver::VarStatus>& rBasis) const;
795  };
796 
797  /**@brief Postsolves duplicate rows.
798  @ingroup Algo
799  */
800  class DuplicateRowsPS : public PostStep
801  {
802  private:
803  const int m_i;
804  const int m_maxLhsIdx;
805  const int m_minRhsIdx;
806  const bool m_maxSense;
807  const bool m_isFirst;
808  const bool m_isLast;
809  const bool m_fixed;
810  const int m_nCols;
811  DSVector m_scale;
812  DataArray<int> m_rIdxLocalOld;
813  DataArray<int> m_perm;
814  DataArray<bool> m_isLhsEqualRhs;
815 
816  public:
817  DuplicateRowsPS(const SPxLP& lp, int _i,
818  int maxLhsIdx, int minRhsIdx, const DSVector& dupRows,
819  const DataArray<double> scale, const DataArray<int> perm, const DataArray<bool> isLhsEqualRhs,
820  bool isTheLast, bool isFixedRow, bool isFirst = false)
821  : PostStep("DuplicateRows", lp.nRows(), lp.nCols())
822  , m_i(_i)
823  , m_maxLhsIdx((maxLhsIdx == -1) ? -1 : maxLhsIdx)
824  , m_minRhsIdx((minRhsIdx == -1) ? -1 : minRhsIdx)
825  , m_maxSense(lp.spxSense() == SPxLP::MAXIMIZE)
826  , m_isFirst(isFirst)
827  , m_isLast(isTheLast)
828  , m_fixed(isFixedRow)
829  , m_nCols(lp.nCols())
830  , m_scale(dupRows.size())
831  , m_rIdxLocalOld(dupRows.size())
832  , m_perm(perm)
833  , m_isLhsEqualRhs(isLhsEqualRhs)
834  {
835  Real rowScale = scale[_i];
836 
837  for(int k = 0; k < dupRows.size(); ++k)
838  {
839  m_scale.add(dupRows.index(k), rowScale / scale[dupRows.index(k)]);
840  m_rIdxLocalOld[k] = dupRows.index(k);
841  }
842  }
843  /// copy constructor
844  DuplicateRowsPS(const DuplicateRowsPS& old)
845  : PostStep(old)
846  , m_i(old.m_i)
847  , m_maxLhsIdx(old.m_maxLhsIdx)
848  , m_minRhsIdx(old.m_minRhsIdx)
849  , m_maxSense(old.m_maxSense)
850  , m_isFirst(old.m_isFirst)
851  , m_isLast(old.m_isLast)
852  , m_fixed(old.m_fixed)
853  , m_nCols(old.m_nCols)
854  , m_scale(old.m_scale)
855  , m_rIdxLocalOld(old.m_rIdxLocalOld)
856  , m_perm(old.m_perm)
857  , m_isLhsEqualRhs(old.m_isLhsEqualRhs)
858  {}
859  /// assignment operator
860  DuplicateRowsPS& operator=( const DuplicateRowsPS& rhs)
861  {
862  if(this != &rhs)
863  {
864  PostStep::operator=(rhs);
865  m_scale = rhs.m_scale;
866  m_rIdxLocalOld = rhs.m_rIdxLocalOld;
867  m_perm = rhs.m_perm;
868  m_isLhsEqualRhs = rhs.m_isLhsEqualRhs;
869  }
870 
871  return *this;
872  }
873  /// clone function for polymorphism
874  inline virtual PostStep* clone() const
875  {
876  return new DuplicateRowsPS(*this);
877  }
878  virtual void execute(DVector& x, DVector& y, DVector& s, DVector& r,
879  DataArray<SPxSolver::VarStatus>& cBasis, DataArray<SPxSolver::VarStatus>& rBasis) const;
880  };
881 
882  /**@brief Postsolves duplicate columns.
883  @ingroup Algo
884  */
885  class DuplicateColsPS : public PostStep
886  {
887  private:
888  const int m_j;
889  const int m_k;
890  const Real m_loJ;
891  const Real m_upJ;
892  const Real m_loK;
893  const Real m_upK;
894  const Real m_scale;
895  const bool m_isFirst;
896  const bool m_isLast;
897  DataArray<int> m_perm;
898 
899  public:
900  DuplicateColsPS(const SPxLP& lp, int _j, int _k, Real scale, DataArray<int> perm, bool isFirst = false, bool isTheLast = false)
901  : PostStep("DuplicateCols", lp.nRows(), lp.nCols())
902  , m_j(_j)
903  , m_k(_k)
904  , m_loJ(lp.lower(_j))
905  , m_upJ(lp.upper(_j))
906  , m_loK(lp.lower(_k))
907  , m_upK(lp.upper(_k))
908  , m_scale(scale)
909  , m_isFirst(isFirst)
910  , m_isLast(isTheLast)
911  , m_perm(perm)
912  {}
913  /// copy constructor
914  DuplicateColsPS(const DuplicateColsPS& old)
915  : PostStep(old)
916  , m_j(old.m_j)
917  , m_k(old.m_k)
918  , m_loJ(old.m_loJ)
919  , m_upJ(old.m_upJ)
920  , m_loK(old.m_loK)
921  , m_upK (old.m_upK)
922  , m_scale (old.m_scale)
923  , m_isFirst(old.m_isFirst)
924  , m_isLast(old.m_isLast)
925  , m_perm(old.m_perm)
926  {}
927  /// assignment operator
928  DuplicateColsPS& operator=( const DuplicateColsPS& rhs)
929  {
930  if(this != &rhs)
931  {
932  PostStep::operator=(rhs);
933  }
934 
935  return *this;
936  }
937  /// clone function for polymorphism
938  inline virtual PostStep* clone() const
939  {
940  return new DuplicateColsPS(*this);
941  }
942  virtual void execute(DVector& x, DVector& y, DVector& s, DVector& r,
943  DataArray<SPxSolver::VarStatus>& cBasis, DataArray<SPxSolver::VarStatus>& rBasis) const;
944  };
945 
946  // friends
947  friend class FreeConstraintPS;
948  friend class EmptyConstraintPS;
949  friend class RowSingletonPS;
950  friend class ForceConstraintPS;
951  friend class FixVariablePS;
952  friend class FixBoundsPS;
953  friend class FreeZeroObjVariablePS;
954  friend class ZeroObjColSingletonPS;
955  friend class FreeColSingletonPS;
956  friend class DoubletonEquationPS;
957  friend class DuplicateRowsPS;
958  friend class DuplicateColsPS;
959 
960 private:
961  //------------------------------------
962  //**@name Types */
963  //@{
964  /// Different simplification steps.
965  enum SimpleStep
966  {
967  EMPTY_ROW = 0,
968  FREE_ROW = 1,
969  SINGLETON_ROW = 2,
970  FORCE_ROW = 3,
971  EMPTY_COL = 4,
972  FIX_COL = 5,
973  FREE_ZOBJ_COL = 6,
974  ZOBJ_SINGLETON_COL = 7,
975  DOUBLETON_ROW = 8,
976  FREE_SINGLETON_COL = 9,
977  DOMINATED_COL = 10,
978  WEAKLY_DOMINATED_COL = 11,
979  DUPLICATE_ROW = 12,
980  FIX_DUPLICATE_COL = 13,
981  SUB_DUPLICATE_COL = 14
982  };
983  //@}
984 
985  //------------------------------------
986  //**@name Data */
987  //@{
988  ///
989  DVector m_prim; ///< unsimplified primal solution vector.
990  DVector m_slack; ///< unsimplified slack vector.
991  DVector m_dual; ///< unsimplified dual solution vector.
992  DVector m_redCost; ///< unsimplified reduced cost vector.
993  DataArray<SPxSolver::VarStatus> m_cBasisStat; ///< basis status of columns.
994  DataArray<SPxSolver::VarStatus> m_rBasisStat; ///< basis status of rows.
995  DataArray<int> m_cIdx; ///< column index vector in original LP.
996  DataArray<int> m_rIdx; ///< row index vector in original LP.
997  DataArray<PostStep*> m_hist; ///< vector of presolve history.
998  bool m_postsolved; ///< status of postsolving.
999  Real m_epsilon; ///< epsilon zero.
1000  Real m_feastol; ///< primal feasibility tolerance.
1001  Real m_opttol; ///< dual feasibility tolerance.
1002  DataArray<int> m_stat; ///< preprocessing history.
1003  SPxLP::SPxSense m_thesense; ///< optimization sense.
1004  //@}
1005 
1006 private:
1007  //------------------------------------
1008  //**@name Private helpers */
1009  //@{
1010  /// handles extreme values by setting them to zero or infinity.
1011  void handleExtremes(SPxLP& lp);
1012 
1013  /// removed empty rows and empty columns.
1014  Result removeEmpty(SPxLP& lp);
1015 
1016  /// remove row singletons.
1017  Result removeRowSingleton(SPxLP& lp, const SVector& row, int& i);
1018 
1019  /// performs simplification steps on the rows of the LP.
1020  Result simplifyRows(SPxLP& lp, bool& again);
1021 
1022  /// performs simplification steps on the columns of the LP.
1023  Result simplifyCols(SPxLP& lp, bool& again);
1024 
1025  /// performs simplification steps on the LP based on dual concepts.
1026  Result simplifyDual(SPxLP& lp, bool& again);
1027 
1028  /// removes duplicate rows.
1029  Result duplicateRows(SPxLP& lp, bool& again);
1030 
1031  /// removes duplicate columns
1032  Result duplicateCols(SPxLP& lp, bool& again);
1033 
1034  /// handles the fixing of a variable. correctIdx is true iff the index mapping has to be updated.
1035  void fixColumn(SPxLP& lp, int i, bool correctIdx = true);
1036 
1037  /// removes a row in the LP.
1038  void removeRow(SPxLP& lp, int i)
1039  {
1040  m_rIdx[i] = m_rIdx[lp.nRows()-1];
1041  lp.removeRow(i);
1042  }
1043  /// removes a column in the LP.
1044  void removeCol(SPxLP& lp, int j)
1045  {
1046  m_cIdx[j] = m_cIdx[lp.nCols()-1];
1047  lp.removeCol(j);
1048  }
1049  /// returns for a given row index of the (reduced) LP the corresponding row index in the unsimplified LP.
1050  int rIdx(int i) const
1051  {
1052  return m_rIdx[i];
1053  }
1054  /// returns for a given column index of the (reduced) LP the corresponding column index in the unsimplified LP.
1055  int cIdx(int j) const
1056  {
1057  return m_cIdx[j];
1058  }
1059  ///
1060  Real epsZero() const
1061  {
1062  return m_epsilon;
1063  }
1064  ///
1065  Real feastol() const
1066  {
1067  return m_feastol;
1068  }
1069  ///
1070  Real opttol() const
1071  {
1072  return m_opttol;
1073  }
1074  //@}
1075 
1076 public:
1077 
1078  //------------------------------------
1079  //**@name Constructors / destructors */
1080  //@{
1081  /// default constructor.
1082  SPxMainSM()
1083  : SPxSimplifier("MainSM")
1084  , m_stat(15)
1085  {}
1086  /// copy constructor.
1087  SPxMainSM(const SPxMainSM& old)
1088  : SPxSimplifier(old)
1089  , m_prim(old.m_prim)
1090  , m_slack(old.m_slack)
1091  , m_dual(old.m_dual)
1092  , m_redCost(old.m_redCost)
1093  , m_cBasisStat(old.m_cBasisStat)
1094  , m_rBasisStat(old.m_rBasisStat)
1095  , m_cIdx(old.m_cIdx)
1096  , m_rIdx(old.m_rIdx)
1097  , m_postsolved(old.m_postsolved)
1098  , m_epsilon(old.m_epsilon)
1099  , m_feastol(old.m_feastol)
1100  , m_opttol(old.m_opttol)
1101  , m_stat(old.m_stat)
1102  , m_thesense(old.m_thesense)
1103  {
1104  // copy pointers in m_hist
1105  m_hist.reSize(0);
1106  for(int k = 0; k < old.m_hist.size(); ++k)
1107  {
1108  if(old.m_hist[k] != 0)
1109  m_hist.append(old.m_hist[k]->clone());
1110  else
1111  m_hist.append(0);
1112  }
1113  }
1114  /// assignment operator
1115  SPxMainSM& operator=( const SPxMainSM& rhs)
1116  {
1117  if(this != &rhs)
1118  {
1119  SPxSimplifier::operator=(rhs);
1120  m_prim = rhs.m_prim;
1121  m_slack = rhs.m_slack;
1122  m_dual = rhs.m_dual;
1123  m_redCost = rhs.m_redCost;
1124  m_cBasisStat = rhs.m_cBasisStat;
1125  m_rBasisStat = rhs.m_rBasisStat;
1126  m_cIdx = rhs.m_cIdx;
1127  m_rIdx = rhs.m_rIdx;
1128  m_postsolved = rhs.m_postsolved;
1129  m_epsilon = rhs.m_epsilon;
1130  m_feastol = rhs.m_feastol;
1131  m_opttol = rhs.m_opttol;
1132  m_stat = rhs.m_stat;
1133  m_thesense = rhs.m_thesense;
1134 
1135  // delete pointers in m_hist
1136  for(int k = 0; k < m_hist.size(); ++k)
1137  {
1138  delete m_hist[k];
1139  m_hist[k] = 0;
1140  }
1141 
1142  m_hist.clear();
1143 
1144  // copy pointers in m_hist
1145  for(int k = 0; k < rhs.m_hist.size(); ++k)
1146  {
1147  if(rhs.m_hist[k] != 0)
1148  m_hist.append(rhs.m_hist[k]->clone());
1149  else
1150  m_hist.append(0);
1151  }
1152  }
1153 
1154  return *this;
1155  }
1156  /// destructor.
1157  virtual ~SPxMainSM()
1158  {
1159  // delete pointers in m_hist
1160  for(int k = 0; k < m_hist.size(); ++k)
1161  {
1162  if( m_hist[k] != 0 )
1163  delete m_hist[k];
1164  }
1165  }
1166  /// clone function for polymorphism
1167  inline virtual SPxSimplifier* clone() const
1168  {
1169  return new SPxMainSM(*this);
1170  }
1171  //@}
1172 
1173  //------------------------------------
1174  //**@name LP simplification */
1175  //@{
1176  /// simplify SPxLP \p lp with identical primal and dual feasibility tolerance.
1177  virtual Result simplify(SPxLP& lp, Real eps, Real delta)
1178  {
1179  return simplify(lp, eps, delta, delta);
1180  }
1181  /// simplify SPxLP \p lp with independent primal and dual feasibility tolerance.
1182  virtual Result simplify(SPxLP& lp, Real eps, Real feastol, Real opttol);
1183 
1184  /// reconstructs an optimal solution for the unsimplified LP.
1185  virtual void unsimplify(const Vector& x, const Vector& y, const Vector& s, const Vector& r,
1186  const SPxSolver::VarStatus rows[], const SPxSolver::VarStatus cols[]);
1187 
1188  /// specifies whether an optimal solution has already been unsimplified.
1189  virtual bool isUnsimplified() const
1190  {
1191  return m_postsolved;
1192  }
1193  /// returns a reference to the unsimplified primal solution.
1194  virtual const Vector& unsimplifiedPrimal()
1195  {
1196  assert(m_postsolved);
1197  return m_prim;
1198  }
1199  /// returns a reference to the unsimplified dual solution.
1200  virtual const Vector& unsimplifiedDual()
1201  {
1202  assert(m_postsolved);
1203  return m_dual;
1204  }
1205  /// returns a reference to the unsimplified slack values.
1206  virtual const Vector& unsimplifiedSlacks()
1207  {
1208  assert(m_postsolved);
1209  return m_slack;
1210  }
1211  /// returns a reference to the unsimplified reduced costs.
1212  virtual const Vector& unsimplifiedRedCost()
1213  {
1214  assert(m_postsolved);
1215  return m_redCost;
1216  }
1217  /// gets basis status for a single row.
1218  virtual SPxSolver::VarStatus getBasisRowStatus(int i) const
1219  {
1220  assert(m_postsolved);
1221  return m_rBasisStat[i];
1222  }
1223  /// gets basis status for a single column.
1224  virtual SPxSolver::VarStatus getBasisColStatus(int j) const
1225  {
1226  assert(m_postsolved);
1227  return m_cBasisStat[j];
1228  }
1229  /// get optimal basis.
1230  virtual void getBasis(SPxSolver::VarStatus rows[], SPxSolver::VarStatus cols[]) const
1231  {
1232  assert(m_postsolved);
1233 
1234  for(int i = 0; i < m_rBasisStat.size(); ++i)
1235  rows[i] = m_rBasisStat[i];
1236 
1237  for(int j = 0; j < m_cBasisStat.size(); ++j)
1238  cols[j] = m_cBasisStat[j];
1239  }
1240  //@}
1241 
1242 private:
1243  //------------------------------------
1244  //**@name Types */
1245  //@{
1246  /// comparator for class SVector::Element: compare nonzeros according to value
1247  struct ElementCompare
1248  {
1249  public:
1250  ElementCompare() {}
1251 
1252  int operator()(const SVector::Element& e1, const SVector::Element& e2) const
1253  {
1254  if (EQ(e1.val, e2.val))
1255  return 0;
1256  if (e1.val < e2.val)
1257  return -1;
1258  else // (e1.val > e2.val)
1259  return 1;
1260  }
1261  };
1262  /// comparator for class SVector::Element: compare nonzeros according to index
1263  struct IdxCompare
1264  {
1265  public:
1266  IdxCompare() {}
1267 
1268  int operator()(const SVector::Element& e1, const SVector::Element& e2) const
1269  {
1270  if (EQ(e1.idx, e2.idx))
1271  return 0;
1272  if (e1.idx < e2.idx)
1273  return -1;
1274  else // (e1.idx > e2.idx)
1275  return 1;
1276  }
1277  };
1278  //@}
1279 };
1280 
1281 } // namespace soplex
1282 #endif // _SPXMAINSM_H_
1283 
1284 //-----------------------------------------------------------------------------
1285 //Emacs Local Variables:
1286 //Emacs mode:c++
1287 //Emacs c-basic-offset:3
1288 //Emacs tab-width:8
1289 //Emacs indent-tabs-mode:nil
1290 //Emacs End:
1291 //-----------------------------------------------------------------------------
© 2003-2013 by Zuse Institute Berlin (ZIB), Imprint Generated on Wed Jan 9 2013 for SoPlex by doxygen