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
double getUpBound(int index) const
Get upper bound for variable or constraint.
CoinMessageHandler * handler_
Message handler.
std::vector< double > rWk2_
scond work vector in row space.
std::vector< bool > col_in_subspace
Flag columns which are in the subspace (usualy remove nonbasic structurals in subspace) ...
Cuts cuts_
Stores extra cuts which are generated along the procedure.
CoinWarmStartBasis * basis_
Keep track of basis status.
int generateExtraCuts(const CglLandP::CachedData &cached, const CglLandP::Parameters &params)
Find extra constraints in current tableau.
int ncols_
cached number of columns in reduced size problem
int plotCGLPobj(int direction, double gammaTolerance, double pivotTol, bool reducedSpace, bool allowDegenerate, bool modularize)
Compute the reduced cost of Cglp.
bool * colCandidateToLeave_
Flag columns which have to be considered for leaving the basis.
std::vector< double > rWk1_
first work vector in row space.
Normalization
Normalization.
Definition: CglLandP.hpp:84
CoinWarmStartBasis::Status getStatus(int index) const
Get the basic status of a variable (structural or slack).
double computeCglpRedCost(int direction, int gammaSign, double tau)
Compute the reduced cost of Cglp.
const int * getBasics() const
void cacheUpdate(const CglLandP::CachedData &cached, bool reducedSpace=0)
Update cached information in case of basis change in a round.
void pullTableauRow(TabRow &row) const
Get the row i of the tableau.
int fastFindBestPivotColumn(int direction, int gammaSign, double pivotTol, double rhsTol, bool reducedSpace, bool allowNonImproving, double &bestSigma)
Find the column which leads to the best cut (i.e., find incoming variable).
void genThisBasisMigs(const CglLandP::CachedData &cached, const CglLandP::Parameters &params)
void setSi(OsiSolverInterface *si)
double getColsolToCut(int index) const
Access to value in solution to cut (indexed in reduced problem)
CoinMessages messages_
Messages.
RhsWeightType
RHS weight in normalization.
Definition: CglLandP.hpp:100
bool isGtConst(int index) const
double computeCglpObjective(const TabRow &row) const
Compute the objective value of the Cglp for given row and rhs (if strengthening shall be applied row ...
~CglLandPSimplex()
Destructor.
std::vector< int > rIntWork_
integer valued work vector on the rows
std::vector< int > M3_
Stores the variables which could be either in M1 or M2.
double computeRedCostConstantsInRow()
Compute the value of sigma and thau (which are constants for a row i as defined in Mike Perregaard th...
std::vector< double > norm_weights_
Weights for the normalization constraint.
void get_M1_M2_M3(const TabRow &row, std::vector< int > &M1, std::vector< int > &M2, std::vector< int > &M3)
Put variables in M1 M2 and M3 according to their sign.
bool checkBasis()
Check that the basis is correct.
int generateExtraCut(int i, const CglLandP::CachedData &cached, const CglLandP::Parameters &params)
Generate a constrainte for a row of the tableau different from the source row.
void removeRows(int nDelete, const int *rowsIdx)
Remove rows from current tableau.
TabRow new_row_
Source row for cut.
std::vector< int > original_index_
Original index of variable before deletions.
void printCutLateX(std::ostream &os, int i)
bool changeBasis(int incoming, int leaving, int direction, bool recompute_source_row)
Perform a change in the basis (direction is 1 if leaving variable is going to ub, 0 otherwise) ...
void compute_p_q_r_s(double gamma, int gammaSign, double &p, double &q, double &r, double &s)
double normalizationFactor(const TabRow &row) const
Compute the normalization factor of the cut.
void loadBasis(const OsiSolverInterface &si, std::vector< int > &M1, std::vector< int > &M2, int k)
void setColsolToCut(int index, double value)
Access to value in solution to cut (indexed in reduced problem)
CglLandPSimplex & operator=(const CglLandPSimplex &)
No assignment operator.
std::vector< double > up_bounds_
Source row for cut.
OsiClpSolverInterface * clp_
Pointer to OsiClpSolverInterface if used.
int fastFindCutImprovingPivotRow(int &direction, int &gammaSign, double tolerance, bool flagPositiveRows)
Find a row which can be used to perform an improving pivot the fast way (i.e., find the leaving varia...
double getLoBound(int index) const
Get lower bound for variable or constraint.
bool optimize(int var, OsiRowCut &cut, const CglLandP::CachedData &cached, const CglLandP::Parameters &params)
Perfom pivots to find the best cuts.
bool own_
Own the data or not?
bool resetSolver(const CoinWarmStartBasis *basis)
reset the solver to optimal basis
double strengthenedIntersectionCutCoef(int i, double alpha_i, double beta) const
return the coefficients of the strengthened intersection cut takes one extra argument seens needs to ...
const CoinWarmStartBasis * getBasis() const
void computeWeights(CglLandP::LHSnorm norm, CglLandP::Normalization type, CglLandP::RhsWeightType rhs)
Compute normalization weights.
double * colsol_
Pointer to the current basic solution.
const int * getNonBasics() const
Some informations that will be changed by the pivots and that we want to keep.
Definition: CglLandP.hpp:242
OsiSolverInterface * si_
Pointer to the solver interface.
CoinPackedVector gammas_
vector to sort the gammas
int rescanReducedCosts(int &direction, int &gammaSign, double tolerance)
Rescan reduced costs tables.
std::vector< int > M2_
Stores the variables which are always in M2 for a given k.
int nrows_
Cached number of rows in reduced size problem.
void printTableau(std::ostream &os)
print the tableau of current basis.
const Validator & validator_
A pointer to a cut validator.
bool inDegenerateSequence_
Say if we are in a sequence of degenerate pivots.
void printTableauLateX(std::ostream &os)
print the tableau of current basis.
int * nonBasics_
Stores the nonBasicVariables.
Class to validate or reject a cut.
void scaleCut(OsiRowCut &cut, double factor) const
Scale the cut by factor.
double rhs_weight_
Weight for rhs of normalization constraint.*/.
TabRow row_i_
Row of leaving candidate.
std::vector< double > rWk3_
third work vector in row space.
std::vector< double > lo_bounds_
Source row for cut.
int findBestPivotColumn(int direction, double pivotTol, bool reducedSpace, bool allowDegeneratePivot, bool modularize)
Find the column which leads to the best cut (i.e., find incoming variable).
void createIntersectionCut(TabRow &row, OsiRowCut &cut) const
Create the intersection cut of row k.
CglLandPSimplex()
No default constructor.
double sigma_
stores the cglp value of the normalized cut obtained from row k_
lpSolver solver_
Type of lp solver (for non-standardize tableau manipulation functions.
bool * rowFlags_
Flag rows which we don't want to try anymore.
std::vector< double > rWk4_
fourth work vector in row space.
int nNegativeRcRows_
number of rows with a <0 rc in current iteration
void updateM1_M2_M3(TabRow &row, double tolerance, bool recucedSpace, bool alwaysComputeCheap)
Update values in M1 M2 and M3 before an iteration.
double normedCoef(double a, int ii) const
Evenutaly multiply a by w if normed_weights_ is not empty.
void adjustTableauRow(int var, TabRow &row, int direction)
Adjust the row of the tableau to reflect leaving variable direction.
void printRowLateX(std::ostream &os, int i)
double * colsolToCut_
Pointer to the solution to cut (need to be modified after each pivot because we are only considering ...
int findBestPivot(int &leaving, int &direction, const CglLandP::Parameters &params)
Find incoming and leaving variables which lead to the most violated adjacent normalized lift-and-proj...
int ncols_orig_
cached numcols in original problem
TabRow row_k_
Source row for cut.
int nrows_orig_
cached numrows in original problem
int insertAllExtr(OsiCuts &cs, CoinRelFltEq eq)
insert all extra cuts in cs.
double intersectionCutCoef(double alpha_i, double beta)
return the coefficients of the intersection cut
bool isInteger(int index)
Say if variable index by i in current tableau is integer.
void setLogLevel(int level)
Class storing parameters.
Definition: CglLandP.hpp:106
void resetOriginalTableauRow(int var, TabRow &row, int direction)
reset the tableau row after a call to adjustTableauRow
double chosenReducedCostVal_
Value for the reduced cost chosen for pivoting.
To store extra cuts generated by columns from which they origin.
int findCutImprovingPivotRow(int &direction, int &gammaSign, double tolerance)
Find a row which can be used to perform an improving pivot return index of the cut or -1 if none exis...
const bool * integers_
pointer to array of integer info for both structural and slacks
void printCglpBasis(std::ostream &os=std::cout)
Print CGLP basis corresponding to current tableau and source row.
void createMIG(TabRow &row, OsiRowCut &cut) const
Create strenghtened row.
double newRowCoefficient(int j, double gamma) const
return the coefficient of the new row (combining row_k + gamma row_i).
bool generateMig(int row, OsiRowCut &cut, const CglLandP::CachedData &cached, const CglLandP::Parameters &params) const
Find Gomory cut (i.e.
std::vector< int > M1_
Stores the variables which are always in M1 for a given k.
int * basics_
Store the basics variable.