
/*
**  This file forms part of the GOBLIN C++ Class Library.
**
**  Written by Christian Fremuth-Paeger, February 2001.
**  
**  Copying, compiling, distribution and modification
**  of this source code is permitted only in accordance
**  with the GOBLIN general licence information.
*/             


#if !defined(_BBSCHEME_H_)

#define _BBSCHEME_H_

#include <spsdig.h>

template <class TIndex,class TObj>
class goblinBBScheme;

template <class TIndex,class TObj>
class goblinBBNode : public goblinDataObject
{
protected:

    TIndex          n;          // Total number of (integer) variables
    TIndex          unfixed;    // Number of unfixed (integer) variables
    
    TObj            objective;  // Objective value of the relaxation
    bool            solved;     // Has relaxation been solved yet?

    virtual TObj            SolveRelaxation() throw() = 0;
        // Returns the objective value of the relaxed subproblem

public:
    
    goblinBBScheme<TIndex,TObj>* scheme;   // Scheme
    goblinBBNode<TIndex,TObj>*   succNode;   // Successor node in the list of active nodes
    TNode           index;      // Node index in the branch tree
    TIndex          depth;      // Bound on the number of non-zeros

    goblinBBNode(TIndex nn,goblinController& thisContext,
            goblinBBScheme<TIndex,TObj>* = NULL) throw();
    ~goblinBBNode() throw();
    
    unsigned long   Allocated() throw();     

    TObj            Objective() throw();
    virtual bool    Feasible() throw()  {return (unfixed==0);};
    TIndex          Unfixed() throw()   {return unfixed;};

    virtual TIndex          SelectVariable() throw() = 0;
        // Select variable to branch with
    virtual char            Direction1(TIndex) throw(ERRange) = 0;
        // Preferred direction before feasibility is achieved
    virtual char            Direction2(TIndex) throw(ERRange) = 0;
        // Preferred direction after feasibility is achieved (1 = up,0 = down)

    virtual goblinBBNode<TIndex,TObj>*  Clone() throw() = 0;
        // Generate a copy of the branch node
    virtual void            Raise(TIndex) throw(ERRange) = 0;
        // Raise lower variable bound
    virtual void            Lower(TIndex) throw(ERRange) = 0;
        // Lower upper variable bound
    virtual TObj            Infinity() throw() = 0;
        // Symbolic value for infeasible subproblems
    virtual void            SaveSolution() throw() = 0;
        // Copy the current solution to the original instance
    virtual TObj            LocalSearch() throw() {return objective;};
        // Plugin for local search methods

};




#if defined(_TRACING_)


class goblinBBTree : public diGraph
{                                        
public:

    goblinBBTree(goblinController &) throw();

    void    ConfigDisplay(goblinController &) throw();

};


#endif



template <class TIndex,class TObj>
class goblinBBScheme : public goblinDataObject
{
private:
    
    enum nodeType {PROCESSED = 0,QUEUED = 1,SAVED = 2,CUTOFF = 3};

    goblinBBNode<TIndex,TObj>* firstActive;

    diGraph*        Tree;       // Branching tree (for tracing)

protected:

    void Optimize() throw();
    bool Inspect(goblinBBNode<TIndex,TObj>*) throw();
    goblinBBNode<TIndex,TObj>* PullActive() throw();
    void PushActive(goblinBBNode<TIndex,TObj>*) throw();
    void StripQueue() throw();

public:

    TIndex  nActive;        // Number of queued subproblems
    TIndex  nIterations;    // Total number of solved subproblems
    TIndex  nDFS;           // Number of dfs steps since the last bfs or improvement
    TIndex  depth;          // Bound on the number of non-zeros (only a copy)

    bool    feasible;   // Has been problem feasibility reached yet?
    char    exhaustive;
        // 0: Only a single feasible solution is produced
        // 1: Starting with some depth first search steps
        // 2: Pure best first search
        
    TObj    bestBound;
    TObj    bestLower;

    goblinBBScheme(goblinBBNode<TIndex,TObj>*,TObj,char = 1) throw();
    ~goblinBBScheme() throw();

    char Phase() throw();
    
    unsigned long   Size() throw();
    unsigned long   Allocated() throw();
    
};


#endif
