|
|||
|
|
|
|||
|
|
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(). | |
| TailOff (Master *master, int NLp) | |
| An alternative constructor takes the length of the tailing off history from the parameter NLp. | |
| ~TailOff () | |
| The destructor. | |
| int | diff (int nLps, double &d) const |
| Can be used to retrieve the difference between the last and a previous LP-solution in percent. | |
| virtual bool | tailOff () const |
| Checks whether there is a tailing-off effect. | |
| Public Member Functions inherited from abacus::AbacusRoot | |
| virtual | ~AbacusRoot () |
| The destructor. | |
Protected Member Functions | |
| void | reset () |
| Clears the solution history. | |
| void | update (double value) |
| A new LP-solution value can be stored by calling the function update(). | |
Protected Attributes | |
| AbaRing< double > * | lpHistory_ |
| The LP-values considered in the tailing off analysis. | |
| Master * | master_ |
| A pointer to the corresponding master of the optimization. | |
Friends | |
| std::ostream & | operator<< (std::ostream &out, const TailOff &rhs) |
| The output operator. | |
| 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. | |
| static bool | endsWith (const string &str, const string &end) |
| Returns true if str ends with end, false otherwise. | |
| static double | fracPart (double x) |
| Returns the absolute value of the fractional part of x. | |
| static const char * | onOff (bool value) |
| Converts a boolean variable to the strings "on" and "off". | |
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.
|
inline |
The constructor takes the length of the tailing off history from Master::tailOffNLp().
| master | A pointer to the corresponding master of the optimization. |
Can be used to retrieve the difference between the last and a previous LP-solution in percent.
| 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. |
|
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.
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.
The output operator.
Writes the memorized LP-values on an output stream.
| out | The output stream. |
| rhs | The tailing-off manager being output. |
|
protected |
