Loading...
Searching...
No Matches
CglGMI.hpp
Go to the documentation of this file.
// Last edit: 02/05/2013
//
// Name: CglGMI.hpp
// Author: Giacomo Nannicini
// Singapore University of Technology and Design, Singapore
// email: nannicini@sutd.edu.sg
// Date: 11/17/09
//-----------------------------------------------------------------------------
// Copyright (C) 2009, Giacomo Nannicini. All Rights Reserved.
#ifndef CglGMI_H
#define CglGMI_H
#include "CglCutGenerator.hpp"
#include "CglGMIParam.hpp"
#include "CoinWarmStartBasis.hpp"
#include "CoinFactorization.hpp"
/* Enable tracking of rejection of cutting planes. If this is disabled,
the cut generator is slightly faster. If defined, it enables proper use
of setTrackRejection and related functions. */
//#define TRACK_REJECT
/* Debug output */
//#define GMI_TRACE
/* Debug output: print optimal tableau */
//#define GMI_TRACETAB
/* Print reason for cut rejection, whenever a cut is discarded */
//#define GMI_TRACE_CLEAN
class CglGMI : public CglCutGenerator {
friend void CglGMIUnitTest(const OsiSolverInterface * siP,
const std::string mpdDir);
public:
enum RejectionType{
failureFractionality,
failureDynamism,
failureViolation,
failureSupport,
failureScale
};
virtual void generateCuts(const OsiSolverInterface & si, OsiCuts & cs,
const CglTreeInfo info = CglTreeInfo());
virtual bool needsOptimalBasis() const { return true; }
// Function for checking equality with user tolerance
inline bool areEqual(double x, double y,
double epsAbs = 1e-12,
double epsRel = 1e-12) {
return (fabs((x) - (y)) <=
std::max(epsAbs, epsRel * std::max(fabs(x), fabs(y))));
}
// Function for checking is a number is zero
inline bool isZero(double x, double epsZero = 1e-20) {
return (fabs(x) <= epsZero);
}
// Function for checking if a number is integer
inline bool isIntegerValue(double x,
double intEpsAbs = 1e-9,
double intEpsRel = 1e-15) {
return (fabs((x) - floor((x)+0.5)) <=
std::max(intEpsAbs, intEpsRel * fabs(x)));
}
// Set the parameters to the values of the given CglGMIParam object.
void setParam(const CglGMIParam &source);
// Return the CglGMIParam object of the generator.
inline CglGMIParam getParam() const {return param;}
inline CglGMIParam & getParam() {return param;}
// Compute entries of is_integer.
void computeIsInteger();
void printOptTab(OsiSolverInterface *solver) const;
void setTrackRejection(bool value);
bool getTrackRejection();
int getNumberRejectedCuts(RejectionType reason);
void resetRejectionCounters();
int getNumberGeneratedCuts();
CglGMI();
CglGMI(const CglGMIParam &param);
CglGMI(const CglGMI &);
virtual CglCutGenerator * clone() const;
CglGMI & operator=(const CglGMI& rhs);
virtual ~CglGMI();
virtual std::string generateCpp( FILE * fp);
private:
// Private member methods
// Method generating the cuts after all CglGMI members are properly set.
void generateCuts(OsiCuts & cs);
inline double aboveInteger(double value) const;
inline bool computeCutFractionality(double varRhs, double& cutRhs);
inline double computeCutCoefficient(double rowElem, int index);
inline void eliminateSlack(double cutElem, int cutIndex, double* cut,
double& cutRhs, const double *elements,
const CoinBigIndex *rowStart, const int *indices,
const int *rowLength, const double *rhs);
inline void flip(double& rowElem, int rowIndex);
inline void unflipOrig(double& rowElem, int rowIndex, double& rowRhs);
inline void unflipSlack(double& rowElem, int rowIndex, double& rowRhs,
const double* slack_val);
inline void packRow(double* row, double* rowElem, int* rowIndex,
int& rowNz);
bool cleanCut(double* cutElem, int* cutIndex, int& cutNz,
double& cutRhs, const double* xbar);
bool checkViolation(const double* cutElem, const int* cutIndex,
int cutNz, double cutrhs, const double* xbar);
bool checkDynamism(const double* cutElem, const int* cutIndex,
int cutNz);
bool checkSupport(int cutNz);
bool removeSmallCoefficients(double* cutElem, int* cutIndex,
int& cutNz, double& cutRhs);
void relaxRhs(double& rhs);
bool scaleCut(double* cutElem, int* cutIndex, int cutNz,
double& cutRhs, int scalingType);
bool scaleCutIntegral(double* cutElem, int* cutIndex, int cutNz,
double& cutRhs);
bool nearestRational(double val, double maxdelta, long maxdnom,
long& numerator, long& denominator);
long computeGcd(long a, long b);
void printvecINT(const char *vecstr, const int *x, int n) const;
void printvecDBL(const char *vecstr, const double *x, int n) const;
void printvecDBL(const char *vecstr, const double *elem, const int * index,
int nz) const;
int factorize(CoinFactorization & factorization,
int* colBasisIndex, int* rowBasisIndex);
// Private member data
CglGMIParam param;
int nrow;
int ncol;
const double *colLower;
const double *colUpper;
const double *rowLower;
const double *rowUpper;
const double *rowRhs;
bool *isInteger;
int *cstat;
int *rstat;
OsiSolverInterface *solver;
const double *xlp;
const double *rowActivity;
const CoinPackedMatrix *byRow;
const CoinPackedMatrix *byCol;
double f0;
double f0compl;
double ratiof0compl;
#if defined(TRACK_REJECT) || defined (TRACK_REJECT_SIMPLE)
bool trackRejection;
int fracFail;
int dynFail;
int violFail;
int suppFail;
int smallCoeffFail;
int scaleFail;
int numGeneratedCuts;
#endif
};
//#############################################################################
void CglGMIUnitTest(const OsiSolverInterface * siP,
const std::string mpdDir );
#endif
CglCutGenerator.hpp
CglGMIParam.hpp
CglGMIUnitTest
void CglGMIUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglGMI class.
CglCutGenerator::CglCutGenerator
CglCutGenerator()
Default constructor.
CglGMIParam
Class collecting parameters for the GMI cut generator.
Definition CglGMIParam.hpp:52
CglGMI::clone
virtual CglCutGenerator * clone() const
Clone.
CglGMI::eliminateSlack
void eliminateSlack(double cutElem, int cutIndex, double *cut, double &cutRhs, const double *elements, const CoinBigIndex *rowStart, const int *indices, const int *rowLength, const double *rhs)
Use multiples of the initial inequalities to cancel out the coefficient on a slack variables.
CglGMI::rowLower
const double * rowLower
Lower bounds for constraints.
Definition CglGMI.hpp:297
CglGMI::nrow
int nrow
Number of rows ( = number of slack variables) in the current LP.
Definition CglGMI.hpp:285
CglGMI::getTrackRejection
bool getTrackRejection()
CglGMI::setParam
void setParam(const CglGMIParam &source)
CglGMI::unflipOrig
void unflipOrig(double &rowElem, int rowIndex, double &rowRhs)
Change the sign of the coefficients of the non basic variables at their upper bound and do the transl...
CglGMI::setTrackRejection
void setTrackRejection(bool value)
Set/get tracking of the rejection of cutting planes.
CglGMI::solver
OsiSolverInterface * solver
Pointer on solver. Reset by each call to generateCuts().
Definition CglGMI.hpp:316
CglGMI::printvecINT
void printvecINT(const char *vecstr, const int *x, int n) const
print a vector of integers
CglGMI::checkSupport
bool checkSupport(int cutNz)
Check the support.
CglGMI::computeCutFractionality
bool computeCutFractionality(double varRhs, double &cutRhs)
Compute the fractionalities involved in the cut, and the cut rhs.
CglGMI::colLower
const double * colLower
Lower bounds for structural variables.
Definition CglGMI.hpp:291
CglGMI::getNumberRejectedCuts
int getNumberRejectedCuts(RejectionType reason)
Get number of cuts rejected for given reason; see above.
CglGMI::rowUpper
const double * rowUpper
Upper bounds for constraints.
Definition CglGMI.hpp:300
CglGMI::needsOptimalBasis
virtual bool needsOptimalBasis() const
Return true if needs optimal basis to do cuts (will return true).
Definition CglGMI.hpp:77
CglGMI::colUpper
const double * colUpper
Upper bounds for structural variables.
Definition CglGMI.hpp:294
CglGMI::ratiof0compl
double ratiof0compl
Definition CglGMI.hpp:335
CglGMI::isIntegerValue
bool isIntegerValue(double x, double intEpsAbs=1e-9, double intEpsRel=1e-15)
Definition CglGMI.hpp:97
CglGMI::packRow
void packRow(double *row, double *rowElem, int *rowIndex, int &rowNz)
Pack a row of ncol elements.
CglGMI::areEqual
bool areEqual(double x, double y, double epsAbs=1e-12, double epsRel=1e-12)
Definition CglGMI.hpp:83
CglGMI::getNumberGeneratedCuts
int getNumberGeneratedCuts()
Get total number of generated cuts since last resetRejectionCounters().
CglGMI::isZero
bool isZero(double x, double epsZero=1e-20)
Definition CglGMI.hpp:91
CglGMI::generateCuts
void generateCuts(OsiCuts &cs)
CglGMI::CglGMI
CglGMI()
Default constructor.
CglGMI::printvecDBL
void printvecDBL(const char *vecstr, const double *elem, const int *index, int nz) const
print a vector of doubles: sparse form
CglGMI::param
CglGMIParam param
Object with CglGMIParam members.
Definition CglGMI.hpp:282
CglGMI::aboveInteger
double aboveInteger(double value) const
Compute the fractional part of value, allowing for small error.
CglGMI::CglGMI
CglGMI(const CglGMI &)
Copy constructor.
CglGMI::computeCutCoefficient
double computeCutCoefficient(double rowElem, int index)
Compute the cut coefficient on a given variable.
CglGMI::operator=
CglGMI & operator=(const CglGMI &rhs)
Assignment operator.
CglGMI::checkDynamism
bool checkDynamism(const double *cutElem, const int *cutIndex, int cutNz)
Check the dynamism.
CglGMI::rowRhs
const double * rowRhs
Righ hand side for constraints (upper bound for ranged constraints).
Definition CglGMI.hpp:303
CglGMI::xlp
const double * xlp
Pointer on point to separate. Reset by each call to generateCuts().
Definition CglGMI.hpp:319
CglGMI::CglGMIUnitTest
friend void CglGMIUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglGMI class.
CglGMI::flip
void flip(double &rowElem, int rowIndex)
Change the sign of the coefficients of the non basic variables at their upper bound.
CglGMI::byCol
const CoinPackedMatrix * byCol
Pointer on matrix of coefficient ordered by columns.
Definition CglGMI.hpp:330
CglGMI::computeGcd
long computeGcd(long a, long b)
Compute the greatest common divisor.
CglGMI::factorize
int factorize(CoinFactorization &factorization, int *colBasisIndex, int *rowBasisIndex)
Recompute the simplex tableau for want of a better accuracy.
CglGMI::RejectionType
RejectionType
Public enum: all possible reasons for cut rejection.
Definition CglGMI.hpp:44
CglGMI::failureFractionality
@ failureFractionality
Definition CglGMI.hpp:45
CglGMI::failureDynamism
@ failureDynamism
Definition CglGMI.hpp:46
CglGMI::failureScale
@ failureScale
Definition CglGMI.hpp:49
CglGMI::failureSupport
@ failureSupport
Definition CglGMI.hpp:48
CglGMI::failureViolation
@ failureViolation
Definition CglGMI.hpp:47
CglGMI::computeIsInteger
void computeIsInteger()
CglGMI::scaleCut
bool scaleCut(double *cutElem, int *cutIndex, int cutNz, double &cutRhs, int scalingType)
Scale the cutting plane in different ways; scaling_type possible values: 0 : scale to obtain integral...
CglGMI::cleanCut
bool cleanCut(double *cutElem, int *cutIndex, int &cutNz, double &cutRhs, const double *xbar)
Clean the cutting plane; the cleaning procedure does several things like removing small coefficients,...
CglGMI::generateCpp
virtual std::string generateCpp(FILE *fp)
Create C++ lines to get to current state.
CglGMI::scaleCutIntegral
bool scaleCutIntegral(double *cutElem, int *cutIndex, int cutNz, double &cutRhs)
Scale the cutting plane in order to generate integral coefficients.
CglGMI::printvecDBL
void printvecDBL(const char *vecstr, const double *x, int n) const
print a vector of doubles: dense form
CglGMI::~CglGMI
virtual ~CglGMI()
Destructor.
CglGMI::rstat
int * rstat
Current basis status: rows.
Definition CglGMI.hpp:313
CglGMI::rowActivity
const double * rowActivity
Pointer on row activity. Reset by each call to generateCuts().
Definition CglGMI.hpp:322
CglGMI::CglGMI
CglGMI(const CglGMIParam &param)
Constructor with specified parameters.
CglGMI::removeSmallCoefficients
bool removeSmallCoefficients(double *cutElem, int *cutIndex, int &cutNz, double &cutRhs)
Remove small coefficients and adjust the rhs accordingly.
CglGMI::getParam
CglGMIParam & getParam()
Definition CglGMI.hpp:115
CglGMI::checkViolation
bool checkViolation(const double *cutElem, const int *cutIndex, int cutNz, double cutrhs, const double *xbar)
Cut cleaning procedures: return true if successfull, false if cut should be discarded by the caller o...
CglGMI::nearestRational
bool nearestRational(double val, double maxdelta, long maxdnom, long &numerator, long &denominator)
Compute the nearest rational number; used by scale_row_integral.
CglGMI::unflipSlack
void unflipSlack(double &rowElem, int rowIndex, double &rowRhs, const double *slack_val)
CglGMI::f0compl
double f0compl
Definition CglGMI.hpp:334
CglGMI::cstat
int * cstat
Current basis status: columns.
Definition CglGMI.hpp:310
CglGMI::byRow
const CoinPackedMatrix * byRow
Pointer on matrix of coefficient ordered by rows.
Definition CglGMI.hpp:326
CglGMI::isInteger
bool * isInteger
Characteristic vectors of structural integer variables or continuous variables currently fixed to int...
Definition CglGMI.hpp:307
CglGMI::printOptTab
void printOptTab(OsiSolverInterface *solver) const
Print the current simplex tableau.
CglGMI::resetRejectionCounters
void resetRejectionCounters()
Reset counters for cut rejection tracking; see above.
CglGMI::relaxRhs
void relaxRhs(double &rhs)
Adjust the rhs by relaxing by a small amount (relative or absolute).
CglGMI::getParam
CglGMIParam getParam() const
Definition CglGMI.hpp:114
CglGMI::ncol
int ncol
Number of structural variables in the current LP.
Definition CglGMI.hpp:288
CglGMI::f0
double f0
Fractionality of the cut and related quantities.
Definition CglGMI.hpp:333
CglGMI::generateCuts
virtual void generateCuts(const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo())
Generate Gomory Mixed-Integer cuts for the model of the solver interface si.
CglTreeInfo
Information about where the cut generator is invoked from.
Definition CglTreeInfo.hpp:15
cut
Definition Cgl012cut.hpp:153