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                                        *
 *          Aykut Bulut, 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-2023, Lehigh University, Yan Xu, Aykut Bulut, and      *
 *                          Ted Ralphs.                                      *
 * All Rights Reserved.                                                      *
 *===========================================================================*/
 
 
#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