- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

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: CglLandP.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 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 {
26 enum LapMessagesTypes
27 {
28 BEGIN_ROUND,
29 END_ROUND,
30 DURING_SEP,
31 CUT_REJECTED,
32 CUT_FAILED,
33 CUT_GAP,
34 LAP_CUT_FAILED_DO_MIG,
35 LAP_MESSAGES_DUMMY_END
36 };
38 class LapMessages : public CoinMessages
39 {
40 public:
42 LapMessages( );
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
58 enum SelectionRules
59 {
60 mostNegativeRc ,
61 bestPivot ,
62 initialReducedCosts
63 };
64
65 enum ExtraCutsMode
66 {
67 none,
68 AtOptimalBasis ,
69 WhenEnteringBasis ,
70 AllViolatedMigs
71 };
72
74 enum SeparationSpaces
75 {
76 Fractional=0 ,
77 Fractional_rc,
78 Full
79 };
80
82 enum Normalization
83 {
84 Unweighted = 0,
85 WeightRHS,
86 WeightLHS,
87 WeightBoth
88 };
89
90 enum LHSnorm
91 {
92 L1 = 0,
93 L2,
94 SupportSize,
95 Infinity,
96 Average,
97 Uniform
98 };
100 enum RhsWeightType
101 {
102 Fixed = 0 ,
103 Dynamic
104 };
107 class Parameters : public CglParam
108 {
109 public:
111 Parameters();
113 Parameters(const Parameters &other);
115 Parameters & operator=(const Parameters &other);
118
121 int pivotLimit;
124 int pivotLimitInTree;
126 int maxCutPerRound;
128 int failedPivotLimit;
131 int degeneratePivotLimit;
133 int extraCutsLimit;
137
138 double pivotTol;
140 double away;
142 double timeLimit;
144 double singleCutTimeLimit;
146 double rhsWeight;
148
151
152 bool useTableauRow;
154 bool modularize;
156 bool strengthen;
158 bool countMistakenRc;
160 SeparationSpaces sepSpace;
162 bool perturb;
164 Normalization normalization;
166 RhsWeightType rhsWeightType;
168 LHSnorm lhs_norm;
170 ExtraCutsMode generateExtraCuts;
172 SelectionRules pivotSelection;
174 };
175
176
178 CglLandP(const CglLandP::Parameters &params = CglLandP::Parameters(),
179 const LAP::Validator &validator = LAP::Validator());
181 ~CglLandP();
183 CglLandP(const CglLandP &source);
185 CglLandP& operator=(const CglLandP &rhs);
187 CglCutGenerator * clone() const;
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
202 LAP::Validator & validator()
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 };
229 Parameters & parameter()
230 {
231 return params_;
232 }
233 private:
234
235
236 void scanExtraCuts(OsiCuts& cs, const double * colsol) const;
237
238 Parameters params_;
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
252 ~CachedData();
254 int * basics_;
256 int *nonBasics_;
258 int nBasics_;
260 int nNonBasics_;
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;
283 CachedData cached_;
285 CoinMessageHandler * handler_;
287 CoinMessages messages_;
289 LAP::Validator validator_;
291 int numrows_;
293 int numcols_;
295 double * originalColLower_;
297 double * originalColUpper_;
299 bool canLift_;
301 OsiCuts extraCuts_;
302 };
303 void CglLandPUnitTest(OsiSolverInterface *si, const std::string & mpsDir);
304
305 #endif
306
CglLandP::CachedData::~CachedData
~CachedData()
CglLandP::initialReducedCosts
Select only those rows which had initialy a 0 reduced cost.
Definition: CglLandP.hpp:62
CglLandP::Parameters::countMistakenRc
bool countMistakenRc
Wether to limit or not the number of mistaken RC (when perturbation is applied).
Definition: CglLandP.hpp:158
CglLandP::getSortedFractionalIndices
void getSortedFractionalIndices(std::vector< int > &indices, const CachedData &data, const CglLandP::Parameters &params) const
Retrieve sorted integer variables which are fractional in the solution.
CglLandP::clone
CglCutGenerator * clone() const
Clone function.
CglLandP::CachedData::nonBasics_
int * nonBasics_
Indices of non-basic variables.
Definition: CglLandP.hpp:256
CglLandP::Parameters::generateExtraCuts
ExtraCutsMode generateExtraCuts
Generate extra constraints from optimal lift-and-project basis.
Definition: CglLandP.hpp:170
CglLandP::Normalization
Normalization
Normalization.
Definition: CglLandP.hpp:82
CoinMessageHandler
Base class for message handling.
Definition: CoinMessageHandler.hpp:327
CglLandP::mostNegativeRc
select most negative reduced cost
Definition: CglLandP.hpp:60
CglLandP::extraCuts_
OsiCuts extraCuts_
Store some extra cut which could be cheaply generated but do not cut current incumbent.
Definition: CglLandP.hpp:301
CglLandP::CachedData::solver_
OsiSolverInterface * solver_
Solver before pivots.
Definition: CglLandP.hpp:270
CglLandP::Dynamic
2 * current number of constraints.
Definition: CglLandP.hpp:103
LAP::CUT_FAILED
Definition: CglLandP.hpp:32
CglLandP::Parameters::failedPivotLimit
int failedPivotLimit
Maximum number of failed pivots before aborting.
Definition: CglLandP.hpp:128
CglLandP::originalColLower_
double * originalColLower_
Original lower bounds for the problem (for lifting cuts).
Definition: CglLandP.hpp:295
CglLandP::Parameters::degeneratePivotLimit
int degeneratePivotLimit
maximum number of consecutive degenerate pivots 0
Definition: CglLandP.hpp:131
CglLandP::RhsWeightType
RhsWeightType
RHS weight in normalization.
Definition: CglLandP.hpp:100
CglLandP::getSortedFractionals
int getSortedFractionals(CoinPackedVector &xFrac, const CachedData &data, const CglLandP::Parameters &params) const
Retrieve sorted integer variables which are fractional in the solution.
LAP::CUT_REJECTED
Definition: CglLandP.hpp:31
CglLandP::params_
Parameters params_
Definition: CglLandP.hpp:238
CglLandP::Parameters::sepSpace
SeparationSpaces sepSpace
Work in the reduced space (only non-structurals enter the basis)
Definition: CglLandP.hpp:160
CglLandP::CachedData::nBasics_
int nBasics_
number of basics variables
Definition: CglLandP.hpp:258
CglLandP::CachedData::integers_
bool * integers_
Stores wheter slacks are integer constrained.
Definition: CglLandP.hpp:268
CglLandP::L1
Definition: CglLandP.hpp:92
CglLandP::Fractional
Definition: CglLandP.hpp:76
CglLandP::Unweighted
Definition: CglLandP.hpp:84
CglLandP::none
Generate no extra cuts.
Definition: CglLandP.hpp:67
LAP::END_ROUND
Definition: CglLandP.hpp:29
CglLandP::Parameters::operator=
Parameters & operator=(const Parameters &other)
Assignment opertator.
CglLandP::parameter
Parameters & parameter()
Definition: CglLandP.hpp:229
CglLandP::originalColUpper_
double * originalColUpper_
Original upper bounds for the problem (for lifting cuts).
Definition: CglLandP.hpp:297
CglLandP::WeightRHS
Definition: CglLandP.hpp:85
CglLandP::CachedData::operator=
CachedData & operator=(const CachedData &source)
CglLandP::CachedData::CachedData
CachedData(int nBasics=0, int nNonBasics=0)
CglLandP::cached_
CachedData cached_
Cached informations about problem.
Definition: CglLandP.hpp:283
CglLandP::setLogLevel
void setLogLevel(int level)
set level of log for cut generation procedure :
Definition: CglLandP.hpp:213
CglLandP::Parameters::normalization
Normalization normalization
How to weight normalization.
Definition: CglLandP.hpp:164
OsiCuts
Collections of row cuts and column cuts.
Definition: OsiCuts.hpp:19
CglLandP::CachedData::slacks_
double * slacks_
Stores the values of the slacks.
Definition: CglLandP.hpp:266
CglLandP::numrows_
int numrows_
number of rows in the original problems.
Definition: CglLandP.hpp:291
CglLandP::CachedData::basics_
int * basics_
Indices of basic variables in starting basis (ordered if variable basics_[i] s basic in row i) ...
Definition: CglLandP.hpp:254
CglLandP::CachedData::clean
void clean()
CglLandP::Parameters::rhsWeight
double rhsWeight
Weight to put in RHS of normalization if static.
Definition: CglLandP.hpp:146
CglLandPValidator.hpp
LAP::LapMessagesTypes
LapMessagesTypes
Definition: CglLandP.hpp:26
CglLandP::AtOptimalBasis
Generate cuts from the optimal basis.
Definition: CglLandP.hpp:68
CglLandPUnitTest
void CglLandPUnitTest(OsiSolverInterface *si, const std::string &mpsDir)
CglLandP::CachedData::nNonBasics_
int nNonBasics_
number of non-basics
Definition: CglLandP.hpp:260
CglLandP::SimplexInterfaceError::SimplexInterfaceError
SimplexInterfaceError()
Definition: CglLandP.hpp:227
CglLandP::Parameters::lhs_norm
LHSnorm lhs_norm
How to weight LHS of normalization.
Definition: CglLandP.hpp:168
LAP::LapMessages::LapMessages
LapMessages()
Constructor.
CglLandP::CglLandPUnitTest
friend void CglLandPUnitTest(OsiSolverInterface *si, const std::string &mpsDir)
CglLandP::Parameters::timeLimit
double timeLimit
Total time limit for cut generation.
Definition: CglLandP.hpp:142
CglLandP::Parameters::pivotLimitInTree
int pivotLimitInTree
Max number of pivots at regular nodes.
Definition: CglLandP.hpp:124
CglLandP::WeightBoth
Definition: CglLandP.hpp:87
CglParam
Class collecting parameters for all cut generators.
Definition: CglParam.hpp:22
CglLandP::Parameters::extraCutsLimit
int extraCutsLimit
Maximum number of extra rows to generate per round.
Definition: CglLandP.hpp:133
CglLandP::Parameters::pivotLimit
int pivotLimit
Max number of pivots before we generate the cut 20.
Definition: CglLandP.hpp:121
CglLandP::canLift_
bool canLift_
Flag to say if cuts can be lifted.
Definition: CglLandP.hpp:299
CglCutGenerator.hpp
CglLandP::CachedData
Some informations that will be changed by the pivots and that we want to keep.
Definition: CglLandP.hpp:241
CglLandP::generateCuts
virtual void generateCuts(const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo())
Generate cuts for the model data contained in si.
CglLandP::validator_
LAP::Validator validator_
cut validator
Definition: CglLandP.hpp:289
CglLandP::messages_
CoinMessages messages_
messages
Definition: CglLandP.hpp:287
CglLandP::needsOptimalBasis
virtual bool needsOptimalBasis() const
Return true if needs optimal basis to do cuts.
Definition: CglLandP.hpp:197
CglLandP::SimplexInterfaceError
Definition: CglLandP.hpp:224
CglLandP::CftCglp
friend class CftCglp
Definition: CglLandP.hpp:54
CglLandP::Parameters::strengthen
bool strengthen
Do we strengthen the final cut (always do if modularize is 1)
Definition: CglLandP.hpp:156
CglLandP::validator
LAP::Validator & validator()
Definition: CglLandP.hpp:202
LAP::LapMessages::~LapMessages
virtual ~LapMessages()
destructor.
Definition: CglLandP.hpp:44
CglLandP::SupportSize
Definition: CglLandP.hpp:94
LAP::Validator
Class to validate or reject a cut.
Definition: CglLandPValidator.hpp:26
OsiSolverInterface
Abstract Base Class for describing an interface to a solver.
Definition: OsiSolverInterface.hpp:62
CglLandP::CglLandP
CglLandP(const CglLandP::Parameters &params=CglLandP::Parameters(), const LAP::Validator &validator=LAP::Validator())
Constructor for the class.
CglLandP::Parameters::maxCutPerRound
int maxCutPerRound
Maximum number of cuts generated at a given round.
Definition: CglLandP.hpp:126
CglLandP::scanExtraCuts
void scanExtraCuts(OsiCuts &cs, const double *colsol) const
CglLandP::LHSnorm
LHSnorm
Definition: CglLandP.hpp:90
CglCutGenerator
Cut Generator Base Class.
Definition: CglCutGenerator.hpp:23
CglLandP::Fractional_rc
Use fractional space only for computing reduced costs.
Definition: CglLandP.hpp:77
CglLandP::Full
Work in full space.
Definition: CglLandP.hpp:78
CglLandP::CachedData::colsol_
double * colsol_
Stores the value of the solution to cut.
Definition: CglLandP.hpp:264
CglLandP::bestPivot
select best possible pivot.
Definition: CglLandP.hpp:61
CglParam.hpp
CglLandP::Parameters::singleCutTimeLimit
double singleCutTimeLimit
Time limit for generating a single cut.
Definition: CglLandP.hpp:144
CoinMessages
Class to hold and manipulate an array of massaged messages.
Definition: CoinMessageHandler.hpp:128
CglLandP::AllViolatedMigs
Generate all violated Mixed integer Gomory cuts in the course of the optimization.
Definition: CglLandP.hpp:70
CglLandP::CachedData::basis_
CoinWarmStartBasis * basis_
Optimal basis.
Definition: CglLandP.hpp:262
CglLandP::Parameters::pivotSelection
SelectionRules pivotSelection
Which rule to apply for choosing entering and leaving variables.
Definition: CglLandP.hpp:172
CoinError
Error Class thrown by an exception.
Definition: CoinError.hpp:42
CglLandP::Parameters::away
double away
A variable have to be at least away from integrity to be generated.
Definition: CglLandP.hpp:140
CglLandP::Parameters::rhsWeightType
RhsWeightType rhsWeightType
How to weight RHS of normalization.
Definition: CglLandP.hpp:166
CoinPackedVector
Sparse Vector.
Definition: CoinPackedVector.hpp:123
CglLandP::WhenEnteringBasis
Generate cuts as soon as a structural enters the basis.
Definition: CglLandP.hpp:69
CglLandP::~CglLandP
~CglLandP()
Destructor.
CglLandP::numcols_
int numcols_
number of columns in the original problems.
Definition: CglLandP.hpp:293
CoinMessageHandler::setLogLevel
void setLogLevel(int value)
Set current log (detail) level.
LAP::LAP_MESSAGES_DUMMY_END
Definition: CglLandP.hpp:35
LAP::BEGIN_ROUND
Definition: CglLandP.hpp:28
CglLandP::Average
Definition: CglLandP.hpp:96
CglLandP::Infinity
Definition: CglLandP.hpp:95
LAP::LAP_CUT_FAILED_DO_MIG
Definition: CglLandP.hpp:34
CglLandP::handler_
CoinMessageHandler * handler_
message handler
Definition: CglLandP.hpp:285
CglLandP::SeparationSpaces
SeparationSpaces
Space where cuts are optimized.
Definition: CglLandP.hpp:74
CglLandP::Uniform
Definition: CglLandP.hpp:97
CglLandP::CachedData::getData
void getData(const OsiSolverInterface &si)
Get the data from a problem.
CglLandP::NoBasisError::NoBasisError
NoBasisError()
Definition: CglLandP.hpp:221
CglLandP::WeightLHS
Definition: CglLandP.hpp:86
CglLandP::Parameters
Class storing parameters.
Definition: CglLandP.hpp:107
CglTreeInfo
Information about where the cut generator is invoked from.
Definition: CglTreeInfo.hpp:15
LAP::LapMessages
Output messages for Cgl.
Definition: CglLandP.hpp:38
CglLandP::Parameters::modularize
bool modularize
Do we apply Egon Balas&#39;s Heuristic for modularized cuts.
Definition: CglLandP.hpp:154
CglLandP
Definition: CglLandP.hpp:49
CglLandP::operator=
CglLandP & operator=(const CglLandP &rhs)
Assignment operator.
LAP::CUT_GAP
Definition: CglLandP.hpp:33
CglLandP::SelectionRules
SelectionRules
Definition: CglLandP.hpp:58
CglLandP::Fixed
Definition: CglLandP.hpp:102
LAP::DURING_SEP
Definition: CglLandP.hpp:30
CglLandP::NoBasisError
Definition: CglLandP.hpp:218
CoinWarmStartBasis
The default COIN simplex (basis-oriented) warm start class.
Definition: CoinWarmStartBasis.hpp:40
CglLandP::Parameters::useTableauRow
bool useTableauRow
Do we use tableau row or the disjunction (I don&#39;t really get that there should be a way to always use...
Definition: CglLandP.hpp:152
CglLandP::Parameters::pivotTol
double pivotTol
Tolerance for small pivots values (should be the same as the solver.
Definition: CglLandP.hpp:138
CglLandP::Parameters::Parameters
Parameters()
Default constructor (with default values)
LAP::CglLandPSimplex
Definition: CglLandPSimplex.hpp:42
CglLandP::Parameters::perturb
bool perturb
Apply perturbation procedure.
Definition: CglLandP.hpp:162
CglLandP::L2
Definition: CglLandP.hpp:93
CglLandP::ExtraCutsMode
ExtraCutsMode
Definition: CglLandP.hpp:65