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