Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

abacus::OpenSub Class Reference

Maintains open subproblems. More...

#include <ogdf/lib/abacus/opensub.h>

+ Inheritance diagram for abacus::OpenSub:

Public Member Functions

 OpenSub (Master *master)
 Creates an empty list of open subproblems. More...
 
double dualBound () const
 Returns the value of the dual bound for all subproblems in the list. More...
 
bool empty () const
 Returns true if there is no subproblem in the set of open subproblems, false otherwise. More...
 
int number () const
 Returns the current number of open subproblems contained in this set. More...
 
- Public Member Functions inherited from abacus::AbacusRoot
virtual ~AbacusRoot ()
 The destructor. More...
 

Private Member Functions

 OpenSub (const OpenSub &rhs)
 
void insert (Sub *sub)
 Adds a subproblem to the set of open subproblems. More...
 
const OpenSuboperator= (const OpenSub &rhs)
 
void prune ()
 Removes all elements from the set of opens subproblems. More...
 
void remove (Sub *sub)
 Removes subproblem from the set of open subproblems. More...
 
Subselect ()
 Selects a subproblem according to the master's strategy and removes it from the list of open subproblems. More...
 
void updateDualBound ()
 Updates dualBound_ according to the dual bounds of the subproblems contained in this set. More...
 

Private Attributes

double dualBound_
 The dual bound of all open subproblems. More...
 
ogdf::List< Sub * > list_
 The list storing the open subproblems. More...
 
Mastermaster_
 A pointer to corresponding master of the optimization. More...
 

Friends

class Master
 
class Sub
 

Additional Inherited Members

- Static Public Member Functions inherited from abacus::AbacusRoot
static bool ascii2bool (const string &str)
 Converts the string str to a boolean value. More...
 
static bool endsWith (const string &str, const string &end)
 Returns true if str ends with end, false otherwise. More...
 
static double fracPart (double x)
 Returns the absolute value of the fractional part of x. More...
 
static const char * onOff (bool value)
 Converts a boolean variable to the strings "on" and "off". More...
 

Detailed Description

Maintains open subproblems.

During a branch-and-bound algorithm a set of open subproblems has to be maintained. New subproblems are inserted in this set after a branching step, or when a subproblem becomes dormant. A subproblem is extracted from this list if it becomes the active subproblem which is optimized.

Definition at line 49 of file opensub.h.

Constructor & Destructor Documentation

◆ OpenSub() [1/2]

abacus::OpenSub::OpenSub ( Master master)
inline

Creates an empty list of open subproblems.

Does not initialize the member dualBound_ since this can only be done if we know the sense of the objective function which is normally unknown when the constructor of the class Master is called which again calls this constructor.

Parameters
masterA pointer to the corresponding master of the optimization.

Definition at line 65 of file opensub.h.

◆ OpenSub() [2/2]

abacus::OpenSub::OpenSub ( const OpenSub rhs)
private

Member Function Documentation

◆ dualBound()

double abacus::OpenSub::dualBound ( ) const

Returns the value of the dual bound for all subproblems in the list.

◆ empty()

bool abacus::OpenSub::empty ( ) const
inline

Returns true if there is no subproblem in the set of open subproblems, false otherwise.

Definition at line 73 of file opensub.h.

◆ insert()

void abacus::OpenSub::insert ( Sub sub)
private

Adds a subproblem to the set of open subproblems.

Parameters
subThe subproblem that is inserted.

◆ number()

int abacus::OpenSub::number ( ) const
inline

Returns the current number of open subproblems contained in this set.

Definition at line 68 of file opensub.h.

◆ operator=()

const OpenSub& abacus::OpenSub::operator= ( const OpenSub rhs)
private

◆ prune()

void abacus::OpenSub::prune ( )
inlineprivate

Removes all elements from the set of opens subproblems.

Definition at line 108 of file opensub.h.

◆ remove()

void abacus::OpenSub::remove ( Sub sub)
inlineprivate

Removes subproblem from the set of open subproblems.

Parameters
subThe subproblem that is removed.

Definition at line 102 of file opensub.h.

◆ select()

Sub* abacus::OpenSub::select ( )
private

Selects a subproblem according to the master's strategy and removes it from the list of open subproblems.

This function scans the list of open subproblems and selects the subproblem with highest priority. Dormant subproblems are ignored if possible.

Returns
The selected subproblem. If the set of open subproblems is empty, 0 is returned.

◆ updateDualBound()

void abacus::OpenSub::updateDualBound ( )
private

Updates dualBound_ according to the dual bounds of the subproblems contained in this set.

Friends And Related Function Documentation

◆ Master

friend class Master
friend

Definition at line 52 of file opensub.h.

◆ Sub

friend class Sub
friend

Definition at line 51 of file opensub.h.

Member Data Documentation

◆ dualBound_

double abacus::OpenSub::dualBound_
private

The dual bound of all open subproblems.

Definition at line 117 of file opensub.h.

◆ list_

ogdf::List<Sub*> abacus::OpenSub::list_
private

The list storing the open subproblems.

Definition at line 116 of file opensub.h.

◆ master_

Master* abacus::OpenSub::master_
private

A pointer to corresponding master of the optimization.

Definition at line 115 of file opensub.h.


The documentation for this class was generated from the following file: