/home/coin/SVN-release/CoinAll-1.1.0/Cgl/src/CglLandP/CglLandPSimplex.hpp

Go to the documentation of this file.

// Copyright (C) 2005, Pierre Bonami and others.  All Rights Reserved.
// Author:   Pierre Bonami                                                  
//           Tepper School of Business
//           Carnegie Mellon University, Pittsburgh, PA 15213
// Date:     21/07/05
//---------------------------------------------------------------------------
#ifndef CglLandPSimplex_H
#define CglLandPSimplex_H

#include <iostream>

#include "CglLandP.hpp"

#include "OsiSolverInterface.hpp"
#include "CoinMessage.hpp"
#include "CoinMessageHandler.hpp"
#include "CoinWarmStartBasis.hpp"
#include "CoinPackedMatrix.hpp"
namespace LAP {
enum LAPS_messages
{
  Separating,
  FoundImprovingRow,
  FoundBestImprovingCol,
  WarnFailedBestImprovingCol,
  LogHead,
  PivotLog,
  FinishedOptimal,
  HitLimit,
  WarnBadSigmaComputation,
  WarnBadRowComputation,
  WarnGiveUpRow,
  PivotFailedSigmaUnchanged,
  PivotFailedSigmaIncreased,
  FailedSigmaIncreased,
  WarnBadRhsComputation,
  WarnFailedPivotTol,
  WarnFailedPivotIIf,
  DUMMY_END
};
class LandPMessages : public CoinMessages
{
public:

  LandPMessages();
};



class CglLandPSimplex
{
public:
    struct TabRow
  {
    TabRow():num(-1), row(NULL), rhs(0), n_(0) {}
    TabRow(const TabRow & source):num(source.num), row(NULL), rhs(source.rhs), n_(source.n_)
    {
      row = new double[n_];
      CoinCopyN(source.row, n_, row);
    }
    void size(int n){if(row != NULL) delete [] row; row = new double[n]; n_=n;}
    ~TabRow(){
      if (row != NULL)
        delete [] row;
    }
    void print(std::ostream & os, int width = 9, const int * nonBasics = NULL,
 int m = 0)
    {
      os.width(3);
      os.precision(4);
      os.setf(std::ios_base::right, std::ios_base::adjustfield);
      os<< num <<": ";
      for(int j = 0 ; j < m ; j++)
        {
          os.width(width);
          os.precision(3);
          //      os.setf(std::ios_base::fixed, std::ios_base::floatfield);
          os.setf(std::ios_base::right, std::ios_base::adjustfield);
          os<<row[nonBasics[j]]<<" ";
        }
      
      os.width(width);
      os.precision(4);
      //    os.setf(std::ios_base::fixed, std::ios_base::floatfield);
      os.setf(std::ios_base::right, std::ios_base::adjustfield);
      os<<rhs;
      
      os<<std::endl;

    }
    int num;
    double *row;
    double rhs;
    int n_;
  };
  CglLandPSimplex(const OsiSolverInterface &si, 
                  const CglLandP::CachedData &cached,
                  bool reducedSpace, int numPivots);
  ~CglLandPSimplex();
  void cacheUpdate(const CglLandP::CachedData &cached, bool reducedSpace = 0);
  bool resetSolver(const CoinWarmStartBasis * basis);
  bool findBestCut(int var, OsiRowCut & cut, const CglLandP::CachedData &cached, const CglLandP::Parameters & params);
  bool generateMig(int row, OsiRowCut &cut, const CglLandP::CachedData &cached, const CglLandP::Parameters & params) const;
  
  CglLandPSimplex()
#ifdef LandP_DEBUG
    :debug_(0,0)
#endif
  {
    std::cerr<<"Class CglLandPSimplex has no default constructor"<<std::endl;
    throw CoinError("No default constructor","CglLandPSimplex","CglLandPSimplex()");
  }
    void setLogLevel(int level)
  { handler_->setLogLevel(level);}


  void setSi(OsiSolverInterface *si)
  {si_ = si;}
  void freeSi()
  {delete si_;}

  struct extraInfo {
    extraInfo():
#if LandP_DEBUG > 1
      Nnz(0), Nneg(0),
#endif
      AngleToObj(0),
      numPivots(0), depth(0.),
      nNegativeRcRows(0), bestRow(0),
      maxBestRow(0), bestRc(0.),
      maxRc(-DBL_MAX)
    {}
#if LandP_DEBUG > 1
    int Nnz;
    int Nneg;
#endif
    double AngleToObj;
    int numPivots;
    double depth;
    int nNegativeRcRows;
    int bestRow;
    int maxBestRow;
    double bestRc;
    double maxRc;
  };
  mutable extraInfo extra;

protected:
  bool changeBasis(int incoming, int leaving, int direction);
  int findCutImprovingPivotRow( int &direction, int &gammaSign, double tolerance);
  int fastFindCutImprovingPivotRow( int &direction, int &gammaSign, double tolerance);
  int rescanReducedCosts( int &direction, int &gammaSign, double tolerance);
  int fastFindBestPivotColumn(int direction, int gammaSign,
                          double pivotTol, double rhsTol, 
                          bool reducedSpace,  
                          bool allowNonImproving, 
                          double &bestSigma);
  int findBestPivotColumn(int direction, 
                          double pivotTol, bool reducedSpace, bool allowDegeneratePivot,
                          bool modularize);
#if 0
int plotCGLPobj(int direction, double gammaTolerance,
                double pivotTol, bool reducedSpace, bool allowDegenerate, bool modularize);
#endif

  int findBestPivot(int &leaving, int & direction, 
                    const CglLandP::Parameters & params);
  double computeCglpObjective(double gamma, bool strengthen);
  double computeCglpObjective(TabRow & row) const;
   inline double intersectionCutCoef(double alpha_i, double beta) const;
  inline double strengthenedIntersectionCutCoef(int i, double alpha_i, double beta) const;
  inline double newRowCoefficient(int j, double gamma) const;
  inline double modularizedCoef(double alpha, double beta) const;
  double computeCglpRedCost(int direction, int gammaSign);
  void computeRedCostConstantsInRow();
  void createIntersectionCut(const TabRow & row, OsiRowCut &cut) const;
        //  void createIntersectionCut(double * row);
  void createMIG( TabRow & row, OsiRowCut &cut) const;
  double normCoef(TabRow &row);
  void scale(OsiRowCut &cut, double norma);
  void scale(OsiRowCut &cut);
  void modularizeRow(TabRow & row);
  void pullTableauRow(TabRow & row) const;
  void adjustTableauRow(int var, TabRow & row, int direction);
  void resetOriginalTableauRow(int var, TabRow & row, int direction);
  inline double getLoBound(int index){return loBounds_[index];}
  inline double getUpBound(int index){return upBounds_[index];}
  void printTableau(std::ostream & os);
private:

  enum lpSolver {clp, cplex, xpress};
  lpSolver solver_;
  void updateM1_M2_M3(TabRow & row, double tolerance, bool recucedSpace, bool alwaysComputeCheap);


  mutable CglLandPSimplex::TabRow row_k_;
  CglLandPSimplex::TabRow perturbed_row_k_;
  CglLandPSimplex::TabRow row_i_;
  CglLandPSimplex::TabRow newRow_;
  CoinPackedVector gammas_;
  double * rWk1_;
  double * rWk2_;
  double * rWk3_;
  double * rWk4_;
  int * rIntWork_;
  bool * rowFlags_;
  bool *colHasToComputeContrib_;
  bool *colCandidateToLeave_;
  int * basics_;
  int * nonBasics_;
  int * inM1_;
  int * inM2_;
  int * inM3_;
  double tau_;
  double sigma_;
  CoinWarmStartBasis basis_;
   double * colsolToCut_;
   double * colsol_;
  int numcols_;
  int numrows_;
  // for fast access to lower bounds (both cols and rows)
  double * loBounds_;
  // for fast access to upper bounds (both cols and rows)
  double * upBounds_;
  bool inDegenerateSequence_;
  double chosenReducedCostVal_;
  const bool * integers_;

  OsiSolverInterface * si_;
  bool own_;


  int nNegativeRc_;
  int nNegativeRcRows_; 
#ifdef LandP_DEBUG

#if LandP_DEBUG > 1

void put_in_non_basic_init_space( OsiRowCut &cut);
#endif
  friend class DebugData;
  class DebugData
  {
  public:
    DebugData(int n, int m):
      bestNewRow_(NULL),
      req(1e-05),
      eq(1e-5)
#if LandP+DEBUG> 1
      , initialTableau_(), initialBasics_(NULL), initialBasis_(NULL)
#endif
      
    { 
      bestNewRow_ = new double[n + m];
#if LandP_DEBUG > 1
      initialBasics_ = new int[m];
      initialNonBasics_ = new int[n];
      initialColsol_ = new double[n + m];
      trueInitialSol_ = new double[n + m];
#endif
    }
    ~DebugData()
    {
      delete [] bestNewRow_;
#if LandP_DEBUG > 1
      delete [] initialBasics_;
      delete [] initialNonBasics_;
      delete [] initialColsol_;
      delete [] trueInitialSol_;
      if(initialBasis_)
        delete initialBasis_;
#endif
    }
    double * bestNewRow_;
    double bestNewRhs_;
    double newSigma_;
    CoinRelFltEq req;
    CoinAbsFltEq eq;

#if LandP_DEBUG > 1

    void getCurrentTableau(OsiSolverInterface &si, CglLandPSimplex &lap);
    CoinPackedMatrix initialTableau_;
    int * initialBasics_;
    int *initialNonBasics_;
    CoinWarmStartBasis * initialBasis_;
    double * initialColsol_;
    double * trueInitialSol_;
#endif
  };
  DebugData debug_;
#endif

  CoinMessageHandler * handler_;

  CoinMessages messages_;
};

double 
CglLandPSimplex::intersectionCutCoef(double alpha_i, double beta) const
{
  if(alpha_i>0) return alpha_i* (1 - beta);
  else return -alpha_i * beta;// (1 - beta);
}

double 
CglLandPSimplex::strengthenedIntersectionCutCoef(int i, double alpha_i, double beta) const
{
  //  double ratio = beta/(1-beta);
  if( (!integers_[i]))
    return intersectionCutCoef(alpha_i, beta);
  else
  {
    double f_i = alpha_i - floor(alpha_i);
    if(f_i < beta)
      return f_i*(1- beta);
    else
      return (1 - f_i)*beta;//(1-beta);
  }
}

double 
CglLandPSimplex::newRowCoefficient(int j, double gamma) const
{
  return row_k_.row[j] + gamma * row_i_.row[j];
}

double 
CglLandPSimplex::modularizedCoef(double alpha, double beta) const
{
  double f_i = alpha - floor(alpha);
  if(f_i <= beta)
    return f_i;
  else
    return f_i - 1;
}




}
#endif

---