Loading...
Searching...
No Matches
CglMixedIntegerRounding.hpp
Go to the documentation of this file.
// LAST EDIT:
//-----------------------------------------------------------------------------
// name: Mixed Integer Rounding Cut Generator
// authors: Joao Goncalves (jog7@lehigh.edu)
// Laszlo Ladanyi (ladanyi@us.ibm.com)
// date: August 11, 2004
//-----------------------------------------------------------------------------
// Copyright (C) 2004, International Business Machines Corporation and others.
// All Rights Reserved.
// This code is published under the Eclipse Public License.
#ifndef CglMixedIntegerRounding_H
#define CglMixedIntegerRounding_H
#include <iostream>
#include <fstream>
//#include <vector>
#include "CoinError.hpp"
#include "CglCutGenerator.hpp"
//=============================================================================
#ifndef CGL_DEBUG
#define CGL_DEBUG 0
#endif
//=============================================================================
// Class to store variable upper bounds (VUB)
class CglMixIntRoundVUB
{
// Variable upper bounds have the form x_j <= a y_j, where x_j is
// a continuous variable and y_j is an integer variable
protected:
int var_; // The index of y_j
double val_; // The value of a
public:
// Default constructor
CglMixIntRoundVUB() : var_(-1), val_(-1) {}
// Copy constructor
CglMixIntRoundVUB(const CglMixIntRoundVUB& source) {
var_ = source.var_;
val_ = source.val_;
}
// Assignment operator
CglMixIntRoundVUB& operator=(const CglMixIntRoundVUB& rhs) {
if (this != &rhs) {
var_ = rhs.var_;
val_ = rhs.val_;
}
return *this;
}
// Destructor
~CglMixIntRoundVUB() {}
// Query and set functions
int getVar() const { return var_; }
double getVal() const { return val_; }
void setVar(const int v) { var_ = v; }
void setVal(const double v) { val_ = v; }
};
//=============================================================================
// Class to store variable lower bounds (VLB).
// It is the same as the class to store variable upper bounds
typedef CglMixIntRoundVUB CglMixIntRoundVLB;
//=============================================================================
// Reference:
// Hugues Marchand and Laurence A. Wolsey
// Aggregation and Mixed Integer Rounding to Solve MIPs
// Operations Research, 49(3), May-June 2001.
// Also published as CORE Dicusion Paper 9839, June 1998.
class CglMixedIntegerRounding : public CglCutGenerator {
friend void CglMixedIntegerRoundingUnitTest(const OsiSolverInterface * siP,
const std::string mpdDir);
private:
//---------------------------------------------------------------------------
// Enumeration constants that describe the various types of rows
enum RowType {
// The row type of this row is NOT defined yet.
ROW_UNDEFINED,
ROW_VARUB,
ROW_VARLB,
ROW_VAREQ,
// The row contains continuous and integer variables;
// the total number of variables is at least 2
ROW_MIX,
// The row contains only continuous variables
ROW_CONT,
// The row contains only integer variables
ROW_INT,
// The row contains other types of rows
ROW_OTHER
};
public:
virtual void generateCuts(const OsiSolverInterface & si, OsiCuts & cs,
const CglTreeInfo info = CglTreeInfo());
//---------------------------------------------------------------------------
CglMixedIntegerRounding ();
CglMixedIntegerRounding (const int maxaggr,
const bool multiply,
const int criterion,
const int preproc = -1);
CglMixedIntegerRounding (
const CglMixedIntegerRounding &);
virtual CglCutGenerator * clone() const;
CglMixedIntegerRounding &
operator=(
const CglMixedIntegerRounding& rhs);
virtual
~CglMixedIntegerRounding ();
virtual void refreshSolver(OsiSolverInterface * solver);
virtual std::string generateCpp( FILE * fp);
//---------------------------------------------------------------------------
inline void setMAXAGGR_ (int maxaggr) {
if (maxaggr > 0) {
MAXAGGR_ = maxaggr;
}
else {
throw CoinError("Unallowable value. maxaggr must be > 0",
"gutsOfConstruct","CglMixedIntegerRounding");
}
}
inline int getMAXAGGR_ () const { return MAXAGGR_; }
inline void setMULTIPLY_ (bool multiply) { MULTIPLY_ = multiply; }
inline bool getMULTIPLY_ () const { return MULTIPLY_; }
inline void setCRITERION_ (int criterion) {
if ((criterion >= 1) && (criterion <= 3)) {
CRITERION_ = criterion;
}
else {
throw CoinError("Unallowable value. criterion must be 1, 2 or 3",
"gutsOfConstruct","CglMixedIntegerRounding");
}
}
inline int getCRITERION_ () const { return CRITERION_; }
void setDoPreproc(int value);
bool getDoPreproc() const;
private:
//--------------------------------------------------------------------------
// Private member methods
// Construct
void gutsOfConstruct (const int maxaggr,
const bool multiply,
const int criterion,
const int preproc);
// Delete
void gutsOfDelete();
// Copy
void gutsOfCopy (const CglMixedIntegerRounding& rhs);
// Do preprocessing.
// It determines the type of each row. It also identifies the variable
// upper bounds and variable lower bounds.
// It may change sense and RHS for ranged rows
void mixIntRoundPreprocess(const OsiSolverInterface& si);
// Determine the type of a given row.
RowType determineRowType(const OsiSolverInterface& si,
const int rowLen, const int* ind,
const double* coef, const char sense,
const double rhs) const;
// Generate MIR cuts
void generateMirCuts( const OsiSolverInterface& si,
const double* xlp,
const double* colUpperBound,
const double* colLowerBound,
const CoinPackedMatrix& matrixByRow,
const double* LHS,
const double* coefByRow,
const int* colInds,
const CoinBigIndex* rowStarts,
const int* rowLengths,
//const CoinPackedMatrix& matrixByCol,
const double* coefByCol,
const int* rowInds,
const CoinBigIndex* colStarts,
const int* colLengths,
OsiCuts& cs ) const;
// Copy row selected to CoinPackedVector
void copyRowSelected( const int iAggregate,
const int rowSelected,
std::set<int>& setRowsAggregated,
int* listRowsAggregated,
double* xlpExtra,
const char sen,
const double rhs,
const double lhs,
const CoinPackedMatrix& matrixByRow,
CoinPackedVector& rowToAggregate,
double& rhsToAggregate) const;
// Select a row to aggregate
bool selectRowToAggregate( const OsiSolverInterface& si,
const CoinPackedVector& rowAggregated,
const double* colUpperBound,
const double* colLowerBound,
const std::set<int>& setRowsAggregated,
const double* xlp, const double* coefByCol,
const int* rowInds, const CoinBigIndex* colStarts,
const int* colLengths,
int& rowSelected,
int& colSelected ) const;
// Aggregation heuristic.
// Combines one or more rows of the original matrix
void aggregateRow( const int colSelected,
CoinPackedVector& rowToAggregate, double rhs,
CoinPackedVector& rowAggregated,
double& rhsAggregated ) const;
// Choose the bound substitution based on the criteria defined by the user
inline bool isLowerSubst(const double inf,
const double aj,
const double xlp,
const double LB,
const double UB) const;
// Bound substitution heuristic
bool boundSubstitution( const OsiSolverInterface& si,
const CoinPackedVector& rowAggregated,
const double* xlp,
const double* xlpExtra,
const double* colUpperBound,
const double* colLowerBound,
CoinPackedVector& mixedKnapsack,
double& rhsMixedKnapsack, double& sStar,
CoinPackedVector& contVariablesInS ) const;
// c-MIR separation heuristic
bool cMirSeparation ( const OsiSolverInterface& si,
const CoinPackedMatrix& matrixByRow,
const CoinPackedVector& rowAggregated,
const int* listRowsAggregated,
const char* sense, const double* RHS,
//const double* coefByRow,
//const int* colInds, const int* rowStarts,
//const int* rowLengths,
const double* xlp, const double sStar,
const double* colUpperBound,
const double* colLowerBound,
const CoinPackedVector& mixedKnapsack,
const double& rhsMixedKnapsack,
const CoinPackedVector& contVariablesInS,
OsiRowCut& flowCut ) const;
// function to create one c-MIR inequality
void cMirInequality( const int numInt,
const double delta,
const double numeratorBeta,
const int *knapsackIndices,
const double* knapsackElements,
const double* xlp,
const double sStar,
const double* colUpperBound,
const std::set<int>& setC,
CoinPackedVector& cMIR,
double& rhscMIR,
double& sCoef,
double& violation) const;
// function to compute G
inline double functionG( const double d, const double f ) const;
// function to print statistics (used only in debug mode)
void printStats(
std::ofstream & fout,
const bool hasCut,
const OsiSolverInterface& si,
const CoinPackedVector& rowAggregated,
const double& rhsAggregated, const double* xlp,
const double* xlpExtra,
const int* listRowsAggregated,
const int* listColsSelected,
const int level,
const double* colUpperBound,
const double* colLowerBound ) const;
private:
//---------------------------------------------------------------------------
// Private member data
// Maximum number of rows to aggregate
int MAXAGGR_;
// Flag that indicates if an aggregated row is also multiplied by -1
bool MULTIPLY_;
// The criterion to use in the bound substitution
int CRITERION_;
// Tolerance used for numerical purposes
double EPSILON_;
int UNDEFINED_;
// If violation of a cut is greater that this number, the cut is accepted
double TOLERANCE_;
int doPreproc_;
// The number of rows of the problem.
int numRows_;
// The number columns of the problem.
int numCols_;
// Indicates whether preprocessing has been done.
bool doneInitPre_;
// The array of CglMixIntRoundVUBs.
CglMixIntRoundVUB* vubs_;
// The array of CglMixIntRoundVLBs.
CglMixIntRoundVLB* vlbs_;
// Array with the row types of the rows in the model.
RowType* rowTypes_;
// The indices of the rows of the initial matrix
int* indRows_;
// The number of rows of type ROW_MIX
int numRowMix_;
// The indices of the rows of type ROW_MIX
int* indRowMix_;
// The number of rows of type ROW_CONT
int numRowCont_;
// The indices of the rows of type ROW_CONT
int* indRowCont_;
// The number of rows of type ROW_INT
int numRowInt_;
// The indices of the rows of type ROW_INT
int* indRowInt_;
// The number of rows of type ROW_CONT that have at least one variable
// with variable upper or lower bound
int numRowContVB_;
// The indices of the rows of type ROW_CONT that have at least one variable
// with variable upper or lower bound
int* indRowContVB_;
// Sense of rows (modified if ranges)
char * sense_;
// RHS of rows (modified if ranges)
double * RHS_;
};
//#############################################################################
// A function that tests the methods in the CglMixedIntegerRounding 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.
void CglMixedIntegerRoundingUnitTest(const OsiSolverInterface * siP,
const std::string mpdDir);
#endif
CglCutGenerator.hpp
CglMixedIntegerRoundingUnitTest
void CglMixedIntegerRoundingUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
CglMixIntRoundVLB
CglMixIntRoundVUB CglMixIntRoundVLB
Definition CglMixedIntegerRounding.hpp:74
CglCutGenerator::CglCutGenerator
CglCutGenerator()
Default constructor.
CglMixIntRoundVUB
Definition CglMixedIntegerRounding.hpp:33
CglMixIntRoundVUB::setVar
void setVar(const int v)
Definition CglMixedIntegerRounding.hpp:66
CglMixIntRoundVUB::val_
double val_
Definition CglMixedIntegerRounding.hpp:39
CglMixIntRoundVUB::setVal
void setVal(const double v)
Definition CglMixedIntegerRounding.hpp:67
CglMixIntRoundVUB::~CglMixIntRoundVUB
~CglMixIntRoundVUB()
Definition CglMixedIntegerRounding.hpp:61
CglMixIntRoundVUB::CglMixIntRoundVUB
CglMixIntRoundVUB()
Definition CglMixedIntegerRounding.hpp:43
CglMixIntRoundVUB::getVar
int getVar() const
Definition CglMixedIntegerRounding.hpp:64
CglMixIntRoundVUB::operator=
CglMixIntRoundVUB & operator=(const CglMixIntRoundVUB &rhs)
Definition CglMixedIntegerRounding.hpp:52
CglMixIntRoundVUB::var_
int var_
Definition CglMixedIntegerRounding.hpp:38
CglMixIntRoundVUB::getVal
double getVal() const
Definition CglMixedIntegerRounding.hpp:65
CglMixIntRoundVUB::CglMixIntRoundVUB
CglMixIntRoundVUB(const CglMixIntRoundVUB &source)
Definition CglMixedIntegerRounding.hpp:46
CglMixedIntegerRounding::doneInitPre_
bool doneInitPre_
Definition CglMixedIntegerRounding.hpp:386
CglMixedIntegerRounding::MAXAGGR_
int MAXAGGR_
Definition CglMixedIntegerRounding.hpp:362
CglMixedIntegerRounding::sense_
char * sense_
Definition CglMixedIntegerRounding.hpp:414
CglMixedIntegerRounding::getDoPreproc
bool getDoPreproc() const
Get doPreproc.
CglMixedIntegerRounding::CglMixedIntegerRounding
CglMixedIntegerRounding()
Default constructor.
CglMixedIntegerRounding::MULTIPLY_
bool MULTIPLY_
Definition CglMixedIntegerRounding.hpp:364
CglMixedIntegerRounding::numRowInt_
int numRowInt_
Definition CglMixedIntegerRounding.hpp:404
CglMixedIntegerRounding::operator=
CglMixedIntegerRounding & operator=(const CglMixedIntegerRounding &rhs)
Assignment operator.
CglMixedIntegerRounding::CglMixedIntegerRoundingUnitTest
friend void CglMixedIntegerRoundingUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
CglMixedIntegerRounding::numRowCont_
int numRowCont_
Definition CglMixedIntegerRounding.hpp:400
CglMixedIntegerRounding::isLowerSubst
bool isLowerSubst(const double inf, const double aj, const double xlp, const double LB, const double UB) const
CglMixedIntegerRounding::numCols_
int numCols_
Definition CglMixedIntegerRounding.hpp:384
CglMixedIntegerRounding::gutsOfConstruct
void gutsOfConstruct(const int maxaggr, const bool multiply, const int criterion, const int preproc)
CglMixedIntegerRounding::UNDEFINED_
int UNDEFINED_
There is no variable upper bound or variable lower bound defined.
Definition CglMixedIntegerRounding.hpp:370
CglMixedIntegerRounding::generateCuts
virtual void generateCuts(const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo())
Generate Mixed Integer Rounding cuts for the model data contained in si.
CglMixedIntegerRounding::printStats
void printStats(std::ofstream &fout, const bool hasCut, const OsiSolverInterface &si, const CoinPackedVector &rowAggregated, const double &rhsAggregated, const double *xlp, const double *xlpExtra, const int *listRowsAggregated, const int *listColsSelected, const int level, const double *colUpperBound, const double *colLowerBound) const
CglMixedIntegerRounding::cMirInequality
void cMirInequality(const int numInt, const double delta, const double numeratorBeta, const int *knapsackIndices, const double *knapsackElements, const double *xlp, const double sStar, const double *colUpperBound, const std::set< int > &setC, CoinPackedVector &cMIR, double &rhscMIR, double &sCoef, double &violation) const
CglMixedIntegerRounding::CglMixedIntegerRounding
CglMixedIntegerRounding(const int maxaggr, const bool multiply, const int criterion, const int preproc=-1)
Alternate Constructor.
CglMixedIntegerRounding::doPreproc_
int doPreproc_
Controls the preprocessing of the matrix to identify rows suitable for cut generation.
Definition CglMixedIntegerRounding.hpp:380
CglMixedIntegerRounding::setMULTIPLY_
void setMULTIPLY_(bool multiply)
Set MULTIPLY_.
Definition CglMixedIntegerRounding.hpp:184
CglMixedIntegerRounding::cMirSeparation
bool cMirSeparation(const OsiSolverInterface &si, const CoinPackedMatrix &matrixByRow, const CoinPackedVector &rowAggregated, const int *listRowsAggregated, const char *sense, const double *RHS, const double *xlp, const double sStar, const double *colUpperBound, const double *colLowerBound, const CoinPackedVector &mixedKnapsack, const double &rhsMixedKnapsack, const CoinPackedVector &contVariablesInS, OsiRowCut &flowCut) const
CglMixedIntegerRounding::indRowInt_
int * indRowInt_
Definition CglMixedIntegerRounding.hpp:406
CglMixedIntegerRounding::indRowMix_
int * indRowMix_
Definition CglMixedIntegerRounding.hpp:398
CglMixedIntegerRounding::setMAXAGGR_
void setMAXAGGR_(int maxaggr)
Set MAXAGGR_.
Definition CglMixedIntegerRounding.hpp:170
CglMixedIntegerRounding::setDoPreproc
void setDoPreproc(int value)
Set doPreproc.
CglMixedIntegerRounding::RowType
RowType
Definition CglMixedIntegerRounding.hpp:95
CglMixedIntegerRounding::ROW_VARUB
@ ROW_VARUB
After the row is flipped to 'L', the row has exactly two variables: one is negative binary and the ot...
Definition CglMixedIntegerRounding.hpp:101
CglMixedIntegerRounding::ROW_VAREQ
@ ROW_VAREQ
The row sense is 'E', the row has exactly two variables: one is binary and the other is a continous,...
Definition CglMixedIntegerRounding.hpp:108
CglMixedIntegerRounding::ROW_CONT
@ ROW_CONT
Definition CglMixedIntegerRounding.hpp:113
CglMixedIntegerRounding::ROW_OTHER
@ ROW_OTHER
Definition CglMixedIntegerRounding.hpp:117
CglMixedIntegerRounding::ROW_VARLB
@ ROW_VARLB
After the row is flipped to 'L', the row has exactly two variables: one is positive binary and the ot...
Definition CglMixedIntegerRounding.hpp:105
CglMixedIntegerRounding::ROW_INT
@ ROW_INT
Definition CglMixedIntegerRounding.hpp:115
CglMixedIntegerRounding::ROW_UNDEFINED
@ ROW_UNDEFINED
Definition CglMixedIntegerRounding.hpp:97
CglMixedIntegerRounding::ROW_MIX
@ ROW_MIX
Definition CglMixedIntegerRounding.hpp:111
CglMixedIntegerRounding::generateCpp
virtual std::string generateCpp(FILE *fp)
Create C++ lines to get to current state.
CglMixedIntegerRounding::indRows_
int * indRows_
Definition CglMixedIntegerRounding.hpp:394
CglMixedIntegerRounding::TOLERANCE_
double TOLERANCE_
Definition CglMixedIntegerRounding.hpp:372
CglMixedIntegerRounding::clone
virtual CglCutGenerator * clone() const
Clone.
CglMixedIntegerRounding::CRITERION_
int CRITERION_
Definition CglMixedIntegerRounding.hpp:366
CglMixedIntegerRounding::getMULTIPLY_
bool getMULTIPLY_() const
Get MULTIPLY_.
Definition CglMixedIntegerRounding.hpp:187
CglMixedIntegerRounding::refreshSolver
virtual void refreshSolver(OsiSolverInterface *solver)
This can be used to refresh any inforamtion.
CglMixedIntegerRounding::numRowContVB_
int numRowContVB_
Definition CglMixedIntegerRounding.hpp:409
CglMixedIntegerRounding::getMAXAGGR_
int getMAXAGGR_() const
Get MAXAGGR_.
Definition CglMixedIntegerRounding.hpp:181
CglMixedIntegerRounding::gutsOfDelete
void gutsOfDelete()
CglMixedIntegerRounding::gutsOfCopy
void gutsOfCopy(const CglMixedIntegerRounding &rhs)
CglMixedIntegerRounding::getCRITERION_
int getCRITERION_() const
Get CRITERION_.
Definition CglMixedIntegerRounding.hpp:201
CglMixedIntegerRounding::boundSubstitution
bool boundSubstitution(const OsiSolverInterface &si, const CoinPackedVector &rowAggregated, const double *xlp, const double *xlpExtra, const double *colUpperBound, const double *colLowerBound, CoinPackedVector &mixedKnapsack, double &rhsMixedKnapsack, double &sStar, CoinPackedVector &contVariablesInS) const
CglMixedIntegerRounding::numRowMix_
int numRowMix_
Definition CglMixedIntegerRounding.hpp:396
CglMixedIntegerRounding::RHS_
double * RHS_
Definition CglMixedIntegerRounding.hpp:416
CglMixedIntegerRounding::functionG
double functionG(const double d, const double f) const
CglMixedIntegerRounding::mixIntRoundPreprocess
void mixIntRoundPreprocess(const OsiSolverInterface &si)
CglMixedIntegerRounding::aggregateRow
void aggregateRow(const int colSelected, CoinPackedVector &rowToAggregate, double rhs, CoinPackedVector &rowAggregated, double &rhsAggregated) const
CglMixedIntegerRounding::EPSILON_
double EPSILON_
Definition CglMixedIntegerRounding.hpp:368
CglMixedIntegerRounding::selectRowToAggregate
bool selectRowToAggregate(const OsiSolverInterface &si, const CoinPackedVector &rowAggregated, const double *colUpperBound, const double *colLowerBound, const std::set< int > &setRowsAggregated, const double *xlp, const double *coefByCol, const int *rowInds, const CoinBigIndex *colStarts, const int *colLengths, int &rowSelected, int &colSelected) const
CglMixedIntegerRounding::copyRowSelected
void copyRowSelected(const int iAggregate, const int rowSelected, std::set< int > &setRowsAggregated, int *listRowsAggregated, double *xlpExtra, const char sen, const double rhs, const double lhs, const CoinPackedMatrix &matrixByRow, CoinPackedVector &rowToAggregate, double &rhsToAggregate) const
CglMixedIntegerRounding::generateMirCuts
void generateMirCuts(const OsiSolverInterface &si, const double *xlp, const double *colUpperBound, const double *colLowerBound, const CoinPackedMatrix &matrixByRow, const double *LHS, const double *coefByRow, const int *colInds, const CoinBigIndex *rowStarts, const int *rowLengths, const double *coefByCol, const int *rowInds, const CoinBigIndex *colStarts, const int *colLengths, OsiCuts &cs) const
CglMixedIntegerRounding::indRowContVB_
int * indRowContVB_
Definition CglMixedIntegerRounding.hpp:412
CglMixedIntegerRounding::rowTypes_
RowType * rowTypes_
Definition CglMixedIntegerRounding.hpp:392
CglMixedIntegerRounding::setCRITERION_
void setCRITERION_(int criterion)
Set CRITERION_.
Definition CglMixedIntegerRounding.hpp:190
CglMixedIntegerRounding::indRowCont_
int * indRowCont_
Definition CglMixedIntegerRounding.hpp:402
CglMixedIntegerRounding::numRows_
int numRows_
Definition CglMixedIntegerRounding.hpp:382
CglMixedIntegerRounding::vlbs_
CglMixIntRoundVLB * vlbs_
Definition CglMixedIntegerRounding.hpp:390
CglMixedIntegerRounding::~CglMixedIntegerRounding
virtual ~CglMixedIntegerRounding()
Destructor.
CglMixedIntegerRounding::vubs_
CglMixIntRoundVUB * vubs_
Definition CglMixedIntegerRounding.hpp:388
CglMixedIntegerRounding::CglMixedIntegerRounding
CglMixedIntegerRounding(const CglMixedIntegerRounding &)
Copy constructor.
CglMixedIntegerRounding::determineRowType
RowType determineRowType(const OsiSolverInterface &si, const int rowLen, const int *ind, const double *coef, const char sense, const double rhs) const
CglTreeInfo
Information about where the cut generator is invoked from.
Definition CglTreeInfo.hpp:15