AlpsSearchStrategy.h

Go to the documentation of this file.

/*===========================================================================*
 * This file is part of the Abstract Library for Parallel Search (ALPS).     *
 *                                                                           *
 * ALPS is distributed under the Eclipse Public License as part of the       *
 * COIN-OR repository (http://www.coin-or.org).                              *
 *                                                                           *
 * Authors:                                                                  *
 *                                                                           *
 *          Yan Xu, Lehigh University                                        *
 *          Ted Ralphs, Lehigh University                                    *
 *                                                                           *
 * Conceptual Design:                                                        *
 *                                                                           *
 *          Yan Xu, Lehigh University                                        *
 *          Ted Ralphs, Lehigh University                                    *
 *          Laszlo Ladanyi, IBM T.J. Watson Research Center                  *
 *          Matthew Saltzman, Clemson University                             *
 *                                                                           * 
 *                                                                           *
 * Copyright (C) 2001-2013, Lehigh University, Yan Xu, and Ted Ralphs.       *
 *===========================================================================*/

#ifndef AlpsSearchStrategy_h_
#define AlpsSearchStrategy_h_

#include "AlpsSearchStrategyBase.h"
#include "AlpsSubTree.h"
#include "AlpsTreeNode.h"

//#############################################################################
//#############################################################################

class AlpsTreeSelection : public AlpsSearchStrategy<AlpsSubTree*> 
{
public:
    AlpsTreeSelection() {}

    virtual ~AlpsTreeSelection() {}
    
    virtual bool compare(AlpsSubTree * x, AlpsSubTree * y) = 0;
};

//#############################################################################

class AlpsNodeSelection : public AlpsSearchStrategy<AlpsTreeNode*> 
{
public:
    AlpsNodeSelection() {}
    
    virtual ~AlpsNodeSelection() {}
    
    virtual bool compare(AlpsTreeNode * x, AlpsTreeNode * y) = 0;
    
    /* Select the next node to be processed. */
    virtual AlpsTreeNode* selectNextNode(AlpsSubTree *subTree);
    
    /* Create new nodes from pregnant node and store them in node pool. */
    virtual void createNewNodes(AlpsSubTree *subTree, AlpsTreeNode *node);
};

//#############################################################################
// SUBTREE SELECTION RULES
//#############################################################################

class AlpsTreeSelectionBest : public AlpsTreeSelection
{
public:
    AlpsTreeSelectionBest() { type_ = AlpsSearchTypeBestFirst; }

    virtual ~AlpsTreeSelectionBest() {}
    
    virtual bool compare(AlpsSubTree * x, AlpsSubTree * y);
};

//#############################################################################

class AlpsTreeSelectionBreadth : public AlpsTreeSelection
{
public:
    AlpsTreeSelectionBreadth() { type_ = AlpsSearchTypeBreadthFirst; }
    
    virtual ~AlpsTreeSelectionBreadth() {}
    
    virtual bool compare(AlpsSubTree * x, AlpsSubTree * y);
};

//#############################################################################

class AlpsTreeSelectionDepth : public AlpsTreeSelection
{
public:
    AlpsTreeSelectionDepth() { type_ = AlpsSearchTypeDepthFirst; }
    
    virtual ~AlpsTreeSelectionDepth() {}
    
    virtual bool compare(AlpsSubTree * x, AlpsSubTree * y);
};

//#############################################################################

class AlpsTreeSelectionEstimate : public AlpsTreeSelection
{
public:
    AlpsTreeSelectionEstimate() { type_ = AlpsSearchTypeBestEstimate; }

    virtual ~AlpsTreeSelectionEstimate() {}
    
    virtual bool compare(AlpsSubTree * x, AlpsSubTree * y);
};

//#############################################################################
// NODE SELECTION RULES
//#############################################################################

class AlpsNodeSelectionBest : public AlpsNodeSelection
{
public:
    AlpsNodeSelectionBest() { type_ = AlpsSearchTypeBestFirst; }

    virtual ~AlpsNodeSelectionBest() {}

    virtual bool compare(AlpsTreeNode * x, AlpsTreeNode * y) {
        return (x->getQuality() > y->getQuality());
    }
};

//#############################################################################

class AlpsNodeSelectionBreadth : public AlpsNodeSelection
{
public:
    AlpsNodeSelectionBreadth() { type_ = AlpsSearchTypeBreadthFirst; }

    virtual ~AlpsNodeSelectionBreadth() {}

    virtual bool compare(AlpsTreeNode * x, AlpsTreeNode * y) {
        return x->getDepth() > y->getDepth();
    }
};

//#############################################################################

class AlpsNodeSelectionDepth : public AlpsNodeSelection
{
 public:
    AlpsNodeSelectionDepth() { type_ = AlpsSearchTypeDepthFirst; }

    virtual ~AlpsNodeSelectionDepth() {}

    virtual bool compare(AlpsTreeNode * x, AlpsTreeNode * y) {
        return (x->getDepth() < y->getDepth());
    }
};

//#############################################################################

class AlpsNodeSelectionEstimate : public AlpsNodeSelection
{
 public:
    AlpsNodeSelectionEstimate() { type_ = AlpsSearchTypeBestEstimate; }

    virtual ~AlpsNodeSelectionEstimate() {}

    virtual bool compare (AlpsTreeNode * x, AlpsTreeNode * y) {
        return (x->getSolEstimate() > y->getSolEstimate());
    }
};

//#############################################################################

class AlpsNodeSelectionHybrid : public AlpsNodeSelection
{
public:
    AlpsNodeSelectionHybrid() { type_ = AlpsSearchTypeHybrid; }

    virtual ~AlpsNodeSelectionHybrid() {}
    
    virtual bool compare(AlpsTreeNode * x, AlpsTreeNode * y) {
        // best first
        return (x->getQuality() > y->getQuality());
    }

    /* Select the next node to be processed. */
    virtual AlpsTreeNode* selectNextNode(AlpsSubTree *subTree);
    
    /* Create new nodes from pregnant node and store them in node pool. */
    virtual void createNewNodes(AlpsSubTree *subTree, AlpsTreeNode *node);
};

//#############################################################################
#endif