1 /*!\file
2 * \author Matthias Elf
3 * \brief the master of the optimization.
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/global.h>
33 #include <ogdf/lib/abacus/optsense.h>
34
35 #include <ogdf/lib/abacus/hash.h>
36 #include <ogdf/basic/Stopwatch.h>
37
38
39 class OsiSolverInterface;
40
41 namespace abacus {
42
43
44 class Sub;
45 class BranchRule;
46 class Variable;
47 class Constraint;
48
49 class History;
50 class OpenSub;
51 class FixCand;
52 class LpMasterOsi;
53
54 template<class BaseType, class CoType> class StandardPool;
55
56
57 //! The master of the optimization.
58 /**
59 * As the name already indicates, the class Master is the central
60 * object of the framework. The most important tasks of the class Master
61 * is the management of the implicit enumeration. Moreover, it provides already
62 * default implementations for constraints, cutting planes, and
63 * variables pools. The class Master also stores various parameter
64 * settings and compiles statistics about the solution process.
65 *
66 * The class Master is an abstract class from which a problem specific
67 * master has to be derived.
68 */
69 class OGDF_EXPORT Master : public AbacusGlobal {
70
71 friend class Sub;
72 friend class FixCand;
73
74 public:
75
76 //! The various statuses of the optimization process.
77 enum STATUS {
78 Optimal, /*!< The optimization terminated with an error and without reaching
79 * one of the resource limits. If there is a feasible solution then the
80 * optimal solution has been computed. */
81 Error, /*!< An error occurred during the optimization process. */
82 OutOfMemory,
83 Unprocessed, /*!< The initial status, before the optimization starts. */
84 Processing, /*!< The status while the optimization is performed. */
85 Guaranteed, /*!< If the optimal solution is not determined but the required guarantee
86 * is reached, then the status is \a Guaranteed. */
87 MaxLevel, /*!< The status, if subproblems are ignored since the maximum enumeration level is exceeded. */
88 MaxCpuTime, /*!< The status, if the optimization terminates since the maximum cpu time is exceeded. */
89 MaxNSub, /*!< The status, if the optimization terminates since the maximum number of subproblems is reached. */
90 MaxCowTime, /*!< The status, if the optimization terminates since the maximum wall-clock time is exceeded. */
91 ExceptionFathom /*!< The status, if at least one subproblem has been fathomed according to a
92 * problem specific criteria determined in the function Sub::exceptionFathom(). */
93 };
94
95 //! Literal values for the enumerators of the corresponding enumeration type.
96 /**
97 * The order of the enumerators is preserved (e.g., <tt>STATUS_[0]=="Optimal"</tt>).
98 */
99 static const char* STATUS_[];
100
101
102 //! The enumeration defining the different enumeration strategies for the branch and bound algorithm.
103 enum ENUMSTRAT {
104 BestFirst, /*!< Best-first search, i.e., select the subproblem with best dual
105 * bound, i.e., the subproblem having minimal dual bound for a minimization
106 * problem, or the subproblem having maximal dual bound for a maximization problem. */
107 BreadthFirst, /*!< Breadth-first search, i.e., select the subproblem with minimal level in the enumeration tree. */
108 DepthFirst, /*!< Depth-first search, i.e., select the subproblem with maximal level in the enumeration tree. */
109 DiveAndBest /*!< As long as no primal feasible solution is known the next subproblem is selected according
110 * to the depth-first search strategy, otherwise the best-first search strategy is applied. */
111 };
112
113 //! Literal values for the enumerators of the corresponding enumeration type.
114 /**
115 * The order of the enumerators is preserved (e.g., <tt>ENUMSTRAT_[0]=="BestFirst"</tt>).
116 */
117 static const char *ENUMSTRAT_[];
118
119 //! This enumeration defines the two currently implemented branching variable selection strategies.
120 enum BRANCHINGSTRAT {
121 CloseHalf, /*!< Selects the variable with fractional part closest to 0.5. */
122 CloseHalfExpensive /*!< Selects the variable with fractional part close to 0.5 (within some
123 * interval around 0.5) and has highest absolute objective function coefficient. */
124 };
125
126 //! Literal values for the enumerators of the corresponding enumeration type.
127 /**
128 * The order of the enumerators is preserved (e.g., <tt>BRANCHINGSTRAT_[0]=="CloseHalf"</tt>).
129 */
130 static const char *BRANCHINGSTRAT_[];
131
132 //! This enumeration provides various methods for the initialization of the primal bound.
133 /**
134 * The modes \a OptimalPrimalBound and \a OptimalOnePrimalBound can be useful in the testing phase.
135 * For these modes the value of an optimum solution must stored in the file given
136 * by the parameter <tt>OptimumFileName</tt> in the parameter file.
137 */
138 enum PRIMALBOUNDMODE {
139 NoPrimalBound, /*!< The primal bound is initialized with \f$-\infty\f$ for maximization problems and
140 * \f$\infty\f$ for minimization problems, respectively. */
141 Optimum, /*!< The primal bound is initialized with the value of the optimum solution. */
142 OptimumOne /*!< The primal bound is initialized with the value of optimum solution minus 1 for maximization problems
143 * and with the value of the optimum solution plus one for minimization problems, respectively. */
144 };
145
146 //! Literal values for the enumerators of the corresponding enumeration type.
147 /**
148 * The order of the enumerators is preserved (e.g., <tt>PRIMALBOUNDMODE_[0]=="None"</tt>).
149 */
150 static const char* PRIMALBOUNDMODE_[];
151
152 //! The way nodes are skipped for the generation of cuts.
153 enum SKIPPINGMODE{
154 SkipByNode, /*!< Cuts are only generated in every <tt>SkipFactor</tt> subproblem, where
155 * <tt>SkipFactor</tt> can be controlled with the parameter file <tt>.abacus</tt>. */
156 SkipByLevel /*!< Cuts are only generated in every <tt>SkipFactor</tt> level of the enumeration tree. */
157 };
158
159 //! Literal values for the enumerators of the corresponding enumeration type.
160 /**
161 * The order of the enumerators is preserved (e.g., <tt>SKIPPINGMODE_[0]=="None"</tt>).
162 */
163 static const char* SKIPPINGMODE_[];
164
165 //! This enumeration defines the ways for automatic constraint elimination during the cutting plane phase.
166 enum CONELIMMODE {
167 NoConElim, /*!< No constraints are eliminated. */
168 NonBinding, /*!< Nonbinding constraints are eliminated. */
169 Basic /*!< Constraints with basic slack variable are eliminated. */
170 };
171
172
173 //! Literal values for the enumerators of the corresponding enumeration type.
174 /**
175 * The order of the enumerators is preserved (e.g., <tt>CONELIMMODE_[0]=="None"</tt>).
176 */
177 static const char* CONELIMMODE_[];
178
179 //! This enumeration defines the ways for automatic variable elimination during the column generation algorithm.
180 enum VARELIMMODE {
181 NoVarElim, /*!< No variables are eliminated. */
182 ReducedCost /*!< Variables with high absolute reduced costs are eliminated. */
183 };
184
185 //! Literal values for the enumerators of the corresponding enumeration type.
186 /**
187 * The order of the enumerators is preserved (e.g., <tt>VARELIMMODE_[0]=="None"</tt>).
188 */
189 static const char* VARELIMMODE_[];
190
191 //! This enumeration defines what kind of output can be generated for the VBCTOOL.
192 enum VBCMODE {
193 NoVbc, /*!< No output for the tree interface. */
194 File, /*!< Output for the tree interface is written to a file. */
195 Pipe /*!< Output for the tree interface is pipeed to the standard output. */
196 };
197
198 //! Literal values for the enumerators of the corresponding enumeration type.
199 /**
200 * The order of the enumerators is preserved (e.g., <tt>VBCMODE_[0]=="None"</tt>).
201 */
202 static const char* VBCMODE_[];
203
204
205 //! This enumeration defines which solvers can be used to solve the LP-relaxations.
206 /**
207 * These are all solvers supported by OSI, see https://projects.coin-or.org/Osi .
208 */
209 enum OSISOLVER { Cbc, Clp, CPLEX, DyLP, FortMP, GLPK, MOSEK, OSL, SoPlex, SYMPHONY, XPRESS_MP, Gurobi, Csdp };
210
211 //! Array for the literal values for possible Osi solvers.
212 static const char* OSISOLVER_[];
213
214 //! The constructor.
215 /**
216 * The members \a primalBound_ and \a dualBound_ stay uninitialized
217 * since this can only be done when the sense of optimization
218 * (minimization or maximization) is known. The initialization
219 * is performed automatically in the function \a optimize().
220 *
221 * \param problemName The name of the problem being solved. Must not be a 0-pointer.
222 * \param cutting If \a true, then cutting planes can be generated if the function
223 * Sub::separate() is redefined.
224 * \param pricing If \a true, then inactive variables are priced in, if the function
225 * Sub::pricing() is redefined.
226 * \param optSense The sense of the optimization. The default value is OptSense::Unknown.
227 * If the sense is unknown when this constructor is called, e.g., if it is
228 * read from a file in the constructor of the derived class, then it must
229 * be initialized in the constructor of the derived class.
230 * \param eps The zero-tolerance used within all member functions of objects which
231 * have a pointer to this master (default value \a 1.0e-4).
232 * \param machineEps The machine dependent zero tolerance (default value \a 1.0e-7).
233 * \param infinity All values greater than \a infinity are regarded as "infinite big",
234 * all values less than \a -infinity are regarded as "infinite small"
235 * (default value \a 1.0e30).
236 * \param readParamFromFile If true, then the parameter file <tt>.abacus</tt> is read,
237 * otherwise the parameters are initialized with default values (default \a true).
238 */
239 Master(const char *problemName, bool cutting, bool pricing,
240 OptSense::SENSE optSense = OptSense::Unknown,
241 double eps = 1.0e-4, double machineEps = 1.0e-7,
242 double infinity = 1.0e30,
243 bool readParamFromFile = false);
244
245 //! The destructor.
246 virtual ~Master();
247
248 //! Performs the optimization by branch-and-bound.
249 /**
250 * \return The status of the optimization.
251 */
252 STATUS optimize();
253
254 /*! @name Bounds
255 *
256 * In order to embed both minimization and maximization problems in this
257 * system we work internally with primal bounds, i.e., a value which
258 * is worse than the best known solution (often a value of a feasible
259 * solution), and dual bounds, i.e., a bound
260 * which is better than the best known solution. Primal and dual bounds
261 * are then interpreted as lower or upper bounds according to the
262 * sense of the optimization.
263 *
264 */
265 //@{
266
267 //! Returns the value of the global lower bound.
268 double lowerBound() const;
269
270 //! Returns the value of the global upper bound.
271 double upperBound() const;
272
273 //! Returns the value of the primal bound.
274 /**
275 * I.e., the \a lowerBound() for a maximization problem and the
276 * \a upperBound() for a minimization problem, respectively.
277 */
primalBound()278 double primalBound() const { return primalBound_; }
279
280 //! Sets the primal bound to \a x and makes a new entry in the solution history.
281 /**
282 * It is an error if the primal bound gets worse.
283 *
284 * \param x The new value of the primal bound.
285 */
286 void primalBound(double x);
287
288 //! Returns the value of the dual bound.
289 /**
290 * I.e., the \a upperBound() for a maximization problem and the
291 * \a lowerBound() for a minimization problem, respectively.
292 */
dualBound()293 double dualBound() const { return dualBound_; }
294
295 //! Sets the dual bound to \a x and makes a new entry in the solution history.
296 /**
297 * It is an error if the dual bound gets worse.L
298 *
299 * \param x The new value of the dual bound.
300 */
301 void dualBound(double x);
302
303 //! Returns true if \a x is better than the best known dual bound; false otherwise.
304 /**
305 * \param x The value being compared with the best know dual bound.
306 */
307 bool betterDual(double x) const;
308
309 //! Can be used to compare a value with the one of the best known primal bound.
310 /**
311 * If the objective function values of all feasible solutions are
312 * integer, then we do not have to be so carefully.
313 *
314 * \param x The value being compared with the primal bound.
315 *
316 * \return true If \a x is not better than the best known primal bound, false otherwise.
317 */
318 bool primalViolated(double x) const;
319
320 //! Can be used to check if a value is better than the best know primal bound.
321 /**
322 * \param x The value compared with the primal bound.
323 *
324 * \return true If \a x is better than the best known primal bound, false otherwise.
325 */
326 bool betterPrimal(double x) const;
327
328 //! Returns the dual bound at the root node.
rootDualBound()329 double rootDualBound() const { return rootDualBound_; }
330
331 //! We use this function, e.g., to adapt the enumeration strategy in the \a DiveAndBest-Strategy.
332 /***
333 * This function is only correct if any primal bound better than plus/minus infinity corresponds
334 * to a feasible solution.
335 *
336 * \return true If a feasible solution of the optimization problem has been found, false otherwise.
337 */
338 bool feasibleFound() const;
339 //@}
340
341 //! Returns the enumeration strategy.
enumerationStrategy()342 ENUMSTRAT enumerationStrategy() const { return enumerationStrategy_; }
343
344 //! Changes the enumeration strategy to \a strat.
345 /**
346 * \param strat The new enumeration strategy.
347 */
enumerationStrategy(ENUMSTRAT strat)348 void enumerationStrategy(ENUMSTRAT strat) { enumerationStrategy_ = strat; }
349
350 /**
351 * Analyzes the enumeration strategy set in the parameter file <tt>.abacus</tt>
352 * and calls the corresponding comparison function for the subproblems
353 * \a s1 and \a s2. This function should be redefined for application
354 * specific enumeration strategies.
355 *
356 * \return 1 If \a s1 has higher priority than \a s2;
357 * \return -1 if \a s2 has higher priority it returns -1; and
358 * \return 0 if both subproblems have equal priority.
359 *
360 * \param s1 A pointer to a subproblem.
361 * \param s2 A pointer to a subproblem.
362 */
363 virtual int enumerationStrategy(const Sub *s1, const Sub *s2);
364
365 //! Can be used to check if the guarantee requirements are fulfilled.
366 /**
367 * I.e., the difference between upper bound and the lower bound in respect to the lowerBound
368 * is less than this guarantee value in percent.
369 *
370 * If the lower bound is zero, but the upper bound is nonzero,
371 * we cannot give any guarantee.
372 *
373 * \warning A guarantee for a solution can only be given if the
374 * pricing problem is solved exactly or no column generation is performed
375 * at all.
376 *
377 * \return true If the guarantee requirements are fulfilled, false otherwise.
378 */
379 bool guaranteed() const;
380
381 //! Can be used to access the guarantee which can be given for the best known feasible solution.
382 /**
383 * It is an error to call this function if the lower bound is zero, but the upper bound
384 * is nonzero.
385 *
386 * \return The guarantee for best known feasible solution in percent.
387 */
388 double guarantee() const;
389
390 //! Writes the guarantee nicely formated on the output stream associated with this object.
391 /**
392 * If no bounds are available, or the lower bound is zero, but the
393 * upper bound is nonzero, then we cannot give any guarantee.
394 */
395 void printGuarantee() const;
396
397 //! Can be used to control the correctness of the optimization if the value of the optimum solution has been loaded.
398 /**
399 * This is done, if a file storing the optimum value is specified with
400 * the parameter <tt>OptimumFileName</tt> in the configuration file
401 * <tt>.abacus</tt>.
402 *
403 * \return true If the optimum solution of the problem is known and equals the primal bound,
404 * false otherwise.
405 */
406 bool check() const;
407
408 /**
409 * Opens the file specified with the parameter <tt>OptimumFileName</tt> in the configuration
410 * file <tt>.abacus</tt> and tries to find a line
411 * with the name of the problem instance (as specified in the
412 * constructor of Master) as first string.
413 *
414 * \param optVal If the return value is \a true, then \a optVal holds the
415 * optimum value found in the line with the name of the problem instance
416 * as first string. Otherwise, \a optVal is undefined.
417 *
418 * \return true If a line with \a problemName_ has been found, false otherwise.
419 */
420 bool knownOptimum(double &optVal) const;
421
422 //! Does nothing but can be redefined in derived classes for output before the timing statistics.
output()423 virtual void output() const { }
424
425 /**
426 * \return true If \a cutting has been set to \a true in the call of the
427 * constructor of the class Master, i.e., if cutting
428 * planes should be generated in the subproblem optimization;
429 * false otherwise.
430 */
cutting()431 bool cutting() const { return cutting_; }
432
433 /**
434 * \return true If \a pricing has been set to true in the call of the
435 * constructor of the class Master, i.e., if a columns
436 * should be generated in the subproblem optimization;
437 * false otherwise.
438 */
pricing()439 bool pricing() const { return pricing_; }
440
441 //! Returns a pointer to the object holding the optimization sense of the problem.
optSense()442 const OptSense *optSense() const { return &optSense_; }
443
444 //! Returns a pointer to the object storing the solution history of this branch and cut problem.
history()445 History *history() const { return history_; }
446
447 //! Returns a pointer to the set of open subproblems.
openSub()448 OpenSub *openSub() const { return openSub_; }
449
450 //! Returns a pointer to the default pool storing the constraints of the problem formulation.
conPool()451 StandardPool<Constraint, Variable> *conPool() const { return conPool_; }
452
453 //! Returns a pointer to the default pool for the generated cutting planes.
cutPool()454 StandardPool<Constraint, Variable> *cutPool() const { return cutPool_; }
455
456 //! Returns a pointer to the default pool storing the variables.
varPool()457 StandardPool<Variable, Constraint> *varPool() const { return varPool_; }
458
459 //! Can be used to access the root node of the branch-and-bound tree.
460 /**
461 * \return A pointer to the root node of the enumeration tree.
462 */
root()463 Sub *root() const { return root_; }
464
465 /**
466 * \return A pointer to the root of the remaining branch-and-bound tree,
467 * i.e., the subproblem which is an ancestor of all open
468 * subproblems and has highest level in the tree.
469 */
rRoot()470 Sub *rRoot() const { return rRoot_; }
471
472 //! Returns the status of the Master.
status()473 STATUS status() const { return status_; }
474
475 //! Returns the name of the instance being optimized (as specified in the constructor of this class).
problemName()476 const string &problemName() const { return problemName_; }
477
478 //! Returns a pointer to the timer measuring the total wall clock time.
totalCowTime()479 const ogdf::StopwatchWallClock *totalCowTime() const { return &totalCowTime_; }
480
481 //! True, if an approximative solver should be used.
solveApprox()482 inline bool solveApprox() const { return solveApprox_; }
483
484 //! returns a pointer to the timer measuring the total cpu time for the optimization.
totalTime()485 const ogdf::StopwatchCPU *totalTime() const { return &totalTime_; }
486
487 //! Returns a pointer to the timer measuring the cpu time spent in members of the LP-interface.
lpTime()488 const ogdf::StopwatchCPU *lpTime() const { return &lpTime_; }
489
490 //! Return a pointer to the timer measuring the cpu time required by the LP solver.
lpSolverTime()491 const ogdf::StopwatchCPU *lpSolverTime() const { return &lpSolverTime_; }
492
493 //! Returns a pointer to the timer measuring the cpu time spent in the separation of cutting planes.
separationTime()494 const ogdf::StopwatchCPU *separationTime() const { return &separationTime_; }
495
496 //! Returns a pointer to the timer measuring the cpu time spent in the heuristics for the computation of feasible solutions.
improveTime()497 const ogdf::StopwatchCPU *improveTime() const { return &improveTime_; }
498
499 //! Returns a pointer to the timer measuring the cpu time spent in pricing.
pricingTime()500 const ogdf::StopwatchCPU *pricingTime() const { return &pricingTime_; }
501
502 //! Returns a pointer to the timer measuring the cpu time spent in finding and selecting the branching rules.
branchingTime()503 const ogdf::StopwatchCPU *branchingTime() const { return &branchingTime_; }
504
505 //! returns the number of generated subproblems.
nSub()506 int nSub() const { return nSub_; }
507
508 //! Returns the number of optimized linear programs (only LP-relaxations).
nLp()509 int nLp() const { return nLp_; }
510
511 //! Returns the highest level in the tree which has been reached during the implicit enumeration.
highestLevel()512 int highestLevel() const { return highestLevel_; }
513
514 //! Returns the number of root changes of the remaining branch-and-cut tree.
nNewRoot()515 int nNewRoot() const { return nNewRoot_; }
516
517 //! Returns the number of subproblems which have already been selected from the set of open subproblems.
nSubSelected()518 int nSubSelected() const { return nSubSelected_; }
519
520 //! Writes all parameters of the class Master together with their values to the global output stream.
521 void printParameters() const;
522
523 //! Returns the branching strategy.
branchingStrategy()524 BRANCHINGSTRAT branchingStrategy() const { return branchingStrategy_; }
525
526 //! Changes the branching strategy to \a strat.
527 /**
528 * \param strat The new branching strategy.
529 */
branchingStrategy(BRANCHINGSTRAT strat)530 void branchingStrategy(BRANCHINGSTRAT strat) { branchingStrategy_ = strat; }
531
532 //! returns the Lp Solver.
defaultLpSolver()533 OSISOLVER defaultLpSolver() const { return defaultLpSolver_; }
534
535 //! Changes the default Lp solver to \a osiSolver.
536 /**
537 * \param osiSolver The new solver.
538 */
defaultLpSolver(OSISOLVER osiSolver)539 void defaultLpSolver(OSISOLVER osiSolver) { defaultLpSolver_ = osiSolver; }
540
lpMasterOsi()541 LpMasterOsi *lpMasterOsi() const { return lpMasterOsi_; }
542
543 //! Returns the number of variables that should be tested for the selection of the branching variable.
nBranchingVariableCandidates()544 int nBranchingVariableCandidates() const { return nBranchingVariableCandidates_; }
545
546 //! Sets the number of tested branching variable candidates to \a n.
547 /**
548 * \param n The new value of the number of tested variables for
549 * becoming branching variable.
550 */
551 void nBranchingVariableCandidates(int n);
552
553 //! The number of simplex iterations that are performed when testing candidates for branching variables within strong branching.
nStrongBranchingIterations()554 int nStrongBranchingIterations() const { return nStrongBranchingIterations_; }
555
556 //! Sets the number of simplex iterations that are performed when testing candidates for branching variables within strong branching.
557 /**
558 * \param n The new value of the number of simplex iterations.
559 */
560 void nStrongBranchingIterations(int n);
561
562 //! The guarantee specification for the optimization.
requiredGuarantee()563 double requiredGuarantee() const { return requiredGuarantee_; }
564
565 //! Changes the guarantee specification tp \a g.
566 /**
567 * \param g The new guarantee specification (in percent).
568 * This must be a nonnative value. Note, if the guarantee specification is changed
569 * after a single node of the enumeration tree has been
570 * fathomed, then the overall guarantee might differ from
571 * the new value.
572 */
573 void requiredGuarantee(double g);
574
575 //! Returns the maximal depth up to which the enumeration should be performed.
576 /**
577 * By default the maximal enumeration depth is \a INT\_MAX.
578 */
maxLevel()579 int maxLevel() const { return maxLevel_; }
580
581 //! This version of the function \a maxLevel() changes the maximal enumeration depth.
582 /**
583 * If it is set to 1 the branch-and-cut algorithm becomes a pure cutting plane algorithm.
584 *
585 * \param ml The new value of the maximal enumeration level.
586 */
587 void maxLevel(int ml);
588
589 //! Returns the maximal number of subproblems to be processed.
590 /**
591 * By default this number is \a INT\_MAX.
592 */
maxNSub()593 int maxNSub() const { return maxNSub_; }
594
595 //! Changes the maximal number of subproblems to \a ml.
596 /**
597 * If it is set to 1 the branch-and-cut algorithm becomes a pure cutting plane algorithm.
598 *
599 * \param ml The new value of the maximal enumeration level.
600 */
601 void maxNSub(int ml);
602
603 //! Returns the maximal cpu time (in seconds) which can be used by the optimization.
maxCpuTime()604 int64_t maxCpuTime() const { return maxCpuTime_; }
605
606 //! Returns the maximal cpu time (as string <tt>hh:mm:ss</tt>) which can be used by the optimization.
607 string maxCpuTimeAsString() const;
608
609 //! Sets the maximally allowed cpu time for the optimization to \a t.
610 /**
611 * \param t The new value of the maximal cpu time in the form <tt>hh:mm:ss</tt>.
612 */
613 void maxCpuTime(const string &t);
614
615 //! Sets the maximally allowed cpu time to \a seconds.
maxCpuTime(int64_t seconds)616 void maxCpuTime(int64_t seconds) { maxCpuTime_ = seconds; }
617
618 //! Sets the maximally allowed cpu time for the optimization to \a hour, \a min, \a sec.
619 void maxCpuTime(int hour, int min, int sec);
620
621 //! Returns the maximal wall-clock time (in seconds) which can be used by the optimization.
maxCowTime()622 int64_t maxCowTime() const { return maxCowTime_; }
623
624 //! Returns the maximal wall-clock time (as string <tt>hh:mm:ss</tt>) which can be used by the optimization.
625 string maxCowTimeAsString() const;
626
627 //! Sets the maximally allowed wall-clock time to \a seconds.
maxCowTime(int64_t seconds)628 void maxCowTime(int64_t seconds) { maxCowTime_ = seconds; }
629
630 //! Sets the maximally allowed wall-clock time for the optimization to \a t.
631 /**
632 * \param t The new value of the maximal cpu time in the form <tt>hh:mm:ss</tt>.
633 */
634 void maxCowTime(const string &t);
635
636 //! If true then we assume that all feasible solutions have integral objective function values.
objInteger()637 bool objInteger() const { return objInteger_; }
638
639 //! Sets the assumption that the objective function values of all feasible solutions are integer.
640 /**
641 * \param b The new value of the assumption.
642 */
objInteger(bool b)643 void objInteger(bool b) { objInteger_ = b; }
644
645 //! Returns the number of linear programs considered in the tailing off analysis.
tailOffNLp()646 int tailOffNLp() const { return tailOffNLp_; }
647
648 //! Sets the number of linear programs considered in the tailing off analysis to \a n.
649 /**
650 * This new value is only
651 * relevant for subproblems activated <b>after</b> the change of this value.
652 *
653 * \param n The new number of LPs for the tailing off analysis.
654 */
tailOffNLp(int n)655 void tailOffNLp(int n) { tailOffNLp_ = n; }
656
657 //! Returns the minimal change of the dual bound for the tailing off analysis in percent.
tailOffPercent()658 double tailOffPercent() const { return tailOffPercent_; }
659
660 //! Sets the minimal change of the dual bound for the tailing off analysis to \a p.
661 /**
662 * This change is only
663 * relevant for subproblems activated <b>after</b> calling this function.
664 *
665 * \param p The new value for the tailing off analysis.
666 */
667 void tailOffPercent(double p);
668
669 //! Returns true if the number of optimizations \a nOpt of a subproblem exceeds the delayed branching threshold, false otherwise.
670 /**
671 * \param nOpt The number of optimizations of a subproblem.
672 */
673 bool delayedBranching(int nOpt) const;
674
675 //! Sets the number of optimizations of a subproblem until sons are created in Sub::branching().
676 /**
677 * If this value is 0, then a branching step is performed at the
678 * end of the subproblem optimization as usually if the subproblem
679 * can be fathomed. Otherwise, if this value is strictly positive,
680 * the subproblem is put back for a later optimization. This can be
681 * advantageous if in the meantime good cutting planes or primal bounds
682 * can be generated. The number of times the subproblem is put back
683 * without branching is indicated by this value.
684 *
685 * \param threshold The new value of the delayed branching threshold.
686 */
dbThreshold(int threshold)687 void dbThreshold(int threshold) { dbThreshold_ = threshold; }
688
689 //! Returns the number of optimizations of a subproblem until sons are created.
690 /**
691 * For further detatails we refer to \a dbThreshold(int).
692 */
dbThreshold()693 int dbThreshold() const { return dbThreshold_; }
694
695 //! Returns the maximal number of rounds, i.e., number of subproblem optimizations, a subproblem is dormant.
696 /**
697 * I.e., it is not selected from the set
698 * of open subproblem if its status is \a Dormant, if possible.
699 */
minDormantRounds()700 int minDormantRounds() const { return minDormantRounds_; }
701
702 //! Sets the number of rounds a subproblem should stay dormant to \a nRounds.
703 /**
704 * \param nRounds The new minimal number of dormant rounds.
705 */
minDormantRounds(int nRounds)706 void minDormantRounds(int nRounds) { minDormantRounds_ = nRounds; }
707
708 //! Returns the mode of the primal bound initialization.
pbMode()709 PRIMALBOUNDMODE pbMode() const { return pbMode_; }
710
711 //! Sets the mode of the primal bound initialization to \a mode.
712 /**
713 * \param mode The new mode of the primal bound initialization.
714 */
pbMode(PRIMALBOUNDMODE mode)715 void pbMode(PRIMALBOUNDMODE mode) { pbMode_ = mode; }
716
717 //! Returns the number of linear programs being solved between two additional pricing steps.
718 /**
719 * If no additional pricing steps should be
720 * executed this parameter has to be set to 0.
721 * The default value of the pricing frequency is 0. This parameter
722 * does not influence the execution of pricing steps which are
723 * required for the correctness of the algorithm.
724 */
pricingFreq()725 int pricingFreq() const { return pricingFreq_; }
726
727 //! Sets the number of linear programs being solved between two additional pricing steps to \a f.
728 /**
729 * \param f The pricing frequency.
730 */
731 void pricingFreq(int f);
732
733 //! Returns the frequency of subproblems in which constraints or variables should be generated.
skipFactor()734 int skipFactor() const { return skipFactor_; }
735
736 //! Sets the frequency for constraint and variable generation to \a f.
737 /**
738 * \param f The new value of the frequency.
739 */
740 void skipFactor(int f);
741
742 //! Sets the skipping strategy to \a mode.
743 /**
744 * \param mode The new skipping strategy.
745 */
skippingMode(SKIPPINGMODE mode)746 void skippingMode(SKIPPINGMODE mode) { skippingMode_ = mode; }
747
748 //! Returns the skipping strategy.
skippingMode()749 SKIPPINGMODE skippingMode() const { return skippingMode_; }
750
751 //! Returns the mode for the elimination of constraints.
conElimMode()752 CONELIMMODE conElimMode() const { return conElimMode_; }
753
754 //! Changes the constraint elimination mode to \a mode.
755 /**
756 * \param mode The new constraint elimination mode.
757 */
conElimMode(CONELIMMODE mode)758 void conElimMode(CONELIMMODE mode) { conElimMode_ = mode; }
759
760 //! Returns the mode for the elimination of variables.
varElimMode()761 VARELIMMODE varElimMode() const { return varElimMode_; }
762
763 //! Changes the variable elimination mode to \a mode.
764 /**
765 * \param mode The new variable elimination mode.
766 */
varElimMode(VARELIMMODE mode)767 void varElimMode(VARELIMMODE mode) { varElimMode_ = mode; }
768
769 //! Returns the zero tolerance for the elimination of constraints by the slack criterion.
conElimEps()770 double conElimEps() const { return conElimEps_; }
771
772 //! Changes the tolerance for the elimination of constraints by the slack criterion to \a eps.
773 /**
774 * \param eps The new tolerance.
775 */
conElimEps(double eps)776 void conElimEps(double eps) { conElimEps_ = eps; }
777
778 //! Returns the zero tolerance for the elimination of variables by the reduced cost criterion.
varElimEps()779 double varElimEps() const { return varElimEps_; }
780
781 //! Changes the tolerance for the elimination of variables by the reduced cost criterion to \a eps.
782 /**
783 * \param eps The new tolerance.
784 */
varElimEps(double eps)785 void varElimEps(double eps) { varElimEps_ = eps; }
786
787 //! Returns the age for the elimination of variables by the reduced cost criterion.
varElimAge()788 int varElimAge() const { return varElimAge_; }
789
790 //! Changes the age for the elimination of variables by the reduced cost criterion to \a age.
791 /**
792 * \param age The new age.
793 */
varElimAge(int age)794 void varElimAge(int age) { varElimAge_ = age; }
795
796 //! Returns the age for the elimination of constraints.
conElimAge()797 int conElimAge() const { return conElimAge_; }
798
799 //! Changes the age for the elimination of constraints to \a age.
800 /**
801 * \param age The new age.
802 */
conElimAge(int age)803 void conElimAge(int age) { conElimAge_ = age; }
804
805 /**
806 * \return true Then variables are fixed and set by reduced cost criteria.
807 * \return false Then no variables are fixed or set by reduced cost criteria.
808 */
fixSetByRedCost()809 bool fixSetByRedCost() const { return fixSetByRedCost_; }
810
811 //! Turns fixing and setting variables by reduced cost on or off.
812 /**
813 * \param on If \a true, then variable fixing and setting by reduced
814 * cost is turned on. Otherwise it is turned of.
815 */
fixSetByRedCost(bool on)816 void fixSetByRedCost(bool on) { fixSetByRedCost_ = on; }
817
818 /**
819 * \return true Then the linear program is output every iteration of the subproblem optimization;
820 * \return false The linear program is not output.
821 */
printLP()822 bool printLP() const { return printLP_; }
823
824 //! Turns the output of the linear program in every iteration on or off.
825 /**
826 * \param on If \a true, then the linear program is output,
827 * otherwise it is not output.
828 */
printLP(bool on)829 void printLP(bool on) { printLP_ = on; }
830
831 //! Returns the maximal number of constraints which should be added in every iteration of the cutting plane algorithm.
maxConAdd()832 int maxConAdd() const { return maxConAdd_; }
833
834 //! Sets the maximal number of constraints that are added in an iteration of the cutting plane algorithm.
835 /***
836 * \param max The maximal number of constraints.
837 */
maxConAdd(int max)838 void maxConAdd(int max) { maxConAdd_ = max; }
839
840 //! Returns the size of the buffer for generated constraints in the cutting plane algorithm.
maxConBuffered()841 int maxConBuffered() const { return maxConBuffered_; }
842
843 //! Changes the maximal number of constraints that are buffered in an iteration of the cutting plane algorithm.
844 /**
845 * \note This function changes only the default value for subproblems
846 * that are activated after its call.
847 *
848 * \param max The new maximal number of buffered constraints.
849 */
maxConBuffered(int max)850 void maxConBuffered(int max) { maxConBuffered_ = max; }
851
852 //! Returns the maximal number of variables which should be added in the column generation algorithm.
maxVarAdd()853 int maxVarAdd() const { return maxVarAdd_; }
854
855 //! Changes the maximal number of variables that are added in an iteration of the subproblem optimization.
856 /**
857 * \param max The new maximal number of added variables.
858 */
maxVarAdd(int max)859 void maxVarAdd(int max) { maxVarAdd_ = max; }
860
861 //! Returns the size of the buffer for the variables generated in the column generation algorithm.
maxVarBuffered()862 int maxVarBuffered() const { return maxVarBuffered_; }
863
864 //! Changes the maximal number of variables that are buffered in an iteration of the subproblem optimization.
865 /**
866 * \note This function changes only the default value for subproblems
867 * that are activated after its call.
868 *
869 * \param max The new maximal number of buffered variables.
870 */
maxVarBuffered(int max)871 void maxVarBuffered(int max) { maxVarBuffered_ = max; }
872
873 //! Returns the maximal number of iterations per subproblem optimization (-1 means no iteration limit).
maxIterations()874 int maxIterations() const { return maxIterations_; }
875
876 //! Changes the default value for the maximal number of iterations of the optimization of a subproblem.
877 /**
878 * \note This function changes only this value for subproblems that
879 * are constructed after this function call. For already constructed
880 * objects the value can be changed with the function
881 * Sub::maxIterations().
882 *
883 * \param max The new maximal number of iterations of the subproblem
884 * optimization (-1 means no limit).
885 */
maxIterations(int max)886 void maxIterations(int max) { maxIterations_ = max; }
887
888 /**
889 * \return true Then we try to eliminate fixed and set variables from the linear program;
890 * \return false Fixed or set variables are not eliminated.
891 */
eliminateFixedSet()892 bool eliminateFixedSet() const { return eliminateFixedSet_; }
893
894 //! Turns the elimination of fixed and set variables on or off.
895 /**
896 * \param turnOn The elimination is turned on if \a turnOn is \a true,
897 * otherwise it is turned off.
898 */
eliminateFixedSet(bool turnOn)899 void eliminateFixedSet(bool turnOn) { eliminateFixedSet_ = turnOn; }
900
901 /**
902 * \return true Then a new root of the remaining branch-and-bound tree is reoptimized
903 * such that the associated reduced costs can be used for the fixing of variables;
904 * \return false A new root is not reoptimized.
905 */
newRootReOptimize()906 bool newRootReOptimize() const { return newRootReOptimize_; }
907
908 //! Turns the reoptimization of new root nodes of the remaining branch and bound tree on or off.
909 /**
910 * \param on If \a true, new root nodes are reoptimized.
911 */
newRootReOptimize(bool on)912 void newRootReOptimize(bool on) { newRootReOptimize_ = on; }
913
914 //! Returns the name of the file that stores the optimum solutions.
optimumFileName()915 const string &optimumFileName() const { return optimumFileName_; }
916
917 //! Changes the name of the file in which the value of the optimum solution is searched.
918 /**
919 * \param name The new name of the file.
920 */
optimumFileName(const char * name)921 void optimumFileName(const char *name) { optimumFileName_ = name; }
922
923 /**
924 * \return true Then the average distance of the fractional solution
925 * from all added cutting planes is output every iteration
926 * of the subproblem optimization.
927 * \return false The average cut distance is not output.
928 */
showAverageCutDistance()929 bool showAverageCutDistance() const { return showAverageCutDistance_; }
930
931 //! Turns the output of the average distance of the added cuts from the fractional solution on or off.
932 /**
933 * \param on If \a true the output is turned on, otherwise it is turned off.
934 */
showAverageCutDistance(bool on)935 void showAverageCutDistance(bool on) { showAverageCutDistance_ = on; }
936
937 //! Returns the mode of output for the Vbc-Tool.
vbcLog()938 VBCMODE vbcLog() const { return VbcLog_; }
939
940 //! Changes the mode of output for the Vbc-Tool to \a mode.
941 /**
942 * This function should only be called before the optimization is
943 * started with the function Master::optimize().
944 *
945 * \param mode The new mode.
946 */
vbcLog(VBCMODE mode)947 void vbcLog(VBCMODE mode) { VbcLog_ = mode; }
948
949 //! Sets solver specific parameters.
950 /**
951 * The default does nothing.
952 *
953 * \return true if an error has occured, false otherwise.
954 */
955 virtual bool setSolverParameters(OsiSolverInterface* interface, bool solverIsApprox);
956
957 protected:
958
959 //! Sets up the default pools for variables, constraints, and cutting planes.
960 /**
961 * \param constraints The constraints of the problem formulation
962 * are inserted in the constraint pool. The size
963 * of the constraint pool equals the number of
964 * \a constraints.
965 * \param variables The variables of the problem formulation are
966 * inserted in the variable pool.
967 * \param varPoolSize The size of the pool for the variables. If
968 * more variables are added the variable pool
969 * is automatically reallocated.
970 * \param cutPoolSize The size of the pool for cutting planes.
971 * \param dynamicCutPool If this argument is true, then the cut
972 * is automatically reallocated if more
973 * constraints are inserted than \a cutPoolSize.
974 * Otherwise, non-active constraints are removed
975 * if the pool becomes full.
976 * The default value is false.
977 */
978 virtual void initializePools(
979 ArrayBuffer<Constraint*> &constraints,
980 ArrayBuffer<Variable*> &variables,
981 int varPoolSize,
982 int cutPoolSize,
983 bool dynamicCutPool = false);
984
985 //! Is overloaded such that also a first set of cutting planes can be inserted into the cutting plane pool.
986 /**
987 * \param constraints The constraints of the problem formulation
988 * are inserted in the constraint pool. The size
989 * of the constraint pool equals the number of
990 * \a constraints.
991 * \param cuts The constraints that are inserted in the cutting
992 * plane pool. The number of constraints in the buffer
993 * must be less or equal than the size of the cutting
994 * plane pool \a cutPoolSize.
995 * \param variables The variables of the problem formulation are
996 * inserted in the variable pool.
997 * \param varPoolSize The size of the pool for the variables. If
998 * more variables are added the variable pool
999 * is automatically reallocated.
1000 * \param cutPoolSize The size of the pool for cutting planes.
1001 * \param dynamicCutPool If this argument is true, then the cut
1002 * is automatically reallocated if more
1003 * constraints are inserted than \a cutPoolSize.
1004 * Otherwise, non-active constraints are removed
1005 * if the pool becomes full.
1006 * The default value is false.
1007 */
1008 virtual void initializePools(
1009 ArrayBuffer<Constraint*> &constraints,
1010 ArrayBuffer<Constraint*> &cuts,
1011 ArrayBuffer<Variable*> &variables,
1012 int varPoolSize,
1013 int cutPoolSize,
1014 bool dynamicCutPool = false);
1015
1016 /**
1017 * Can be used to initialize the sense
1018 * of the optimization in derived classes, if this has not been already
1019 * performed when the constructor of Master has been called.
1020 *
1021 * \param sense The sense of the optimization (OptSense::Min or OptSense::Max).
1022 */
initializeOptSense(OptSense::SENSE sense)1023 void initializeOptSense(OptSense::SENSE sense) { optSense_.sense(sense); }
1024
1025 //! Implements the best first search enumeration.
1026 /**
1027 * If the bounds of both subproblems are equal, then
1028 * the subproblems are compared with the function \a equalSubCompare().
1029 *
1030 * \return -1 If subproblem \a s1 has a worse dual bound than \a s2,
1031 * i.e., if it has a smaller dual bound for minimization or
1032 * a larger dual bound for maximization problems.
1033 * \return 1 If subproblem \a s2 has a worse dual bound than \a s1.
1034 * \return 0 If both subproblems have the same priority in the enumeration strategy.
1035 *
1036 * \param s1 A subproblem.
1037 * \param s2 A subproblem.
1038 */
1039 int bestFirstSearch(const Sub* s1, const Sub* s2) const;
1040
1041 /**
1042 * Is called from the function
1043 * \a bestFirstSearch() and from the function \a depthFirstSearch()
1044 * if the subproblems \a s1 and \a s2 have the same priority.
1045 *
1046 * If both subproblems were generated by setting a binary variable, then
1047 * that subproblem has higher priority of which the branching variable is
1048 * set to upper bound.
1049 *
1050 * This function can be redefined to resolve equal subproblems according
1051 * to problem specific criteria.
1052 * As the root node is compared with itself and has no branching rule,
1053 * we have to insert the first line of this function.
1054 *
1055 * \param s1 A subproblem.
1056 * \param s2 A subproblem.
1057 *
1058 * \return 0 If both subproblems were not generated by setting a
1059 * variable, or the branching variable of both subproblems
1060 * is set to the same bound.
1061 * \return 1 If the branching variable of the first subproblem
1062 * is set to the upper bound.
1063 * \return -1 If the branching variable of the second subproblem
1064 * is set to the upper bound.
1065 */
1066 virtual int equalSubCompare(const Sub *s1, const Sub *s2) const;
1067
1068 //! Implements the depth first search enumeration strategy, i.e., the subproblem with maximum \a level is selected.
1069 /**
1070 * If the level of both subproblems are equal, then
1071 * the subproblems are compared with the function \a equalSubCompare().
1072 *
1073 * \return -1 If subproblem \a s1 has higher priority,
1074 * \return 0 if both subproblems have equal priority,
1075 * \return 1 otherwise.
1076 *
1077 * \param s1 The first subproblem.
1078 * \param s2 The second subproblem.
1079 */
1080 int depthFirstSearch(const Sub* s1, const Sub* s2) const;
1081
1082 //! Implements the breadth first search enumeration strategy, i.e., the subproblem with minimum \a level is selected.
1083 /**
1084 * If both subproblems have the same \a level, the smaller
1085 * one is the one which has been generated earlier, i.e., the one with
1086 * the smaller \a id.
1087 *
1088 * \return -1 If subproblem \a s1 has higher priority,
1089 * \return 0 if both subproblems have equal priority,
1090 * \return 1 otherwise.
1091 *
1092 * \param s1 The first subproblem.
1093 * \param s2 The second subproblem.
1094 */
1095 int breadthFirstSearch(const Sub* s1, const Sub* s2) const;
1096
1097
1098 //! Performs depth-first search until a feasible solution is found, then the search process is continued with best-first search.
1099 /**
1100 * \return -1 If subproblem \a s1 has higher priority,
1101 * \return 0 if both subproblems have equal priority,
1102 * \return 1 otherwise.
1103 *
1104 * \param s1 The first subproblem.
1105 * \param s2 The second subproblem.
1106 */
1107 int diveAndBestFirstSearch(const Sub *s1, const Sub* s2) const;
1108
1109 /**
1110 * Is only a dummy. This function can be used to initialize parameters of derived classes
1111 * and to overwrite parameters read from the file <tt>.abacus</tt> by the
1112 * function \a \_initializeParameters().
1113 */
initializeParameters()1114 virtual void initializeParameters() { }
1115
1116 //! Should return a pointer to the first subproblem of the optimization, i.e., the root node of the enumeration tree.
1117 /**
1118 * This is a pure virtual function since
1119 * a pointer to a problem specific subproblem should be returned,
1120 * which is derived from the class Sub.
1121 */
1122 virtual Sub *firstSub() = 0;
1123
1124 /**
1125 * The default implementation of \a initializeOptimization() does nothing.
1126 *
1127 * This virtual function can be used as an entrance point to perform
1128 * some initializations after \a optimize() is called.
1129 */
initializeOptimization()1130 virtual void initializeOptimization() { }
1131
1132 /**
1133 * The default implementation of \a terminateOptimization() does nothing.
1134 *
1135 * This virtual function can be used as an entrance point
1136 * after the optimization process is finished.
1137 */
terminateOptimization()1138 virtual void terminateOptimization() { }
1139
1140 //! Assigns the parameters that were read from a file to the member variables of the master.
1141 virtual void assignParameters();
1142
1143 private:
1144
1145 //! \brief Reads the parameter-file <tt>.abacus</tt>.
1146 /**
1147 * This file is searched in the directory given by the
1148 * environment variable ABACUS_DIR, then the virtual function \a initializeParameters()
1149 * is called which can initialize parameters of derived classes and overwrite
1150 * parameters of this class.
1151 *
1152 * All parameters are first inserted together
1153 * with their values in a parameter table in the function \a readParameters().
1154 * If the virtual dummy function \a initializeParameters() is redefined
1155 * in a derived class and also reads a parameter file with the function
1156 * \a readParameters(), then already inserted parameters can be overwritten.
1157 *
1158 * After all parameters are input we extract with the function \a assignParameter()
1159 * all parameters. Problem specific parameters should be extracted in
1160 * a redefined version of \a initializeParameters().
1161 * extracted from this table
1162 */
1163 void _initializeParameters();
1164
1165 void _createLpMasters();
1166 void _deleteLpMasters();
1167 void _initializeLpParameters();
1168
1169 //! Initializes the LP solver specific default parameters if they are not read from <tt>.abacus</tt>.
1170 /**
1171 * This function is implemented in the file \a lpif.cc.
1172 */
1173 void _setDefaultLpParameters();
1174
1175 //! \brief Prints the LP solver specific parameters.
1176 /**
1177 * This function is implemented in the file \a lpif.cc.
1178 */
1179 void _printLpParameters() const;
1180
1181 //! \brief Prints the LP solver specific statistics.
1182 /**
1183 * This function is implemented in the file \a lpif.cc.
1184 */
1185 void _outputLpStatistics() const;
1186
1187 //! \brief Returns a pointer to an open subproblem for further processing.
1188 /**
1189 * If the set of open subproblems is empty or
1190 * one of the criteria for early termination of the optimization
1191 * (maximal cpu time, maximal elapsed time, guarantee) is
1192 * fulfilled 0 is returned.
1193 */
1194 Sub *select();
1195
1196 int initLP();
1197
1198 //! Writes the string \a info to the stream associated with the Tree Interface.
1199 /**
1200 * A \$ is preceded if
1201 * the output is written to standard out for further pipelining.
1202 * If \a time is true a time string is written in front of the
1203 * information. The default value of \a time is \a true.
1204 */
1205 void writeTreeInterface(const string &info, bool time = true) const;
1206
1207 /**
1208 * Adds the subproblem \a sub to the
1209 * stream storing information for graphical output of the enumeration
1210 * tree if this logging is turned on.
1211 */
1212 void treeInterfaceNewNode(Sub *sub) const;
1213
1214 //! Assigns the \a color to the subproblem \a sub in the Tree Interface.
1215 void treeInterfacePaintNode(int id, int color) const;
1216
1217 //! Passes the new lower bound \a lb to the Tree Interface.
1218 void treeInterfaceLowerBound(double lb) const;
1219
1220 //! Passes the new upper bound \a ub to the Tree Interface.
1221 void treeInterfaceUpperBound(double ub) const;
1222
1223 //! Updates the node information in the node with number \a id by writing the lower bound \a lb and the upper bound \a ub to the node.
1224 void treeInterfaceNodeBounds(int id, double lb, double ub);
1225
1226 //! Registers a new subproblem which is on level \a level in enumeration tree.
1227 /**
1228 * It is called each time a new subproblem is generated.
1229 */
1230 void newSub(int level);
1231
1232 //! Increments the counter for linear programs and should be called in each optimization call of the LP-relaxation.
countLp()1233 void countLp() { ++nLp_; }
1234
1235 //! Increments the counter of the number of fixed variables by \a n.
newFixed(int n)1236 void newFixed(int n) { nFixed_ += n; }
1237
1238 //! Increments the counter for the total number of added constraints by \a n.
addCons(int n)1239 void addCons(int n) { nAddCons_ += n; }
1240
1241 //! Increments the counter for the total number of removed constraints by \a n.
removeCons(int n)1242 void removeCons(int n) { nRemCons_ += n; }
1243
1244 //! Increments the counter for the total number of added variables by \a n.
addVars(int n)1245 void addVars(int n) { nAddVars_ += n; }
1246
1247 //! Increments the counter for the total number of removed variables by \a n.
removeVars(int n)1248 void removeVars(int n) { nRemVars_ += n; }
1249
1250 //! Returns a pointer to the object storing the variables which are candidates for being fixed.
fixCand()1251 FixCand *fixCand() const { return fixCand_; }
1252
1253 //! Sets the root of the remaining branch-and-cut tree to \a newRoot.
1254 /**
1255 * If \a reoptimize is \a true a reoptimization of the
1256 * subproblem \a *newRoot is performed.
1257 * This is controlled via a function argument since it might not be
1258 * desirable when we find a new \a rRoot_ during the fathoming
1259 * of a complete subtree Sub::FathomTheSubtree().
1260 */
1261 void rRoot(Sub *newRoot, bool reoptimize);
1262
1263 //! Sets the status of the Master.
status(STATUS stat)1264 void status(STATUS stat) { status_ = stat; }
1265
1266 //! Updates the final dual bound of the root node.
1267 /**
1268 * This function should be only called at the end of the root node optimization.
1269 */
1270 void rootDualBound(double x);
1271
1272 void theFuture();
1273
1274 //! The name of the optimized problem.
1275 string problemName_;
1276
1277 bool readParamFromFile_;
1278
1279 //! The sense of the objective function.
1280 OptSense optSense_;
1281
1282 //! The root node of the enumeration tree.
1283 Sub *root_;
1284
1285 //! The root node of the remaining enumeration tree.
1286 Sub *rRoot_;
1287
1288 //! The set of open subproblems.
1289 OpenSub *openSub_;
1290
1291 //! The solution history.
1292 History *history_;
1293
1294 //! The enumeration strategy.
1295 ENUMSTRAT enumerationStrategy_;
1296
1297 //! The branching strategy.
1298 BRANCHINGSTRAT branchingStrategy_;
1299
1300 //! The number of candidates that are evaluated for branching on variables.
1301 int nBranchingVariableCandidates_;
1302
1303 //! The number of simplex iterations that are performed when testing a branching variable candidate within strong branching.
1304 int nStrongBranchingIterations_;
1305
1306 //! The default LP-Solver.
1307 OSISOLVER defaultLpSolver_;
1308
1309 LpMasterOsi *lpMasterOsi_;
1310
1311 //! The default pool with the constraints of the problem formulation.
1312 StandardPool<Constraint, Variable> *conPool_;
1313
1314
1315 //! The default pool of dynamically generated constraints.
1316 StandardPool<Constraint, Variable> *cutPool_;
1317
1318 //! The default pool with the variables of the problem formulation.
1319 StandardPool<Variable, Constraint> *varPool_;
1320
1321 //! The best known primal bound.
1322 double primalBound_;
1323
1324 //! The best known dual bound.
1325 double dualBound_;
1326
1327 //! The best known dual bound at the end of the optimization of the root node.
1328 double rootDualBound_;
1329
1330 //! The variables which are candidates for being fixed.
1331 FixCand *fixCand_;
1332
1333 //! If \a true, then constraints are generated in the optimization.
1334 bool cutting_;
1335
1336 //! If \a true, then variables are generated in the optimization.
1337 bool pricing_;
1338
1339 //! If \a true, then an approximative solver is used to solve linear programs
1340 bool solveApprox_;
1341
1342 //! The number of subproblems already selected from the list of open subproblems.
1343 int nSubSelected_;
1344
1345 //! Ouput for the Tree Interface is generated depending on the value of this variable.
1346 VBCMODE VbcLog_;
1347
1348 //! A pointer to the log stream for the VBC-Tool.
1349 std::ostream *treeStream_;
1350
1351 //! The guarantee in percent which should be reached when the optimization stops.
1352 /**
1353 * If this value is 0.0, then the optimum solution is determined.
1354 */
1355 double requiredGuarantee_;
1356
1357 //! The maximal level in enumeration tree.
1358 /**
1359 * Up to this level subproblems are considered in the enumeration.
1360 */
1361 int maxLevel_;
1362
1363 //! The maximal number of subproblems to be processed.
1364 /**
1365 * Up to this number subproblems are considered in the enumeration.
1366 */
1367 int maxNSub_;
1368
1369 //! The maximal available cpu time.
1370 int64_t maxCpuTime_;
1371
1372 //! The maximal available wall-clock time.
1373 int64_t maxCowTime_;
1374
1375 //! \a true, if all objective function values of feasible solutions are assumed to be integer.
1376 bool objInteger_;
1377
1378 //! The number of LP-iterations for the tailing off analysis.
1379 int tailOffNLp_;
1380
1381 //! The minimal change of the LP-value on the tailing off analysis.
1382 double tailOffPercent_;
1383
1384 //! The number of optimizations of an Sub until branching is performed.
1385 int dbThreshold_;
1386
1387 /**
1388 * The minimal number of rounds, i.e., number of subproblem optimizations,
1389 * a subproblem is dormant, i.e., it is not selected from the set
1390 * of open subproblem if its status is \a Dormant, if possible.
1391 */
1392 int minDormantRounds_;
1393
1394 //! The mode of the primal bound initialization.
1395 PRIMALBOUNDMODE pbMode_;
1396
1397 //! The number of solved LPs between two additional pricing steps.
1398 int pricingFreq_;
1399
1400 //! The frequency constraints or variables are generated depending on the skipping mode.
1401 int skipFactor_;
1402
1403 /**
1404 * Either constraints are generated only every \a skipFactor_ subproblem
1405 * (\a SkipByNode) only every \a skipFactor_ level (\a SkipByLevel).
1406 */
1407 SKIPPINGMODE skippingMode_;
1408
1409 //! If \a true, then variables are fixed and set by reduced cost criteria.
1410 bool fixSetByRedCost_;
1411
1412 //! If \a true, then the linear program is output every iteration.
1413 bool printLP_;
1414
1415 //! The maximal number of added constraints per iteration of the cutting plane algorithm.
1416 int maxConAdd_;
1417
1418 //! The size of the buffer for generated cutting planes.
1419 int maxConBuffered_;
1420
1421 //! The maximal number of added variables per iteration of the column generation algorithm.
1422 int maxVarAdd_;
1423
1424 //! The size of the buffer for generated variables.
1425 int maxVarBuffered_;
1426
1427 //! The maximal number of iterations of the cutting plane/column generation algorithm in the subproblem.
1428 int maxIterations_;
1429
1430 //! If \a true, then nonbasic fixed and set variables are eliminated.
1431 bool eliminateFixedSet_;
1432
1433 /**
1434 * If \a true, then an already earlier processed node is reoptimized
1435 * if it becomes the new root of the remaining branch-and-bound tree.
1436 */
1437 bool newRootReOptimize_;
1438
1439 //! The name of a file storing a list of optimum solutions of problem instances.
1440 string optimumFileName_;
1441
1442 /**
1443 * If \a true then the average distance of the added cutting planes
1444 * is output every iteration of the cutting plane algorithm.
1445 */
1446 bool showAverageCutDistance_;
1447
1448 //! The way constraints are automatically eliminated in the cutting plane algorithm.
1449 CONELIMMODE conElimMode_;
1450
1451 //! The way variables are automatically eliminated in the column generation algorithm.
1452 VARELIMMODE varElimMode_;
1453
1454 //! The tolerance for the elimination of constraints by the mode \a NonBinding/
1455 double conElimEps_;
1456
1457 //! The tolerance for the elimination of variables by the mode \a ReducedCost.
1458 double varElimEps_;
1459
1460 //! The number of iterations an elimination criterion must be satisfied until a constraint can be removed.
1461 int conElimAge_;
1462
1463 //! The number of iterations an elimination criterion must be satisfied until a variable can be removed.
1464 int varElimAge_;
1465
1466 //! The current status of the optimization.
1467 STATUS status_;
1468
1469 //! The timer for the total elapsed time.
1470 ogdf::StopwatchWallClock totalCowTime_;
1471
1472 //! The timer for the total cpu time for the optimization.
1473 ogdf::StopwatchCPU totalTime_;
1474
1475 //! The timer for the cpu time spent in the LP-interface.
1476 ogdf::StopwatchCPU lpTime_;
1477
1478 ogdf::StopwatchCPU lpSolverTime_;
1479
1480 //! The timer for the cpu time spent in the separation
1481 ogdf::StopwatchCPU separationTime_;
1482
1483 //! The timer for the cpu time spent in the heuristics for the computation of feasible solutions.
1484 ogdf::StopwatchCPU improveTime_;
1485
1486 //! The timer for the cpu time spent in pricing.
1487 ogdf::StopwatchCPU pricingTime_;
1488
1489 //! The timer for the cpu time spent in determining the branching rules.
1490 ogdf::StopwatchCPU branchingTime_;
1491
1492 //! The number of generated subproblems.
1493 int nSub_;
1494
1495 //! The number of solved LPs.
1496 int nLp_;
1497
1498 //! The highest level which has been reached in the enumeration tree.
1499 int highestLevel_;
1500
1501 //! The total number of fixed variables.
1502 int nFixed_;
1503
1504 //! The total number of added constraints.
1505 int nAddCons_;
1506
1507 //! The total number of removed constraints.
1508 int nRemCons_;
1509
1510 //! The total number of added variables.
1511 int nAddVars_;
1512
1513 //! The total number of removed variables.
1514 int nRemVars_;
1515
1516 //! The number of changes of the root of the remaining branch-and-bound tree.
1517 int nNewRoot_;
1518
1519 Master(const Master &rhs);
1520 const Master &operator=(const Master& rhs);
1521 };
1522
1523
lowerBound()1524 inline double Master::lowerBound() const
1525 {
1526 if (optSense_.max()) return primalBound_;
1527 else return dualBound_;
1528 }
1529
upperBound()1530 inline double Master::upperBound() const
1531 {
1532 if (optSense_.max()) return dualBound_;
1533 else return primalBound_;
1534 }
1535
1536 }
1537