Loading...
Searching...
No Matches
CglLandP.hpp
Go to the documentation of this file.
// Copyright (C) 2005-2009, Pierre Bonami and others. All Rights Reserved.
// Author: Pierre Bonami
// Tepper School of Business
// Carnegie Mellon University, Pittsburgh, PA 15213
// Date: 07/21/05
//
// $Id$
//
// This code is licensed under the terms of the Eclipse Public License (EPL).
//---------------------------------------------------------------------------
#ifndef CglLandP_H
#define CglLandP_H
#include "CglLandPValidator.hpp"
#include "CglCutGenerator.hpp"
#include "CglParam.hpp"
#include <iostream>
class CoinWarmStartBasis;
namespace LAP
{
enum LapMessagesTypes
{
BEGIN_ROUND,
END_ROUND,
DURING_SEP,
CUT_REJECTED,
CUT_FAILED,
CUT_GAP,
LAP_CUT_FAILED_DO_MIG,
LAP_MESSAGES_DUMMY_END
};
class LapMessages : public CoinMessages
{
public:
LapMessages( );
virtual ~LapMessages() {}
};
class CglLandPSimplex;
}
class CglLandP : public CglCutGenerator
{
friend void CglLandPUnitTest(OsiSolverInterface *si, const std::string & mpsDir);
friend class LAP::CglLandPSimplex;
friend class CftCglp;
public:
enum SelectionRules
{
mostNegativeRc ,
bestPivot ,
initialReducedCosts
};
enum ExtraCutsMode
{
none,
AtOptimalBasis ,
WhenEnteringBasis ,
AllViolatedMigs
};
enum SeparationSpaces
{
Fractional=0 ,
Fractional_rc,
Full
};
enum Normalization
{
Unweighted = 0,
WeightRHS,
WeightLHS,
WeightBoth
};
enum LHSnorm
{
L1 = 0,
L2,
SupportSize,
Infinity,
Average,
Uniform
};
enum RhsWeightType
{
Fixed = 0 ,
Dynamic
};
class Parameters : public CglParam
{
public:
Parameters();
Parameters(const Parameters &other);
Parameters & operator=(const Parameters &other);
int pivotLimit;
int pivotLimitInTree;
int maxCutPerRound;
int failedPivotLimit;
int degeneratePivotLimit;
int extraCutsLimit;
double pivotTol;
double away;
double timeLimit;
double singleCutTimeLimit;
double rhsWeight;
bool useTableauRow;
bool modularize;
bool strengthen;
bool countMistakenRc;
SeparationSpaces sepSpace;
bool perturb;
Normalization normalization;
RhsWeightType rhsWeightType;
LHSnorm lhs_norm;
ExtraCutsMode generateExtraCuts;
SelectionRules pivotSelection;
};
CglLandP(const CglLandP::Parameters &params = CglLandP::Parameters(),
const LAP::Validator &validator = LAP::Validator());
~CglLandP();
CglLandP(const CglLandP &source);
CglLandP& operator=(const CglLandP &rhs);
CglCutGenerator * clone() const;
virtual void generateCuts(const OsiSolverInterface & si, OsiCuts & cs,
const CglTreeInfo info = CglTreeInfo());
virtual bool needsOptimalBasis() const
{
return true;
}
LAP::Validator & validator()
{
return validator_;
}
void setLogLevel(int level)
{
handler_->setLogLevel(level);
}
class NoBasisError : public CoinError
{
public:
NoBasisError(): CoinError("No basis available","LandP","") {}
};
class SimplexInterfaceError : public CoinError
{
public:
SimplexInterfaceError(): CoinError("Invalid conversion to simplex interface", "CglLandP","CglLandP") {}
};
Parameters & parameter()
{
return params_;
}
private:
void scanExtraCuts(OsiCuts& cs, const double * colsol) const;
Parameters params_;
struct CachedData
{
CachedData(int nBasics = 0 , int nNonBasics = 0);
CachedData(const CachedData & source);
CachedData& operator=(const CachedData &source);
void getData(const OsiSolverInterface &si);
void clean();
~CachedData();
int * basics_;
int *nonBasics_;
int nBasics_;
int nNonBasics_;
CoinWarmStartBasis * basis_;
double * colsol_;
double * slacks_;
bool * integers_;
OsiSolverInterface * solver_;
};
int getSortedFractionals(CoinPackedVector &xFrac,
const CachedData & data,
const CglLandP::Parameters& params) const;
void getSortedFractionalIndices(std::vector<int>& indices,
const CachedData &data,
const CglLandP::Parameters & params) const;
CachedData cached_;
CoinMessageHandler * handler_;
CoinMessages messages_;
LAP::Validator validator_;
int numrows_;
int numcols_;
double * originalColLower_;
double * originalColUpper_;
bool canLift_;
OsiCuts extraCuts_;
};
void CglLandPUnitTest(OsiSolverInterface *si, const std::string & mpsDir);
#endif
CglCutGenerator.hpp
CglLandPValidator.hpp
CglLandPUnitTest
void CglLandPUnitTest(OsiSolverInterface *si, const std::string &mpsDir)
CglParam.hpp
CglCutGenerator::CglCutGenerator
CglCutGenerator()
Default constructor.
CglLandP::NoBasisError::NoBasisError
NoBasisError()
Definition CglLandP.hpp:221
CglLandP::Parameters
Class storing parameters.
Definition CglLandP.hpp:108
CglLandP::Parameters::away
double away
A variable have to be at least away from integrity to be generated.
Definition CglLandP.hpp:140
CglLandP::Parameters::pivotLimit
int pivotLimit
Max number of pivots before we generate the cut \default 20.
Definition CglLandP.hpp:121
CglLandP::Parameters::Parameters
Parameters()
Default constructor (with default values).
CglLandP::Parameters::modularize
bool modularize
Do we apply Egon Balas's Heuristic for modularized cuts.
Definition CglLandP.hpp:154
CglLandP::Parameters::failedPivotLimit
int failedPivotLimit
Maximum number of failed pivots before aborting.
Definition CglLandP.hpp:128
CglLandP::Parameters::strengthen
bool strengthen
Do we strengthen the final cut (always do if modularize is 1).
Definition CglLandP.hpp:156
CglLandP::Parameters::maxCutPerRound
int maxCutPerRound
Maximum number of cuts generated at a given round.
Definition CglLandP.hpp:126
CglLandP::Parameters::pivotLimitInTree
int pivotLimitInTree
Max number of pivots at regular nodes.
Definition CglLandP.hpp:124
CglLandP::Parameters::lhs_norm
LHSnorm lhs_norm
How to weight LHS of normalization.
Definition CglLandP.hpp:168
CglLandP::Parameters::sepSpace
SeparationSpaces sepSpace
Work in the reduced space (only non-structurals enter the basis).
Definition CglLandP.hpp:160
CglLandP::Parameters::Parameters
Parameters(const Parameters &other)
Copy constructor.
CglLandP::Parameters::generateExtraCuts
ExtraCutsMode generateExtraCuts
Generate extra constraints from optimal lift-and-project basis.
Definition CglLandP.hpp:170
CglLandP::Parameters::perturb
bool perturb
Apply perturbation procedure.
Definition CglLandP.hpp:162
CglLandP::Parameters::operator=
Parameters & operator=(const Parameters &other)
Assignment opertator.
CglLandP::Parameters::extraCutsLimit
int extraCutsLimit
Maximum number of extra rows to generate per round.
Definition CglLandP.hpp:133
CglLandP::Parameters::singleCutTimeLimit
double singleCutTimeLimit
Time limit for generating a single cut.
Definition CglLandP.hpp:144
CglLandP::Parameters::normalization
Normalization normalization
How to weight normalization.
Definition CglLandP.hpp:164
CglLandP::Parameters::rhsWeight
double rhsWeight
Weight to put in RHS of normalization if static.
Definition CglLandP.hpp:146
CglLandP::Parameters::pivotTol
double pivotTol
Tolerance for small pivots values (should be the same as the solver.
Definition CglLandP.hpp:138
CglLandP::Parameters::pivotSelection
SelectionRules pivotSelection
Which rule to apply for choosing entering and leaving variables.
Definition CglLandP.hpp:172
CglLandP::Parameters::useTableauRow
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
CglLandP::Parameters::timeLimit
double timeLimit
Total time limit for cut generation.
Definition CglLandP.hpp:142
CglLandP::Parameters::countMistakenRc
bool countMistakenRc
Wether to limit or not the number of mistaken RC (when perturbation is applied).
Definition CglLandP.hpp:158
CglLandP::Parameters::rhsWeightType
RhsWeightType rhsWeightType
How to weight RHS of normalization.
Definition CglLandP.hpp:166
CglLandP::Parameters::degeneratePivotLimit
int degeneratePivotLimit
maximum number of consecutive degenerate pivots \default 0
Definition CglLandP.hpp:131
CglLandP::SimplexInterfaceError::SimplexInterfaceError
SimplexInterfaceError()
Definition CglLandP.hpp:227
CglLandP::extraCuts_
OsiCuts extraCuts_
Store some extra cut which could be cheaply generated but do not cut current incumbent.
Definition CglLandP.hpp:301
CglLandP::canLift_
bool canLift_
Flag to say if cuts can be lifted.
Definition CglLandP.hpp:299
CglLandP::operator=
CglLandP & operator=(const CglLandP &rhs)
Assignment operator.
CglLandP::validator
LAP::Validator & validator()
Definition CglLandP.hpp:202
CglLandP::cached_
CachedData cached_
Cached informations about problem.
Definition CglLandP.hpp:283
CglLandP::generateCuts
virtual void generateCuts(const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo())
Generate cuts for the model data contained in si.
CglLandP::CglLandPUnitTest
friend void CglLandPUnitTest(OsiSolverInterface *si, const std::string &mpsDir)
CglLandP::getSortedFractionals
int getSortedFractionals(CoinPackedVector &xFrac, const CachedData &data, const CglLandP::Parameters &params) const
Retrieve sorted integer variables which are fractional in the solution.
CglLandP::SelectionRules
SelectionRules
Definition CglLandP.hpp:59
CglLandP::initialReducedCosts
@ initialReducedCosts
Select only those rows which had initialy a 0 reduced cost.
Definition CglLandP.hpp:62
CglLandP::mostNegativeRc
@ mostNegativeRc
select most negative reduced cost
Definition CglLandP.hpp:60
CglLandP::bestPivot
@ bestPivot
select best possible pivot.
Definition CglLandP.hpp:61
CglLandP::SeparationSpaces
SeparationSpaces
Space where cuts are optimized.
Definition CglLandP.hpp:75
CglLandP::Full
@ Full
Work in full space.
Definition CglLandP.hpp:78
CglLandP::Fractional_rc
@ Fractional_rc
Use fractional space only for computing reduced costs.
Definition CglLandP.hpp:77
CglLandP::Fractional
@ Fractional
Definition CglLandP.hpp:76
CglLandP::setLogLevel
void setLogLevel(int level)
set level of log for cut generation procedure :
Definition CglLandP.hpp:213
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::params_
Parameters params_
Definition CglLandP.hpp:238
CglLandP::RhsWeightType
RhsWeightType
RHS weight in normalization.
Definition CglLandP.hpp:101
CglLandP::Fixed
@ Fixed
Definition CglLandP.hpp:102
CglLandP::Dynamic
@ Dynamic
2 * current number of constraints.
Definition CglLandP.hpp:103
CglLandP::numrows_
int numrows_
number of rows in the original problems.
Definition CglLandP.hpp:291
CglLandP::originalColUpper_
double * originalColUpper_
Original upper bounds for the problem (for lifting cuts).
Definition CglLandP.hpp:297
CglLandP::clone
CglCutGenerator * clone() const
Clone function.
CglLandP::handler_
CoinMessageHandler * handler_
message handler
Definition CglLandP.hpp:285
CglLandP::ExtraCutsMode
ExtraCutsMode
Definition CglLandP.hpp:66
CglLandP::WhenEnteringBasis
@ WhenEnteringBasis
Generate cuts as soon as a structural enters the basis.
Definition CglLandP.hpp:69
CglLandP::none
@ none
Generate no extra cuts.
Definition CglLandP.hpp:67
CglLandP::AllViolatedMigs
@ AllViolatedMigs
Generate all violated Mixed integer Gomory cuts in the course of the optimization.
Definition CglLandP.hpp:70
CglLandP::AtOptimalBasis
@ AtOptimalBasis
Generate cuts from the optimal basis.
Definition CglLandP.hpp:68
CglLandP::LHSnorm
LHSnorm
Definition CglLandP.hpp:91
CglLandP::Average
@ Average
Definition CglLandP.hpp:96
CglLandP::Infinity
@ Infinity
Definition CglLandP.hpp:95
CglLandP::L2
@ L2
Definition CglLandP.hpp:93
CglLandP::Uniform
@ Uniform
Definition CglLandP.hpp:97
CglLandP::L1
@ L1
Definition CglLandP.hpp:92
CglLandP::SupportSize
@ SupportSize
Definition CglLandP.hpp:94
CglLandP::~CglLandP
~CglLandP()
Destructor.
CglLandP::validator_
LAP::Validator validator_
cut validator
Definition CglLandP.hpp:289
CglLandP::originalColLower_
double * originalColLower_
Original lower bounds for the problem (for lifting cuts).
Definition CglLandP.hpp:295
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::CglLandP
CglLandP(const CglLandP &source)
Copy constructor.
CglLandP::Normalization
Normalization
Normalization.
Definition CglLandP.hpp:83
CglLandP::Unweighted
@ Unweighted
Definition CglLandP.hpp:84
CglLandP::WeightRHS
@ WeightRHS
Definition CglLandP.hpp:85
CglLandP::WeightLHS
@ WeightLHS
Definition CglLandP.hpp:86
CglLandP::WeightBoth
@ WeightBoth
Definition CglLandP.hpp:87
CglLandP::CglLandP
CglLandP(const CglLandP::Parameters &params=CglLandP::Parameters(), const LAP::Validator &validator=LAP::Validator())
Constructor for the class.
CglLandP::CftCglp
friend class CftCglp
Definition CglLandP.hpp:54
CglLandP::numcols_
int numcols_
number of columns in the original problems.
Definition CglLandP.hpp:293
CglLandP::scanExtraCuts
void scanExtraCuts(OsiCuts &cs, const double *colsol) const
CglLandP::parameter
Parameters & parameter()
Definition CglLandP.hpp:229
CglParam::CglParam
CglParam(const double inf=COIN_DBL_MAX, const double eps=1e-6, const double eps_c=1e-5, const int max_s=COIN_INT_MAX)
Default constructor.
CglTreeInfo
Information about where the cut generator is invoked from.
Definition CglTreeInfo.hpp:15
LAP::CglLandPSimplex
Definition CglLandPSimplex.hpp:43
LAP::LapMessages::LapMessages
LapMessages()
Constructor.
LAP::LapMessages::~LapMessages
virtual ~LapMessages()
destructor.
Definition CglLandP.hpp:44
LAP::Validator
Class to validate or reject a cut.
Definition CglLandPValidator.hpp:27
LAP
Performs one round of Lift & Project using CglLandPSimplex to build cuts.
Definition CglLandP.hpp:25
LAP::LapMessagesTypes
LapMessagesTypes
Definition CglLandP.hpp:27
LAP::DURING_SEP
@ DURING_SEP
Definition CglLandP.hpp:30
LAP::END_ROUND
@ END_ROUND
Definition CglLandP.hpp:29
LAP::CUT_REJECTED
@ CUT_REJECTED
Definition CglLandP.hpp:31
LAP::CUT_GAP
@ CUT_GAP
Definition CglLandP.hpp:33
LAP::CUT_FAILED
@ CUT_FAILED
Definition CglLandP.hpp:32
LAP::LAP_MESSAGES_DUMMY_END
@ LAP_MESSAGES_DUMMY_END
Definition CglLandP.hpp:35
LAP::LAP_CUT_FAILED_DO_MIG
@ LAP_CUT_FAILED_DO_MIG
Definition CglLandP.hpp:34
LAP::BEGIN_ROUND
@ BEGIN_ROUND
Definition CglLandP.hpp:28
CglLandP::CachedData
Some informations that will be changed by the pivots and that we want to keep.
Definition CglLandP.hpp:242
CglLandP::CachedData::operator=
CachedData & operator=(const CachedData &source)
CglLandP::CachedData::nBasics_
int nBasics_
number of basics variables
Definition CglLandP.hpp:258
CglLandP::CachedData::CachedData
CachedData(int nBasics=0, int nNonBasics=0)
CglLandP::CachedData::~CachedData
~CachedData()
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::nNonBasics_
int nNonBasics_
number of non-basics
Definition CglLandP.hpp:260
CglLandP::CachedData::getData
void getData(const OsiSolverInterface &si)
Get the data from a problem.
CglLandP::CachedData::integers_
bool * integers_
Stores wheter slacks are integer constrained.
Definition CglLandP.hpp:268
CglLandP::CachedData::basis_
CoinWarmStartBasis * basis_
Optimal basis.
Definition CglLandP.hpp:262
CglLandP::CachedData::solver_
OsiSolverInterface * solver_
Solver before pivots.
Definition CglLandP.hpp:270
CglLandP::CachedData::slacks_
double * slacks_
Stores the values of the slacks.
Definition CglLandP.hpp:266
CglLandP::CachedData::nonBasics_
int * nonBasics_
Indices of non-basic variables.
Definition CglLandP.hpp:256
CglLandP::CachedData::CachedData
CachedData(const CachedData &source)
CglLandP::CachedData::clean
void clean()
CglLandP::CachedData::colsol_
double * colsol_
Stores the value of the solution to cut.
Definition CglLandP.hpp:264