Cgl  0.60.3
CglLandP.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: 07/21/05
6 //
7 // $Id$
8 //
9 // This code is licensed under the terms of the Eclipse Public License (EPL).
10 //---------------------------------------------------------------------------
11 #ifndef CglLandP_H
12 #define CglLandP_H
13 
14 #include "CglLandPValidator.hpp"
15 #include "CglCutGenerator.hpp"
16 #include "CglParam.hpp"
17 
18 #include <iostream>
19 class CoinWarmStartBasis;
24 namespace LAP
25 {
27 {
36 };
38 class LapMessages : public CoinMessages
39 {
40 public:
44  virtual ~LapMessages() {}
45 };
46 class CglLandPSimplex;
47 }
48 
49 class CglLandP : public CglCutGenerator
50 {
51  friend void CglLandPUnitTest(OsiSolverInterface *si, const std::string & mpsDir);
52 
53  friend class LAP::CglLandPSimplex;
54  friend class CftCglp;
55 
56 public:
57 
59  {
63  };
64 
66  {
71  };
72 
75  {
78  Full
79  };
80 
83  {
88  };
89 
90  enum LHSnorm
91  {
92  L1 = 0,
93  L2,
97  Uniform
98  };
101  {
102  Fixed = 0 ,
103  Dynamic
104  };
107  class Parameters : public CglParam
108  {
109  public:
113  Parameters(const Parameters &other);
115  Parameters & operator=(const Parameters &other);
118 
137 
138  double pivotTol;
140  double away;
142  double timeLimit;
146  double rhsWeight;
148 
151 
162  bool perturb;
174  };
175 
176 
183  CglLandP(const CglLandP &source);
188 
191 
192  virtual void generateCuts(const OsiSolverInterface & si, OsiCuts & cs,
193  const CglTreeInfo info = CglTreeInfo());
194 
196 
197  virtual bool needsOptimalBasis() const
198  {
199  return true;
200  }
201 
203  {
204  return validator_;
205  }
213  void setLogLevel(int level)
214  {
215  handler_->setLogLevel(level);
216  }
217 
218  class NoBasisError : public CoinError
219  {
220  public:
221  NoBasisError(): CoinError("No basis available","LandP","") {}
222  };
223 
224  class SimplexInterfaceError : public CoinError
225  {
226  public:
227  SimplexInterfaceError(): CoinError("Invalid conversion to simplex interface", "CglLandP","CglLandP") {}
228  };
230  {
231  return params_;
232  }
233 private:
234 
235 
236  void scanExtraCuts(OsiCuts& cs, const double * colsol) const;
237 
239 
241  struct CachedData
242  {
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 
250  void clean();
251 
254  int * basics_;
258  int nBasics_;
262  CoinWarmStartBasis * basis_;
264  double * colsol_;
266  double * slacks_;
268  bool * integers_;
270  OsiSolverInterface * solver_;
271  };
274  int getSortedFractionals(CoinPackedVector &xFrac,
275  const CachedData & data,
276  const CglLandP::Parameters& params) const;
279  void getSortedFractionalIndices(std::vector<int>& indices,
280  const CachedData &data,
281  const CglLandP::Parameters & params) const;
285  CoinMessageHandler * handler_;
287  CoinMessages messages_;
291  int numrows_;
293  int numcols_;
299  bool canLift_;
301  OsiCuts extraCuts_;
302 };
303 void CglLandPUnitTest(OsiSolverInterface *si, const std::string & mpsDir);
304 
305 #endif
306 
void CglLandPUnitTest(OsiSolverInterface *si, const std::string &mpsDir)
Cut Generator Base Class.
Class storing parameters.
Definition: CglLandP.hpp:108
double away
A variable have to be at least away from integrity to be generated.
Definition: CglLandP.hpp:140
int pivotLimit
Max number of pivots before we generate the cut \default 20.
Definition: CglLandP.hpp:121
Parameters()
Default constructor (with default values)
bool modularize
Do we apply Egon Balas's Heuristic for modularized cuts.
Definition: CglLandP.hpp:154
int failedPivotLimit
Maximum number of failed pivots before aborting.
Definition: CglLandP.hpp:128
bool strengthen
Do we strengthen the final cut (always do if modularize is 1)
Definition: CglLandP.hpp:156
int maxCutPerRound
Maximum number of cuts generated at a given round.
Definition: CglLandP.hpp:126
int pivotLimitInTree
Max number of pivots at regular nodes.
Definition: CglLandP.hpp:124
LHSnorm lhs_norm
How to weight LHS of normalization.
Definition: CglLandP.hpp:168
SeparationSpaces sepSpace
Work in the reduced space (only non-structurals enter the basis)
Definition: CglLandP.hpp:160
Parameters(const Parameters &other)
Copy constructor.
ExtraCutsMode generateExtraCuts
Generate extra constraints from optimal lift-and-project basis.
Definition: CglLandP.hpp:170
bool perturb
Apply perturbation procedure.
Definition: CglLandP.hpp:162
int extraCutsLimit
Maximum number of extra rows to generate per round.
Definition: CglLandP.hpp:133
double singleCutTimeLimit
Time limit for generating a single cut.
Definition: CglLandP.hpp:144
Parameters & operator=(const Parameters &other)
Assignment opertator.
Normalization normalization
How to weight normalization.
Definition: CglLandP.hpp:164
double rhsWeight
Weight to put in RHS of normalization if static.
Definition: CglLandP.hpp:146
double pivotTol
Tolerance for small pivots values (should be the same as the solver.
Definition: CglLandP.hpp:138
SelectionRules pivotSelection
Which rule to apply for choosing entering and leaving variables.
Definition: CglLandP.hpp:172
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:152
double timeLimit
Total time limit for cut generation.
Definition: CglLandP.hpp:142
bool countMistakenRc
Wether to limit or not the number of mistaken RC (when perturbation is applied).
Definition: CglLandP.hpp:158
RhsWeightType rhsWeightType
How to weight RHS of normalization.
Definition: CglLandP.hpp:166
int degeneratePivotLimit
maximum number of consecutive degenerate pivots \default 0
Definition: CglLandP.hpp:131
OsiCuts extraCuts_
Store some extra cut which could be cheaply generated but do not cut current incumbent.
Definition: CglLandP.hpp:301
Parameters & parameter()
Definition: CglLandP.hpp:229
bool canLift_
Flag to say if cuts can be lifted.
Definition: CglLandP.hpp:299
CachedData cached_
Cached informations about problem.
Definition: CglLandP.hpp:283
LAP::Validator & validator()
Definition: CglLandP.hpp:202
virtual void generateCuts(const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo())
Generate cuts for the model data contained in si.
friend void CglLandPUnitTest(OsiSolverInterface *si, const std::string &mpsDir)
int getSortedFractionals(CoinPackedVector &xFrac, const CachedData &data, const CglLandP::Parameters &params) const
Retrieve sorted integer variables which are fractional in the solution.
SelectionRules
Definition: CglLandP.hpp:59
@ initialReducedCosts
Select only those rows which had initialy a 0 reduced cost.
Definition: CglLandP.hpp:62
@ mostNegativeRc
select most negative reduced cost
Definition: CglLandP.hpp:60
@ bestPivot
select best possible pivot.
Definition: CglLandP.hpp:61
SeparationSpaces
Space where cuts are optimized.
Definition: CglLandP.hpp:75
@ Full
Work in full space.
Definition: CglLandP.hpp:78
@ Fractional_rc
Use fractional space only for computing reduced costs.
Definition: CglLandP.hpp:77
@ Fractional
Definition: CglLandP.hpp:76
void setLogLevel(int level)
set level of log for cut generation procedure :
Definition: CglLandP.hpp:213
void getSortedFractionalIndices(std::vector< int > &indices, const CachedData &data, const CglLandP::Parameters &params) const
Retrieve sorted integer variables which are fractional in the solution.
Parameters params_
Definition: CglLandP.hpp:238
RhsWeightType
RHS weight in normalization.
Definition: CglLandP.hpp:101
@ Dynamic
2 * current number of constraints.
Definition: CglLandP.hpp:103
int numrows_
number of rows in the original problems.
Definition: CglLandP.hpp:291
double * originalColUpper_
Original upper bounds for the problem (for lifting cuts).
Definition: CglLandP.hpp:297
CglLandP & operator=(const CglLandP &rhs)
Assignment operator.
CoinMessageHandler * handler_
message handler
Definition: CglLandP.hpp:285
@ WhenEnteringBasis
Generate cuts as soon as a structural enters the basis.
Definition: CglLandP.hpp:69
@ none
Generate no extra cuts.
Definition: CglLandP.hpp:67
@ AllViolatedMigs
Generate all violated Mixed integer Gomory cuts in the course of the optimization.
Definition: CglLandP.hpp:70
@ AtOptimalBasis
Generate cuts from the optimal basis.
Definition: CglLandP.hpp:68
@ Infinity
Definition: CglLandP.hpp:95
@ SupportSize
Definition: CglLandP.hpp:94
~CglLandP()
Destructor.
LAP::Validator validator_
cut validator
Definition: CglLandP.hpp:289
double * originalColLower_
Original lower bounds for the problem (for lifting cuts).
Definition: CglLandP.hpp:295
CoinMessages messages_
messages
Definition: CglLandP.hpp:287
virtual bool needsOptimalBasis() const
Return true if needs optimal basis to do cuts.
Definition: CglLandP.hpp:197
CglLandP(const CglLandP &source)
Copy constructor.
Normalization
Normalization.
Definition: CglLandP.hpp:83
@ Unweighted
Definition: CglLandP.hpp:84
@ WeightRHS
Definition: CglLandP.hpp:85
@ WeightLHS
Definition: CglLandP.hpp:86
@ WeightBoth
Definition: CglLandP.hpp:87
CglLandP(const CglLandP::Parameters &params=CglLandP::Parameters(), const LAP::Validator &validator=LAP::Validator())
Constructor for the class.
friend class CftCglp
Definition: CglLandP.hpp:54
int numcols_
number of columns in the original problems.
Definition: CglLandP.hpp:293
CglCutGenerator * clone() const
Clone function.
void scanExtraCuts(OsiCuts &cs, const double *colsol) const
Class collecting parameters for all cut generators.
Definition: CglParam.hpp:22
Information about where the cut generator is invoked from.
Definition: CglTreeInfo.hpp:15
Output messages for Cgl.
Definition: CglLandP.hpp:39
LapMessages()
Constructor.
virtual ~LapMessages()
destructor.
Definition: CglLandP.hpp:44
Class to validate or reject a cut.
Performs one round of Lift & Project using CglLandPSimplex to build cuts.
Definition: CglLandP.hpp:25
LapMessagesTypes
Definition: CglLandP.hpp:27
@ DURING_SEP
Definition: CglLandP.hpp:30
@ END_ROUND
Definition: CglLandP.hpp:29
@ CUT_REJECTED
Definition: CglLandP.hpp:31
@ CUT_GAP
Definition: CglLandP.hpp:33
@ CUT_FAILED
Definition: CglLandP.hpp:32
@ LAP_MESSAGES_DUMMY_END
Definition: CglLandP.hpp:35
@ LAP_CUT_FAILED_DO_MIG
Definition: CglLandP.hpp:34
@ BEGIN_ROUND
Definition: CglLandP.hpp:28
Some informations that will be changed by the pivots and that we want to keep.
Definition: CglLandP.hpp:242
int nBasics_
number of basics variables
Definition: CglLandP.hpp:258
CachedData(int nBasics=0, int nNonBasics=0)
int * basics_
Indices of basic variables in starting basis (ordered if variable basics_[i] s basic in row i)
Definition: CglLandP.hpp:254
int nNonBasics_
number of non-basics
Definition: CglLandP.hpp:260
CachedData & operator=(const CachedData &source)
void getData(const OsiSolverInterface &si)
Get the data from a problem.
bool * integers_
Stores wheter slacks are integer constrained.
Definition: CglLandP.hpp:268
CoinWarmStartBasis * basis_
Optimal basis.
Definition: CglLandP.hpp:262
OsiSolverInterface * solver_
Solver before pivots.
Definition: CglLandP.hpp:270
double * slacks_
Stores the values of the slacks.
Definition: CglLandP.hpp:266
int * nonBasics_
Indices of non-basic variables.
Definition: CglLandP.hpp:256
CachedData(const CachedData &source)
double * colsol_
Stores the value of the solution to cut.
Definition: CglLandP.hpp:264