coin-Cgl
CglLandP.hpp
Go to the documentation of this file.
1 // Copyright (C) 2005, 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: 07/21/05
6 //---------------------------------------------------------------------------
7 #ifndef CglLandP_H
8 #define CglLandP_H
9 
10 //Several level of Debug
11 // 1 - A few simple sanity check
12 // 2 - do extra computations on cut quality
13 // 3 - Output cut in initial non-basic space (only if logLevel >= 3 )
14 // 4 - Double check (compute in two different ways) reduced cost and f+ f-
15 //#define LandP_DEBUG 1
16 
17 
18 #include "CglLandPValidator.hpp"
19 #include "CglCutGenerator.hpp"
20 #include "CglParam.hpp"
21 
22 #ifdef DO_STAT
23 #include "CglLandPStats.hpp"
24 #endif
25 #include <iostream>
26 class CoinWarmStartBasis;
31 namespace LAP
32 {
41 };
43 class LapMessages : public CoinMessages
44 {
45 public:
47  LapMessages( );
49  virtual ~LapMessages(){}
50 };
51 class CglLandPSimplex;
52 }
53 
54 class CglLandP : public CglCutGenerator
55 {
56  friend void CglLandPUnitTest(OsiSolverInterface *si, const std::string & mpsDir);
57 
58  friend class LAP::CglLandPSimplex;
59  friend class CftCglp;
60 
61 public:
62 
67  };
68 
74  };
75 
81  };
82 
89  };
90 
91  enum LHSnorm {
92  L1 = 0,
93  L2,
98  };
101  Fixed = 0 ,
103  };
106 class Parameters : public CglParam
107  {
108  public:
110  Parameters();
112  Parameters(const Parameters &other);
114  Parameters & operator=(const Parameters &other);
117 
136 
137  double pivotTol;
139  double away;
141  mutable double timeLimit;
145  double rhsWeight;
147 
150 
161  bool perturb;
173  };
174 
175 
180  ~CglLandP();
182  CglLandP(const CglLandP &source);
184  CglLandP& operator=(const CglLandP &rhs);
186  CglCutGenerator * clone() const;
187 
188 #ifdef DO_STAT
189  void setIdString(const std::string &id) {
190  roundsStats_.setIdString(id);
191  }
192 #endif
193 
196 
197  virtual void generateCuts(const OsiSolverInterface & si, OsiCuts & cs,
198  const CglTreeInfo info = CglTreeInfo()) const;
199 
201 
202  virtual bool needsOptimalBasis() const {
203  return true;
204  }
205 
207  return validator_;
208  }
216  void setLogLevel(int level) {
217  handler_->setLogLevel(level);
218  }
219 
220 class NoBasisError : public CoinError
221  {
222  public:
223  NoBasisError(): CoinError("No basis available","LandP","") {}
224  };
225 
226 class SimplexInterfaceError : public CoinError
227  {
228  public:
229  SimplexInterfaceError(): CoinError("Invalid conversion to simplex interface", "CglLandP","CglLandP") {}
230  };
232  return params_;
233  }
234 private:
235 
236 
237  void scanExtraCuts(OsiCuts& cs, const double * colsol) const;
238 
240 
242  struct CachedData {
243  CachedData(int nBasics = 0 , int nNonBasics = 0);
244  CachedData(const CachedData & source);
245 
246  CachedData& operator=(const CachedData &source);
248  void getData(const OsiSolverInterface &si);
249  ~CachedData();
251  int * basics_;
255  int nBasics_;
259  CoinWarmStartBasis * basis_;
261  double * colsol_;
263  double * slacks_;
265  bool * integers_;
266  };
269  int getSortedFractionals(CoinPackedVector &xFrac,
270  const CachedData & data,
271  const CglLandP::Parameters& params) const;
274  void getSortedFractionalIndices(std::vector<int>& indices,
275  const CachedData &data,
276  const CglLandP::Parameters & params) const;
280  CoinMessageHandler * handler_;
282  CoinMessages messages_;
286  mutable int numrows_;
288  mutable int numcols_;
290  mutable double * originalColLower_;
292  mutable double * originalColUpper_;
294  mutable bool canLift_;
296  mutable OsiCuts extraCuts_;
297 #ifdef DO_STAT
298 public:
300  mutable roundsStatistics roundsStats_;
301 #endif
302 };
303 void CglLandPUnitTest(OsiSolverInterface *si, const std::string & mpsDir);
304 
305 #endif
306 
Select only those rows which had initialy a 0 reduced cost.
Definition: CglLandP.hpp:66
bool countMistakenRc
Wether to limit or not the number of mistaken RC (when perturbation is applied).
Definition: CglLandP.hpp:157
void getSortedFractionalIndices(std::vector< int > &indices, const CachedData &data, const CglLandP::Parameters &params) const
Retrieve sorted integer variables which are fractional in the solution.
CglCutGenerator * clone() const
Clone function.
int * nonBasics_
Indices of non-basic variables.
Definition: CglLandP.hpp:253
ExtraCutsMode generateExtraCuts
Generate extra constraints from optimal lift-and-project basis.
Definition: CglLandP.hpp:169
Normalization
Normalization.
Definition: CglLandP.hpp:84
select most negative reduced cost
Definition: CglLandP.hpp:64
OsiCuts extraCuts_
Store some extra cut which could be cheaply generated but do not cut current incumbent.
Definition: CglLandP.hpp:296
2 * current number of constraints.
Definition: CglLandP.hpp:102
int failedPivotLimit
Maximum number of failed pivots before aborting.
Definition: CglLandP.hpp:127
double * originalColLower_
Original lower bounds for the problem (for lifting cuts).
Definition: CglLandP.hpp:290
int degeneratePivotLimit
maximum number of consecutive degenerate pivots 0
Definition: CglLandP.hpp:130
RhsWeightType
RHS weight in normalization.
Definition: CglLandP.hpp:100
int getSortedFractionals(CoinPackedVector &xFrac, const CachedData &data, const CglLandP::Parameters &params) const
Retrieve sorted integer variables which are fractional in the solution.
Parameters params_
Definition: CglLandP.hpp:239
SeparationSpaces sepSpace
Work in the reduced space (only non-structurals enter the basis)
Definition: CglLandP.hpp:159
int nBasics_
number of basics variables
Definition: CglLandP.hpp:255
bool * integers_
Stores wheter slacks are integer constrained.
Definition: CglLandP.hpp:265
Generate no extra cuts.
Definition: CglLandP.hpp:70
Parameters & operator=(const Parameters &other)
Assignment opertator.
Parameters & parameter()
Definition: CglLandP.hpp:231
double * originalColUpper_
Original upper bounds for the problem (for lifting cuts).
Definition: CglLandP.hpp:292
CachedData & operator=(const CachedData &source)
CachedData(int nBasics=0, int nNonBasics=0)
CachedData cached_
Cached informations about problem.
Definition: CglLandP.hpp:278
void setLogLevel(int level)
set level of log for cut generation procedure :
Definition: CglLandP.hpp:216
Normalization normalization
How to weight normalization.
Definition: CglLandP.hpp:163
double * slacks_
Stores the values of the slacks.
Definition: CglLandP.hpp:263
int numrows_
number of rows in the original problems.
Definition: CglLandP.hpp:286
int * basics_
Indices of basic variables in starting basis (ordered if variable basics_[i] s basic in row i) ...
Definition: CglLandP.hpp:251
double rhsWeight
Weight to put in RHS of normalization if static.
Definition: CglLandP.hpp:145
LapMessagesTypes
Definition: CglLandP.hpp:33
Generate cuts from the optimal basis.
Definition: CglLandP.hpp:71
void CglLandPUnitTest(OsiSolverInterface *si, const std::string &mpsDir)
int nNonBasics_
number of non-basics
Definition: CglLandP.hpp:257
LHSnorm lhs_norm
How to weight LHS of normalization.
Definition: CglLandP.hpp:167
LapMessages()
Constructor.
friend void CglLandPUnitTest(OsiSolverInterface *si, const std::string &mpsDir)
double timeLimit
Total time limit for cut generation.
Definition: CglLandP.hpp:141
int pivotLimitInTree
Max number of pivots at regular nodes.
Definition: CglLandP.hpp:123
Class collecting parameters for all cut generators.
Definition: CglParam.hpp:17
int extraCutsLimit
Maximum number of extra rows to generate per round.
Definition: CglLandP.hpp:132
int pivotLimit
Max number of pivots before we generate the cut 20.
Definition: CglLandP.hpp:120
bool canLift_
Flag to say if cuts can be lifted.
Definition: CglLandP.hpp:294
Some informations that will be changed by the pivots and that we want to keep.
Definition: CglLandP.hpp:242
LAP::Validator validator_
cut validator
Definition: CglLandP.hpp:284
CoinMessages messages_
messages
Definition: CglLandP.hpp:282
virtual bool needsOptimalBasis() const
Return true if needs optimal basis to do cuts.
Definition: CglLandP.hpp:202
friend class CftCglp
Definition: CglLandP.hpp:59
bool strengthen
Do we strengthen the final cut (always do if modularize is 1)
Definition: CglLandP.hpp:155
LAP::Validator & validator()
Definition: CglLandP.hpp:206
virtual ~LapMessages()
destructor.
Definition: CglLandP.hpp:49
Class to validate or reject a cut.
CglLandP(const CglLandP::Parameters &params=CglLandP::Parameters(), const LAP::Validator &validator=LAP::Validator())
Constructor for the class.
int maxCutPerRound
Maximum number of cuts generated at a given round.
Definition: CglLandP.hpp:125
void scanExtraCuts(OsiCuts &cs, const double *colsol) const
Cut Generator Base Class.
Use fractional space only for computing reduced costs.
Definition: CglLandP.hpp:79
Work in full space.
Definition: CglLandP.hpp:80
double * colsol_
Stores the value of the solution to cut.
Definition: CglLandP.hpp:261
select best possible pivot.
Definition: CglLandP.hpp:65
double singleCutTimeLimit
Time limit for generating a single cut.
Definition: CglLandP.hpp:143
Generate all violated Mixed integer Gomory cuts in the course of the optimization.
Definition: CglLandP.hpp:73
virtual void generateCuts(const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo()) const
Generate cuts for the model data contained in si.
CoinWarmStartBasis * basis_
Optimal basis.
Definition: CglLandP.hpp:259
SelectionRules pivotSelection
Which rule to apply for choosing entering and leaving variables.
Definition: CglLandP.hpp:171
double away
A variable have to be at least away from integrity to be generated.
Definition: CglLandP.hpp:139
RhsWeightType rhsWeightType
How to weight RHS of normalization.
Definition: CglLandP.hpp:165
Generate cuts as soon as a structural enters the basis.
Definition: CglLandP.hpp:72
~CglLandP()
Destructor.
int numcols_
number of columns in the original problems.
Definition: CglLandP.hpp:288
CoinMessageHandler * handler_
message handler
Definition: CglLandP.hpp:280
SeparationSpaces
Space where cuts are optimized.
Definition: CglLandP.hpp:77
void getData(const OsiSolverInterface &si)
Get the data from a problem.
Class storing parameters.
Definition: CglLandP.hpp:106
Information about where the cut generator is invoked from.
Definition: CglTreeInfo.hpp:13
Output messages for Cgl.
Definition: CglLandP.hpp:43
bool modularize
Do we apply Egon Balas's Heuristic for modularized cuts.
Definition: CglLandP.hpp:153
CglLandP & operator=(const CglLandP &rhs)
Assignment operator.
SelectionRules
Definition: CglLandP.hpp:63
bool useTableauRow
Do we use tableau row or the disjunction (I don't really get that there should be a way to always use...
Definition: CglLandP.hpp:151
double pivotTol
Tolerance for small pivots values (should be the same as the solver.
Definition: CglLandP.hpp:137
Parameters()
Default constructor (with default values)
bool perturb
Apply perturbation procedure.
Definition: CglLandP.hpp:161