1 /*!\file 2 * \author Matthias Elf 3 * \brief tailing off manager. 4 * 5 * \par License: 6 * This file is part of ABACUS - A Branch And CUt System 7 * Copyright (C) 1995 - 2003 8 * University of Cologne, Germany 9 * 10 * \par 11 * This library is free software; you can redistribute it and/or 12 * modify it under the terms of the GNU Lesser General Public 13 * License as published by the Free Software Foundation; either 14 * version 2.1 of the License, or (at your option) any later version. 15 * 16 * \par 17 * This library is distributed in the hope that it will be useful, 18 * but WITHOUT ANY WARRANTY; without even the implied warranty of 19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 20 * Lesser General Public License for more details. 21 * 22 * \par 23 * You should have received a copy of the GNU Lesser General Public 24 * License along with this library; if not, write to the Free Software 25 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 26 * 27 * \see http://www.gnu.org/copyleft/gpl.html 28 */ 29 30 #pragma once 31 32 #include <ogdf/lib/abacus/ring.h> 33 #include <ogdf/lib/abacus/master.h> 34 35 namespace abacus { 36 37 38 //! Tailing off manager. 39 /** 40 * During the cutting plane phase of the optimization of a single 41 * subproblem it can be quite often observed that during the first 42 * iterations a significant decrease of the optimum value of the 43 * LP occurs, yet, this decrease becomes smaller and 44 * smaller in later iterations. This effect is called 45 * <i>tailing off</i> (see M. Padberg, G. Rinaldi, A branch-and-cut 46 * algorithm for the resolution of large-scale symmetric traveling 47 * salesman problems, SIAM Review 33, pp. 60-100). 48 * Experimental results show that it might 49 * be better to branch, although violated constraints can still 50 * be generated, than to continue the cutting plane phase. 51 * 52 * This class stores the history of the values of the last 53 * LP-solutions and implements all functions to control this 54 * tailing-off effect. 55 * The parameters are taken from the associated master. 56 */ 57 class TailOff : public AbacusRoot { 58 friend class Sub; 59 public: 60 61 //! The constructor takes the length of the tailing off history from Master::tailOffNLp(). 62 /** 63 * \param master A pointer to the corresponding master of the optimization. 64 */ TailOff(Master * master)65 TailOff(Master *master) : master_(master) 66 { 67 if (master->tailOffNLp() > 0) 68 lpHistory_ = new AbaRing<double>(master->tailOffNLp()); 69 else 70 lpHistory_ = nullptr; 71 } 72 73 //! An alternative constructor takes the length of the tailing off history from the parameter NLp. 74 /** 75 * \param master A pointer to the corresponding master of the optimization. 76 * \param NLp The length of the tailing off history. 77 */ TailOff(Master * master,int NLp)78 TailOff(Master *master, int NLp) : master_(master) 79 { 80 if (NLp > 0) 81 lpHistory_ = new AbaRing<double>(NLp); 82 else 83 lpHistory_ = nullptr; 84 } 85 86 //! The destructor. ~TailOff()87 ~TailOff() { delete lpHistory_; } 88 89 90 //! The output operator 91 /** 92 * Writes the memorized LP-values on an output stream. 93 * 94 * \param out The output stream. 95 * \param rhs The tailing-off manager being output. 96 * 97 * \return A reference to the output stream. 98 */ 99 friend std::ostream &operator<<(std::ostream &out, const TailOff &rhs); 100 101 //! Checks whether there is a tailing-off effect. 102 /** 103 * We assume a tailing-off effect if during the last Master::tailOffNLps() 104 * iterations of the cutting plane algorithms 105 * the dual bound changed at most Master::tailOffPercent() percent. 106 * 107 * \return true if a tailing off effect is observed, false otherwise. 108 */ 109 virtual bool tailOff() const; 110 111 //! Can be used to retrieve the difference between the last and a previous LP-solution in percent. 112 /** 113 * \param nLps The number of LPs before the last solved linear program 114 * with which the last solved LP-value should be compared. 115 * \param d Contains the absolute difference bewteen the value of the 116 * last solved 117 * linear program and the value of the linear program solved 118 * \a nLps before in percent relative to the older value. 119 * 120 * \return 0 if the difference could be computed, i.e., the old 121 * LP-value \a nLPs before the last one is store in the history, 122 * 1 otherwise. 123 */ 124 int diff(int nLps, double &d) const; 125 126 protected: 127 128 //! A new LP-solution value can be stored by calling the function \a update(). 129 /** 130 * This update should be performed after every solution 131 * of an LP in the cutting plane generation phase of the subproblem 132 * optimization process. 133 * 134 * \param value The LP-solution value. 135 */ update(double value)136 void update(double value) { 137 if (lpHistory_) 138 lpHistory_->insert(value); 139 } 140 141 142 //! Clears the solution history. 143 /** 144 * This function 145 * should be called if variables are added, because 146 * normally the solution value of the LP-relaxation gets worse 147 * after the addition of variables. Such a 148 * change could falsely indicate a tailing-off effect if the 149 * history of LP-values is not reset. 150 */ reset()151 void reset() { 152 if (lpHistory_) 153 lpHistory_->clear(); 154 } 155 156 157 //! A pointer to the corresponding master of the optimization. 158 Master *master_; 159 160 //! The LP-values considered in the tailing off analysis. 161 AbaRing<double> *lpHistory_; 162 }; 163 164 } 165