home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / tlx501.zip / SRC / BBSEARCH.CPP < prev    next >
C/C++ Source or Header  |  1996-07-08  |  7KB  |  214 lines
  1. /****************************************************************************
  2.     $Id: bbsearch.cpp 501.0 1995/03/07 12:26:08 RON Exp $
  3.  
  4.     Copyright (c) 1994-95 Tarma Software Research. All rights reserved.
  5.  
  6.     Project:    Tarma Library for C++ V5.0
  7.     Author:     Ron van der Wal
  8.  
  9.     Implementation of class TLBBSearcher, the branch & bound searcher.
  10.  
  11.     $Log: bbsearch.cpp $
  12.     Revision 501.0  1995/03/07 12:26:08  RON
  13.     Updated for TLX 5.01
  14.     Revision 1.17  1995/02/22 12:29:02  RON
  15.     Update for release 012
  16.     Added partial support for SunPro C++ compiler
  17.     Revision 1.16  1995/01/13  15:29:00  ron
  18.     Removed mIncumbent initialization in several places
  19.  
  20.     Revision 1.15  1995/01/12  13:37:13  ron
  21.     Adapted to previous Searcher/ProblemRep model
  22.  
  23.     Revision 1.14  1995/01/06  15:55:53  ron
  24.     Adapted to new Searcher/Problem model
  25.  
  26.     Revision 1.13  1995/01/05  15:20:24  ron
  27.     Added SetIncumbent()
  28.     Formatting and naming changes
  29.  
  30.     Revision 1.12  1994/11/16  15:36:04  ron
  31.     Added module info; rearranged #include directives
  32.  
  33.     Revision 1.11  1994/10/12  10:02:40  ron
  34.     Removed template instantiations
  35.     Switched to GetInfo() style of partial problem inclusion
  36.  
  37.     Revision 1.10  1994/10/11  19:01:19  ron
  38.     Replaced DeadEnd() + SolveProblem() by ProcessProblem()
  39.  
  40.     Revision 1.9  1994/10/10  16:45:08  ron
  41.     Added searcher description and termination
  42.  
  43.     Revision 1.8  1994/10/05  18:33:48  ron
  44.     Formatting changes
  45.  
  46.     Revision 1.7  1994/09/28  14:12:49  ron
  47.     Added dead-end check to ContinueProblem()
  48.  
  49.     Revision 1.6  1994/09/27  20:21:58  ron
  50.     Changed path separator from / to \
  51.  
  52.     Revision 1.5  1994/09/26  15:38:49  ron
  53.     Renamed TLPointer<T> to TLCountedPtr<T>
  54.  
  55.     Revision 1.4  1994/09/13  10:10:39  ron
  56.     Added calls to EnterProblem() and LeaveProblem() in order to keep the
  57.     searcher statistics up to date
  58.  
  59.     Revision 1.3  1994/09/12  14:52:40  ron
  60.     Adapted Search() implementation to changes in TLSearcher interface
  61.  
  62.     Revision 1.2  1994/09/06  14:07:36  ron
  63.     Adapted to general changes in searching framework
  64.  
  65.     Revision 1.1  1994/08/16  18:12:52  ron
  66.     Initial revision
  67.  
  68. ****************************************************************************/
  69.  
  70. #include <tlx\501\_build.h>
  71.  
  72. TLX_MODULE_INFO("$Revision: 501.0 $");
  73.  
  74. #include <float.h>
  75. #include <tlx\501\solve\searcher.h>
  76.  
  77. /*-------------------------------------------------------------------------*/
  78.     TLBBSearcher::TLBBSearcher()
  79.  
  80. /*  Default constructor. Initializes the searcher.
  81. ---------------------------------------------------------------------------*/
  82. {
  83.     mIncumbent = DBL_MAX;
  84.     mTerminate = false;
  85. }
  86.  
  87. /*-------------------------------------------------------------------------*/
  88.     const char *TLBBSearcher::Description() const
  89.  
  90. /*  Returns a description of the searcher.
  91. ---------------------------------------------------------------------------*/
  92. {
  93.     return "Global branch & bound searcher";
  94. }
  95.  
  96. /*-------------------------------------------------------------------------*/
  97.     bool TLBBSearcher::PreProcess()
  98.  
  99. /*  Called to prepare for the search. It calls the inherited version, then
  100.     discards any previous solutions and previous best value.
  101. ---------------------------------------------------------------------------*/
  102. {
  103.     if (!TLSearcher::PreProcess())
  104.         return false;
  105.  
  106.     //mIncumbent = DBL_MAX;     // Do not initialize; may be set externally
  107.     mTerminate = false;
  108.     return true;
  109. }
  110.  
  111. /*-------------------------------------------------------------------------*/
  112.     void TLBBSearcher::Search()
  113.  
  114. /*  Solves the problem represented by the problem representation to optimality, or
  115.     proves it to be infeasible. Returns the number of solutions found
  116.     (0 = infeasible); the solutions themselves may be inspected by a
  117.     call to GetSolutions().
  118.  
  119.     The branch & bound algorithm is a variation on the one presented in:
  120.  
  121.     T. Ibaraki: Enumerative Approaches to Combinatorial Optimization
  122.                 (Part I), pp. 88-94. JG Baltzer AG, 1988.
  123. ---------------------------------------------------------------------------*/
  124. {
  125.     TLProblemList actnodes(100, 100);   // Active nodes
  126.     if (CreateInitialProblem(actnodes) < 1)
  127.     {
  128.         TLX_TRACE_WARN(TLX, ("No initial problems created - search aborted"));
  129.         return;
  130.     }
  131.  
  132.     for (TLProblemState *curproblem = 0; !mTerminate && !actnodes.IsEmpty();
  133.          LeaveState(curproblem))
  134.     {
  135.         // Select the next node to investigate and remove it from the list
  136.         // of active nodes.
  137.  
  138.         curproblem = actnodes.ExtractFirst();
  139.         TLX_ASSERT_PTR(curproblem);
  140.         EnterState(curproblem);
  141.  
  142.         // Let the problem representation solve the subproblem. This must
  143.         // result in a calculation of the upperbound and the lowerbound
  144.         // for the solution.
  145.  
  146.         if (!Process(curproblem))
  147.             continue;
  148.  
  149.         // Perform lower bound and dominance checks; do not take any further
  150.         // action if the node can be terminated on these grounds.
  151.  
  152.         TLBBInfo *info = DYNACAST(TLBBInfo *, curproblem->GetInfo());
  153.         TLX_ASSERT_PTR(info);
  154.  
  155.         if (info->LowerBound() > mIncumbent || info->IsDominated())
  156.             continue;
  157.  
  158.         // Check the upper bound to see if it improves on the current
  159.         // best value. Because we store all optimal solutions, we
  160.         // must distinguish between a strict improvement or a match of
  161.         // the current best value.
  162.         //
  163.         // If the upperbound is less than infinity, it is assumed that a
  164.         // feasible solution realising this upperbound is available; else
  165.         // we assume that the upperbound was not calculated and that no
  166.         // solution is available (the lowerbound and dominance are used,
  167.         // though).
  168.  
  169.         double upbound = info->UpperBound();
  170.         if (upbound <= mIncumbent && upbound < DBL_MAX)
  171.         {
  172.             if (upbound < mIncumbent)   // Strictly less?
  173.             {
  174.                 ClearSolutions();
  175.                 mIncumbent = upbound;
  176.             }
  177.  
  178.             // At least as good as previous solutions - store it
  179.  
  180.             CreateSolution(curproblem);
  181.         }
  182.         else
  183.             GenerateBranches(curproblem, actnodes);
  184.     }
  185.  
  186.     // If we get here, there are no more active nodes.
  187.     TLX_ASSERT(mTerminate || SolutionCount() > 0 || mIncumbent == DBL_MAX);
  188. }
  189.  
  190. /*-------------------------------------------------------------------------*/
  191.     void TLBBSearcher::SetIncumbent(double aIncumbent)
  192.  
  193. /*  Sets the incumbent value, possibly because the problem representation
  194.     has some means to establish an initial lower bound before any
  195.     subproblem is processed.
  196. ---------------------------------------------------------------------------*/
  197. {
  198.     if (aIncumbent > mIncumbent)
  199.         TLX_TRACE_WARN(TLX, ("New incumbent %f greater than current %f",
  200.                        aIncumbent, mIncumbent));
  201.     mIncumbent = aIncumbent;
  202. }
  203.  
  204. /*-------------------------------------------------------------------------*/
  205.     void TLBBSearcher::Terminate()
  206.  
  207. /*  Sets the termination flag, which causes the searcher to terminate as
  208.     soon as possible.
  209. ---------------------------------------------------------------------------*/
  210. {
  211.     mTerminate = true;
  212. }
  213.  
  214.