diff options
Diffstat (limited to 'build/Bonmin/include/coin/CglMixedIntegerRounding.hpp')
| -rw-r--r-- | build/Bonmin/include/coin/CglMixedIntegerRounding.hpp | 429 |
1 files changed, 0 insertions, 429 deletions
diff --git a/build/Bonmin/include/coin/CglMixedIntegerRounding.hpp b/build/Bonmin/include/coin/CglMixedIntegerRounding.hpp deleted file mode 100644 index 10580cb..0000000 --- a/build/Bonmin/include/coin/CglMixedIntegerRounding.hpp +++ /dev/null @@ -1,429 +0,0 @@ -// 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 |