home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / tlx501.zip / SRC / BBSRCHDF.CPP < prev    next >
C/C++ Source or Header  |  1996-07-08  |  7KB  |  215 lines
  1. /****************************************************************************
  2.     $Id: bbsrchdf.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 TLBBSearcherDF, branch & bound searcher with
  10.     depth-first searching only.
  11.  
  12.     $Log: bbsrchdf.cpp $
  13.     Revision 501.0  1995/03/07 12:26:08  RON
  14.     Updated for TLX 5.01
  15.     Revision 1.19  1995/02/22 12:22:46  RON
  16.     Update for release 012
  17.     Added partial support for SunPro C++ compiler
  18.     Revision 1.18  1995/01/16  12:24:10  ron
  19.     Removed best gap statistics
  20.  
  21.     Revision 1.17  1995/01/13  15:29:25  ron
  22.     Changed mBestProblem to mBestGap (due to change again)
  23.  
  24.     Revision 1.16  1995/01/12  13:37:32  ron
  25.     Adapted to previous Searcher/ProblemRep model
  26.  
  27.     Revision 1.15  1995/01/10  16:31:29  ron
  28.     Added ReportStats() and best lower bound memory
  29.  
  30.     Revision 1.14  1995/01/06  15:55:54  ron
  31.     Adapted to new Searcher/Problem model
  32.  
  33.     Revision 1.13  1995/01/05  15:20:53  ron
  34.     Added SetIncumbent()
  35.     Formatting and naming changes
  36.  
  37.     Revision 1.12  1994/11/16  15:36:11  ron
  38.     Added module info; rearranged #include directives
  39.  
  40.     Revision 1.11  1994/10/12  10:03:24  ron
  41.     Switched to GetInfo() style of partial problem inclusion
  42.  
  43.     Revision 1.10  1994/10/11  19:01:46  ron
  44.     Replaced DeadEnd() + SolveProblem() by ProcessProblem()
  45.  
  46.     Revision 1.9  1994/10/10  16:45:31  ron
  47.     Added searcher description
  48.  
  49.     Revision 1.8  1994/10/05  18:34:02  ron
  50.     Formatting changes
  51.  
  52.     Revision 1.7  1994/09/28  14:13:09  ron
  53.     Added dead-end check to ContinueProblem()
  54.  
  55.     Revision 1.6  1994/09/27  20:22:00  ron
  56.     Changed path separator from / to \
  57.  
  58.     Revision 1.5  1994/09/26  15:39:09  ron
  59.     Changed include file references
  60.  
  61.     Revision 1.4  1994/09/13  10:11:26  ron
  62.     Adapted to changes in the TLProblemRep hierarchy
  63.  
  64.     Revision 1.3  1994/09/12  14:53:07  ron
  65.     Adapted ContinueProblem() implementation to changes in TLSearcher
  66.     interface
  67.  
  68.     Revision 1.2  1994/09/06  14:07:56  ron
  69.     Adapted to general changes in searcher framework
  70.  
  71.     Revision 1.1  1994/08/16  18:12:53  ron
  72.     Initial revision
  73.  
  74. ****************************************************************************/
  75.  
  76. #include <tlx\501\_build.h>
  77.  
  78. TLX_MODULE_INFO("$Revision: 501.0 $");
  79.  
  80. #include <float.h>
  81. #include <tlx\501\log.h>
  82. #include <tlx\501\solve\searcher.h>
  83. #include <tlx\501\util.h>
  84.  
  85. /*-------------------------------------------------------------------------*/
  86.     TLBBSearcherDF::TLBBSearcherDF()
  87.  
  88. /*  Default constructor. Initializes the searcher.
  89. ---------------------------------------------------------------------------*/
  90. {
  91.     mIncumbent = DBL_MAX;
  92. }
  93.  
  94. /*-------------------------------------------------------------------------*/
  95.     bool TLBBSearcherDF::ContinueProblem(TLProblemState *aProblem)
  96.  
  97. /*  Called to check if the current subproblem may be continued after it has
  98.     been processed by the problem representation. In this implementation,
  99.     we perform bounds checks etc. to determine if we must continue.
  100.  
  101.     The cut-off conditions are described in:
  102.  
  103.     T. Ibaraki: Enumerative Approaches to Combinatorial Optimization
  104.                 (Part I), pp. 88-94. JG Baltzer AG, 1988.
  105. ---------------------------------------------------------------------------*/
  106. {
  107.     TLX_ASSERT_PTR(aProblem);
  108.     TLX_ASSERT(aProblem->mIsProcessed);
  109.  
  110.     // The problem representation must have processed the subproblem already.
  111.     // This must result in a calculation of the upperbound and the lowerbound
  112.     // for the solution.
  113.  
  114.     TLBBInfo *info = DYNACAST(TLBBInfo *, aProblem->GetInfo());
  115.     TLX_ASSERT_PTR(info);
  116.  
  117.     // Lower bound and dominance checks
  118.  
  119.     double lbound = info->LowerBound();
  120.  
  121.     if (lbound > mIncumbent || info->IsDominated())
  122.         return false;
  123.  
  124.     // Check the upper bound to see if it improves on the current
  125.     // best value. Because we store all optimal solutions, we
  126.     // must distinguish between a strict improvement or a match of
  127.     // the current best value.
  128.     //
  129.     // If the upperbound is less than infinity, it is assumed that a
  130.     // feasible solution realising this upperbound is available; else
  131.     // we assume that the upperbound was not calculated and that no
  132.     // solution is available (the lowerbound and dominance are used,
  133.     // though).
  134.  
  135.     double upbound = info->UpperBound();
  136.     if (upbound <= mIncumbent && upbound < DBL_MAX)
  137.     {
  138.         if (upbound < mIncumbent)       // Strictly less?
  139.         {
  140.             ClearSolutions();
  141.             mIncumbent = upbound;
  142.         }
  143.  
  144.         // At least as good as previous solutions - store it
  145.  
  146.         CreateSolution(aProblem);
  147.     }
  148.  
  149.     TLX_ASSERT(mIncumbent >= lbound);
  150.  
  151.     return true;
  152. }
  153.  
  154. /*-------------------------------------------------------------------------*/
  155.     bool TLBBSearcherDF::ContinueSearch()
  156.  
  157. /*  Called to determine whether or not the search process at large must be
  158.     continued after finding a solution. This version returns true as long
  159.     as not sufficient solutions are found and improvements in upper bound
  160.     are possible.
  161. ---------------------------------------------------------------------------*/
  162. {
  163.     //return mBestGap > 0 && SolutionCount() < GetStats().mMaxSol;
  164.     return true;
  165. }
  166.  
  167. /*-------------------------------------------------------------------------*/
  168.     const char *TLBBSearcherDF::Description() const
  169.  
  170. /*  Returns a description of the searcher.
  171. ---------------------------------------------------------------------------*/
  172. {
  173.     return "Depth-first branch & bound searcher";
  174. }
  175.  
  176. /*-------------------------------------------------------------------------*/
  177.     bool TLBBSearcherDF::PreProcess()
  178.  
  179. /*  Called to prepare for the search. It calls the inherited version, then
  180.     discards any previous solutions and previous best value.
  181. ---------------------------------------------------------------------------*/
  182. {
  183.     if (!TLBTSearcher::PreProcess())
  184.         return false;
  185.  
  186.     //mIncumbent = DBL_MAX;     // Do not initialize; may be set externally
  187.     return true;
  188. }
  189.  
  190. /*-------------------------------------------------------------------------*/
  191.     void TLBBSearcherDF::ReportStats()
  192.  
  193. /*  Prints search statistics on stderr and the log output.
  194. ---------------------------------------------------------------------------*/
  195. {
  196.     TLSearcher::ReportStats();
  197.  
  198.     TLX_LOG_ENTRY("B&B: incumbent = %f", mIncumbent);
  199. }
  200.  
  201. /*-------------------------------------------------------------------------*/
  202.     void TLBBSearcherDF::SetIncumbent(double aIncumbent)
  203.  
  204. /*  Sets the incumbent value, possibly because the problem representation
  205.     has some means to establish an initial lower bound before any
  206.     subproblem is processed.
  207. ---------------------------------------------------------------------------*/
  208. {
  209.     if (aIncumbent > mIncumbent)
  210.         TLX_TRACE_WARN(TLX, ("New incumbent %f greater than current %f",
  211.                        aIncumbent, mIncumbent));
  212.     mIncumbent = aIncumbent;
  213. }
  214.  
  215.