Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

abacus::TailOff Class Reference

Tailing off manager. More...

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

+ Inheritance diagram for abacus::TailOff:

Public Member Functions

 TailOff (Master *master)
 The constructor takes the length of the tailing off history from Master::tailOffNLp(). More...
 
 TailOff (Master *master, int NLp)
 An alternative constructor takes the length of the tailing off history from the parameter NLp. More...
 
 ~TailOff ()
 The destructor. More...
 
int diff (int nLps, double &d) const
 Can be used to retrieve the difference between the last and a previous LP-solution in percent. More...
 
virtual bool tailOff () const
 Checks whether there is a tailing-off effect. More...
 
- Public Member Functions inherited from abacus::AbacusRoot
virtual ~AbacusRoot ()
 The destructor. More...
 

Protected Member Functions

void reset ()
 Clears the solution history. More...
 
void update (double value)
 A new LP-solution value can be stored by calling the function update(). More...
 

Protected Attributes

AbaRing< double > * lpHistory_
 The LP-values considered in the tailing off analysis. More...
 
Mastermaster_
 A pointer to the corresponding master of the optimization. More...
 

Friends

std::ostream & operator<< (std::ostream &out, const TailOff &rhs)
 The output operator. More...
 
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

Tailing off manager.

During the cutting plane phase of the optimization of a single subproblem it can be quite often observed that during the first iterations a significant decrease of the optimum value of the LP occurs, yet, this decrease becomes smaller and smaller in later iterations. This effect is called tailing off (see M. Padberg, G. Rinaldi, A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems, SIAM Review 33, pp. 60-100). Experimental results show that it might be better to branch, although violated constraints can still be generated, than to continue the cutting plane phase.

This class stores the history of the values of the last LP-solutions and implements all functions to control this tailing-off effect. The parameters are taken from the associated master.

Definition at line 57 of file tailoff.h.

Constructor & Destructor Documentation

◆ TailOff() [1/2]

abacus::TailOff::TailOff ( Master master)
inline

The constructor takes the length of the tailing off history from Master::tailOffNLp().

Parameters
masterA pointer to the corresponding master of the optimization.

Definition at line 65 of file tailoff.h.

◆ TailOff() [2/2]

abacus::TailOff::TailOff ( Master master,
int  NLp 
)
inline

An alternative constructor takes the length of the tailing off history from the parameter NLp.

Parameters
masterA pointer to the corresponding master of the optimization.
NLpThe length of the tailing off history.

Definition at line 78 of file tailoff.h.

◆ ~TailOff()

abacus::TailOff::~TailOff ( )
inline

The destructor.

Definition at line 87 of file tailoff.h.

Member Function Documentation

◆ diff()

int abacus::TailOff::diff ( int  nLps,
double &  d 
) const

Can be used to retrieve the difference between the last and a previous LP-solution in percent.

Parameters
nLpsThe number of LPs before the last solved linear program with which the last solved LP-value should be compared.
dContains the absolute difference bewteen the value of the last solved linear program and the value of the linear program solved nLps before in percent relative to the older value.
Returns
0 if the difference could be computed, i.e., the old LP-value nLPs before the last one is store in the history, 1 otherwise.

◆ reset()

void abacus::TailOff::reset ( )
inlineprotected

Clears the solution history.

This function should be called if variables are added, because normally the solution value of the LP-relaxation gets worse after the addition of variables. Such a change could falsely indicate a tailing-off effect if the history of LP-values is not reset.

Definition at line 151 of file tailoff.h.

◆ tailOff()

virtual bool abacus::TailOff::tailOff ( ) const
virtual

Checks whether there is a tailing-off effect.

We assume a tailing-off effect if during the last Master::tailOffNLps() iterations of the cutting plane algorithms the dual bound changed at most Master::tailOffPercent() percent.

Returns
true if a tailing off effect is observed, false otherwise.

◆ update()

void abacus::TailOff::update ( double  value)
inlineprotected

A new LP-solution value can be stored by calling the function update().

This update should be performed after every solution of an LP in the cutting plane generation phase of the subproblem optimization process.

Parameters
valueThe LP-solution value.

Definition at line 136 of file tailoff.h.

Friends And Related Function Documentation

◆ operator<<

std::ostream& operator<< ( std::ostream &  out,
const TailOff rhs 
)
friend

The output operator.

Writes the memorized LP-values on an output stream.

Parameters
outThe output stream.
rhsThe tailing-off manager being output.
Returns
A reference to the output stream.

◆ Sub

friend class Sub
friend

Definition at line 58 of file tailoff.h.

Member Data Documentation

◆ lpHistory_

AbaRing<double>* abacus::TailOff::lpHistory_
protected

The LP-values considered in the tailing off analysis.

Definition at line 161 of file tailoff.h.

◆ master_

Master* abacus::TailOff::master_
protected

A pointer to the corresponding master of the optimization.

Definition at line 158 of file tailoff.h.


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