1 /*!\file
2 * \author Matthias Elf
3 *
4 * \brief constraints and variables.
5 *
6 * \par License:
7 * This file is part of ABACUS - A Branch And CUt System
8 * Copyright (C) 1995 - 2003
9 * University of Cologne, Germany
10 *
11 * \par
12 * This library is free software; you can redistribute it and/or
13 * modify it under the terms of the GNU Lesser General Public
14 * License as published by the Free Software Foundation; either
15 * version 2.1 of the License, or (at your option) any later version.
16 *
17 * \par
18 * This library is distributed in the hope that it will be useful,
19 * but WITHOUT ANY WARRANTY; without even the implied warranty of
20 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
21 * Lesser General Public License for more details.
22 *
23 * \par
24 * You should have received a copy of the GNU Lesser General Public
25 * License along with this library; if not, write to the Free Software
26 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
27 *
28 * \see http://www.gnu.org/copyleft/gpl.html
29 */
30
31 #pragma once
32
33 #include <ogdf/lib/abacus/abacusroot.h>
34
35 namespace abacus {
36
37 class Master;
38 class Sub;
39 class Variable;
40 class Constraint;
41
42 template<class BaseType, class CoType> class PoolSlot;
43 template<class BaseType, class CoType> class PoolSlotRef;
44 template<class BaseType, class CoType> class StandardPool;
45 template<class BaseType, class CoType> class CutBuffer;
46
47
48 //! Common base class for constraints (Constraint) and variables (Variable).
49 /**
50 * ConVar is the common base class for constraints and variables, which
51 * are implemented in the derived classes Constraint and Variable,
52 * respectively.
53 * It might seem a bit strange to implement a common base class for
54 * these two objects. Besides several technical reasons, there is
55 * linear programming duality which motivates this point of view.
56 * E.g., the separation problem for the primal problem is equivalent
57 * to the pricing problem for the dual problem.
58 *
59 * ConVar is <b>not</b> the base class for constraints and variables
60 * as they are used in the interface to the linear programming solver.
61 * There are the classes Row and Column for this purpose. ConVar is
62 * the father of a class hierarchy for abstract constraints and
63 * variables which are used in the branch-and-bound algorithm.
64 */
65 class OGDF_EXPORT ConVar : public AbacusRoot {
66
67 friend class PoolSlot<Constraint, Variable>;
68 friend class PoolSlot<Variable, Constraint>;
69 friend class PoolSlotRef<Constraint, Variable>;
70 friend class PoolSlotRef<Variable, Constraint>;
71 friend class StandardPool<Constraint, Variable>;
72 friend class StandardPool<Variable, Constraint>;
73 friend class CutBuffer<Constraint, Variable>;
74 friend class CutBuffer<Variable, Constraint>;
75 friend class Sub;
76
77 public:
78
79 //! Creates an instance of type ConVar.
80 /**
81 * \param master A pointer to the corresponding master of the optimization.
82 * \param sub A pointer the subproblem the constraint/variable is associated with.
83 * If the item is not associated with any subproblem, then this
84 * can also be the 0-pointer.
85 * \param dynamic If this paramument is \a true, then the constraint/variable can also be
86 * removed again from the set of active constraints/variables after it is
87 * added once.
88 * \param local If \a local is \a true, then the constraint/variable is only locally
89 * valid.
90 */
ConVar(Master * master,const Sub * sub,bool dynamic,bool local)91 ConVar (Master *master, const Sub *sub, bool dynamic, bool local) :
92 master_(master),
93 sub_(sub),
94 expanded_(false),
95 nReferences_(0),
96 dynamic_(dynamic),
97 nActive_(0),
98 nLocks_(0),
99 local_(local)
100 { }
101
102 virtual ~ConVar();
103
104
105 //! Checks if the constraint/variable is active in at least one active subproblem.
106 /**
107 * \return true if the constraint/variable is active, false otherwise.
108 */
active()109 bool active() const { return (nActive_ != 0); }
110
111
112 //! Returns true if the constraint/variable is only locally valid, false otherwise.
local()113 bool local() const { return local_; }
114
115 //! Returns true if the constraint/variable is globally valid, false otherwise.
global()116 bool global() const { return !local_; }
117
118
119 //! Return true if the constraint/variable is dynamic.
120 /**
121 * \return true if the constraint/variable can be also removed from the set of active
122 * constraints/variables after it has been activated, false otherwise.
123 */
dynamic()124 virtual bool dynamic() const { return dynamic_; }
125
126
127 /**
128 * @name Expand and Compress
129 *
130 * Constraints/Variables often have to be stored in a format different
131 * from the format used in the linear program. One reason is to save
132 * memory and the other reason is that if constraints and/or variable
133 * sets are dynamic, then we require a format to compute the coefficients
134 * of later activated variables/constraints.
135 *
136 * The disadvantage of such a constraint format is that the computation
137 * of a single constraint coefficient can be very time consuming. Often
138 * it cannot be done in constant time. Hence we provide a mechanism
139 * which converts a constraint/variable to a format enabling efficient
140 * computation of coefficients. The following functions provide this
141 * feature.
142 */
143 //@{
144
145 //! Returns true if the expanded format of a constraint/variable is available, false otherwise.
expanded()146 bool expanded() const { return expanded_; }
147
148
149 //! Expands a constraint/variable.
150 /**
151 * The default implementation does nothing. It should be redefined in derived classes.
152 * Attention: Data that is compacted/compressed needs to be marked as mutable, as
153 * this function is supposed to be applicable for const objects! Compressing/expanding
154 * is NOT expected to change the "outer" status of this class, and compression/expansion
155 * is done automatically on the fly on an as-needed basis.
156 */
expand()157 virtual void expand() const { }
158
159 //! Compresses a constraint/variable.
160 /**
161 * The default implementation does nothing. It should be redefined in derived classes.
162 * Attention: Data that is compacted/compressed needs to be marked as mutable, as
163 * this function is supposed to be applicable for const objects! Compressing/expanding
164 * is NOT expected to change the "outer" status of this class, and compression/expansion
165 * is done automatically on the fly on an as-needed basis.
166 */
compress()167 virtual void compress() const { }
168
169 //! Returns true if the constraint/variable can be destructed.
170 /**
171 * This is per default only possible if the reference counter is 0 and no lock is set.
172 * The function is declared virtual such that problem specific implementations are possible.
173 */
deletable()174 virtual bool deletable() const {
175 return !(nReferences_ || nLocks_);
176 }
177
178 //@}
179
180 //! Writes the constraint/variable to the output stream \a out.
181 /**
182 * This function is used since the output operator cannot be declared
183 * virtual. The default implementation only writes
184 * <tt>"ConVar::print() is only a dummy."</tt>.
185 * We do not declare this function pure virtual since it is not really
186 * required, mainly only for debugging. In this case a constraint/variable
187 * specific redefinition is strongly recommended.
188 *
189 * Normally, the implementation <tt>out << *this</tt> should be sufficient.
190 *
191 * \param out The output stream.
192 */
193 virtual void print(std::ostream &out) const;
194
195 //! Returns a const pointer to the subproblem associated with the constraint/variable.
196 /**
197 * Note, this can also be the 0-pointer.
198 */
sub()199 const Sub *sub() const { return sub_; }
200
201
202 //! Associates a new subproblem with the constraint/variable.
203 /**
204 * \param sub The new subproblem associated with the constraint/variable.
205 */
sub(Sub * sub)206 void sub(Sub *sub) { sub_ = sub; }
207
208
209 //! Should provide a key for the constraint/variable that can be used to insert it into a hash table.
210 /**
211 * As usual for hashing, it is not required that any two items have
212 * different keys.
213 *
214 * This function is required if the constraint/variable is stored in a
215 * pool of the class NonDuplPool.
216 *
217 * The default implementation just throws an exception.
218 * This function is not a pure virtual function because in the default
219 * version of ABACUS it is not required.
220 *
221 * We do not use \a double as result type because typical problems in
222 * floating point arithmetic might give slightly different hash keys
223 * for two constraints that are equal from a mathematical point of
224 * view.
225 *
226 * \return An integer providing a hash key for the constraint/variable.
227 */
228 virtual unsigned hashKey() const;
229
230 //! Should return the name of the constraint/variable.
231 /**
232 * This function is required to emulate a simple
233 * run time type information (RTTI) that is still missing in g++.
234 * This function will be removed as soon as RTTI is supported sufficiently.
235 *
236 * A user must take care that for each redefined version of this
237 * function in a derived class a unique name is returned. Otherwise
238 * fatal run time errors can occur. Therefore, we recommend to return
239 * always the name of the class.
240 *
241 * This function is required if the constraint/variable is stored in a
242 * pool of the class NonDuplPool.
243 *
244 * The default implementation shows a warning and throws an exception.
245 * This function is not a pure virtual function because in the default
246 * version of ABACUS it is not required.
247 *
248 * \return The name of the constraint/variable.
249 */
250 virtual const char *name() const;
251
252 //! Should compare if the constraint/variable is identical (in a mathematical sense) with the constraint/variable \a cv.
253 /**
254 * Using RTTI or its emulation provided by the function name()
255 * it is sufficient to implement this functions for
256 * constraints/variables of the same type.
257 *
258 * This function is required if the constraint/variable is stored in a
259 * pool of the class NonDuplPool.
260 *
261 * The default implementation shows a warning and throws an exception.
262 * This function is not a pure virtual function because in the default
263 * version of ABACUS it is not required.
264 *
265 * \param cv The constraint/variable that should be compared with this object.
266 *
267 * \return true If the constraint/variable represented by this object
268 * represents the same item as the constraint/variable \a cv,
269 * false otherwise.
270 */
271 virtual bool equal(const ConVar *cv) const;
272
273 //! The function should return a rank associated with the constraint/variable.
274 /**
275 * The default implementation returns 0.
276 *
277 * \return The rank of the constraint/variable.
278 */
rank()279 virtual double rank() const { return 0; }
280
281 protected:
282
283 Master *master_; //!< A pointer to the corresponding master of the optimization.
284
285 //! A pointer to the subproblem associated with the constraint/variable.
286 /**
287 * This may be also the 0-pointer.
288 */
289 const Sub *sub_;
290
291 mutable bool expanded_; //!< true, if expanded version of constraint/variables available. [mutable in const-objects to allow compress/expand on const]
292
293 int nReferences_; //!< The number of references to the pool slot the constraint is stored in.
294
295 /**
296 * If this member is \a true then the constraint/variable can be also removed from the active formulation
297 * after it is added the first time. For constraints/variables which should be
298 * never removed from the active formulation this member should be set to \a false.
299 */
300 bool dynamic_;
301
302 //! The number of active subproblems of which the constraint/variable belongs to the set of active constraints/variables.
303 /**
304 * This value is always 0 after construction and has to be set and reset during the subproblem
305 * optimization. This member is mainly used to accelerate pool separation and to control that the same variable
306 * is not multiply included into a set of active variables.
307 */
308 int nActive_;
309
310 int nLocks_; //!< The number of locks which have been set on the constraint/variable.
311
312 bool local_; //!< true if the constraint/variable is only locally valid
313
314 private:
315
316 //! Tries to generate the expanded format of the constraint/variable.
317 /**
318 * This will be only possible if the virtual
319 * function expand() is redefined for the specific constraint/variable.
320 */
321 void _expand() const;
322
323
324 //! Removes the expanded format of the constraint/variable.
325 /**
326 * This will be only possible if the virtual
327 * function \a compress() is redefined for the specific constraint/variable.
328 */
329 void _compress() const;
330
331 //! Must be called if the constraint/variable is added to the active formulation of an active subproblem.
332 /**
333 * This function is only called within member functions of the class Sub.
334 */
activate()335 void activate() { ++nActive_; }
336
337
338 //! Counterpart of activate().
339 /**
340 * Is also called within members of the class Sub to indicate
341 * that the constraint/variable does not belong any more to the active
342 * formulation of an active subproblem.
343 */
344 void deactivate();
345
346 //! Returns the number of references to the pool slot PoolSlotRef storing this constraint/variable.
347 /**
348 * We require the bookkeeping of the references in order to determine
349 * if a constraint/variable can be deleted without causing any harm.
350 */
nReferences()351 int nReferences() const { return nReferences_; }
352
353
354 //! Indicates that there is a new reference to the pool slot storing this constraint/variable.
355 /**
356 * The function is only called from members of the class PoolSlotRef.
357 */
addReference()358 void addReference() { ++nReferences_; }
359
360
361 //! Is the counterpart of the function addReference() and indicates the removal of a reference to this constraint.
362 /**
363 * It is only called from members of the class PoolSlotRef.
364 */
365 void removeReference();
366
367 /** @name Locking
368 *
369 * If a constraint/variable has just been separated and added to
370 * the buffer of currently separated constraints/variables, then
371 * this item should not be removed before the buffer is emptied
372 * at the beginning of the next iteration. Hence, we provide a
373 * locking mechanism for constraints/variables by the following
374 * three functions.
375 */
376 //@{
377
378 //! Returns true if at least one lock is set on the constraint/variable, false otherwise.
locked()379 bool locked() const { return (nLocks_ != 0); }
380
381
382 //! Adds an additional lock to the constraint/variable.
lock()383 void lock() { ++nLocks_; }
384
385
386 //! Removes one lock from the constraint/variable.
387 void unlock();
388
389 //@}
390 };
391
392
~ConVar()393 inline ConVar::~ConVar()
394 {
395 #ifdef OGDF_DEBUG
396 if (nActive_) {
397 Logger::ifout() << "ConVar::~ConVar(): constraint/variable still active: \ncounter = " << nActive_ << "\n";
398 }
399
400 if (nLocks_) {
401 Logger::ifout() << "ConVar::~ConVar(): constraint/variable has still " << nLocks_ << " locks\n";
402 }
403
404 #ifndef OGDF_USE_ASSERT_EXCEPTIONS // do not throw exceptions in destructor
405 OGDF_ASSERT(nActive_ == 0);
406 OGDF_ASSERT(nLocks_ == 0);
407 #endif
408 #endif
409 }
410
411
deactivate()412 inline void ConVar::deactivate()
413 {
414 OGDF_ASSERT(nActive_ != 0);
415 --nActive_;
416 }
417
418
removeReference()419 inline void ConVar::removeReference()
420 {
421 if(--nReferences_ < 0) {
422 Logger::ifout() << "ConVar::removeReference : reference counter negative\n";
423 OGDF_THROW_PARAM(AlgorithmFailureException, ogdf::AlgorithmFailureCode::Convar);
424 }
425 }
426
427
unlock()428 inline void ConVar::unlock()
429 {
430 OGDF_ASSERT(nLocks_ != 0);
431 --nLocks_;
432 }
433
434
435 }
436