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...
Master *	master_
	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

master

A 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

master	A pointer to the corresponding master of the optimization.
NLp	The 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

nLps	The number of LPs before the last solved linear program with which the last solved LP-value should be compared.
d	Contains 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

value

The 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

out	The output stream.
rhs	The 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:

• include/ogdf/lib/abacus/tailoff.h