home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
OS/2 Shareware BBS: 10 Tools
/
10-Tools.zip
/
tlx501.zip
/
SRC
/
BBSEARCH.CPP
< prev
next >
Wrap
C/C++ Source or Header
|
1996-07-08
|
7KB
|
214 lines
/****************************************************************************
$Id: bbsearch.cpp 501.0 1995/03/07 12:26:08 RON Exp $
Copyright (c) 1994-95 Tarma Software Research. All rights reserved.
Project: Tarma Library for C++ V5.0
Author: Ron van der Wal
Implementation of class TLBBSearcher, the branch & bound searcher.
$Log: bbsearch.cpp $
Revision 501.0 1995/03/07 12:26:08 RON
Updated for TLX 5.01
Revision 1.17 1995/02/22 12:29:02 RON
Update for release 012
Added partial support for SunPro C++ compiler
Revision 1.16 1995/01/13 15:29:00 ron
Removed mIncumbent initialization in several places
Revision 1.15 1995/01/12 13:37:13 ron
Adapted to previous Searcher/ProblemRep model
Revision 1.14 1995/01/06 15:55:53 ron
Adapted to new Searcher/Problem model
Revision 1.13 1995/01/05 15:20:24 ron
Added SetIncumbent()
Formatting and naming changes
Revision 1.12 1994/11/16 15:36:04 ron
Added module info; rearranged #include directives
Revision 1.11 1994/10/12 10:02:40 ron
Removed template instantiations
Switched to GetInfo() style of partial problem inclusion
Revision 1.10 1994/10/11 19:01:19 ron
Replaced DeadEnd() + SolveProblem() by ProcessProblem()
Revision 1.9 1994/10/10 16:45:08 ron
Added searcher description and termination
Revision 1.8 1994/10/05 18:33:48 ron
Formatting changes
Revision 1.7 1994/09/28 14:12:49 ron
Added dead-end check to ContinueProblem()
Revision 1.6 1994/09/27 20:21:58 ron
Changed path separator from / to \
Revision 1.5 1994/09/26 15:38:49 ron
Renamed TLPointer<T> to TLCountedPtr<T>
Revision 1.4 1994/09/13 10:10:39 ron
Added calls to EnterProblem() and LeaveProblem() in order to keep the
searcher statistics up to date
Revision 1.3 1994/09/12 14:52:40 ron
Adapted Search() implementation to changes in TLSearcher interface
Revision 1.2 1994/09/06 14:07:36 ron
Adapted to general changes in searching framework
Revision 1.1 1994/08/16 18:12:52 ron
Initial revision
****************************************************************************/
#include <tlx\501\_build.h>
TLX_MODULE_INFO("$Revision: 501.0 $");
#include <float.h>
#include <tlx\501\solve\searcher.h>
/*-------------------------------------------------------------------------*/
TLBBSearcher::TLBBSearcher()
/* Default constructor. Initializes the searcher.
---------------------------------------------------------------------------*/
{
mIncumbent = DBL_MAX;
mTerminate = false;
}
/*-------------------------------------------------------------------------*/
const char *TLBBSearcher::Description() const
/* Returns a description of the searcher.
---------------------------------------------------------------------------*/
{
return "Global branch & bound searcher";
}
/*-------------------------------------------------------------------------*/
bool TLBBSearcher::PreProcess()
/* Called to prepare for the search. It calls the inherited version, then
discards any previous solutions and previous best value.
---------------------------------------------------------------------------*/
{
if (!TLSearcher::PreProcess())
return false;
//mIncumbent = DBL_MAX; // Do not initialize; may be set externally
mTerminate = false;
return true;
}
/*-------------------------------------------------------------------------*/
void TLBBSearcher::Search()
/* Solves the problem represented by the problem representation to optimality, or
proves it to be infeasible. Returns the number of solutions found
(0 = infeasible); the solutions themselves may be inspected by a
call to GetSolutions().
The branch & bound algorithm is a variation on the one presented in:
T. Ibaraki: Enumerative Approaches to Combinatorial Optimization
(Part I), pp. 88-94. JG Baltzer AG, 1988.
---------------------------------------------------------------------------*/
{
TLProblemList actnodes(100, 100); // Active nodes
if (CreateInitialProblem(actnodes) < 1)
{
TLX_TRACE_WARN(TLX, ("No initial problems created - search aborted"));
return;
}
for (TLProblemState *curproblem = 0; !mTerminate && !actnodes.IsEmpty();
LeaveState(curproblem))
{
// Select the next node to investigate and remove it from the list
// of active nodes.
curproblem = actnodes.ExtractFirst();
TLX_ASSERT_PTR(curproblem);
EnterState(curproblem);
// Let the problem representation solve the subproblem. This must
// result in a calculation of the upperbound and the lowerbound
// for the solution.
if (!Process(curproblem))
continue;
// Perform lower bound and dominance checks; do not take any further
// action if the node can be terminated on these grounds.
TLBBInfo *info = DYNACAST(TLBBInfo *, curproblem->GetInfo());
TLX_ASSERT_PTR(info);
if (info->LowerBound() > mIncumbent || info->IsDominated())
continue;
// Check the upper bound to see if it improves on the current
// best value. Because we store all optimal solutions, we
// must distinguish between a strict improvement or a match of
// the current best value.
//
// If the upperbound is less than infinity, it is assumed that a
// feasible solution realising this upperbound is available; else
// we assume that the upperbound was not calculated and that no
// solution is available (the lowerbound and dominance are used,
// though).
double upbound = info->UpperBound();
if (upbound <= mIncumbent && upbound < DBL_MAX)
{
if (upbound < mIncumbent) // Strictly less?
{
ClearSolutions();
mIncumbent = upbound;
}
// At least as good as previous solutions - store it
CreateSolution(curproblem);
}
else
GenerateBranches(curproblem, actnodes);
}
// If we get here, there are no more active nodes.
TLX_ASSERT(mTerminate || SolutionCount() > 0 || mIncumbent == DBL_MAX);
}
/*-------------------------------------------------------------------------*/
void TLBBSearcher::SetIncumbent(double aIncumbent)
/* Sets the incumbent value, possibly because the problem representation
has some means to establish an initial lower bound before any
subproblem is processed.
---------------------------------------------------------------------------*/
{
if (aIncumbent > mIncumbent)
TLX_TRACE_WARN(TLX, ("New incumbent %f greater than current %f",
aIncumbent, mIncumbent));
mIncumbent = aIncumbent;
}
/*-------------------------------------------------------------------------*/
void TLBBSearcher::Terminate()
/* Sets the termination flag, which causes the searcher to terminate as
soon as possible.
---------------------------------------------------------------------------*/
{
mTerminate = true;
}