CutPlane.h

Go to the documentation of this file.

/*--------------------------------------------------------------------------*/
/*---------------------------- File CutPlane.h -----------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/
 
#ifndef __CutPlane
 #define __CutPlane  /* self-identification: #endif at the end of the file */
 
/*--------------------------------------------------------------------------*/
/*-------------------------------- MACROS ----------------------------------*/
/*--------------------------------------------------------------------------*/
 
/*--------------------------------------------------------------------------*/
/*------------------------------ INCLUDES ----------------------------------*/
/*--------------------------------------------------------------------------*/
 
#include "NDOSlver.h"
 
#include "OsiSolverInterface.hpp"
 
/*--------------------------------------------------------------------------*/
/*----------------------------- NAMESPACE ----------------------------------*/
/*--------------------------------------------------------------------------*/
 
namespace NDO_di_unipi_it
{
 
/*--------------------------------------------------------------------------*/
/*--------------------------- CLASS CutPlane -------------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------- GENERAL NOTES --------------------------------*/
/*--------------------------------------------------------------------------*/
class CutPlane : public NDOSolver
{
 
/*--------------------------------------------------------------------------*/
/*----------------------- PUBLIC PART OF THE CLASS -------------------------*/
/*--------------------------------------------------------------------------*/
 
 public:
 
/*--------------------------------------------------------------------------*/
/*--------------------------- PUBLIC METHODS -------------------------------*/
/*--------------------------------------------------------------------------*/
/*---------------------------- CONSTRUCTOR ---------------------------------*/
/*--------------------------------------------------------------------------*/
  CutPlane( std::istream *iStrm = 0 );
 
/*-------------------------- OTHER INITIALIZATIONS -------------------------*/
/*--------------------------------------------------------------------------*/
   void SetOsiSolver( OsiSolverInterface* osi = 0 );
 
 
/*--------------------------------------------------------------------------*/
 
   void SetRadius( LMNum rad = Inf< LMNum >() );
 
/*--------------------------------------------------------------------------*/
 
   void SetFiOracle( FiOracle *Fi = 0 );
 
/*--------------------------------------------------------------------------*/
 
   void SetLambda( cLMRow tLambda = 0 );
 
/*--------------------------------------------------------------------------*/
 
   void KeepBestLambda( const bool KBL = true );
 
/*--------------------------------------------------------------------------*/
 
   void SetNDOLog( ostream *outs = 0 , const char lvl = 0 );
 
/*-------------------- METHODS FOR SOLVING THE PROBLEM ---------------------*/
/*--------------------------------------------------------------------------*/
   NDOStatus Solve( void );
 
/*--------------------------------------------------------------------------*/
 
 
/*---------------------- METHODS FOR READING RESULTS -----------------------*/
/*--------------------------------------------------------------------------*/
 
   cLMRow ReadSol( cIndex_Set &I , Index &D );
 
/*--------------------------------------------------------------------------*/
 
   cLMRow ReadBestSol( cIndex_Set &I , Index &D );
 
/*--------------------------------------------------------------------------*/
      
   HpNum ReadFiVal( cIndex wFi = Inf< Index >() );
 
/*--------------------------------------------------------------------------*/
 
   HpNum ReadBestFiVal( cIndex wFi = Inf< Index >() );
 
/*--------------------------------------------------------------------------*/
   
   bool IsOptimal( HpNum eps = 0 ) const;
  
/*--------------------------------------------------------------------------*/
 
  cHpRow ReadMult( cIndex_Set &I , Index &D , cIndex wFi = Inf< Index >() );
  
/*--------------------------------------------------------------------------*/
 
   HpNum ReadLBMult( cIndex wFi = Inf< Index >() );
 
/*-------------- METHODS FOR READING THE DATA OF THE PROBLEM ---------------*/
/*--------------------------------------------------------------------------*/
/*------------- METHODS FOR ADDING / REMOVING / CHANGING DATA --------------*/
/*--------------------------------------------------------------------------*/
   void AddVariables( Index NNwVrs , cLMRow IVs = 0 );
 
/*--------------------------------------------------------------------------*/
 
   void RemoveVariables( cIndex_Set whch = 0 , Index hwmny = 0 );
 
/*--------------------------------------------------------------------------*/
 
   void ChgFiV( cIndex wFi = Inf< Index >() )
   {
    throw NDOException( "CutPlane::ChgFiV not implemented yet" );
    }
 
/*--------------------------------------------------------------------------*/
 
   void ChgSbG( cIndex strt = 0 , Index stp = Inf< Index >() ,
        cIndex wFi = Inf< Index >() )
   {
    throw NDOException( "CutPlane::ChgSbG not implemented yet" );
    }
 
/*------------------------------ DESTRUCTOR --------------------------------*/
/*--------------------------------------------------------------------------*/
   virtual ~CutPlane();
 
 
/*-------------------- PROTECTED PART OF THE CLASS -------------------------*/
/*--------------------------------------------------------------------------*/
 
 protected:
 
/*--------------------------------------------------------------------------*/
/*---------------------- PROTECTED PART OF THE CLASS -----------------------*/
/*--------------------------------------------------------------------------*/
/*-------------------------- PROTECTED METHODS -----------------------------*/
/*--------------------------------------------------------------------------*/
 
/*--------------------------------------------------------------------------*/
/*----------------------- PROTECTED DATA STRUCTURES  -----------------------*/
/*--------------------------------------------------------------------------*/
 
 
 private:
 
/*--------------------------------------------------------------------------*/
/*--------------------- PRIVATE PART OF THE CLASS --------------------------*/
/*--------------------------------------------------------------------------*/
/*-------------------------- PRIVATE METHODS -------------------------------*/
/*--------------------------------------------------------------------------*/
 
   inline void FiAndGi( void );
 
/* Solve Fi subproblem and retrieve corresponding subgradients.
   The Fi problem is solved with the last Lambda found and if some
   solution is atractive, corresponding sugradients is retrieved and
   a new line is added in the RMP. The number of lines added depends
   of the number of subproblems in the Oracle. */
 
/*--------------------------------------------------------------------------*/
 
   inline Index DelRMPRows( HpNum lim );
 
// Delete RMP rows with slacks greater than lim.
 
/*--------------------------------------------------------------------------*/
 
   inline void OutRsts( void );
 
// Function to output results when LOG >=1.
 
/*--------------------------------------------------------------------------*/
 
   inline void MemDealloc( void );
 
// Function to free the allocated arrays. 
 
/*--------------------------------------------------------------------------*/
/*----------------------- PRIVATE DATA STRUCTURES  -------------------------*/
/*--------------------------------------------------------------------------*/
 
   // algorithmic parameters- - - - - - - - - - - - - - - - - - - - - - - - -
 
   Index NumNames;     // number of items (re)allocated each time
 
   HpNum PurgeRows;    // purge (delete) rows options
   Index PurgeInvl;    // how often the purge rows is done.
 
   Index HeurSubGU;    /* number of subgradients asked to the FiOracle
              (every iteration) when the restricted master
              problem is artificially feasible */
   Index HeurSubGF;    /* number of subgradients asked to the FiOracle
              (every HeurInvl - next parameter) when the
              restricted master problem is feasible */
   Index HeurInvl;     /* how often "extra" subgradients are asked by the
              CutPlane (when the restricted master problem is
              feasible) */
 
   Index KpPrimals;    // if == 0, do not care for primal information
 
   Index PrintInvl;    // how often do we print log information
 
   // other stuff - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
 
   Index MaxNumVar;
   LMRow Lambda;           // The current point
   LMRow BestLambda;       // The best point found so far
   Index_Set Base;         // Vector of the indices of nonzeroes in Lambda
   Index BaseSize;         // Size of Base
   bool KpBstL;            // If LmbdBst has to be kept
   HpRow FiLambda;         // Fi( Lambda ) of each component of Fi
   HpRow BestFiLambda;     // Fi( BestLambda ) of each component of Fi
   HpNum AFiLambda;        // Value of Fi( Lambda )
   HpNum ABestFiLambda;    // Best value of Fi found so far.
   SgRow Gi;               // SubGradient returned by the FiOracle
 
   OsiSolverInterface *OsiS;  // Instance of OsiSolverInterface.
 
   HpNum AValueRMP;        // Value of the approximation of Fi in the RMP
   HpRow ValueRMP;         // Optimal values of the RMP, for each component
   Index RowsAdded;        // Rows added to the RMP in the current iteration
   Index MaxNRows;         // Maximum number of rows of the RMP.
   HpNum Gap;              // Gap between FiLambda and ValueRMP
   HpNum LowerBound;       // Lower Bound over Fi
   bool TrueLB;            // true if LowerBound is a "true" lower bound
               // rather than just the "minus infinity"
   bool loptimal;          // true if the solution found is optimal to the
               // current master problem. When adding of
               // variables is being used, note that the solution
               // may not be optimal to the full problem.
 
   // oracle solutions management related - - - - - - - - - - - - - - - - - -
   // CutPlane is responsible to give a name to each of the primal solutions
   // on which the subgradients are calculated. it is for him to "know" which
   // names are being used and which are not. the following structures are
   // relative to that management of names. also, each name that is being
   // used has a corresponding row in the RMP. the primal solution
   // associated with row i is kept in FullNames[ i ]
 
   Index_Set EmptyNames;   // Vector of Empty Gi names.
   Index_Set FullNames;    // Vector of Full Gi names.
   Index_Set SubPNames;    // Vector with Fi-components of subgradients
 
   SIndex LastFull;        // Pointer to the last Full name.
   Index FirstEmpty;       // Pointer to the first Empty name.
   Index AllocNumber;      // Number of allocations to RowNames.
 
/*--------------------------------------------------------------------------*/
 
 };  // end( class CutPlane )
 
/*--------------------------------------------------------------------------*/
/*------------------- inline methods implementation ------------------------*/
/*--------------------------------------------------------------------------*/
 
/*--------------------------------------------------------------------------*/
 
};  //end( namespace( NDO_di_unipi_it ) )
 
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
 
#endif  /* CutPlane.h included */
 
/*--------------------------------------------------------------------------*/
/*------------------------ End File CutPlane.h -----------------------------*/
/*--------------------------------------------------------------------------*/