// 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;
//=============================================================================
/** Mixed Integer Rounding Cut Generator Class */
// 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,
/** After the row is flipped to 'L', the row has exactly two variables:
one is negative binary and the other is a continous,
and the RHS is zero.*/
ROW_VARUB,
/** After the row is flipped to 'L', the row has exactly two variables:
one is positive binary and the other is a continous,
and the RHS is zero.*/
ROW_VARLB,
/** The row sense is 'E', the row has exactly two variables:
one is binary and the other is a continous, and the RHS is zero.*/
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:
/**@name Generate Cuts */
//@{
/** Generate Mixed Integer Rounding cuts for the model data
contained in si. The generated cuts are inserted
in the collection of cuts cs.
*/
virtual void generateCuts(const OsiSolverInterface & si, OsiCuts & cs,
const CglTreeInfo info = CglTreeInfo());
//@}
//---------------------------------------------------------------------------
/**@name Constructors and destructors */
//@{
/// Default constructor
CglMixedIntegerRounding ();
/// Alternate Constructor
CglMixedIntegerRounding (const int maxaggr,
const bool multiply,
const int criterion,
const int preproc = -1);
/// Copy constructor
CglMixedIntegerRounding (
const CglMixedIntegerRounding &);
/// Clone
virtual CglCutGenerator * clone() const;
/// Assignment operator
CglMixedIntegerRounding &
operator=(
const CglMixedIntegerRounding& rhs);
/// Destructor
virtual
~CglMixedIntegerRounding ();
/// This can be used to refresh any inforamtion
virtual void refreshSolver(OsiSolverInterface * solver);
/// Create C++ lines to get to current state
virtual std::string generateCpp( FILE * fp);
//@}
//---------------------------------------------------------------------------
/**@name Set and get methods */
//@{
/// Set MAXAGGR_
inline void setMAXAGGR_ (int maxaggr) {
if (maxaggr > 0) {
MAXAGGR_ = maxaggr;
}
else {
throw CoinError("Unallowable value. maxaggr must be > 0",
"gutsOfConstruct","CglMixedIntegerRounding");
}
}
/// Get MAXAGGR_
inline int getMAXAGGR_ () const { return MAXAGGR_; }
/// Set MULTIPLY_
inline void setMULTIPLY_ (bool multiply) { MULTIPLY_ = multiply; }
/// Get MULTIPLY_
inline bool getMULTIPLY_ () const { return MULTIPLY_; }
/// Set CRITERION_
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");
}
}
/// Get CRITERION_
inline int getCRITERION_ () const { return CRITERION_; }
/// Set doPreproc
void setDoPreproc(int value);
/// Get doPreproc
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 int* rowStarts,
const int* rowLengths,
//const CoinPackedMatrix& matrixByCol,
const double* coefByCol,
const int* rowInds,
const int* 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 int* 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_;
/// There is no variable upper bound or variable lower bound defined
int UNDEFINED_;
// If violation of a cut is greater that this number, the cut is accepted
double TOLERANCE_;
/** Controls the preprocessing of the matrix to identify rows suitable for
cut generation.<UL>
<LI> -1: preprocess according to solver settings;
<LI> 0: Do preprocessing only if it has not yet been done;
<LI> 1: Do preprocessing.
</UL>
Default value: -1 **/
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