Cgl  0.59.9
CglLandPSimplex.hpp
Go to the documentation of this file.
1 // Copyright (C) 2005-2009 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 // $Id: CglLandPSimplex.hpp 1122 2013-04-06 20:39:53Z stefan $
8 //
9 // This code is licensed under the terms of the Eclipse Public License (EPL).
10 //---------------------------------------------------------------------------
11 #ifndef CglLandPSimplex_H
12 #define CglLandPSimplex_H
13 
14 #include <iostream>
15 #include <vector>
16 
17 #include "CglConfig.h"
18 #include "CglLandP.hpp"
19 
20 #include "OsiSolverInterface.hpp"
21 #include "CoinMessage.hpp"
22 #include "CoinMessageHandler.hpp"
23 #include "CoinWarmStartBasis.hpp"
24 #include "CoinPackedMatrix.hpp"
25 
26 #ifdef COIN_HAS_OSICLP
27 #include "OsiClpSolverInterface.hpp"
28 #endif
29 
30 #include "CglLandPTabRow.hpp"
31 #include "CglLandPUtils.hpp"
32 #include "CglLandPMessages.hpp"
33 
34 //#define APPEND_ROW
35 #define OLD_COMPUTATION
36 
37 namespace LAP
38 {
40 class DebugData;
41 
43 {
44 public:
46  CglLandPSimplex(const OsiSolverInterface &si,
47  const CglLandP::CachedData &cached,
48  const CglLandP::Parameters &params,
49  Validator &validator);
53  void cacheUpdate(const CglLandP::CachedData &cached, bool reducedSpace = 0);
55  bool resetSolver(const CoinWarmStartBasis * basis);
57  bool optimize(int var, OsiRowCut & cut, const CglLandP::CachedData &cached, const CglLandP::Parameters & params);
59  bool generateMig(int row, OsiRowCut &cut, const CglLandP::Parameters & params);
60 
62  int generateExtraCuts(const CglLandP::CachedData &cached, const CglLandP::Parameters & params);
64  int generateExtraCut(int i, const CglLandP::CachedData & cached,
65  const CglLandP::Parameters& params);
66 
67  void genThisBasisMigs(const CglLandP::CachedData &cached,
68  const CglLandP::Parameters & params) ;
69 
71  int insertAllExtr(OsiCuts & cs, CoinRelFltEq eq);
72 
73  void setLogLevel(int level)
74  {
75  handler_->setLogLevel(level);
76  }
77 
78 
79  void setSi(OsiSolverInterface *si)
80  {
81  si_ = si;
82 #ifdef COIN_HAS_OSICLP
83  OsiClpSolverInterface * clpSi = dynamic_cast<OsiClpSolverInterface *>(si_);
84  if (clpSi)
85  {
86  clp_ = clpSi;
87  }
88 #endif
89  }
90  void freeSi()
91  {
92  assert(si_ != NULL);
93  delete si_;
94  si_ = NULL;
95 #ifdef COIN_HAS_OSICLP
96  clp_ = NULL;
97 #endif
98  }
99 
101  {
102  return cuts_;
103  }
104  void loadBasis(const OsiSolverInterface &si,
105  std::vector<int> &M1, std::vector<int> &M2,
106  int k);
107 
108 
109  int getNumCols() const
110  {
111  return ncols_;
112  }
113 
114  int getNumRows() const
115  {
116  return nrows_;
117  }
118 
119  const CoinWarmStartBasis * getBasis() const
120  {
121  return basis_;
122  }
123  const int * getNonBasics() const
124  {
125  return nonBasics_;
126  }
127 
128  const int * getBasics() const
129  {
130  return basics_;
131  }
132 
133  void outPivInfo(int ncuts)
134  {
135  handler_->message(RoundStats, messages_)<<ncuts<<numPivots_
136  <<numSourceRowEntered_
137  <<numIncreased_<<CoinMessageEol;
138  }
139 #ifdef APPEND_ROW
140 
141  void append_row(int row_num, bool modularize) ;
143  void update_row(TabRow &row);
144 
145  void check_mod_row(TabRow &row);
146 #endif
147 protected:
149  bool changeBasis(int incoming, int leaving, int direction,
150 #ifndef OLD_COMPUTATION
151  bool recompute_source_row,
152 #endif
153  bool modularize);
157  int fastFindCutImprovingPivotRow( int &direction, int &gammaSign, double tolerance, bool flagPositiveRows);
159  int rescanReducedCosts( int &direction, int &gammaSign, double tolerance);
161  int fastFindBestPivotColumn(int direction, int gammaSign,
162  double pivotTol, double rhsTol,
163  bool reducedSpace,
164  bool allowNonImproving,
165  double &bestSigma, bool modularize);
166 
174  int findBestPivot(int &leaving, int & direction,
175  const CglLandP::Parameters & params);
176 
177 
180  double computeCglpObjective(const TabRow & row, bool modularize = false) const;
184  inline double strengthenedIntersectionCutCoef(int i, double alpha_i, double beta) const;
187  inline double newRowCoefficient(int j, double gamma) const;
189  void createIntersectionCut(TabRow & row, OsiRowCut &cut) const;
191  double normalizationFactor(const TabRow & row) const;
193  void scaleCut(OsiRowCut & cut, double factor) const;
195  // void createIntersectionCut(double * row);
197  void createMIG( TabRow & row, OsiRowCut &cut) const;
199  void pullTableauRow(TabRow & row) const;
201  void adjustTableauRow(int var, TabRow & row, int direction);
203  void resetOriginalTableauRow(int var, TabRow & row, int direction);
205  inline double getLoBound(int index) const
206  {
207  return lo_bounds_[original_index_[index]];
208  }
210  inline double getUpBound(int index) const
211  {
212  return up_bounds_[original_index_[index]];
213  }
215  inline double getColsolToCut(int index) const
216  {
217  return colsolToCut_[original_index_[index]];
218  }
219  bool isGtConst(int index) const
220  {
221  return (index >= ncols_ && lo_bounds_[original_index_[index]] < -1e-10 && up_bounds_[original_index_[index]] <= 1e-09);
222  }
224  inline void setColsolToCut(int index, double value)
225  {
226  colsolToCut_[original_index_[index]] = value;
227  }
229  inline CoinWarmStartBasis::Status getStatus(int index) const
230  {
231  if (index < ncols_) return basis_->getStructStatus(index);
232  return basis_->getArtifStatus(index - ncols_);
233  }
235  inline bool isInteger(int index) const
236  {
237  return integers_[original_index_[index]];
238  }
243  double normedCoef(double a, int ii) const
244  {
245  if (norm_weights_.empty())
246  {
247  return a;
248  }
249  else
250  {
251  return a*norm_weights_[ii];
252  }
253  }
255  void printTableau(std::ostream & os);
256 
258  void printEverything();
260  void printTableauLateX(std::ostream & os);
261  void printRowLateX(std::ostream & os, int i);
262  void printCutLateX(std::ostream & os, int i);
263 
265  void printCglpBasis(std::ostream& os = std::cout);
267  void get_M1_M2_M3(const TabRow & row,
268  std::vector<int> &M1,
269  std::vector<int> &M2,
270  std::vector<int> &M3);
272  void eliminate_slacks(double * vec) const;
273 private:
275  CglLandPSimplex();
279  CglLandPSimplex& operator=(const CglLandPSimplex&);
280 #ifdef COIN_HAS_OSICLP
281 
282  OsiClpSolverInterface * clp_;
283 #endif
284 
286  void updateM1_M2_M3(TabRow & row, double tolerance, bool alwaysComputeCheap);
288  void removeRows(int nDelete, const int * rowsIdx);
289 
290 
291  void compute_p_q_r_s(double gamma, int gammaSign, double &p, double & q, double & r , double &s);
292 
293 
296 
297  TabRow row_k_;
299  TabRow original_row_k_;
301  TabRow row_i_;
302 #ifndef NDBEUG
303  TabRow new_row_;
304 #endif
305 
306  CoinPackedVector gammas_;
308  std::vector<double> rWk1_;
310  std::vector<double> rWk2_;
312  std::vector<double> rWk3_;
314  std::vector<double> rWk4_;
316  std::vector<int> rIntWork_;
318  bool * rowFlags_;
320  std::vector<bool> col_in_subspace;
322  bool *colCandidateToLeave_;
324  int * basics_;
326  int * nonBasics_;
328  std::vector<int> M1_;
330  std::vector<int> M2_;
332  std::vector<int> M3_;
334  double sigma_;
336  CoinWarmStartBasis * basis_;
338  double * colsolToCut_;
340  double * colsol_;
342  int ncols_orig_;
344  int nrows_orig_;
346  int ncols_;
348  int nrows_;
349  // for fast access to lower bounds (both cols and rows)
350  std::vector<double> lo_bounds_;
351  // for fast access to upper bounds (both cols and rows)
352  std::vector<double> up_bounds_;
354  bool inDegenerateSequence_;
356  double chosenReducedCostVal_;
358  const bool * integers_;
360  std::vector<int> original_index_;
362  Cuts cuts_;
366 
367  OsiSolverInterface * si_;
370  bool own_;
372  Validator & validator_;
374  std::vector<double> norm_weights_;
376  double rhs_weight_;
377 
379  int nNegativeRcRows_;
381  bool checkBasis();
382 
384  int numPivots_;
386  int numSourceRowEntered_;
388  int numIncreased_;
389 
391  CoinMessageHandler * handler_;
393  CoinMessages messages_;
394 #ifndef NDEBUG
395  double bestSigma_;
396 #endif
397 
398 protected:
402  double computeCglpRedCost(int direction, int gammaSign, double tau);
406  double computeCglpObjective(double gamma, bool strengthen, TabRow &row);
408  double computeCglpObjective(double gamma, bool strengthen);
411  int findCutImprovingPivotRow( int &direction, int &gammaSign, double tolerance);
413  int findBestPivotColumn(int direction,
414  double pivotTol, bool reducedSpace, bool allowDegeneratePivot,
415  bool modularize);
416 #if 1
417  int plotCGLPobj(int direction, double gammaTolerance,
418  double pivotTol, bool reducedSpace, bool allowDegenerate, bool modularize);
419 #endif
420 
422 };
423 
424 
426 double CglLandPSimplex::strengthenedIntersectionCutCoef(int i, double alpha_i, double beta) const
427 {
428  // double ratio = beta/(1-beta);
429  if ( (!integers_[i]))
430  return intersectionCutCoef(alpha_i, beta);
431  else
432  {
433  double f_i = alpha_i - floor(alpha_i);
434  if (f_i < beta)
435  return f_i*(1- beta);
436  else
437  return (1 - f_i)*beta;//(1-beta);
438  }
439 }
440 
443 double
444 CglLandPSimplex::newRowCoefficient(int j, double gamma) const
445 {
446  return row_k_[j] + gamma * row_i_[j];
447 }
448 
449 }
450 #endif
int insertAllExtr(OsiCuts &cs, CoinRelFltEq eq)
insert all extra cuts in cs.
Normalization
Normalization.
Definition: CglLandP.hpp:82
bool optimize(int var, OsiRowCut &cut, const CglLandP::CachedData &cached, const CglLandP::Parameters &params)
Perfom pivots to find the best cuts.
bool resetSolver(const CoinWarmStartBasis *basis)
reset the solver to optimal basis
void printTableau(std::ostream &os)
print the tableau of current basis.
Class storing parameters.
Definition: CglLandP.hpp:107
void setColsolToCut(int index, double value)
Access to value in solution to cut (indexed in reduced problem)
double normalizationFactor(const TabRow &row) const
Compute the normalization factor of the cut.
void computeWeights(CglLandP::LHSnorm norm, CglLandP::Normalization type, CglLandP::RhsWeightType rhs)
Compute normalization weights.
CoinWarmStartBasis::Status getStatus(int index) const
Get the basic status of a variable (structural or slack).
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 rescanReducedCosts(int &direction, int &gammaSign, double tolerance)
Rescan reduced costs tables.
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 genThisBasisMigs(const CglLandP::CachedData &cached, const CglLandP::Parameters &params)
void outPivInfo(int ncuts)
RhsWeightType
RHS weight in normalization.
Definition: CglLandP.hpp:100
double computeRedCostConstantsInRow()
Compute the value of sigma and thau (which are constants for a row i as defined in Mike Perregaard th...
bool changeBasis(int incoming, int leaving, int direction, bool modularize)
Perform a change in the basis (direction is 1 if leaving variable is going to ub, 0 otherwise) ...
double normedCoef(double a, int ii) const
Evenutaly multiply a by w if normed_weights_ is not empty.
void createIntersectionCut(TabRow &row, OsiRowCut &cut) const
Create the intersection cut of row k.
double getUpBound(int index) const
Get upper bound for variable or constraint.
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 ...
void printEverything()
Print everything .
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...
#define OLD_COMPUTATION
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.
void eliminate_slacks(double *vec) const
Put a vector in structural sapce.
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 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).
int fastFindBestPivotColumn(int direction, int gammaSign, double pivotTol, double rhsTol, bool reducedSpace, bool allowNonImproving, double &bestSigma, bool modularize)
Find the column which leads to the best cut (i.e., find incoming variable).
~CglLandPSimplex()
Destructor.
double intersectionCutCoef(double alpha_i, double beta)
return the coefficients of the intersection cut
Performs one round of Lift & Project using CglLandPSimplex to build cuts.
Definition: CglLandP.hpp:24
double getLoBound(int index) const
Get lower bound for variable or constraint.
void printTableauLateX(std::ostream &os)
print the tableau of current basis.
const int * getBasics() const
int generateExtraCuts(const CglLandP::CachedData &cached, const CglLandP::Parameters &params)
Find extra constraints in current tableau.
bool isGtConst(int index) const
void setSi(OsiSolverInterface *si)
const CoinWarmStartBasis * getBasis() const
void loadBasis(const OsiSolverInterface &si, std::vector< int > &M1, std::vector< int > &M2, int k)
void setLogLevel(int level)
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...
To store extra cuts generated by columns from which they origin.
void scaleCut(OsiRowCut &cut, double factor) const
Scale the cut by factor.
void printCglpBasis(std::ostream &os=std::cout)
Print CGLP basis corresponding to current tableau and source row.
double computeCglpRedCost(int direction, int gammaSign, double tau)
Compute the reduced cost of Cglp.
const int * getNonBasics() const
double getColsolToCut(int index) const
Access to value in solution to cut (indexed in reduced problem)
int plotCGLPobj(int direction, double gammaTolerance, double pivotTol, bool reducedSpace, bool allowDegenerate, bool modularize)
void adjustTableauRow(int var, TabRow &row, int direction)
Adjust the row of the tableau to reflect leaving variable direction.
void resetOriginalTableauRow(int var, TabRow &row, int direction)
reset the tableau row after a call to adjustTableauRow
void printRowLateX(std::ostream &os, int i)
bool generateMig(int row, OsiRowCut &cut, const CglLandP::Parameters &params)
Find Gomory cut (i.e.
bool isInteger(int index) const
Say if variable index by i in current tableau is integer.
double computeCglpObjective(const TabRow &row, bool modularize=false) const
Compute the objective value of the Cglp for given row and rhs (if strengthening shall be applied row ...
Class to validate or reject a cut.
void createMIG(TabRow &row, OsiRowCut &cut) const
Create strenghtened row.
void printCutLateX(std::ostream &os, int i)
double newRowCoefficient(int j, double gamma) const
return the coefficient of the new row (combining row_k + gamma row_i).