Cgl  0.59.9
Classes | Friends | List of all members
CglProbing Class Reference

Probing Cut Generator Class. More...

#include <CglProbing.hpp>

+ Inheritance diagram for CglProbing:
+ Collaboration diagram for CglProbing:

Classes

struct  CliqueType
 Clique type. More...
 

Public Member Functions

Generate Cuts
virtual void generateCuts (const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo())
 Generate probing/disaggregation cuts for the model of the solver interface, si. More...
 
int generateCutsAndModify (const OsiSolverInterface &si, OsiCuts &cs, CglTreeInfo *info)
 
snapshot etc
int snapshot (const OsiSolverInterface &si, char *possible=NULL, bool withObjective=true)
 Create a copy of matrix which is to be used this is to speed up process and to give global cuts Can give an array with 1 set to select, 0 to ignore column bounds are tightened If array given then values of 1 will be set to 0 if redundant. More...
 
void deleteSnapshot ()
 Deletes snapshot. More...
 
int createCliques (OsiSolverInterface &si, int minimumSize=2, int maximumSize=100)
 Creates cliques for use by probing. More...
 
void deleteCliques ()
 Delete all clique information. More...
 
OsiSolverInterface * cliqueModel (const OsiSolverInterface *model, int type)
 Create a fake model by adding cliques if type&4 then delete rest of model first, if 1 then add proper cliques, 2 add fake cliques. More...
 
Get tighter column bounds
const double * tightLower () const
 Lower. More...
 
const double * tightUpper () const
 Upper. More...
 
const char * tightenBounds () const
 Array which says tighten continuous. More...
 
Get possible freed up row bounds - only valid after mode==3
const double * relaxedRowLower () const
 Lower. More...
 
const double * relaxedRowUpper () const
 Upper. More...
 
Change mode
void setMode (int mode)
 Set. More...
 
int getMode () const
 Get. More...
 
Change maxima
void setMaxPass (int value)
 Set maximum number of passes per node. More...
 
int getMaxPass () const
 Get maximum number of passes per node. More...
 
void setLogLevel (int value)
 Set log level - 0 none, 1 - a bit, 2 - more details. More...
 
int getLogLevel () const
 Get log level. More...
 
void setMaxProbe (int value)
 Set maximum number of unsatisfied variables to look at. More...
 
int getMaxProbe () const
 Get maximum number of unsatisfied variables to look at. More...
 
void setMaxLook (int value)
 Set maximum number of variables to look at in one probe. More...
 
int getMaxLook () const
 Get maximum number of variables to look at in one probe. More...
 
void setMaxElements (int value)
 Set maximum number of elements in row for it to be considered. More...
 
int getMaxElements () const
 Get maximum number of elements in row for it to be considered. More...
 
void setMaxPassRoot (int value)
 Set maximum number of passes per node (root node) More...
 
int getMaxPassRoot () const
 Get maximum number of passes per node (root node) More...
 
void setMaxProbeRoot (int value)
 Set maximum number of unsatisfied variables to look at (root node) More...
 
int getMaxProbeRoot () const
 Get maximum number of unsatisfied variables to look at (root node) More...
 
void setMaxLookRoot (int value)
 Set maximum number of variables to look at in one probe (root node) More...
 
int getMaxLookRoot () const
 Get maximum number of variables to look at in one probe (root node) More...
 
void setMaxElementsRoot (int value)
 Set maximum number of elements in row for it to be considered (root node) More...
 
int getMaxElementsRoot () const
 Get maximum number of elements in row for it to be considered (root node) More...
 
virtual bool mayGenerateRowCutsInTree () const
 Returns true if may generate Row cuts in tree (rather than root node). More...
 
Get information back from probing
int numberThisTime () const
 Number looked at this time. More...
 
const int * lookedAt () const
 Which ones looked at this time. More...
 
Stop or restart row cuts (otherwise just fixing from probing)
void setRowCuts (int type)
 Set 0 no cuts, 1 just disaggregation type, 2 coefficient ( 3 both) More...
 
int rowCuts () const
 Get. More...
 
Information on cliques
int numberCliques () const
 Number of cliques. More...
 
CliqueTypecliqueType () const
 Clique type. More...
 
int * cliqueStart () const
 Start of each clique. More...
 
CliqueEntrycliqueEntry () const
 Entries for clique. More...
 
Whether use objective as constraint
void setUsingObjective (int yesNo)
 Set 0 don't 1 do -1 don't even think about it. More...
 
int getUsingObjective () const
 Get. More...
 
Mark which continuous variables are to be tightened
void tightenThese (const OsiSolverInterface &solver, int number, const int *which)
 Mark variables to be tightened. More...
 
Constructors and destructors
 CglProbing ()
 Default constructor. More...
 
 CglProbing (const CglProbing &)
 Copy constructor. More...
 
virtual CglCutGeneratorclone () const
 Clone. More...
 
CglProbingoperator= (const CglProbing &rhs)
 Assignment operator. More...
 
virtual ~CglProbing ()
 Destructor. More...
 
virtual void refreshSolver (OsiSolverInterface *solver)
 This can be used to refresh any inforamtion. More...
 
virtual std::string generateCpp (FILE *fp)
 Create C++ lines to get to current state. More...
 
- Public Member Functions inherited from CglCutGenerator
 CglCutGenerator ()
 Default constructor. More...
 
 CglCutGenerator (const CglCutGenerator &)
 Copy constructor. More...
 
CglCutGeneratoroperator= (const CglCutGenerator &rhs)
 Assignment operator. More...
 
virtual ~CglCutGenerator ()
 Destructor. More...
 
int getAggressiveness () const
 Get Aggressiveness - 0 = neutral, 100 is normal root node. More...
 
void setAggressiveness (int value)
 Set Aggressiveness - 0 = neutral, 100 is normal root node. More...
 
void setGlobalCuts (bool trueOrFalse)
 Set whether can do global cuts. More...
 
bool canDoGlobalCuts () const
 Say whether can do global cuts. More...
 
virtual bool needsOptimalBasis () const
 Return true if needs optimal basis to do cuts. More...
 
virtual int maximumLengthOfCutInTree () const
 Return maximum length of cut in tree. More...
 

Friends

struct CglProbing::disaggregation_struct_tag
 
void CglProbingUnitTest (const OsiSolverInterface *siP, const std::string mpdDir)
 A function that tests the methods in the CglProbing class. More...
 

Additional Inherited Members

- Public Attributes inherited from CglCutGenerator
int aggressive_
 Aggressiveness - 0 = neutral, 100 is normal root node. More...
 
bool canDoGlobalCuts_
 True if can do global cuts i.e. no general integers. More...
 

Detailed Description

Probing Cut Generator Class.

Definition at line 25 of file CglProbing.hpp.

Constructor & Destructor Documentation

CglProbing::CglProbing ( )

Default constructor.

CglProbing::CglProbing ( const CglProbing )

Copy constructor.

virtual CglProbing::~CglProbing ( )
virtual

Destructor.

Member Function Documentation

virtual void CglProbing::generateCuts ( const OsiSolverInterface &  si,
OsiCuts &  cs,
const CglTreeInfo  info = CglTreeInfo() 
)
virtual

Generate probing/disaggregation cuts for the model of the solver interface, si.

This is a simplification of probing ideas put into OSL about ten years ago. The only known documentation is a copy of a talk handout - we think Robin Lougee-Heimer has a copy!

For selected integer variables (e.g. unsatisfied ones) the effect of setting them up or down is investigated. Setting a variable up may in turn set other variables (continuous as well as integer). There are various possible results:

1) It is shown that problem is infeasible (this may also be because objective function or reduced costs show worse than best solution). If the other way is feasible we can generate a column cut (and continue probing), if not feasible we can say problem infeasible.

2) If both ways are feasible, it can happen that x to 0 implies y to 1 and x to 1 implies y to 1 (again a column cut). More common is that x to 0 implies y to 1 and x to 1 implies y to 0 so we could substitute for y which might lead later to more powerful cuts. This is not done in this code as there is no mechanism for returning information.

3) When x to 1 a constraint went slack by c. We can tighten the constraint ax + .... <= b (where a may be zero) to (a+c)x + .... <= b. If this cut is violated then it is generated.

4) Similarly we can generate implied disaggregation cuts

Note - differences to cuts in OSL.

a) OSL had structures intended to make this faster. b) The "chaining" in 2) was done c) Row cuts modified original constraint rather than adding cut b) This code can cope with general integer variables.

Insert the generated cuts into OsiCut, cs.

If a "snapshot" of a matrix exists then this will be used. Presumably this will give global cuts and will be faster. No check is done to see if cuts will be global.

Otherwise use current matrix.

Both row cuts and column cuts may be returned

The mode options are: 0) Only unsatisfied integer variables will be looked at. If no information exists for that variable then probing will be done so as a by-product you "may" get a fixing or infeasibility. This will be fast and is only available if a snapshot exists (otherwise as 1). The bounds in the snapshot are the ones used. 1) Look at unsatisfied integer variables, using current bounds. Probing will be done on all looked at. 2) Look at all integer variables, using current bounds. Probing will be done on all

If generateCutsAndModify is used then new relaxed row bounds and tightened column bounds are generated Returns number of infeasibilities

Implements CglCutGenerator.

int CglProbing::generateCutsAndModify ( const OsiSolverInterface &  si,
OsiCuts &  cs,
CglTreeInfo info 
)
int CglProbing::snapshot ( const OsiSolverInterface &  si,
char *  possible = NULL,
bool  withObjective = true 
)

Create a copy of matrix which is to be used this is to speed up process and to give global cuts Can give an array with 1 set to select, 0 to ignore column bounds are tightened If array given then values of 1 will be set to 0 if redundant.

Objective may be added as constraint Returns 1 if infeasible otherwise 0

void CglProbing::deleteSnapshot ( )

Deletes snapshot.

int CglProbing::createCliques ( OsiSolverInterface &  si,
int  minimumSize = 2,
int  maximumSize = 100 
)

Creates cliques for use by probing.

Only cliques >= minimumSize and < maximumSize created Can also try and extend cliques as a result of probing (root node). Returns number of cliques found.

void CglProbing::deleteCliques ( )

Delete all clique information.

OsiSolverInterface* CglProbing::cliqueModel ( const OsiSolverInterface *  model,
int  type 
)

Create a fake model by adding cliques if type&4 then delete rest of model first, if 1 then add proper cliques, 2 add fake cliques.

const double* CglProbing::tightLower ( ) const

Lower.

const double* CglProbing::tightUpper ( ) const

Upper.

const char* CglProbing::tightenBounds ( ) const
inline

Array which says tighten continuous.

Definition at line 143 of file CglProbing.hpp.

const double* CglProbing::relaxedRowLower ( ) const

Lower.

const double* CglProbing::relaxedRowUpper ( ) const

Upper.

void CglProbing::setMode ( int  mode)

Set.

int CglProbing::getMode ( ) const

Get.

void CglProbing::setMaxPass ( int  value)

Set maximum number of passes per node.

int CglProbing::getMaxPass ( ) const

Get maximum number of passes per node.

void CglProbing::setLogLevel ( int  value)

Set log level - 0 none, 1 - a bit, 2 - more details.

int CglProbing::getLogLevel ( ) const

Get log level.

void CglProbing::setMaxProbe ( int  value)

Set maximum number of unsatisfied variables to look at.

int CglProbing::getMaxProbe ( ) const

Get maximum number of unsatisfied variables to look at.

void CglProbing::setMaxLook ( int  value)

Set maximum number of variables to look at in one probe.

int CglProbing::getMaxLook ( ) const

Get maximum number of variables to look at in one probe.

void CglProbing::setMaxElements ( int  value)

Set maximum number of elements in row for it to be considered.

int CglProbing::getMaxElements ( ) const

Get maximum number of elements in row for it to be considered.

void CglProbing::setMaxPassRoot ( int  value)

Set maximum number of passes per node (root node)

int CglProbing::getMaxPassRoot ( ) const

Get maximum number of passes per node (root node)

void CglProbing::setMaxProbeRoot ( int  value)

Set maximum number of unsatisfied variables to look at (root node)

int CglProbing::getMaxProbeRoot ( ) const

Get maximum number of unsatisfied variables to look at (root node)

void CglProbing::setMaxLookRoot ( int  value)

Set maximum number of variables to look at in one probe (root node)

int CglProbing::getMaxLookRoot ( ) const

Get maximum number of variables to look at in one probe (root node)

void CglProbing::setMaxElementsRoot ( int  value)

Set maximum number of elements in row for it to be considered (root node)

int CglProbing::getMaxElementsRoot ( ) const

Get maximum number of elements in row for it to be considered (root node)

virtual bool CglProbing::mayGenerateRowCutsInTree ( ) const
virtual

Returns true if may generate Row cuts in tree (rather than root node).

Used so know if matrix will change in tree. Really meant so column cut generators can still be active without worrying code. Default is true

Reimplemented from CglCutGenerator.

int CglProbing::numberThisTime ( ) const
inline

Number looked at this time.

Definition at line 214 of file CglProbing.hpp.

const int* CglProbing::lookedAt ( ) const
inline

Which ones looked at this time.

Definition at line 217 of file CglProbing.hpp.

void CglProbing::setRowCuts ( int  type)

Set 0 no cuts, 1 just disaggregation type, 2 coefficient ( 3 both)

int CglProbing::rowCuts ( ) const

Get.

int CglProbing::numberCliques ( ) const
inline

Number of cliques.

Definition at line 237 of file CglProbing.hpp.

CliqueType* CglProbing::cliqueType ( ) const
inline

Clique type.

Definition at line 240 of file CglProbing.hpp.

int* CglProbing::cliqueStart ( ) const
inline

Start of each clique.

Definition at line 243 of file CglProbing.hpp.

CliqueEntry* CglProbing::cliqueEntry ( ) const
inline

Entries for clique.

Definition at line 246 of file CglProbing.hpp.

void CglProbing::setUsingObjective ( int  yesNo)

Set 0 don't 1 do -1 don't even think about it.

int CglProbing::getUsingObjective ( ) const

Get.

void CglProbing::tightenThese ( const OsiSolverInterface &  solver,
int  number,
const int *  which 
)

Mark variables to be tightened.

virtual CglCutGenerator* CglProbing::clone ( ) const
virtual

Clone.

Implements CglCutGenerator.

CglProbing& CglProbing::operator= ( const CglProbing rhs)

Assignment operator.

virtual void CglProbing::refreshSolver ( OsiSolverInterface *  solver)
virtual

This can be used to refresh any inforamtion.

Reimplemented from CglCutGenerator.

virtual std::string CglProbing::generateCpp ( FILE *  fp)
virtual

Create C++ lines to get to current state.

Reimplemented from CglCutGenerator.

Friends And Related Function Documentation

friend struct CglProbing::disaggregation_struct_tag
friend

Definition at line 357 of file CglProbing.hpp.

void CglProbingUnitTest ( const OsiSolverInterface *  siP,
const std::string  mpdDir 
)
friend

A function that tests the methods in the CglProbing class.

The only reason for it not to be a member method is that this way it doesn't have to be compiled into the library. And that's a gain, because the library should be compiled with optimization on, but this method should be compiled with debugging.


The documentation for this class was generated from the following file: