root/pico/stable/1.3/src/milp/pico/lpBasedHeuristic.h

/*  _________________________________________________________________________
 *
 *  Acro: A Common Repository for Optimizers
 *  Copyright (c) 2008 Sandia Corporation.
 *  This software is distributed under the BSD License.
 *  Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
 *  the U.S. Government retains certain rights in this software.
 *  For more information, see the README.txt file in the top Acro directory.
 *  _________________________________________________________________________
 */

/**
 * \file lpBasedHeuristic.h
 *
 * Defines the pico::lpBasedHeuristic class.
 */


/// This is a base class for all heuristics that start from
/// LP-feasible but integer-infeasible solutions.


#ifndef pico_lpBasedHeuristic_h
#define pico_lpBasedHeuristic_h


#include <acro_config.h>
#include <utilib/CommonIO.h>
#include <pico/PicoLPInterface.h>
#include <pico/PicoLPSolver.h>
#include <CoinPackedVector.hpp>
#include <CoinShallowPackedVector.hpp>
#include <pebbl/pebblBase.h>
#include <pebbl/gRandom.h>
#include <pico/lpSetupObj.h>

#ifdef ACRO_HAVE_MPI
#include <utilib/Basic2DArray.h>
#include <pebbl/parBranching.h>
#else
#include <pebbl/branching.h>
#endif

namespace pico {

  using namespace utilib;
  using namespace pebbl;
  using std::min;

  // Forward declaration of needed classes

  class MILP;
  class MILPProblem;
  class MILPNode;
  class MILPSolution;
#ifdef ACRO_HAVE_MPI
  class parMILP;
#endif


  /// Tiny class to help heuristics share LP interfaces

  class lpShareObj
    {
    public:

      PicoLPSolver     lpOwner;
      PicoLPInterface* lp;

      int timesShared;
      int seqNum;

      double originalObjConst;

#ifdef ACRO_HAVE_MPI
      int psSize;   // If we might presplit, also store grouping parameters
      int psDepth;
#endif

      lpShareObj() :
        lp(NULL),
        timesShared(0),
        seqNum(-1),
        originalObjConst(0)
#ifdef ACRO_HAVE_MPI
        , psSize(0),
        psDepth(0)
#endif
        { };
    };

  
  /// Note: declaration of preSplitNode class may eventually have to
  /// go here after we get rid of the old Eckstein-Nediak
  /// "mipHeuristic" class.


  /// Main base class for LP-based MIP heuristics

  class lpBasedHeuristic : public CommonIO, public ParameterSet
    {

      ///
      /// First, atuff that is used in both serial and parallel
      ///

    public:

      /// Constructor.  Just set up name and parameters.

      lpBasedHeuristic();

      /// Main reset method

      virtual void reset(MILP* mGlobal_, lpShareObj* lpShare_ = NULL);

      /// Destructor; basically just a subset of some stuff done by
      /// the reset method

      virtual ~lpBasedHeuristic() { destructorResetCommonCode(); };

      /// To invoke the heuristic on a subproblem (if it wants to run)
      /// although virtual, it will typically not need to be overridden.

      virtual void possibleRun(MILPNode* sp);

    protected:

      /// Used by both reset and destructor

      void destructorResetCommonCode();

      /// To decide whether to run on a subproblem

      virtual bool wantToRunOn(MILPNode* sp);

      /// A generic form of wantToRunOn that takes a random number
      /// generator as an additional argument.

      bool standardWantRunDecision(MILPNode* sp,utilib::Uniform& rng);

      /// Overridable function used by standard implementation of wantToRunOn

      virtual double gapFunction(double gap) { return min(gap,1.0); };

      /// Standard code once we have decided that we do want to run

      virtual void applyHeuristicTo(MILPNode* sp);

      /// To see whether the LP needs to be set up to match a
      /// subproblem; if not, it already has been

      virtual bool needLPSetup(MILPNode* sp);

      /// To get the LP set up to match a subproblem

      virtual void setupLP(MILPNode* sp);

      /// Standard core implementation of setupLP

      void standardLPSetup(MILPNode* sp);

      /// To indicate the LP has indeed been set up to match a
      /// particular subproblem.

      virtual void markLPSetup(MILPNode* sp);

      /// To apply any necessary transformations to the LP; in the base
      /// version, this is a stub

      virtual void transformLP() { };

      /// Pure virtual function to actually run the heuristic

      virtual MILPSolution* runHeuristic() = 0;

      /// Standard wrapper code around the LP, similar to MILPNode:runLP

      virtual PicoLPInterface::problemState runLP(__LPSolver_Interface *lp 
                                                  = NULL);

      /// Default procedure to construct a solution from the LP

      virtual MILPSolution* makeSolution();

      /// To track how often the heuristic is succeeding, and update
      /// the "quality" measure

      virtual void trackPerformance(double oldIncumbentValue,
                                    double boundValue,
                                    double intMeasure);

      /// To add an "objective cut", something that many heuristics need

      void addObjCut();

      /// Optional validation check

      bool validate(DoubleVector trialSolution,double objective);

      /// Utility methods to remove rows or columsn from the end of the LP

      void clearRows(int rowsToRemain);
      void clearCols(int colsToRemain);

      /// Utility functions to access data from the main MILP class

      bool   haveIncumbent();
      double relGap();


      /// Data members

    public:

      /// Indicates whether this heuristic uses an objective cut

      bool useObjCut;

      /// Self-determined "quality" of the heuristic and related information

      double quality;
      int    timesInvoked;
      int    timesSucceeded;
      double hpCost;           // "Heuristic pseudocost" = ratio of 
                               // sumObjDiffs and sumIntMeasures below
      double timeSpent;

      /// Name of the heuristic

      const char* name;

      /// Heuristic debug level

      int heurDebug;

    protected:

      /// Pointers to key objects

      MILP*            mGlobal;
      branching*       bGlobal;
      MILPProblem*     problem;
      lpShareObj*      lpShare;
      PicoLPInterface* lp;

      /// Used to calculate hpCost, but probably don't need to be public

      double sumObjDiffs;
      double sumIntMeasures;

      /// Most heuristics will probably want to examine the LP
      /// solution vector that comes from the subproblem or LP setup
      /// object.  The way the rest of PICO works, this contains only
      /// integer variables.

      DoubleVector lpSolIntsOnly;
      
      /// Used to create the objective cut, if we want one

      IntVector               cSparseNdx;
      DoubleVector            cSparse;
      CoinShallowPackedVector cVector;

      /// Stores any changes we've made to the constant portion of the
      /// objective function

      double objConstChange;

      /// Information we don't want to retrieve repeatedly about the problem

      int baseRows;    // Rows in original problem
      int baseCols;    // Columns in original problem
      pebblBase::optimType sense;
      int numInts;

      double intTol;

      /// loadedRows is the number of rows right after setting up the
      /// LP to match the subproblem, but before any transformations.
      /// It might be larger than baseRows because of cuts.
      /// loadedCols is included for symmetry.

      int loadedRows;
      int loadedCols;

      /// Parameters

      int    depthThreshold;
      double qualityAdjustUp;
      double qualityAdjustDown;


      ///
      /// The remainder of the class is used only in parallel
      ///

#ifdef ACRO_HAVE_MPI

    public:

      /// The following method is called before the heuristic is used
      /// in parallel.  The "hNum" argument is supposed to be the
      /// position of the heuristic in the master array of heuristics,
      /// but could in principle be anything so long as it is
      /// identical in all processors.

      virtual void parallelReset(parMILP* pmGlobal_, int hNum);

      /// Ramp-up-related methods

      /// Main routine called when we might want to use a heuristic in
      /// ramp-up: the ramp-up equivalent of "possibleRun".  Although
      /// virtual, it should probably not have to be overridden.

    public:

      virtual void possibleRampUpRun(MILPNode* sp);

      /// Clean up at end of the ramp-up phase

      virtual void rampUpCleanUp();

      /// Decides whether to run during ramp-up.  If you don't want a
      /// heuristic to be used at all during ramp up, clear the
      /// usedInRampUp data member.

    protected:

      virtual bool wantRampUpRunOn(MILPNode* sp);

      /// Ramp-up method for invoking heuristic once we've decided to
      /// use it.  ALthough virtual, it probably won't need to be
      /// overridden.

      virtual void applyRampUpHeuristic(MILPNode* sp);

      /// Predicate that decides if the LP needs to be set up during
      /// ramp-up, or whether it has already been setup correctly.
      /// Does not need to be overridden if one is using the standard
      /// "presplitting" approach to ramp-up.

      virtual bool needRampUpLPSetup(MILPNode* sp);

      /// Sister routine to the above that marks an LP as set up
      /// during ramp-up.  The default implementation is for
      /// presplitting.

      virtual void markRampUpLPSetup(MILPNode* sp);

      /// Routine to set up LPs during ramp up.  The default
      /// implementation uses presplitting.  This routine returns a
      /// flag which is true if anything ended up being done
      /// differently from the serial version.

      virtual bool setupRampUpLP(MILPNode* sp);

      /// Core method to run the heuristic during ramp up.  The
      /// default implementation is just to run it the same way as in
      /// serial, although the results could be different if the LP
      /// has been set up differently.

      virtual MILPSolution* runRampUpHeuristic() { return runHeuristic(); };

      /// Incumbent-thread-related methods

    public:

      /// These methods are the main vehicles for putting solutions
      /// into the heuristic's rounding pool, for later rounding when
      /// the incumbent thread is running. The first offers a
      /// subproblem, and the second offers an LP setup object.  Note
      /// that these routines may decide not to use the offered
      /// solution.  The lpSetupObj version will delete its argument
      /// if it does not want to put it in the pool.  These methods
      /// are virtual, but I don't think it's very likely overrides
      /// will be needed.  The "level" argument is optional and
      /// defaults to zero, appropriate for newly-seen solution.

      virtual void offerToRoundingPool(MILPNode* sp,int level=0);

      virtual void offerToRoundingPool(lpSetupObj* lpo,int level=0);

      // Called to prune the rounding pool if a new incumbent comes along

      virtual void prunePool();

      /// Run the heuristic inside the incumbent thread

      void poolRun();

      /// Method that decides if a particular heuristic is able to run

      virtual bool ready() { return poolSize > 0; };

      /// Initialize the rounding pool.  Override if you want a
      /// non-default rounding pool representation.

      virtual void initRoundingPool();

    protected:

      /// "Scores" for ranking subproblems and LP setup objects (lower
      /// scores are better).  "rScore" means "randomized score"

      virtual double score(double bound,double intMeasure);

      virtual double rScore(double bound,double intMeasure)
        {
          return pebbl::gRandom()*score(bound,intMeasure);
        };

      virtual double rScore(MILPNode* sp);

      virtual double rScore(lpSetupObj* lpo);

      /// Methods for deciding whether something should enter the
      /// rounding pool, and doing rounding pool manipulations.
      /// Override if you want a different rounding pool
      /// representation.

      /// Do we want to put a newly-offered solution into the pool?
      /// The "l" argument is the "level" of the pool, and defaults to
      /// zero.

      virtual bool wantInRoundingPool(double bound,
                                      double intMeasure,
                                      int    l = 0);

      /// To insert new objects into the pool

      virtual void poolInsert(lpSetupObj* lpo,int level=0);

      /// To remove objects from the pool; for a different pool
      /// representation, this will probably need different arguments
      /// instead of a simple override.

      virtual void poolRemove(int level,int entry);

      /// Select something from the pool to try to round (and also
      /// remove it from the pool)

      virtual lpSetupObj* selectFromPool();

      /// Invokes the heuristic once we've chosen an object to run on

      void applyPoolHeuristic(lpSetupObj* lpo);

      /// Called on lp setup objects after they have been run.  The
      /// default implementation just puts the solution back in the
      /// pool.  Override if you want different behavior, such as just
      /// deleting the object.

      void postPoolRun(MILPSolution* solReturned,lpSetupObj* lpo);

      /// To setup the LP from pool objects

      virtual void setupLP(lpSetupObj* lpo);
 
      virtual void standardLPSetup(lpSetupObj* lpo);

      /// Data members

    public:

      // Parameters -- set in specialParallelInits(), possibly from
      // command-line parameters, if you don't want the generic
      // default values.

      // Flags that control when the heuristic is used

      bool usedInRampUp;         // Call this heuristic during ramp-up?
      bool usedInThread;         // Use in the incumbent thread?
      bool usedInQuickHeuristic; // Use in "quick" subproblem heuristic?   

      // The following are parameters used in the default ramp-up
      // (presplitting) implementation, and might not be used if
      // standard ramp-up is overridden.

      int preSplitSize;       // Preferred size for presplitting groups
      int preSplitDepth;      // Preferred depth of presplitting

      // Incumbent-thread-related parameters

      int maxPool;
      int poolLevels;

      double poolEnterProb;
      double poolBlockProb;
      double combineLevelProb;

     // Ramp-up-related variables

      double rampUpTime;      // Time used by heuristic during ramp-up
      double threadTime;      // Time used by heuristic within incumbent thread

      int rampUpTimesInvoked;
      int rampUpTimesSucceeded;

    protected:

      // Pointers to parallel MILP and parallel branching classes

      parMILP*           pmGlobal;
      parallelBranching* pbGlobal;

      // A random number generator that won't vary by processor --
      // needed during ramp-up to make synchronized random decisions
      // whether to run heuristics.

      PM_LCG  rampUpLCG;
      Uniform rampUpRNG;

      // Default representation of pool of solutions to be rounded
      // when invoked by the incumbent thread.

      Basic2DArray<lpSetupObj*> rPool;

      IntVector levelSize;
      int       firstUsedLevel;
      int       lastUsedLevel;
      int       poolSize;

      int       lastSelectLevel;

#endif

    };

} // namespace pico

#endif