coin-Cgl
CglLandPSimplex.hpp
Go to the documentation of this file.
1 // Copyright (C) 2005, 2007 Pierre Bonami and others. All Rights Reserved.
2 // Author: Pierre Bonami
3 // Tepper School of Business
4 // Carnegie Mellon University, Pittsburgh, PA 15213
5 // Date: 21/07/05
6 //---------------------------------------------------------------------------
7 #ifndef CglLandPSimplex_H
8 #define CglLandPSimplex_H
9 
10 #include <iostream>
11 #include <vector>
12 
13 #include "CglLandP.hpp"
14 
15 #include "OsiSolverInterface.hpp"
16 #include "CoinMessage.hpp"
17 #include "CoinMessageHandler.hpp"
18 #include "CoinWarmStartBasis.hpp"
19 #include "CoinPackedMatrix.hpp"
20 
21 #include "OsiClpSolverInterface.hpp"
22 #include "CglLandPTabRow.hpp"
23 #include "CglLandPUtils.hpp"
24 #include "CglLandPMessages.hpp"
25 namespace LAP
26 {
28 class DebugData;
29 
31 {
32 public:
34  CglLandPSimplex(const OsiSolverInterface &si,
35  const CglLandP::CachedData &cached,
36  const CglLandP::Parameters &params,
37  const Validator &validator);
41  void cacheUpdate(const CglLandP::CachedData &cached, bool reducedSpace = 0);
43  bool resetSolver(const CoinWarmStartBasis * basis);
45  bool optimize(int var, OsiRowCut & cut, const CglLandP::CachedData &cached, const CglLandP::Parameters & params);
47  bool generateMig(int row, OsiRowCut &cut, const CglLandP::CachedData &cached, const CglLandP::Parameters & params) const;
48 
50  int generateExtraCuts(const CglLandP::CachedData &cached, const CglLandP::Parameters & params);
52  int generateExtraCut(int i, const CglLandP::CachedData & cached,
53  const CglLandP::Parameters& params);
54 
55  void genThisBasisMigs(const CglLandP::CachedData &cached,
56  const CglLandP::Parameters & params) ;
57 
59  int insertAllExtr(OsiCuts & cs, CoinRelFltEq eq);
60 
61  void setLogLevel(int level) {
62  handler_->setLogLevel(level);
63  }
64 
65 
66  void setSi(OsiSolverInterface *si) {
67  si_ = si;
68  OsiClpSolverInterface * clpSi = dynamic_cast<OsiClpSolverInterface *>(si_);
69  if (clpSi) {
70  solver_ = clp;
71  clp_ = clpSi;
72  }
73  }
74  void freeSi() {
75  delete si_;
76  clp_ = NULL;
77  }
78 
80  return cuts_;
81  }
82  void loadBasis(const OsiSolverInterface &si,
83  std::vector<int> &M1, std::vector<int> &M2,
84  int k);
85 
86 
87  int getNumCols() const {
88  return ncols_;
89  }
90 
91  int getNumRows() const {
92  return nrows_;
93  }
94 
95  const CoinWarmStartBasis * getBasis() const{
96  return basis_;
97  }
98  const int * getNonBasics() const{
99  return nonBasics_;
100  }
101 
102  const int * getBasics() const{
103  return basics_;
104  }
105 
106 protected:
108  bool changeBasis(int incoming, int leaving, int direction, bool recompute_source_row);
112  int fastFindCutImprovingPivotRow( int &direction, int &gammaSign, double tolerance, bool flagPositiveRows);
114  int rescanReducedCosts( int &direction, int &gammaSign, double tolerance);
116  int fastFindBestPivotColumn(int direction, int gammaSign,
117  double pivotTol, double rhsTol,
118  bool reducedSpace,
119  bool allowNonImproving,
120  double &bestSigma);
121 
129  int findBestPivot(int &leaving, int & direction,
130  const CglLandP::Parameters & params);
131 
132 
135  double computeCglpObjective(const TabRow & row) const;
139  inline double strengthenedIntersectionCutCoef(int i, double alpha_i, double beta) const;
142  inline double newRowCoefficient(int j, double gamma) const;
144  void createIntersectionCut(TabRow & row, OsiRowCut &cut) const;
146  double normalizationFactor(const TabRow & row) const;
148  void scaleCut(OsiRowCut & cut, double factor) const;
150  // void createIntersectionCut(double * row);
152  void createMIG( TabRow & row, OsiRowCut &cut) const;
154  void pullTableauRow(TabRow & row) const;
156  void adjustTableauRow(int var, TabRow & row, int direction);
158  void resetOriginalTableauRow(int var, TabRow & row, int direction);
160  inline double getLoBound(int index) const {
161  return lo_bounds_[original_index_[index]];
162  }
164  inline double getUpBound(int index) const {
165  return up_bounds_[original_index_[index]];
166  }
168  inline double getColsolToCut(int index) const {
169  return colsolToCut_[original_index_[index]];
170  }
171  bool isGtConst(int index) const {
172  return (index >= ncols_ && lo_bounds_[original_index_[index]] < -1e-10 && up_bounds_[original_index_[index]] <= 1e-09);
173  }
175  inline void setColsolToCut(int index, double value) {
176  colsolToCut_[original_index_[index]] = value;
177  }
179  inline CoinWarmStartBasis::Status getStatus(int index) const {
180  if (index < ncols_) return basis_->getStructStatus(index);
181  return basis_->getArtifStatus(index - ncols_);
182  }
184  inline bool isInteger(int index) {
185  return integers_[original_index_[index]];
186  }
191  double normedCoef(double a, int ii) const{
192  if (norm_weights_.empty()){
193  return a;
194  }
195  else {
196  return a*norm_weights_[ii];
197  }
198  }
200  void printTableau(std::ostream & os);
201 
203  void printTableauLateX(std::ostream & os);
204  void printRowLateX(std::ostream & os, int i);
205  void printCutLateX(std::ostream & os, int i);
206 
208  void printCglpBasis(std::ostream& os = std::cout);
210  void get_M1_M2_M3(const TabRow & row,
211  std::vector<int> &M1,
212  std::vector<int> &M2,
213  std::vector<int> &M3);
214 private:
216  CglLandPSimplex();
221  enum lpSolver {clp
222 #ifdef COIN_HAS_CPX
223  ,cplex
224 #endif
225 #ifdef COIN_HAX_XPR
226  ,xpress
227 #endif
228  };
232  OsiClpSolverInterface * clp_;
233 
234 
236  void updateM1_M2_M3(TabRow & row, double tolerance, bool recucedSpace, bool alwaysComputeCheap);
238  void removeRows(int nDelete, const int * rowsIdx);
239 
240 
241  void compute_p_q_r_s(double gamma, int gammaSign, double &p, double & q, double & r , double &s);
242 
243 
246 
247  mutable TabRow row_k_;
250 #ifndef NDBEUG
252 #endif
253 
254  CoinPackedVector gammas_;
256  std::vector<double> rWk1_;
258  std::vector<double> rWk2_;
260  std::vector<double> rWk3_;
262  std::vector<double> rWk4_;
264  std::vector<int> rIntWork_;
266  bool * rowFlags_;
268  std::vector<bool> col_in_subspace;
272  int * basics_;
274  int * nonBasics_;
276  std::vector<int> M1_;
278  std::vector<int> M2_;
280  std::vector<int> M3_;
282  double sigma_;
284  CoinWarmStartBasis * basis_;
286  double * colsolToCut_;
288  double * colsol_;
294  int ncols_;
296  int nrows_;
297  // for fast access to lower bounds (both cols and rows)
298  std::vector<double> lo_bounds_;
299  // for fast access to upper bounds (both cols and rows)
300  std::vector<double> up_bounds_;
306  const bool * integers_;
308  std::vector<int> original_index_;
314 
315  OsiSolverInterface * si_;
318  bool own_;
322  std::vector<double> norm_weights_;
324  double rhs_weight_;
325 
329  bool checkBasis();
330 
331 
333  CoinMessageHandler * handler_;
335  CoinMessages messages_;
336 #ifndef NDEBUG
337  double bestSigma_;
338 #endif
339 #ifdef LandP_DEBUG
340  DebugData debug_;
341 #endif
342 
343 protected:
347  double computeCglpRedCost(int direction, int gammaSign, double tau);
351  double computeCglpObjective(double gamma, bool strengthen, TabRow &row);
353  double computeCglpObjective(double gamma, bool strengthen);
356  int findCutImprovingPivotRow( int &direction, int &gammaSign, double tolerance);
358  int findBestPivotColumn(int direction,
359  double pivotTol, bool reducedSpace, bool allowDegeneratePivot,
360  bool modularize);
361 #if 1
362  int plotCGLPobj(int direction, double gammaTolerance,
363  double pivotTol, bool reducedSpace, bool allowDegenerate, bool modularize);
364 #endif
365 
367 };
368 
369 
371 double CglLandPSimplex::strengthenedIntersectionCutCoef(int i, double alpha_i, double beta) const
372 {
373  // double ratio = beta/(1-beta);
374  if ( (!integers_[i]))
375  return intersectionCutCoef(alpha_i, beta);
376  else {
377  double f_i = alpha_i - floor(alpha_i);
378  if (f_i < beta)
379  return f_i*(1- beta);
380  else
381  return (1 - f_i)*beta;//(1-beta);
382  }
383 }
384 
387 double
388 CglLandPSimplex::newRowCoefficient(int j, double gamma) const
389 {
390  return row_k_[j] + gamma * row_i_[j];
391 }
392 
393 
394 
395 
396 #ifdef LandP_DEBUG
397 
398 #if LandP_DEBUG > 1
399 
400 void put_in_non_basic_init_space( OsiRowCut &cut);
401 
403 void outputCurrentCut(const CglLandP::Parameters & params);
404 
405 #endif
406 friend class DebugData;
408 class DebugData
409 {
410 public:
411  DebugData(int n, int m):
412  bestNewRow_(NULL),
413  req(1e-05),
414  eq(1e-5)
415 #if LandP+DEBUG> 1
416  , initialTableau_(), initialBasics_(NULL), initialBasis_(NULL)
417 #endif
418  {
419  bestNewRow_ = new double[n + m];
420 #if LandP_DEBUG > 1
421  initialBasics_ = new int[m];
422  initialNonBasics_ = new int[n];
423  initialColsol_ = new double[n + m];
424  trueInitialSol_ = new double[n + m];
425 #endif
426  }
427  ~DebugData() {
428  delete [] bestNewRow_;
429 #if LandP_DEBUG > 1
430  delete [] initialBasics_;
431  delete [] initialNonBasics_;
432  delete [] initialColsol_;
433  delete [] trueInitialSol_;
434  if (initialBasis_)
435  delete initialBasis_;
436 #endif
437  }
439  double * bestNewRow_;
441  double bestNewRhs_;
443  double newSigma_;
445  CoinRelFltEq req;
447  CoinAbsFltEq eq;
449  double lastSigma_;
451  int outStatus_;
452 
454  bool checkSigma();
456  bool checkNewCut();
458  bool saveOutgoingStatus();
459 
460 #if LandP_DEBUG > 1
461 
462  void getCurrentTableau(OsiSolverInterface &si, CglLandPSimplex &lap);
464  CoinPackedMatrix initialTableau_;
466  int * initialBasics_;
468  int *initialNonBasics_;
470  CoinWarmStartBasis * initialBasis_;
472  double * initialColsol_;
474  double * trueInitialSol_;
475 #endif
476 };
477 #endif
478 
479 }
480 #endif