Open
Graph Drawing
Framework

  v. 2022.02 (Dogwood)
 
Overview Class Hierarchy Class Index Class List Members Namespaces Source Files

MinSteinerTreeDirectedCut.h
Go to the documentation of this file.
1 
42 #pragma once
43 
44 #include <ogdf/external/abacus.h>
45 
46 #include <ogdf/basic/Graph.h>
47 #include <ogdf/graphalg/steiner_tree/EdgeWeightedGraph.h>
48 #include <ogdf/graphalg/steiner_tree/EdgeWeightedGraphCopy.h>
49 #include <ogdf/basic/Logger.h>
50 
51 #include <memory>
52 #include <ogdf/graphalg/MinSTCutMaxFlow.h>
53 
54 #include <ogdf/lib/abacus/opensub.h>
55 // heuristics, approximation algorithms:
56 #include <ogdf/graphalg/MinSteinerTreeTakahashi.h>
57 
58 
59 // turn on/off logging for STP b&c algorithm
60 //#define OGDF_STP_EXACT_LOGGING
61 
62 // TODO: Add module option for max flow algorithm
63 
64 namespace ogdf {
65 
67 
70 template<typename T>
71 class MinSteinerTreeDirectedCut : public MinSteinerTreeModule<T> {
72 protected:
73  // all the settings
74  const char *m_configFile;
75  double m_eps;
76 #ifdef OGDF_STP_EXACT_LOGGING
77  Logger::Level m_outputLevel;
78 #endif
79  std::unique_ptr<MaxFlowModule<double>> m_maxFlowModuleOption;
80  bool m_addDegreeConstraints;
81  bool m_addIndegreeEdgeConstraints;
82  bool m_addGSEC2Constraints;
83  bool m_addFlowBalanceConstraints;
84  int m_maxNrAddedCuttingPlanes;
85  bool m_shuffleTerminals;
86  bool m_backCutComputation;
87  bool m_nestedCutComputation;
88  int m_separationStrategy;
89  int m_saturationStrategy;
90  bool m_minCardinalityCuts;
91  int m_callPrimalHeuristic;
92  MinSteinerTreeModule<double> *m_primalHeuristic;
93  int m_poolSizeInitFactor;
94 
95  // Abacus LP classes
96  class Sub;
97  class EdgeConstraint;
98  class DegreeConstraint;
99  class DegreeEdgeConstraint;
100  class DirectedCutConstraint;
101  class EdgeVariable;
102 
103 public:
104  class Master;
105 
106  // a lot of setter methods
108  void setEpsilon(double eps) {
109  m_eps = eps;
110  }
112  void setConfigFile(const char *configfile) {
113  m_configFile = configfile;
114  }
115 #ifdef OGDF_STP_EXACT_LOGGING
116  void setOutputLevel(Logger::Level outputLevel)
118  {
119  m_outputLevel = outputLevel;
120  }
121 #endif
122  void setMaxFlowModule(MaxFlowModule<double> *module)
124  {
125  m_maxFlowModuleOption.reset(module);
126  }
128  void useDegreeConstraints(bool b)
129  {
130  m_addDegreeConstraints = b;
131  }
133  void useIndegreeEdgeConstraints(bool b)
134  {
135  m_addIndegreeEdgeConstraints = b;
136  }
138  void useGSEC2Constraints(bool b)
139  {
140  m_addGSEC2Constraints = b;
141  }
143  void useFlowBalanceConstraints(bool b)
144  {
145  m_addFlowBalanceConstraints = b;
146  }
148  void setMaxNumberAddedCuttingPlanes(int b)
149  {
150  m_maxNrAddedCuttingPlanes = b;
151  }
153  void useTerminalShuffle(bool b)
154  {
155  m_shuffleTerminals = b;
156  }
158  void useBackCuts(bool b)
159  {
160  m_backCutComputation = b;
161  }
163  void useNestedCuts(bool b)
164  {
165  m_nestedCutComputation = b;
166  }
168  void setSeparationStrategy(int b)
169  {
170  m_separationStrategy = b;
171  }
173  void setSaturationStrategy(int b)
174  {
175  m_saturationStrategy = b;
176  }
178  void useMinCardinalityCuts(bool b)
179  {
180  m_minCardinalityCuts = b;
181  }
183  void setPrimalHeuristic(MinSteinerTreeModule<double> *b) {
184  m_primalHeuristic = b;
185  }
187  void setPrimalHeuristicCallStrategy(int b)
188  {
189  OGDF_ASSERT(b >= 0);
190  OGDF_ASSERT(b <= 2);
191  m_callPrimalHeuristic = b;
192  }
194  void setPoolSizeInitFactor(int b)
195  {
196  m_poolSizeInitFactor = b;
197  }
198 
199  MinSteinerTreeDirectedCut()
200  : m_configFile(nullptr)
201  , m_eps(1e-6)
202 #ifdef OGDF_STP_EXACT_LOGGING
203  , m_outputLevel(Logger::Level::Default)
204 #endif
205  , m_maxFlowModuleOption(new MaxFlowGoldbergTarjan<double>())
206  , m_addDegreeConstraints(true)
207  , m_addIndegreeEdgeConstraints(true)
208  , m_addGSEC2Constraints(true)
209  , m_addFlowBalanceConstraints(true)
210  , m_maxNrAddedCuttingPlanes(500)
211  , m_shuffleTerminals(true)
212  , m_backCutComputation(true)
213  , m_nestedCutComputation(true)
214  , m_separationStrategy(1)
215  , m_saturationStrategy(1)
216  , m_minCardinalityCuts(true)
217  , m_callPrimalHeuristic(1)
218  , m_primalHeuristic(nullptr)
219  , m_poolSizeInitFactor(5)
220  {
221  }
222 
223 protected:
224  virtual T computeSteinerTree(const EdgeWeightedGraph<T> &G, const List<node> &terminals, const NodeArray<bool> &isTerminal,
225  EdgeWeightedGraphCopy<T> *&finalSteinerTree) override;
226 };
227 
229 template<typename T>
230 class MinSteinerTreeDirectedCut<T>::Master : public abacus::Master, public Logger
231 {
232 public:
242  Master(const EdgeWeightedGraph<T> &wG,
243  const List<node> &terminals,
244  const NodeArray<bool> &isTerminal,
245  double eps,
246  bool relaxed = false);
247 
249  virtual ~Master()
250  {
251  delete[] m_bestSolution;
252  delete[] m_terminals;
253  delete[] m_nodes;
254  delete[] m_edges;
255  delete m_pGraph;
256  delete m_pWeightedGraphPH;
257  delete m_pCutPool;
258  }
259 
261  void setConfigFile(const char *filename)
262  {
263  m_configfile = filename;
264  }
265 #ifdef OGDF_STP_EXACT_LOGGING
266  void setOutputLevel(Level outputLevel)
268  {
269  this->globalLogLevel(Level::Default);
270  this->localLogMode(LogMode::Log);
271  if (outputLevel >= Level::Minor
272  && outputLevel <= Level::Force) {
273  this->localLogLevel((Level)outputLevel);
274  this->globalMinimumLogLevel((Level)outputLevel);
275  }
276  }
277 #endif
278  void setMaxFlowModule(MaxFlowModule<double> *module) {
280  m_maxFlowModule = module;
281  }
282 
284  MaxFlowModule<double> *getMaxFlowModule()
285  {
286  return m_maxFlowModule;
287  }
288 
290  void useDegreeConstraints(bool b)
291  {
292  m_addDegreeConstraints = b;
293  }
295  void useIndegreeEdgeConstraints(bool b)
296  {
297  m_addIndegreeEdgeConstraints = b;
298  }
300  void useGSEC2Constraints(bool b)
301  {
302  m_addGSEC2Constraints = b;
303  }
305  void useFlowBalanceConstraints(bool b)
306  {
307  m_addFlowBalanceConstraints = b;
308  }
310  void setMaxNumberAddedCuttingPlanes(int b)
311  {
312  m_maxNrAddedCuttingPlanes = b;
313  this->maxConAdd(m_maxNrAddedCuttingPlanes);
314  this->maxConBuffered(m_maxNrAddedCuttingPlanes);
315  }
317  void useTerminalShuffle(bool b)
318  {
319  m_shuffleTerminals = b;
320  }
322  void useBackCuts(bool b)
323  {
324  m_backCutComputation = b;
325  }
327  void useNestedCuts(bool b)
328  {
329  m_nestedCutComputation = b;
330  }
332  void setSeparationStrategy(int b)
333  {
334  OGDF_ASSERT(b >= 1);
335  OGDF_ASSERT(b <= 2);
336  m_separationStrategy = b;
337  }
339  void setSaturationStrategy(int b)
340  {
341  OGDF_ASSERT(b >= 1);
342  OGDF_ASSERT(b <= 2);
343  m_saturationStrategy = b;
344  }
346  void useMinCardinalityCuts(bool b)
347  {
348  m_minCardinalityCuts = b;
349  }
351  void setPrimalHeuristicCallStrategy(int b)
352  {
353  OGDF_ASSERT(b >= 0);
354  OGDF_ASSERT(b <= 2);
355  m_callPrimalHeuristic = b;
356  }
358  void setPoolSizeInitFactor(int b)
359  {
360  m_poolSizeInitFactor = b;
361  }
362 
364  void setPrimalHeuristic(MinSteinerTreeModule<double> *pMinSteinerTreeModule) {
365  m_primalHeuristic.reset(pMinSteinerTreeModule);
366  }
368  std::unique_ptr<MinSteinerTreeModule<double>> &getPrimalHeuristic() {return m_primalHeuristic;}
369 
371  abacus::NonDuplPool<abacus::Constraint, abacus::Variable> *cutPool() {return m_pCutPool;}
372 
374  virtual abacus::Sub *firstSub() override
375  {
376  return new Sub(this);
377  }
378 
380  bool isSolutionEdge(edge e) const
381  {
382  return m_isSolutionEdge[m_mapToBidirectedGraph1[e]]
383  || m_isSolutionEdge[m_mapToBidirectedGraph2[e]];
384  }
385 
387  const Graph &graph() const {return *m_pGraph;}
388 
390  int nNodes() const {return m_pGraph->numberOfNodes();}
392  int nEdges() const {return m_pGraph->numberOfEdges();}
394  int nEdgesU() const {return m_nEdgesU;}
396  node rootNode() const {return m_root;}
397 
399  int nTerminals() const {return m_nTerminals;}
401  const node *terminals() const {return m_terminals;}
403  node terminal(int i) const {return m_terminals[i];}
405  bool isTerminal(node n) const {return m_isTerminal[n];}
407  const NodeArray<bool> isTerminal() const {return m_isTerminal;}
408 
410  int edgeID(edge e) const {return m_edgeIDs[e];}
412  int nodeID(node n) const {return m_nodeIDs[n];}
413 
415  node *nodes() const {return m_nodes;}
417  const NodeArray<int> &nodeIDs() const {return m_nodeIDs;}
419  const EdgeArray<int> &edgeIDs() const {return m_edgeIDs;}
420 
422  edge getEdge(int i) const {return m_edges[i];}
424  node getNode(int i) const {return m_nodes[i];}
425 
427  const EdgeArray<double> &capacities() const {return m_capacities;}
429  double capacities(edge e) const {return m_capacities[e];}
430 
432  edge twin(edge e) const {return m_twin[e];}
433  // the twin edge array
434  const EdgeArray<edge> &twins() const {return m_twin;}
435 
437  EdgeVariable *getVar(edge e) const {return m_edgeToVar[e];}
439  EdgeVariable *getVarTwin(edge e) const {return m_edgeToVar[m_twin[e]];}
440 
442  bool relaxed() const {return m_relaxed;}
443 
445  double solutionValue() const {return this->primalBound();}
447  double *bestSolution() const {return m_bestSolution;}
449  void updateBestSolution(double *values);
451  void updateBestSolutionByEdges(const List<edge> &sol);
452 
454  void setRelaxedSolValue(double val) {m_relaxedSolValue = val;}
456  void setNIterRoot(int val) {m_nIterRoot = val;}
457 
459  int maxNrAddedCuttingPlanes() const {return m_maxNrAddedCuttingPlanes;}
461  bool computeNestedCuts() const {return m_nestedCutComputation;}
463  bool computeBackCuts() const {return m_backCutComputation;}
465  bool minCardinalityCuts() const {return m_minCardinalityCuts;}
467  bool callPrimalHeuristic() const {return m_callPrimalHeuristic > 0;}
469  int callPrimalHeuristicStrategy() const {return m_callPrimalHeuristic;}
471  int separationStrategy() const {return m_separationStrategy;}
473  int saturationStrategy() const {return m_saturationStrategy;}
474 
476  bool shuffleTerminals() const {return m_shuffleTerminals;}
477 
479  int maxPoolSize() const {return m_maxPoolSize;}
481  void checkSetMaxPoolSize()
482  {
483  if (m_poolSizeMax < m_pCutPool->size())
484  m_poolSizeMax = m_pCutPool->size();
485  }
487  int poolSizeInit() const {return m_poolSizeInit;}
488 
490  void incNrCutsTotal(int val) {m_nrCutsTotal += val;}
492  void incNrCutsTotal() {m_nrCutsTotal++;}
494  int nrCutsTotal() const {return m_nrCutsTotal;}
495 
496  /*
497  * Methods for primal heuristics.
498  * Naming convention: suffix "PH"
499  */
500  /*
501  * Edge weighted bidirected graph; used and modified for primal heuristics.
502  * Required for calling MinSteinerTreeModule algorihms
503  */
504  EdgeWeightedGraph<double> &weightedGraphPH() {return *m_pWeightedGraphPH;}
506  const List<node> &terminalListPH() const {return m_terminalListPH;}
508  const NodeArray<bool> &isTerminalPH() const {return m_isTerminalPH;}
510  node rootNodePH() const {return m_rootPH;}
512  edge edgeGToWgPH(edge e) const {return m_edgesGToWgPH[e];}
514  edge edgeWgToGPH(edge e) const {return m_edgesWgToGPH[e];}
515 
516  /*
517  * some additional timers
518  */
520  StopwatchWallClock *separationTimer() {return &m_separationTimer;}
522  StopwatchWallClock *timerMinSTCut() {return &m_timerMinSTCut;}
524  StopwatchWallClock *primalHeuristicTimer() {return &m_primalHeuristicTimer;}
525 
526 protected:
528  virtual void initializeOptimization() override;
530  virtual void terminateOptimization() override;
532  virtual void initializeParameters() override;
533 
534 private:
535  MaxFlowModule<double> *m_maxFlowModule;
536 
538  const char *m_configfile;
539 
541  std::unique_ptr<MinSteinerTreeModule<double>> m_primalHeuristic;
542 
544  bool m_relaxed;
545 
547  double m_relaxedSolValue;
548 
550  int m_nIterRoot;
551 
553  const EdgeWeightedGraph<T> &m_wG;
554 
556  Graph *m_pGraph;
557 
559  int m_nEdgesU;
561  edge *m_edges;
563  EdgeArray<int> m_edgeIDs;
565  EdgeArray<edge> m_twin;
566 
568  EdgeArray<double> m_capacities;
570  EdgeArray<EdgeVariable*> m_edgeToVar;
571 
573  EdgeArray<edge> m_mapToOrigGraph;
575  EdgeArray<edge> m_mapToBidirectedGraph1;
577  EdgeArray<edge> m_mapToBidirectedGraph2;
578 
580  node *m_nodes;
582  NodeArray<int> m_nodeIDs;
584  NodeArray<bool> m_isTerminal;
586  int m_nTerminals;
588  node *m_terminals;
589 
591  node m_root;
592 
594  double *m_bestSolution;
595  EdgeArray<bool> m_isSolutionEdge;
596 
597  /*
598  * Stuff for primal heuristics
599  */
601  EdgeWeightedGraph<double> *m_pWeightedGraphPH;
603  List<node> m_terminalListPH;
605  NodeArray<bool> m_isTerminalPH;
607  NodeArray<node> m_nodesGToWgPH;
609  EdgeArray<edge> m_edgesGToWgPH;
611  EdgeArray<edge> m_edgesWgToGPH;
613  node m_rootPH;
614 
616  abacus::NonDuplPool<abacus::Constraint, abacus::Variable> *m_pCutPool;
618  int m_poolSizeInitFactor;
620  int m_poolSizeInit;
622  int m_poolSizeMax;
624  int m_maxPoolSize;
626  int m_nrCutsTotal;
627 
629  bool m_addGSEC2Constraints;
631  bool m_addDegreeConstraints;
633  bool m_addIndegreeEdgeConstraints;
635  bool m_addFlowBalanceConstraints;
636 
638  int m_maxNrAddedCuttingPlanes;
640  bool m_shuffleTerminals;
642  bool m_backCutComputation;
644  bool m_nestedCutComputation;
646  /*
647  * basic strategy:
648  * Computes mincut between the root and a terminal. Saturates cutedges afterwards.
649  * Continues with same terminal until no violated cut is found. Considers next terminal.
650  * 1: When switching to next terminal saturated edges remain saturated (default)
651  * 2: When switching to next terminal saturated edges are reset to original capacity
652  */
653  int m_separationStrategy;
655  /*
656  * for all cutedges e:
657  * 1: capacity[e]=1 (default)
658  * 2: capacity[e]=1/C with C=nr of cutedges
659  */
660  int m_saturationStrategy;
661 
663  /*
664  * adds epsilon to each arc capacity before computing the minimum cut
665  */
666  bool m_minCardinalityCuts;
667 
669  /*
670  * 0: no PH
671  * 1: call PH right before branchting
672  * 2: call PH every iteration
673  */
674  int m_callPrimalHeuristic;
675 
677  StopwatchWallClock m_separationTimer;
679  StopwatchWallClock m_timerMinSTCut;
681  StopwatchWallClock m_primalHeuristicTimer;
682 
683  Master(const Master &rhs);
684  const Master &operator= (const Master &rhs);
685 };
686 
688 template<typename T>
689 class MinSteinerTreeDirectedCut<T>::Sub : public abacus::Sub
690 {
691 public:
693  explicit Sub(abacus::Master *master);
695  Sub(abacus::Master *master, abacus::Sub *father, abacus::BranchRule *branchRule);
697  virtual ~Sub()
698  {
699  }
700 
701 #ifdef OGDF_STP_EXACT_LOGGING
702  void printCurrentSolution(bool onlyNonZeros = true);
704 #endif
705 
706 protected:
708  virtual bool feasible() override;
709 
711  virtual int separate() override
712  {
713  if (m_alreadySeparated == -1) {
714  m_alreadySeparated = mySeparate();
715  }
716  return m_alreadySeparated;
717  }
719  int mySeparate();
720 
722  void myImprove();
723 
724 #ifdef OGDF_STP_EXACT_LOGGING
725  void printMainInfosInFeasible(bool header = false) const;
727 #endif
728 
729 private:
730 #ifdef OGDF_STP_EXACT_LOGGING
731  void printConstraint(abacus::Constraint *constraint, Logger::Level level = Logger::Level::Default) const;
733 #endif
734 
736  Master *m_pMaster;
737 
739  int m_alreadySeparated;
740 
742  int m_maxNrCuttingPlanes;
744  bool m_computeNestedCuts;
746  int m_separationStrategy;
748  int m_saturationStrategy;
750  bool m_computeBackCuts;
752  bool m_shuffleTerminals;
754  bool m_minCardinalityCuts;
755 
757  /*
758  * 0: no PH
759  * 1: call PH right before branchting
760  * 2: call PH every iteration
761  */
762  int m_callPrimalHeuristic;
763 
765  virtual Sub *generateSon(abacus::BranchRule *rule) override
766  {
767  return new Sub(master_, this, rule);
768  }
769 };
770 
772 template<typename T>
773 class MinSteinerTreeDirectedCut<T>::EdgeVariable : public abacus::Variable
774 {
775 public:
776  EdgeVariable(abacus::Master *master,
777 #if 0
778  const abacus::Sub *sub,
779 #endif
780  int id,
781  edge e,
782  double coeff,
783  double lb = 0.0,
784  double ub = 1.0,
785  abacus::VarType::TYPE vartype = abacus::VarType::Binary
786  )
787  : abacus::Variable(master, nullptr /*, sub*/, false, false, coeff, lb, ub, vartype)
788  , m_edge(e)
789  , m_id(id)
790  {
791  }
792 
794  edge theEdge() const {return m_edge;}
796  int id() const {return m_id;}
798  double coefficient() const {return this->obj();}
800  node source() const {return m_edge->source();}
802  node target() const {return m_edge->target();}
803 
804 private:
806  edge m_edge;
808  int m_id;
809 };
810 
811 
813 template<typename T>
814 class MinSteinerTreeDirectedCut<T>::EdgeConstraint : public abacus::Constraint
815 {
816 public:
817  EdgeConstraint(abacus::Master *master,
818  edge e1,
819  edge e2,
820  int factor = 1.0,
821  abacus::CSense::SENSE sense = abacus::CSense::Less,
822  double rhs = 1.0)
823  : abacus::Constraint(master, nullptr, sense, rhs, false, false, false)
824  , m_e1(e1)
825  , m_e2(e2)
826  , m_factor(factor)
827  {
828  }
829 
831  double coeff(const abacus::Variable *v) const override
832  {
833  EdgeVariable *edgeVar = (EdgeVariable*)v;
834  edge e = edgeVar->theEdge();
835  if (e != m_e1 && e != m_e2)
836  return 0.0;
837  return m_factor;
838  }
839 
840 private:
842  edge m_e1;
844  edge m_e2;
846  int m_factor;
847 };
848 
849 
851 template<typename T>
852 class MinSteinerTreeDirectedCut<T>::DegreeConstraint : public abacus::Constraint
853 {
854 public:
855  DegreeConstraint(abacus::Master *master,
856  node n,
857  double coeffIn,
858  double coeffOut,
859  abacus::CSense::SENSE sense,
860  double rhs)
861  : abacus::Constraint(master, nullptr, sense, rhs, false, false, false)
862  , m_node(n)
863  , m_coeffIn(coeffIn)
864  , m_coeffOut(coeffOut)
865  {
866  }
867 
869  virtual double coeff(const abacus::Variable *v) const override
870  {
871  EdgeVariable *edgeVar = (EdgeVariable*)v;
872  edge e = edgeVar->theEdge();
873  if (e->target() == m_node) {
874  return m_coeffIn;
875  } else {
876  if (e->source() == m_node) {
877  return m_coeffOut;
878  } else {
879  return 0.0;
880  }
881  }
882  }
883 
885  node theNode() const {return m_node;}
886 
887 private:
889  node m_node;
891  double m_coeffIn;
893  double m_coeffOut;
894 };
895 
896 
898 template<typename T>
899 class MinSteinerTreeDirectedCut<T>::DegreeEdgeConstraint : public abacus::Constraint
900 {
901 public:
902  DegreeEdgeConstraint(abacus::Master *master,
903  edge e,
904  double coeffIn,
905  double coeffEdge,
906  abacus::CSense::SENSE sense,
907  double rhs)
908  : abacus::Constraint(master, nullptr, sense, rhs, false, false, false)
909  , m_edge(e)
910  , m_coeffIn(coeffIn)
911  , m_coeffEdge(coeffEdge)
912  {
913  }
914 
916  double coeff(const abacus::Variable *v) const override
917  {
918  EdgeVariable *edgeVar = (EdgeVariable*)v;
919  edge e = edgeVar->theEdge();
920  // the edge
921  if (e->isParallelDirected(m_edge))
922  return m_coeffEdge;
923  // all edges to vertices x != source
924  if (e->target() != m_edge->source())
925  return 0.0;
926  // reverse edge
927  if (e->source() == m_edge->target())
928  return 0.0;
929  // all ingoing edges of the source (except the reverse edge, of course)
930  return m_coeffIn;
931  }
932 
934  edge theEdge() const {return m_edge;}
935 private:
937  edge m_edge;
939  double m_coeffIn;
941  double m_coeffEdge;
942 };
943 
944 
946 template<typename T>
947 class MinSteinerTreeDirectedCut<T>::DirectedCutConstraint : public abacus::Constraint
948 {
949 public:
950  DirectedCutConstraint(abacus::Master *master, const Graph &g, const MinSTCutMaxFlow<double> *minSTCut, MinSTCutMaxFlow<double>::cutType _cutType)
951  : abacus::Constraint(master, nullptr, abacus::CSense::Greater, 1.0, false, false, false)
952  , m_pGraph(&g)
953  , m_name("")
954  {
955 #ifdef OGDF_STP_EXACT_LOGGING
956  std::cout << "Creating new DirectedCutConstraint: " << std::endl;
957 #endif
958  m_hashKey = 0;
959  m_marked.init(g);
960  for (node n : g.nodes) {
961  if(_cutType == MinSTCutMaxFlow<double>::cutType::FRONT_CUT) {
962  m_marked[n] = minSTCut->isInFrontCut(n);
963 #ifdef OGDF_STP_EXACT_LOGGING
964  if(m_marked[n]) {
965  // TODO: Use lout instead
966  std::cout << " marked node " << n << std::endl;
967  }
968 #endif
969  } else {
970  OGDF_ASSERT(_cutType == MinSTCutMaxFlow<double>::cutType::BACK_CUT);
971  m_marked[n] = !minSTCut->isInBackCut(n);
972  }
973  if (m_marked[n]) {
974  m_nMarkedNodes++;
975  m_hashKey += n->index();
976  }
977  }
978  m_hashKey += m_nMarkedNodes*g.numberOfNodes()*g.numberOfNodes();
979 #ifdef OGDF_STP_EXACT_LOGGING
980  std::cout << " front cut edges:" << std::endl;
981  for (edge e : g.edges) {
982  if(minSTCut->isFrontCutEdge(e)) {
983  std::cout << " " << e << std::endl;
984  }
985  }
986  std::cout << " back cut edges:" << std::endl;
987  for (edge e : g.edges) {
988  if(minSTCut->isBackCutEdge(e)) {
989  std::cout << " " << e << std::endl;
990  }
991  }
992 #endif
993  }
994 
995  double coeff(const abacus::Variable *v) const override;
996 
998  bool active(node n) const {
999  return m_marked[n];
1000  }
1002  bool cutedge(edge e) const {
1003  return m_marked[e->source()] && !m_marked[e->target()];
1004  }
1006  int nMarkedNodes() const { return m_nMarkedNodes; }
1008  bool marked(node n) const { return m_marked[n]; }
1010  unsigned hashKey() const override { return m_hashKey; };
1012  bool equal(const ConVar *cv) const override;
1014  const char *name() const override { return m_name; }
1015 
1016 private:
1018  const Graph *m_pGraph;
1019 
1021  /*
1022  * A vertex is marked iff it is separated by the cut
1023  * i.e., it is contained in the same set as the target
1024  */
1025  NodeArray<bool> m_marked;
1026 
1028  int m_nMarkedNodes;
1029 
1031  unsigned int m_hashKey;
1033  const char *m_name;
1034 };
1035 
1036 
1037 template<typename T>
1038 MinSteinerTreeDirectedCut<T>::Master::Master(
1039  const EdgeWeightedGraph<T> &wG,
1040  const List<node> &terminals,
1041  const NodeArray<bool> &isTerminal,
1042  double eps,
1043  bool relaxed)
1044  : abacus::Master("MinSteinerTreeDirectedCut::Master", true, false, abacus::OptSense::Min, eps)
1045  , m_maxFlowModule(nullptr)
1046  , m_configfile(nullptr)
1047  , m_relaxed(relaxed)
1048  , m_relaxedSolValue(-1)
1049  , m_nIterRoot(-1)
1050  , m_wG(wG)
1051  , m_pCutPool(nullptr)
1052  , m_poolSizeInitFactor(5)
1053  , m_poolSizeMax(0)
1054  , m_maxPoolSize(-1)
1055  , m_nrCutsTotal(0)
1056  , m_addGSEC2Constraints(true)
1057  , m_addDegreeConstraints(true)
1058  , m_addIndegreeEdgeConstraints(true)
1059  , m_addFlowBalanceConstraints(true)
1060  , m_maxNrAddedCuttingPlanes(500)
1061  , m_shuffleTerminals(true)
1062  , m_backCutComputation(true)
1063  , m_nestedCutComputation(true)
1064  , m_separationStrategy(1)
1065  , m_saturationStrategy(1)
1066  , m_minCardinalityCuts(true)
1067  , m_callPrimalHeuristic(1)
1068 {
1069 #ifdef OGDF_STP_EXACT_LOGGING
1070  lout(Level::Default)
1071  << "Master::Master(): default LP solver: "
1072  << this->OSISOLVER_[this->defaultLpSolver()] << std::endl;
1073 #endif
1074  m_pGraph = new Graph();
1075 
1076  edge e1, e2;
1077  int i = 0;
1078  int t = 0;
1079 
1080  m_nodes = new node[m_wG.numberOfNodes()];
1081  m_nodeIDs.init(*m_pGraph);
1082  m_isTerminal.init(*m_pGraph);
1083  m_nTerminals = terminals.size();
1084  m_root = nullptr;
1085 
1086 #ifdef OGDF_STP_EXACT_LOGGING
1087  lout(Level::Default)
1088  << "Master::Master(): nTerminals="
1089  << m_nTerminals << std::flush;
1090  lout(Level::Minor) << " terminals: " << std::flush;
1091 #endif
1092  NodeArray<node> nodeMapping(m_wG);
1093  m_terminals = new node[m_nTerminals];
1094 
1095  for (node nOrig : m_wG.nodes) {
1096  node n = m_pGraph->newNode();
1097  nodeMapping[nOrig] = n;
1098  m_nodes[i] = n;
1099  m_nodeIDs[n] = i;
1100  m_isTerminal[n] = isTerminal[nOrig];
1101  if (m_isTerminal[n]) {
1102 #ifdef OGDF_STP_EXACT_LOGGING
1103  lout(Level::Minor) << n << "," << std::flush;
1104 #endif
1105  m_terminals[t++] = n;
1106  }
1107  i++;
1108  }
1109 #ifdef OGDF_STP_EXACT_LOGGING
1110  lout(Level::Minor) << std::endl << "Master::Master(): edges: ";
1111 #endif
1112 
1113  m_nEdgesU = m_wG.numberOfEdges();
1114  m_capacities.init(*m_pGraph);
1115  m_twin.init(*m_pGraph);
1116  m_edgeIDs.init(*m_pGraph);
1117  m_edges = new edge[2*m_nEdgesU];
1118 
1119  m_mapToOrigGraph.init(*m_pGraph);
1120  m_mapToBidirectedGraph1.init(m_wG);
1121  m_mapToBidirectedGraph2.init(m_wG);
1122 
1123  i = 0;
1124  for (edge eOrig : m_wG.edges) {
1125  e1 = m_pGraph->newEdge(nodeMapping[eOrig->source()],
1126  nodeMapping[eOrig->target()]);
1127  e2 = m_pGraph->newEdge(nodeMapping[eOrig->target()], nodeMapping[eOrig->source()]);
1128  m_capacities[e1] = m_capacities[e2] = m_wG.weight(eOrig);
1129  m_twin[e1] = e2;
1130  m_twin[e2] = e1;
1131  m_edges[i] = e1;
1132  m_edgeIDs[e1] = i++;
1133  m_edges[i] = e2;
1134  m_edgeIDs[e2] = i++;
1135  m_mapToOrigGraph[e1] = eOrig;
1136  m_mapToOrigGraph[e2] = eOrig;
1137  m_mapToBidirectedGraph1[eOrig] = e1;
1138  m_mapToBidirectedGraph2[eOrig] = e2;
1139 #ifdef OGDF_STP_EXACT_LOGGING
1140  lout(Level::Minor) << " " << eOrig << "[" << e1 << ", " << e2 << "]" << std::flush;
1141 #endif
1142  }
1143 #ifdef OGDF_STP_EXACT_LOGGING
1144  lout(Level::Default) << std::endl;
1145 #endif
1146  for (node n : m_pGraph->nodes) {
1147  if (m_isTerminal[n]) {
1148  // possibility to set the root node
1149  // default: terminal with highest degree
1150  if (!m_root)
1151  m_root = n;
1152  else {
1153  if (m_root->degree() < n->degree())
1154  m_root = n;
1155  }
1156  }
1157  }
1158 
1159 #ifdef OGDF_STP_EXACT_LOGGING
1160  lout(Level::Medium) << "Master::Master(): m_root=" << m_root << std::endl;
1161 #endif
1162 
1163  m_isSolutionEdge.init(*m_pGraph, false);
1164  m_bestSolution = new double[m_pGraph->numberOfEdges()];
1165  for (i = 0; i < m_pGraph->numberOfEdges(); i++) {
1166  m_bestSolution[i] = 1.0;
1167  }
1168 
1169  // stuff for "primal heuristic"
1170  m_pWeightedGraphPH = new EdgeWeightedGraph<double>();
1171  m_nodesGToWgPH.init(*m_pGraph);
1172  m_edgesGToWgPH.init(*m_pGraph);
1173  m_isTerminalPH.init(*m_pWeightedGraphPH);
1174  m_edgesWgToGPH.init(*m_pWeightedGraphPH);
1175 
1176  for (node nOrig : m_pGraph->nodes) {
1177  node n = m_pWeightedGraphPH->newNode();
1178  m_nodesGToWgPH[nOrig] = n;
1179  m_isTerminalPH[n] = m_isTerminal[nOrig];
1180  if (m_isTerminalPH[n])
1181  m_terminalListPH.pushBack(n);
1182  if (m_root == nOrig)
1183  m_rootPH = n;
1184  }
1185 
1186  for (edge eOrig : m_pGraph->edges) {
1187  edge e = m_pWeightedGraphPH->newEdge(m_nodesGToWgPH[eOrig->source()], m_nodesGToWgPH[eOrig->target()], 0.0);
1188  m_edgesGToWgPH[eOrig] = e;
1189  m_edgesWgToGPH[e] = eOrig;
1190  }
1191 
1192  // set default primal heuristic module to takahashi algorithm
1193  m_primalHeuristic.reset(new MinSteinerTreeTakahashi<double>());
1194 }
1195 
1196 template<typename T>
1197 void
1198 MinSteinerTreeDirectedCut<T>::Master::initializeParameters()
1199 {
1200  if (m_configfile) {
1201  bool objectiveInteger = false;
1202  try {
1203  this->readParameters(m_configfile);
1204  }
1205  catch (AlgorithmFailureException) {
1206 #ifdef OGDF_STP_EXACT_LOGGING
1207  lout(Level::Alarm)
1208  << "Master::initializeParameters(): Error reading parameters."
1209  << "Using default values." << std::endl;
1210 #endif
1211  }
1212 #ifdef OGDF_STP_EXACT_LOGGING
1213  int outputLevel;
1214  getParameter("OutputLevel", outputLevel);
1215  setOutputLevel(static_cast<Level>(outputLevel));
1216 #endif
1217  int solver = (OSISOLVER) findParameter("DefaultLpSolver", 12, OSISOLVER_);
1218  this->defaultLpSolver((OSISOLVER)solver);
1219  getParameter("AddGSEC2Constraints", m_addGSEC2Constraints);
1220  getParameter("AddDegreeConstraints", m_addDegreeConstraints);
1221  getParameter("AddIndegreeEdgeConstraints", m_addIndegreeEdgeConstraints);
1222  getParameter("AddFlowBalanceConstraints", m_addFlowBalanceConstraints);
1223  getParameter("MaxNrCuttingPlanes", m_maxNrAddedCuttingPlanes);
1224  getParameter("ShuffleTerminals", m_shuffleTerminals);
1225  getParameter("BackCutComputation", m_backCutComputation);
1226  getParameter("NestedCutComputation", m_nestedCutComputation);
1227  getParameter("SeparationStrategy", m_separationStrategy);
1228  getParameter("SaturationStrategy", m_saturationStrategy);
1229  getParameter("MinCardinalityCuts", m_minCardinalityCuts);
1230  getParameter("PrimalHeuristic", m_callPrimalHeuristic);
1231  getParameter("PoolSizeInitFactor", m_poolSizeInitFactor);
1232  getParameter("ObjInteger", objectiveInteger);
1233  this->objInteger(objectiveInteger);
1234  }
1235 
1236 #ifdef OGDF_STP_EXACT_LOGGING
1237  lout(Level::High)
1238  << "Master::initializeParameters(): parameters:" << std::endl
1239  << "\tLP-Solver " << OSISOLVER_[this->defaultLpSolver()] << std::endl
1240  << "\tOutputLevel " << this->localLogLevel() << std::endl
1241  << "\tAddDegreeConstraints " << m_addDegreeConstraints << std::endl
1242  << "\tAddIndegreeEdgeConstraints " << m_addIndegreeEdgeConstraints << std::endl
1243  << "\tAddGSEC2Constraints " << m_addGSEC2Constraints << std::endl
1244  << "\tAddFlowBalanceConstraints " << m_addFlowBalanceConstraints << std::endl
1245  << "\tMaxNrCuttingPlanes " << m_maxNrAddedCuttingPlanes << std::endl
1246  << "\tShuffleTerminals " << m_shuffleTerminals << std::endl
1247  << "\tBackCutComputation " << m_backCutComputation << std::endl
1248  << "\tMinCardinalityCuts " << m_minCardinalityCuts << std::endl
1249  << "\tNestedCutComputation " << m_nestedCutComputation << std::endl;
1250  if (m_nestedCutComputation) {
1251  lout(Level::High)
1252  << "\t SeparationStrategy " << m_separationStrategy << std::endl
1253  << "\t SaturationStrategy " << m_saturationStrategy << std::endl;
1254  }
1255  lout(Level::High)
1256  << "\tPrimalHeuristic " << m_callPrimalHeuristic << std::endl
1257  << "\tPoolSizeInitFactor " << m_poolSizeInitFactor << std::endl
1258  << "\tObjective integer " << this->objInteger() << std::endl
1259  << std::endl;
1260 #endif
1261  setMaxNumberAddedCuttingPlanes(m_maxNrAddedCuttingPlanes);
1262 }
1263 
1264 template<typename T>
1265 void
1266 MinSteinerTreeDirectedCut<T>::Master::initializeOptimization()
1267 {
1268 #ifdef OGDF_STP_EXACT_LOGGING
1269  lout(Level::High)
1270  << "Master::initializeOptimization(): Instance properties:" << std::endl
1271  << "\t(nNodes,nEdges) : (" << m_pGraph->numberOfNodes()
1272  << ", " << m_nEdgesU << ")" << std::endl
1273  << "\tNumber of terminals : " << m_nTerminals << std::endl
1274  << "\tRoot node : " << m_root << std::endl
1275  << std::endl;
1276 #endif
1277  int i;
1278 
1279  // buffer for variables; one for each directed edge
1280  ArrayBuffer<abacus::Variable*> variables(m_pGraph->numberOfEdges());
1281 
1282  // add (edge) variables
1283  EdgeVariable *eVar;
1284  m_edgeToVar.init(*m_pGraph, nullptr);
1285 
1286  abacus::VarType::TYPE vartype = abacus::VarType::Binary;
1287  if (m_relaxed) {
1288  vartype = abacus::VarType::Continuous;
1289  }
1290 
1291  for (i = 0; i < m_pGraph->numberOfEdges(); i++) {
1292  edge e = m_edges[i];
1293  if (e->target() != m_root // not going into root
1294  && !e->isSelfLoop()) {
1295  eVar = new EdgeVariable(this, i, e, m_capacities[e], 0.0, 1.0, vartype);
1296 #ifdef OGDF_STP_EXACT_LOGGING
1297  lout(Level::Minor) << "\tadding variable x_" << i << ", edge " << e << std::endl;
1298 #endif
1299  }
1300  else {
1301  // ub = lb = 0 is not nice, but makes life easier -> ids
1302  OGDF_ASSERT(m_capacities[e] >= 0);
1303  eVar = new EdgeVariable(this, i, e, m_capacities[e], 0.0, 0.0, vartype);
1304 #ifdef OGDF_STP_EXACT_LOGGING
1305  lout(Level::Minor) << "\tmuting variable x_" << i << ", edge " << e << std::endl;
1306 #endif
1307  }
1308  variables.push(eVar);
1309  m_edgeToVar[e] = eVar;
1310  }
1311 
1312  // add constraints
1313  int nCons = 0;
1314  if (m_addGSEC2Constraints)
1315  nCons += m_nEdgesU;
1316  if (m_addDegreeConstraints)
1317  nCons += m_pGraph->numberOfNodes();
1318  if (m_addIndegreeEdgeConstraints)
1319  nCons += m_pGraph->numberOfEdges();
1320  if (m_addFlowBalanceConstraints)
1321  nCons += m_pGraph->numberOfNodes()-1;
1322 
1323  ArrayBuffer<abacus::Constraint*> basicConstraints(nCons);
1324 
1325  i = 0;
1326  if (m_addGSEC2Constraints) {
1327  EdgeArray<bool> marked(*m_pGraph, false);
1328  for (edge e : m_pGraph->edges) {
1329  if (!marked[e]
1330  && !e->isSelfLoop()) { // we have to ignore self-loops here
1331  EdgeConstraint *newCon =
1332  new EdgeConstraint(this, e, m_twin[e], 1, abacus::CSense::Less, 1.0);
1333  basicConstraints.push(newCon);
1334  marked[e] = true;
1335  marked[m_twin[e]] = true;
1336 
1337 #ifdef OGDF_STP_EXACT_LOGGING
1338  lout(Level::Minor) << "\tadding constraint " << i++ << " GSEC2: edge " << e << std::endl;
1339 #endif
1340  }
1341  }
1342  }
1343 
1344  // "degree" constraints:
1345  // (1) forall terminals t != m_root: x(delta-(t)) == 1
1346  // (2) forall non-temrinals n : x(delta-(n)) <= 1
1347  // (3) for the root : x(delta+(m_root)) >= 1
1348  if (m_addDegreeConstraints)
1349  {
1350  for (node n : m_pGraph->nodes) {
1351  DegreeConstraint *newCon;
1352  if (n == m_root) {
1353  // (3)
1354  newCon = new DegreeConstraint(this, n, 0.0, 1.0, abacus::CSense::Greater, 1.0);
1355  }
1356  else {
1357  if (m_isTerminal[n]) {
1358  // (1)
1359  newCon = new DegreeConstraint(this, n, 1.0, 0.0, abacus::CSense::Equal, 1.0);
1360  }
1361  else {
1362  // (2)
1363  newCon = new DegreeConstraint(this, n, 1.0, 0.0, abacus::CSense::Less, 1.0);
1364  }
1365  }
1366  basicConstraints.push(newCon);
1367 
1368 #ifdef OGDF_STP_EXACT_LOGGING
1369  lout(Level::Minor) << "\tadding constraint " << i++ << " Degree: node " << n << std::endl;
1370 #endif
1371  }
1372  }
1373 
1374  if (m_addIndegreeEdgeConstraints) {
1375  for (edge e : m_pGraph->edges) {
1376  if (e->source() != m_root) {
1377  DegreeEdgeConstraint *newCon =
1378  new DegreeEdgeConstraint(this, e, 1.0, -1.0, abacus::CSense::Greater, 0.0);
1379  basicConstraints.push(newCon);
1380 
1381 #ifdef OGDF_STP_EXACT_LOGGING
1382  lout(Level::Minor) << "\tadding constraint " << i++ << " Indegree: edge " << e << std::endl;
1383 #endif
1384  }
1385  }
1386  }
1387 
1388  if (m_addFlowBalanceConstraints) {
1389  for (node n : m_pGraph->nodes) {
1390  if (!m_isTerminal[n]) {
1391  DegreeConstraint *newCon =
1392  new DegreeConstraint(this, n, -1.0, 1.0, abacus::CSense::Greater, 0.0);
1393  basicConstraints.push(newCon);
1394 
1395 #ifdef OGDF_STP_EXACT_LOGGING
1396  lout(Level::Minor) << "\tadding constraint " << i++ << " Flow-Balance: node " << n << std::endl;
1397 #endif
1398  }
1399  }
1400  }
1401 
1402  m_poolSizeInit = m_poolSizeInitFactor * m_pGraph->numberOfEdges();
1403  m_poolSizeMax = m_poolSizeInit;
1404  // initialize the non-duplicate cut pool
1405  m_pCutPool = new abacus::NonDuplPool<abacus::Constraint, abacus::Variable>(this, m_poolSizeInit, true);
1406 
1407  this->initializePools(
1408  basicConstraints,
1409  variables,
1410  0,
1411  nCons,
1412  true);
1413 
1414 #ifdef OGDF_STP_EXACT_LOGGING
1415  lout(Level::Minor) << "Master::initializeOptimization() done." << std::endl;
1416 #endif
1417 }
1418 
1419 
1420 template<typename T>
1421 void
1422 MinSteinerTreeDirectedCut<T>::Master::terminateOptimization()
1423 {
1424  int nOnesInSol = 0;
1425  for (int i = 0; i < m_pGraph->numberOfEdges(); i++) {
1426  if (m_bestSolution[i] > 0.5) {
1427  m_isSolutionEdge[m_edges[i]] = true;
1428  nOnesInSol++;
1429  }
1430  }
1431 
1432 #ifdef OGDF_STP_EXACT_LOGGING
1433  lout(Level::High) << std::endl;
1434  if (is_lout(Level::Medium)) {
1435  lout(Level::Medium) << "\toptimum solution edges:" << std::endl;
1436  for (edge e : m_pGraph->edges) {
1437  if (m_isSolutionEdge[e])
1438  lout(Level::Medium) << "\t" << e << std::endl;
1439  }
1440  }
1441  lout(Level::Medium) << std::endl;
1442 
1443  lout(Level::High)
1444  << "Finished optimization. Statistics:" << std::endl
1445  << "Solution " << std::endl
1446  << " value " << this->primalBound() << std::endl
1447  << " rounded sol. value " << ((int)this->primalBound()) << std::endl
1448  << " nr edges " << nOnesInSol << std::endl
1449  << "Status " << this->STATUS_[this->status()] << std::endl
1450  << "Primal/dual bound " << this->primalBound() << "/" << this->dualBound() << std::endl
1451  << "Relaxed solution value " << this->m_relaxedSolValue << std::endl
1452  << "Nr subproblems " << this->nSub() << std::endl
1453  << "Nr solved LPs " << this->nLp() << std::endl
1454  << "nr solved LPs in root " << m_nIterRoot << std::endl
1455  << std::endl
1456 
1457  << "LP Solver " << this->OSISOLVER_[this->defaultLpSolver()] << std::endl
1458  << "Enumeration strategy " << this->ENUMSTRAT_[this->enumerationStrategy()] << std::endl
1459  << "Branching strategy " << this->BRANCHINGSTRAT_[this->branchingStrategy()] << std::endl
1460  << "Objective integer " << (this->objInteger()? "true":"false") << std::endl
1461  << std::endl
1462 
1463  << "Total time (centi sec) " << this->totalTime()->centiSeconds() << std::endl
1464  << "Total time " << *this->totalTime() << std::endl
1465  << "Total cow-time " << *this->totalCowTime() << std::endl
1466  << "LP time " << *this->lpTime() << std::endl
1467  << "LP solver time " << *this->lpSolverTime() << std::endl
1468  << "Separation time " << this->m_separationTimer << std::endl
1469  << "Minimum Cut time " << this->m_timerMinSTCut << std::endl
1470  << "Primal heuristic time " << this->m_primalHeuristicTimer << std::endl
1471  << std::endl
1472 
1473  << "Initial cutpool size " << this->m_poolSizeInit << std::endl
1474  << "Maximum cutpool size " << this->m_poolSizeMax << std::endl
1475  << "Nr separated cuts " << m_nrCutsTotal << std::endl;
1476 
1477  int nDuplicates, nCollisions;
1478  m_pCutPool->statistics(nDuplicates, nCollisions);
1479  lout(Level::High)
1480  << "Cutpool duplications " << nDuplicates << std::endl
1481  << "Cutpool collisions " << nCollisions << std::endl
1482  << std::endl;
1483 #endif
1484 }
1485 
1486 
1487 template<typename T>
1488 void
1489 MinSteinerTreeDirectedCut<T>::Master::updateBestSolution(double *values)
1490 {
1491  double eps = this->eps();
1492  double oneMinusEps = 1.0 - eps;
1493  for (int i = 0; i < m_pGraph->numberOfEdges(); i++) {
1494  if (values[i] > oneMinusEps)
1495  m_bestSolution[i] = 1.0;
1496  else
1497  if (values[i] < eps)
1498  m_bestSolution[i] = 0.0;
1499  else
1500  m_bestSolution[i] = values[i];
1501  }
1502 }
1503 
1504 template<typename T>
1505 void
1506 MinSteinerTreeDirectedCut<T>::Master::updateBestSolutionByEdges(const List<edge> &sol)
1507 {
1508  for (int i = 0; i < m_pGraph->numberOfEdges(); i++) {
1509  m_bestSolution[i] = 0.0;
1510  }
1511  for (ListConstIterator<edge> it = sol.begin(); it.valid(); it++) {
1512  m_bestSolution[m_edgeIDs[*it]] = 1.0;
1513  }
1514 }
1515 
1516 
1517 template<typename T>
1518 MinSteinerTreeDirectedCut<T>::Sub::Sub(abacus::Master *master)
1519  : abacus::Sub(master,0,0,0)
1520  , m_alreadySeparated(-1)
1521 {
1522  m_pMaster = (Master*) master;
1523  m_computeNestedCuts = m_pMaster->computeNestedCuts();
1524  m_computeBackCuts = m_pMaster->computeBackCuts();
1525  m_shuffleTerminals = m_pMaster->shuffleTerminals();
1526  m_minCardinalityCuts = m_pMaster->minCardinalityCuts();
1527  m_maxNrCuttingPlanes = m_pMaster->maxNrAddedCuttingPlanes();
1528  m_callPrimalHeuristic= m_pMaster->callPrimalHeuristicStrategy();
1529  m_separationStrategy = m_pMaster->separationStrategy();
1530  m_saturationStrategy = m_pMaster->saturationStrategy();
1531 }
1532 
1533 
1534 template<typename T>
1535 MinSteinerTreeDirectedCut<T>::Sub::Sub(abacus::Master *master, abacus::Sub *father, abacus::BranchRule *branchRule)
1536  : abacus::Sub(master, father, branchRule)
1537  , m_alreadySeparated(-1)
1538 {
1539  m_pMaster = (Master*) master;
1540 #ifdef OGDF_STP_EXACT_LOGGING
1541  m_pMaster->lout(Logger::Level::High)
1542  << std::setw(7) << this->id()
1543  << std::setw(7) << this->nIter_
1544  << " new subproblem, parent=" << father->id() << std::endl;
1545 #endif
1546  m_computeNestedCuts = m_pMaster->computeNestedCuts();
1547  m_computeBackCuts = m_pMaster->computeBackCuts();
1548  m_shuffleTerminals = m_pMaster->shuffleTerminals();
1549  m_minCardinalityCuts = m_pMaster->minCardinalityCuts();
1550  m_maxNrCuttingPlanes = m_pMaster->maxNrAddedCuttingPlanes();
1551  m_callPrimalHeuristic= m_pMaster->callPrimalHeuristicStrategy();
1552  m_separationStrategy = m_pMaster->separationStrategy();
1553  m_saturationStrategy = m_pMaster->saturationStrategy();
1554 }
1555 
1556 #ifdef OGDF_STP_EXACT_LOGGING
1557 template<typename T>
1558 void
1559 MinSteinerTreeDirectedCut<T>::Sub::printMainInfosInFeasible(bool header) const
1560 {
1561  if (header) {
1562  // print header
1563  m_pMaster->lout(Logger::Level::High)
1564  << std::endl
1565  << std::setw(7) << "id"
1566  << std::setw(7) << "iter"
1567  << std::setw(10) << "lp value"
1568  << std::setw(10) << "gl. LB"
1569  << std::setw(10) << "gl. UB"
1570  << std::setw(10) << "nSub"
1571  << std::setw(10) << "nOpenSub"
1572  << std::endl;
1573  }
1574  else {
1575  m_pMaster->lout(Logger::Level::High)
1576  << std::setw(7) << this->id()
1577  << std::setw(7) << this->nIter_
1578  << std::setw(10) << lp_->value();
1579  if (this->id() == 1)
1580  m_pMaster->lout(Logger::Level::High) << std::setw(10) << "--";
1581  else
1582  m_pMaster->lout(Logger::Level::High) << std::setw(10) << master_->lowerBound();
1583  if (master_->feasibleFound())
1584  m_pMaster->lout(Logger::Level::High) << std::setw(10) << master_->upperBound();
1585  else
1586  m_pMaster->lout(Logger::Level::High) << std::setw(10) << "--";
1587  m_pMaster->lout(Logger::Level::High)
1588  << std::setw(10) << master_->nSub()
1589  << std::setw(10) << master_->openSub()->number()
1590  << std::endl;
1591  m_pMaster->lout(Logger::Level::Minor)
1592  << "\tcurrent LP:" << std::endl;
1593  m_pMaster->lout(Logger::Level::Minor) << *lp_;
1594  m_pMaster->lout(Logger::Level::Minor) << std::endl;
1595  }
1596 }
1597 #endif
1598 
1599 template<typename T>
1600 bool
1601 MinSteinerTreeDirectedCut<T>::Sub::feasible()
1602 {
1603  double eps = master_->eps();
1604  double oneMinusEps = 1.0 - eps;
1605 
1606 #ifdef OGDF_STP_EXACT_LOGGING
1607  if (this->nIter_ == 1) {
1608  this->printMainInfosInFeasible(true);
1609  }
1610  else
1611  this->printMainInfosInFeasible(false);
1612 #endif
1613 
1614  // separate directed cuts
1615  m_alreadySeparated = mySeparate();
1616 
1617  if (m_alreadySeparated > 0) {
1618  if (m_callPrimalHeuristic == 2 && !m_pMaster->relaxed()) {
1619  myImprove();
1620  }
1621  return false;
1622  }
1623 
1624  if (this->id() == 1) {
1625  // set some statistics if we are in the root node
1626  m_pMaster->setRelaxedSolValue(lp_->value());
1627  m_pMaster->setNIterRoot(nIter_);
1628  }
1629 
1630  if (!m_pMaster->relaxed()) {
1631  // check integrality
1632  for (int i = 0; i < m_pMaster->nEdges(); i++) {
1633  if (xVal_[i] > eps && xVal_[i] < oneMinusEps) {
1634  // found non-integral solution but no violated directed cuts
1635  // i.e., we have to branch.
1636  // But first, we call the primal heuristic
1637  if (m_callPrimalHeuristic > 0) {
1638  myImprove();
1639  }
1640 
1641 #ifdef OGDF_STP_EXACT_LOGGING
1642  m_pMaster->lout(Logger::Level::Default)
1643  << "\tsolution is fractional -> Branching." << std::endl;
1644 #endif
1645  return false;
1646  }
1647  }
1648  }
1649 
1650  if (m_pMaster->betterPrimal(lp_->value())) {
1651 #ifdef OGDF_STP_EXACT_LOGGING
1652  m_pMaster->lout(Logger::Level::High)
1653  << std::setw(7) << this->id()
1654  << std::setw(7) << this->nIter_
1655  << " found better integer solution with value " << lp_->value();
1656  if (m_pMaster->is_lout(Logger::Level::Medium)) {
1657  m_pMaster->lout(Logger::Level::Medium) << ", variables > 0:" << std::endl;
1658  printCurrentSolution();
1659  }
1660  else
1661  m_pMaster->lout(Logger::Level::High) << std::endl;
1662 #endif
1663  m_pMaster->primalBound(lp_->value());
1664  m_pMaster->updateBestSolution(xVal_);
1665  }
1666 
1667  return true;
1668 }
1669 
1670 #ifdef OGDF_STP_EXACT_LOGGING
1671 template<typename T>
1672 void
1673 MinSteinerTreeDirectedCut<T>::Sub::printCurrentSolution(bool onlyNonZeros)
1674 {
1675  int nOnesInSol = 0;
1676  double eps = master_->eps();
1677  double oneMinusEps = 1.0 - eps;
1678  for (int i = 0; i < nVar(); i++) {
1679  if (xVal_[i] > -eps && xVal_[i] < eps) {
1680  if (!onlyNonZeros) {
1681  m_pMaster->lout(Logger::Level::Minor) << "\tx" << i << "=0" << std::flush;
1682  m_pMaster->lout(Logger::Level::Minor) << " [edge " << ((EdgeVariable*)variable(i))->theEdge() << "]" << std::endl;
1683  }
1684  }
1685  else if (xVal_[i] > oneMinusEps && xVal_[i] < 1+eps) {
1686  m_pMaster->lout(Logger::Level::Minor) << "\tx" << i << "=1" << std::flush;
1687  m_pMaster->lout(Logger::Level::Minor) << " [edge " << ((EdgeVariable*)variable(i))->theEdge() << "]" << std::endl;
1688  nOnesInSol++;
1689  }
1690  else {
1691  m_pMaster->lout(Logger::Level::Minor) << "\tx" << i << "=" << xVal_[i] << std::flush;
1692  m_pMaster->lout(Logger::Level::Minor) << " [edge " << ((EdgeVariable*)variable(i))->theEdge() << "]" << std::endl;
1693  }
1694  }
1695  m_pMaster->lout(Logger::Level::Medium) << "\tnEdges=" << nOnesInSol << std::endl << std::flush;
1696 }
1697 #endif
1698 
1699 template<typename T>
1700 int
1701 MinSteinerTreeDirectedCut<T>::Sub::mySeparate()
1702 {
1703 #ifdef OGDF_STP_EXACT_LOGGING
1704  m_pMaster->lout(Logger::Level::Medium)
1705  << "Sub::mySeparate(): id="
1706  << this->id() << ", iter=" << this->nIter_ << std::endl;
1707 #endif
1708  m_pMaster->separationTimer()->start();
1709  double eps = master_->eps();
1710  double cardEps = eps / 100;
1711  double oneMinusEps = 1 - eps;
1712  node r = m_pMaster->rootNode();
1713  const Graph &g = m_pMaster->graph();
1714  int nEdgesU = m_pMaster->nEdgesU();
1715 
1716  int nTerminals = m_pMaster->nTerminals();
1717  const node *masterTerminals = m_pMaster->terminals();
1718  Array<node> terminal(nTerminals);
1719 
1720  for (int i = 0; i < nTerminals; i++) {
1721  terminal[i] = masterTerminals[i];
1722  }
1723 
1724  if (m_shuffleTerminals) {
1725  // shuffle the ordering of the terminals
1726  int j;
1727  node h = nullptr;
1728  for (int i = 0; i < nTerminals-1; i++) {
1729  j = randomNumber(i, nTerminals-1);
1730  h = terminal[i];
1731  terminal[i] = terminal[j];
1732  terminal[j] = h;
1733  }
1734  }
1735 
1736 #ifdef OGDF_STP_EXACT_LOGGING
1737  if (m_pMaster->is_lout(Logger::Level::Medium)) {
1738  m_pMaster->lout(Logger::Level::Medium)
1739  << "Sub::mySeparate(): considered terminal ordering: ";
1740  for (int i = 0; i < nTerminals; i++)
1741  m_pMaster->lout(Logger::Level::Medium) << terminal[i] << " ";
1742  m_pMaster->lout(Logger::Level::Medium) << std::endl;
1743  }
1744 #endif
1745 
1746  EdgeArray<double> capacities;
1747  capacities.init(g, 0);
1748  for (edge e : g.edges) {
1749  // some LP solvers might return a negative epsilon instead of 0 due to numerical reasons
1750  capacities[e] = max(xVal_[m_pMaster->edgeID(e)], 0.);
1751  if (m_minCardinalityCuts)
1752  capacities[e] += cardEps;
1753  }
1754 
1755 #ifdef OGDF_STP_EXACT_LOGGING
1756  m_pMaster->lout(Logger::Level::Minor)
1757  << "Sub::mySeparate(): current capacities (>0) for mincut computation:" << std::endl;
1758  for (edge e : g.edges) {
1759  if (capacities[e] >= 2*cardEps) {
1760  m_pMaster->lout(Logger::Level::Minor) << "\tcapacity[" << e << "]=" << capacities[e] << std::endl;
1761  }
1762  }
1763 #endif
1764  // Minimum s-t-cut object
1765  MinSTCutMaxFlow<double> minSTCut;
1766  // current terminal
1767  node t;
1768  // index of current terminal
1769  int ti = 0;
1770  // value of current cut
1771  double cutValue = 2.0;
1772  // value of current back cut
1773  double cutValueBack = 0.0;
1774  // for backcut computation
1775  int nOtherNodes = 0;
1776  // upper bound for mincut computation
1777  double uBound = 1 + nEdgesU*cardEps;
1778  // nr of violated cuts found
1779  int cutsFound = 0;
1780 
1781  // buffer for new constraints
1782  ArrayBuffer<abacus::Constraint*> newConstraints(m_maxNrCuttingPlanes);
1783 
1784  // size of cut and backcut
1785  int cardinalityCut, cardinalityBackcut;
1786  cardinalityCut = cardinalityBackcut = 0;
1787 
1788  // Only relevant if nested cuts are computed:
1789  // this list contains the modified edges i.e., the saturated edges.
1790  // The capacity of these edges can is reset in SeparationStrategy 2
1791  List<edge> modified;
1792 
1793  // main while loop for the computation of the cutting planes
1794  while (cutsFound < m_maxNrCuttingPlanes && ti < nTerminals) {
1795  t = terminal[ti];
1796  if (t != r) {
1797 #ifdef OGDF_STP_EXACT_LOGGING
1798  m_pMaster->lout(Logger::Level::Medium)
1799  << "Sub::mySeparate(): computing minimum cut between root " << r << " and " << t << std::flush;
1800 #endif
1801  // /compute the minimum r-t-cut
1802  /*
1803  * the cut itself is stored in the integer array with values
1804  * in {0,1,2}. If a node has the value 1, it is contained in the
1805  * subset of the root, 2 indicates the set of the separated node, and
1806  * 0 depicts the set in between
1807  */
1808  m_pMaster->timerMinSTCut()->start();
1809 
1810  EdgeArray<double> flow;
1811  MaxFlowModule<double> *mf = m_pMaster->getMaxFlowModule();
1812  OGDF_ASSERT(mf != nullptr);
1813  mf->init(g);
1814  mf->useEpsilonTest(cardEps / 100);
1815  cutValue = mf->computeFlow(capacities, r, t, flow);
1816 #ifdef OGDF_STP_EXACT_LOGGING
1817  m_pMaster->lout(Logger::Level::Medium) << " Calculated flow:" << std::endl;
1818  for (edge flowEdge : g.edges) {
1819  m_pMaster->lout(Logger::Level::Medium)
1820  << " " << flowEdge << " : "
1821  << flow[flowEdge] << " / " << capacities[flowEdge] << std::endl;
1822  }
1823 #endif
1824 
1825  // used epsilon should be smaller than the eps used for cardinality cuts heuristic
1826  minSTCut.setEpsilonTest(new EpsilonTest(cardEps / 100));
1827  minSTCut.call(g, capacities, flow, r, t);
1828 
1829  m_pMaster->timerMinSTCut()->stop();
1830  cutValueBack = 0;
1831 
1832 #ifdef OGDF_STP_EXACT_LOGGING
1833  m_pMaster->lout(Logger::Level::Medium) << ", cutvalue=" << cutValue << std::flush;
1834 #endif
1835 
1836  // min cardinality
1837  if (m_minCardinalityCuts && cutValue < uBound) {
1838  for (edge e : g.edges) {
1839  if (minSTCut.isFrontCutEdge(e)) {
1840  cutValue -= cardEps;
1841  }
1842  if (m_computeBackCuts && minSTCut.isBackCutEdge(e)) {
1843  cutValueBack += capacities[e] - cardEps;
1844  }
1845  }
1846  } else if (m_computeBackCuts) {
1847  for (edge e : g.edges) {
1848  if (minSTCut.isBackCutEdge(e)) {
1849  cutValueBack += capacities[e];
1850  }
1851  }
1852  }
1853 
1854  if (m_saturationStrategy == 2) {
1855  cardinalityCut = cardinalityBackcut = 0;
1856  for (edge e : g.edges) {
1857  if (minSTCut.isFrontCutEdge(e))
1858  cardinalityCut++;
1859  if (m_computeBackCuts && minSTCut.isBackCutEdge(e))
1860  cardinalityBackcut++;
1861  }
1862  }
1863 
1864 #ifdef OGDF_STP_EXACT_LOGGING
1865  m_pMaster->lout(Logger::Level::Medium)
1866  << ", actual cutvalue=" << cutValue;
1867  if (m_computeBackCuts)
1868  m_pMaster->lout(Logger::Level::Medium)
1869  << ", actual cutValueBack=" << cutValueBack;
1870  m_pMaster->lout(Logger::Level::Medium) << std::endl;
1871 #endif
1872  nOtherNodes = 0;
1873 
1874  if (cutValue < oneMinusEps) {
1875  // found violated cut
1876  cutsFound++;
1877  // generate new constraint
1878  DirectedCutConstraint *newCut = new DirectedCutConstraint(master_, g, &minSTCut, MinSTCutMaxFlow<double>::cutType::FRONT_CUT);
1879  // push cut to the set of new constraints
1880  newConstraints.push(newCut);
1881 
1882 #ifdef OGDF_STP_EXACT_LOGGING
1883  m_pMaster->lout(Logger::Level::Medium)
1884  << "Sub::mySeparate(): found violated cut:" << std::endl;
1885  printConstraint(newCut, Logger::Level::Medium);
1886 #endif
1887  if (m_computeBackCuts
1888  && !minSTCut.frontCutIsComplementOfBackCut()
1889  && cutsFound < m_maxNrCuttingPlanes
1890  && cutValueBack <= oneMinusEps) {
1891  cutsFound++;
1892  // generate new constraint
1893  DirectedCutConstraint *newBackCut = new DirectedCutConstraint(master_, g, &minSTCut, MinSTCutMaxFlow<double>::cutType::BACK_CUT);
1894  // push cut to the set of new constraints
1895  newConstraints.push(newBackCut);
1896 
1897 #ifdef OGDF_STP_EXACT_LOGGING
1898  m_pMaster->lout(Logger::Level::Medium)
1899  << "Sub::mySeparate(): found violated cut (backcut):" << std::endl;
1900  printConstraint(newBackCut, Logger::Level::Medium);
1901 #endif
1902  }
1903 
1904  // saturate cut edges in case of nested cut computation
1905  if (m_computeNestedCuts)
1906  {
1907  for (edge e : g.edges) {
1908  if (minSTCut.isFrontCutEdge(e)) {
1909  if (m_saturationStrategy == 2)
1910  capacities[e] = 1.0/(double)cardinalityCut + eps;
1911  else
1912  capacities[e] = 1.0 + eps;
1913  // for resetting the saturation after each iteration
1914  if (m_separationStrategy == 2)
1915  modified.pushBack(e);
1916  }
1917  else {
1918  if (m_computeBackCuts
1919  && nOtherNodes > 0
1920  && cutValueBack <= oneMinusEps
1921  && minSTCut.isBackCutEdge(e)) {
1922  if (m_saturationStrategy == 2)
1923  capacities[e] = 1.0/(double)cardinalityBackcut + eps;
1924  else
1925  capacities[e] = 1.0 + eps;
1926  // for resetting the saturation after each iteration
1927  if (m_separationStrategy == 2)
1928  modified.pushBack(e);
1929  }
1930  }
1931  }
1932  }
1933  }
1934  }
1935 
1936  if (!m_computeNestedCuts) {
1937  ti++;
1938  } else {
1939  if (cutValue > oneMinusEps || r == t) {
1940  ti++;
1941  if (m_separationStrategy == 2) {
1942  while (!modified.empty()) {
1943  edge e = modified.popFrontRet();
1944  capacities[e] = xVal_[m_pMaster->edgeID(e)];
1945  if (m_minCardinalityCuts)
1946  capacities[e] += cardEps;
1947  }
1948  }
1949  }
1950  }
1951  }
1952 
1953  m_alreadySeparated = cutsFound;
1954 
1955  if (cutsFound > 0) {
1956  // add separated directed cuts
1957  int nAdded = addCons(newConstraints, m_pMaster->cutPool());
1958  // update statistics
1959  m_pMaster->incNrCutsTotal(nAdded);
1960  m_pMaster->checkSetMaxPoolSize();
1961  if (nAdded != cutsFound) {
1962  // ToDo: is this a problem?!
1963  }
1964  }
1965 
1966 #ifdef OGDF_STP_EXACT_LOGGING
1967  m_pMaster->lout(Logger::Level::Medium)
1968  << "Sub::mySeparate(): id="
1969  << this->id() << ", iter=" << this->nIter_
1970  << " separated " << cutsFound << " directed cuts" << std::endl;
1971 #endif
1972  m_pMaster->separationTimer()->stop();
1973 
1974  return cutsFound;
1975 }
1976 
1977 template<typename T>
1978 void
1979 MinSteinerTreeDirectedCut<T>::Sub::myImprove()
1980 {
1981  m_pMaster->primalHeuristicTimer()->start();
1982 
1983 #ifdef OGDF_STP_EXACT_LOGGING
1984  m_pMaster->lout(Logger::Level::Minor)
1985  << "Sub::myImprove(): id="
1986  << this->id() << ", iter=" << this->nIter_ << std::endl;
1987 #endif
1988  double eps = master_->eps();
1989  const Graph &g = m_pMaster->graph();
1990  EdgeWeightedGraph<double> &ewg = m_pMaster->weightedGraphPH();
1991 
1992 #ifdef OGDF_STP_EXACT_LOGGING
1993  if (m_pMaster->ilout(Logger::Level::Minor)) {
1994  m_pMaster->lout(Logger::Level::Minor)
1995  << "Sub::myImprove(): current solution:" << std::endl;
1996  for(edge e : g.edges) {
1997  m_pMaster->lout(Logger::Level::Minor)
1998  << "\tx" << m_pMaster->edgeID(e) << "=" << xVal_[m_pMaster->edgeID(e)]
1999  << ", edge " << e << std::endl;
2000  }
2001  }
2002 #endif
2003 
2004  // set edge weights to eps + (1-x_e)*c_e, forall edges e
2005  // thereby, use minimum of e and twin(e), respectively
2006  double currWeight, twinWeight;
2007  for (edge e : g.edges) {
2008  edge e2 = m_pMaster->twin(e);
2009  currWeight = 1.0-xVal_[m_pMaster->edgeID(e)];
2010  twinWeight = 1.0-xVal_[m_pMaster->edgeID(e2)];
2011  if (twinWeight < currWeight)
2012  currWeight = twinWeight;
2013  if (currWeight < 0)
2014  currWeight = 0;
2015  ewg.setWeight(m_pMaster->edgeGToWgPH(e), eps + currWeight * variable(m_pMaster->edgeID(e))->obj());
2016  }
2017 
2018 #ifdef OGDF_STP_EXACT_LOGGING
2019  if (m_pMaster->ilout(Logger::Level::Minor)) {
2020  m_pMaster->lout(Logger::Level::Minor)
2021  << "Sub::myImprove(): edge weights:" << std::endl;
2022  for (edge e : g.edges) {
2023  m_pMaster->lout(Logger::Level::Minor)
2024  << "\tweight[" << e << "]=" << ewg.weight(m_pMaster->edgeGToWgPH(e)) << std::endl;
2025  }
2026  }
2027 #endif
2028 
2029  // get primal heuristic algorithm
2030  auto &primalHeuristic = m_pMaster->getPrimalHeuristic();
2031 
2032  // the computed heuristic solution
2033  EdgeWeightedGraphCopy<double> *heuristicSolutionWg = nullptr;
2034 
2035 #ifdef OGDF_STP_EXACT_LOGGING
2036  // heuristic solution value for the modified edge weights
2037  double tmpHeuristicSolutionValue =
2038 #endif
2039  // call primal heuristic
2040  primalHeuristic->call(
2041  m_pMaster->weightedGraphPH(),
2042  m_pMaster->terminalListPH(),
2043  m_pMaster->isTerminalPH(),
2044  heuristicSolutionWg);
2045 
2046  // verify that solution is a Steiner tree
2047  bool isSteinerTree = primalHeuristic->isSteinerTree(
2048  m_pMaster->weightedGraphPH(),
2049  m_pMaster->terminalListPH(),
2050  m_pMaster->isTerminalPH(),
2051  *heuristicSolutionWg);
2052 
2053 #ifdef OGDF_STP_EXACT_LOGGING
2054  m_pMaster->lout(Logger::Level::Default)
2055  << "Sub::myImprove(): primal heuristic algorithm returned solution with "
2056  << "value " << tmpHeuristicSolutionValue << ", isSteinerTree=" << isSteinerTree << std::endl;
2057 #endif
2058 
2059  if (isSteinerTree) {
2060  // actual heuristic solution value, i.e., by using real edge weights
2061  double heuristicSolutionValue = 0.0;
2062  // list of edges in the heuristic solution
2063  List<edge> solutionEdges;
2064 
2065  for (edge e : heuristicSolutionWg->edges) {
2066  edge e2 = m_pMaster->edgeWgToGPH(heuristicSolutionWg->original(e));
2067  solutionEdges.pushBack(e2);
2068  heuristicSolutionValue += m_pMaster->capacities(e2);
2069 #ifdef OGDF_STP_EXACT_LOGGING
2070  m_pMaster->lout(Logger::Level::Minor)
2071  << "\t" << e << " -> " << e2 << " c=" << m_pMaster->capacities(e2) << std::endl;
2072 #endif
2073  }
2074 
2075 #ifdef OGDF_STP_EXACT_LOGGING
2076  m_pMaster->lout(Logger::Level::Default)
2077  << "Sub::myImprove(): found integer solution with value "
2078  << heuristicSolutionValue << std::endl;
2079 #endif
2080  if (m_pMaster->betterPrimal(heuristicSolutionValue)) {
2081 #ifdef OGDF_STP_EXACT_LOGGING
2082  m_pMaster->lout(Logger::Level::High)
2083  << std::setw(7) << this->id()
2084  << std::setw(7) << this->nIter_
2085  << " primal heuristic founds better integer solution with value " << heuristicSolutionValue << std::endl;
2086 #endif
2087  m_pMaster->primalBound(heuristicSolutionValue);
2088  m_pMaster->updateBestSolutionByEdges(solutionEdges);
2089  }
2090  }
2091 #ifdef OGDF_STP_EXACT_LOGGING
2092  else {
2093  m_pMaster->lout(Logger::Level::High)
2094  << "Sub::myImprove(): id="
2095  << this->id() << ", iter=" << this->nIter_
2096  << ": computed solution is no Steiner tree!" << std::endl;
2097  }
2098 #endif
2099 
2100  delete heuristicSolutionWg;
2101  m_pMaster->primalHeuristicTimer()->stop();
2102 }
2103 
2104 #ifdef OGDF_STP_EXACT_LOGGING
2105 template<typename T>
2106 void
2107 MinSteinerTreeDirectedCut<T>::Sub::printConstraint(abacus::Constraint *constraint, Logger::Level level) const
2108 {
2109  double eps = master_->eps();
2110  double val = 0;
2111  abacus::Variable *var;
2112  bool first = true;
2113  for (int i = 0; i < nVar(); i++) {
2114  var = variable(i);
2115  val = constraint->coeff(var);
2116  if (val > eps || val < -eps) {
2117  if (val > 0) {
2118  if (val > 1-eps && val < 1+eps) {
2119  if (!first)
2120  m_pMaster->lout(level) << " + ";
2121  }
2122  else {
2123  if (!first)
2124  m_pMaster->lout(level) << " + " << val;
2125  }
2126  }
2127  else {
2128  if (val < -1+eps && val > -1-eps) {
2129  if (!first)
2130  m_pMaster->lout(level) << " - ";
2131  else
2132  m_pMaster->lout(level) << " -";
2133  }
2134  else {
2135  if (!first)
2136  m_pMaster->lout(level) << " - " << (-1)*val;
2137  else
2138  m_pMaster->lout(level) << val;
2139  }
2140  }
2141  m_pMaster->lout(level) << "x" << i;
2142  first = false;
2143  }
2144  }
2145  m_pMaster->lout(level)
2146  << " " << *(constraint->sense()) << " "
2147  << constraint->rhs() << std::endl;
2148 }
2149 #endif
2150 
2151 template<typename T>
2152 bool
2153 MinSteinerTreeDirectedCut<T>::DirectedCutConstraint::equal(const ConVar *cv) const
2154 {
2155  if (m_hashKey != cv->hashKey()) {
2156  return false;
2157  }
2158  DirectedCutConstraint *dirCut = (DirectedCutConstraint*)cv;
2159  if (m_nMarkedNodes != dirCut->nMarkedNodes())
2160  return false;
2161  for (node n : m_pGraph->nodes) {
2162  if (m_marked[n] != dirCut->marked(n)) {
2163  return false;
2164  }
2165  }
2166  return true;
2167 }
2168 
2169 
2170 template<typename T>
2171 double
2172 MinSteinerTreeDirectedCut<T>::DirectedCutConstraint::coeff(const abacus::Variable *v) const
2173 {
2174  EdgeVariable *edgeVar = (EdgeVariable*)v;
2175  if (this->cutedge(edgeVar->theEdge())) {
2176  return 1.0;
2177  }
2178  return 0.0;
2179 }
2180 
2181 
2182 template<typename T>
2183 T MinSteinerTreeDirectedCut<T>::computeSteinerTree(const EdgeWeightedGraph<T> &G, const List<node> &terminals, const NodeArray<bool> &isTerminal, EdgeWeightedGraphCopy<T> *&finalSteinerTree)
2184 {
2185  Master stpMaster(G, terminals, isTerminal, m_eps);
2186  if (m_configFile) {
2187  stpMaster.setConfigFile(m_configFile);
2188  }
2189 #ifdef OGDF_STP_EXACT_LOGGING
2190  stpMaster.setOutputLevel(m_outputLevel);
2191 #endif
2192  stpMaster.useDegreeConstraints(m_addDegreeConstraints);
2193  stpMaster.useIndegreeEdgeConstraints(m_addIndegreeEdgeConstraints);
2194  stpMaster.useGSEC2Constraints(m_addGSEC2Constraints);
2195  stpMaster.useFlowBalanceConstraints(m_addFlowBalanceConstraints);
2196  stpMaster.setMaxNumberAddedCuttingPlanes(m_maxNrAddedCuttingPlanes);
2197  stpMaster.useTerminalShuffle(m_shuffleTerminals);
2198  stpMaster.useBackCuts(m_backCutComputation);
2199  stpMaster.useNestedCuts(m_nestedCutComputation);
2200  stpMaster.setSeparationStrategy(m_separationStrategy);
2201  stpMaster.setSaturationStrategy(m_saturationStrategy);
2202  stpMaster.useMinCardinalityCuts(m_minCardinalityCuts);
2203  stpMaster.setMaxFlowModule(m_maxFlowModuleOption.get());
2204  if (m_primalHeuristic) {
2205  stpMaster.setPrimalHeuristic(m_primalHeuristic);
2206  }
2207  stpMaster.setPrimalHeuristicCallStrategy(m_callPrimalHeuristic);
2208  stpMaster.setPoolSizeInitFactor(m_poolSizeInitFactor);
2209  // XXX: should we set stpMaster.objInteger true/false according to weights automatically?
2210 
2211  // now solve LP
2212  stpMaster.optimize();
2213 
2214  // collect solution edges to build Steiner tree
2215  finalSteinerTree = new EdgeWeightedGraphCopy<T>();
2216  finalSteinerTree->createEmpty(G);
2217  T weight(0);
2218  for (edge e = G.firstEdge(); e; e = e->succ()) {
2219  if (stpMaster.isSolutionEdge(e)) {
2220  const node vO = e->source();
2221  node vC = finalSteinerTree->copy(vO);
2222  if (!vC) {
2223  vC = finalSteinerTree->newNode(vO);
2224  }
2225  const node wO = e->target();
2226  node wC = finalSteinerTree->copy(wO);
2227  if (!wC) {
2228  wC = finalSteinerTree->newNode(wO);
2229  }
2230  T edgeCost = G.weight(e);
2231  finalSteinerTree->newEdge(e, edgeCost);
2232  weight += edgeCost;
2233  }
2234  }
2235 
2236  return weight;
2237 }
2238 
2239 }
ogdf::ArrayBuffer
An array that keeps track of the number of inserted elements; also usable as an efficient stack.
Definition: Array.h:45
abacus::CSense::Greater
@ Greater
Definition: csense.h:51
ogdf::MinSteinerTreeDirectedCut::DegreeConstraint::m_coeffIn
double m_coeffIn
coefficient of ingoing edges
Definition: MinSteinerTreeDirectedCut.h:891
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
ogdf::MinSteinerTreeDirectedCut::Sub::m_computeBackCuts
bool m_computeBackCuts
Definition: MinSteinerTreeDirectedCut.h:750
ogdf::MinSteinerTreeDirectedCut::DirectedCutConstraint::equal
bool equal(const ConVar *cv) const override
tests if cuts are equal; required method for nonduplpool
Definition: MinSteinerTreeDirectedCut.h:2153
ogdf::MinSteinerTreeDirectedCut::DirectedCutConstraint::nMarkedNodes
int nMarkedNodes() const
the number of marked nodes
Definition: MinSteinerTreeDirectedCut.h:1006
ogdf::MinSteinerTreeDirectedCut::Master::m_poolSizeMax
int m_poolSizeMax
maximal size of the pool
Definition: MinSteinerTreeDirectedCut.h:622
ogdf::MinSteinerTreeDirectedCut::Master::m_addIndegreeEdgeConstraints
bool m_addIndegreeEdgeConstraints
add constraints concerning the indegree of a node w.r.t. one outgoing edge: indeg(v) >= outgoing edge...
Definition: MinSteinerTreeDirectedCut.h:633
ogdf::MinSteinerTreeDirectedCut::Master::incNrCutsTotal
void incNrCutsTotal(int val)
increases the number of separated directed cuts
Definition: MinSteinerTreeDirectedCut.h:490
ogdf::MinSteinerTreeModule::isSteinerTree
static bool isSteinerTree(const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, const EdgeWeightedGraphCopy< T > &steinerTree)
Checks in O(n) time if a given tree is acually a Steiner Tree.
Definition: MinSteinerTreeModule.h:427
ogdf::MinSTCutMaxFlow::setEpsilonTest
void setEpsilonTest(EpsilonTest *et)
Assigns a new epsilon test.
Definition: MinSTCutMaxFlow.h:110
ogdf::EdgeArray::init
void init()
Reinitializes the array. Associates the array with no graph.
Definition: EdgeArray.h:283
Graph.h
Includes declaration of graph class.
MinSteinerTreeTakahashi.h
Implementation of the 2(1-1/l)-approximation algorithm for the minimum Steiner tree problem by Matsuy...
ogdf::MinSteinerTreeDirectedCut::Master::m_separationTimer
StopwatchWallClock m_separationTimer
timer for separation
Definition: MinSteinerTreeDirectedCut.h:677
ogdf::EdgeWeightedGraph::newEdge
edge newEdge(node v, node w, T weight)
Definition: EdgeWeightedGraph.h:55
ogdf::MinSteinerTreeDirectedCut::Master::initializeParameters
virtual void initializeParameters() override
read/set parameters from file
Definition: MinSteinerTreeDirectedCut.h:1198
abacus::NonDuplPool< abacus::Constraint, abacus::Variable >
ogdf::MinSteinerTreeDirectedCut::m_addFlowBalanceConstraints
bool m_addFlowBalanceConstraints
Definition: MinSteinerTreeDirectedCut.h:83
ogdf::EpsilonTest
Definition: EpsilonTest.h:40
ogdf::MinSteinerTreeDirectedCut::Master::rootNode
node rootNode() const
the designated root node (special terminal)
Definition: MinSteinerTreeDirectedCut.h:396
ogdf::MinSteinerTreeDirectedCut::m_callPrimalHeuristic
int m_callPrimalHeuristic
Definition: MinSteinerTreeDirectedCut.h:91
ogdf::MinSTCutMaxFlow::isFrontCutEdge
bool isFrontCutEdge(const edge e) const
Returns whether this edge is leaving the front cut.
Definition: MinSTCutMaxFlow.h:130
ogdf::MinSteinerTreeDirectedCut::DegreeEdgeConstraint
Constraint for relating the indegree and one outgoing edge of a node.
Definition: MinSteinerTreeDirectedCut.h:899
ogdf::MinSteinerTreeDirectedCut::m_addGSEC2Constraints
bool m_addGSEC2Constraints
Definition: MinSteinerTreeDirectedCut.h:82
ogdf::MinSteinerTreeDirectedCut::Master::nEdgesU
int nEdgesU() const
returns number of undirected edges, i.e., nEdges()/2
Definition: MinSteinerTreeDirectedCut.h:394
abacus::BranchRule
Abstract base class for all branching rules.
Definition: branchrule.h:59
ogdf::MinSteinerTreeDirectedCut::Master::m_separationStrategy
int m_separationStrategy
parameter: separation strategy, only important if nested cuts are computed
Definition: MinSteinerTreeDirectedCut.h:653
ogdf::MinSteinerTreeDirectedCut::DegreeConstraint::DegreeConstraint
DegreeConstraint(abacus::Master *master, node n, double coeffIn, double coeffOut, abacus::CSense::SENSE sense, double rhs)
Definition: MinSteinerTreeDirectedCut.h:855
abacus.h
Includes Abacus.
ogdf::MinSteinerTreeDirectedCut::Master::getMaxFlowModule
MaxFlowModule< double > * getMaxFlowModule()
Get the maximum flow module used by separation algorithm.
Definition: MinSteinerTreeDirectedCut.h:284
ogdf::MinSteinerTreeDirectedCut::EdgeVariable::source
node source() const
source node
Definition: MinSteinerTreeDirectedCut.h:800
OGDF_ASSERT
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition: basic.h:41
ogdf::GraphCopy::original
const Graph & original() const
Returns a reference to the original graph.
Definition: GraphCopy.h:292
ogdf::MinSteinerTreeDirectedCut::Master::m_pCutPool
abacus::NonDuplPool< abacus::Constraint, abacus::Variable > * m_pCutPool
the non-duplicate cut pool for the directed Steiner cuts
Definition: MinSteinerTreeDirectedCut.h:616
ogdf::Graph::newEdge
edge newEdge(node v, node w)
Creates a new edge (v,w) and returns it.
ogdf::EdgeWeightedGraph::weight
T weight(const edge e) const
Definition: EdgeWeightedGraph.h:68
ogdf::Logger::Level::Minor
@ Minor
ogdf::StopwatchWallClock
Implements a stopwatch measuring wall-clock time.
Definition: Stopwatch.h:195
ogdf::MinSteinerTreeDirectedCut::Master::computeBackCuts
bool computeBackCuts() const
parameter: back cut computation
Definition: MinSteinerTreeDirectedCut.h:463
ogdf::MinSteinerTreeDirectedCut::Master::getNode
node getNode(int i) const
id -> node
Definition: MinSteinerTreeDirectedCut.h:424
abacus::Constraint::rhs
virtual double rhs() const
Returns the right hand side of the constraint.
Definition: constraint.h:130
ogdf::MinSteinerTreeDirectedCut::Master::solutionValue
double solutionValue() const
solution value after solving the problem, i.e., returns final primal bound
Definition: MinSteinerTreeDirectedCut.h:445
ogdf::MinSteinerTreeDirectedCut::Sub::Sub
Sub(abacus::Master *master)
Constructor for the root problem of the b&b tree.
Definition: MinSteinerTreeDirectedCut.h:1518
ogdf::MinSteinerTreeDirectedCut::Master::m_edgesWgToGPH
EdgeArray< edge > m_edgesWgToGPH
edge mapping m_pWeightedGraphPH -> m_pGraph
Definition: MinSteinerTreeDirectedCut.h:611
ogdf::MinSteinerTreeDirectedCut::Sub::m_alreadySeparated
int m_alreadySeparated
nr of already separated cuts, default is -1
Definition: MinSteinerTreeDirectedCut.h:739
ogdf::MinSteinerTreeDirectedCut::Master::edgeID
int edgeID(edge e) const
edge -> id of lp variable
Definition: MinSteinerTreeDirectedCut.h:410
ogdf::MinSteinerTreeDirectedCut::Master::m_relaxedSolValue
double m_relaxedSolValue
statistics: solution value of the relaxed master problem
Definition: MinSteinerTreeDirectedCut.h:547
ogdf::MinSteinerTreeDirectedCut::Master::terminalListPH
const List< node > & terminalListPH() const
list of terminals (in m_pWeightedGraphPH)
Definition: MinSteinerTreeDirectedCut.h:506
ogdf::MinSteinerTreeDirectedCut::Master::m_addDegreeConstraints
bool m_addDegreeConstraints
parameter: add constraints concerning the indegree of a node, like: indeg <= 1 for all vertices
Definition: MinSteinerTreeDirectedCut.h:631
ogdf::MinSteinerTreeDirectedCut::DegreeEdgeConstraint::DegreeEdgeConstraint
DegreeEdgeConstraint(abacus::Master *master, edge e, double coeffIn, double coeffEdge, abacus::CSense::SENSE sense, double rhs)
Definition: MinSteinerTreeDirectedCut.h:902
ogdf::MinSteinerTreeDirectedCut::Master::getPrimalHeuristic
std::unique_ptr< MinSteinerTreeModule< double > > & getPrimalHeuristic()
the primal heuristic module
Definition: MinSteinerTreeDirectedCut.h:368
ogdf::MinSteinerTreeDirectedCut::useGSEC2Constraints
void useGSEC2Constraints(bool b)
Switch usage of constraints x_uv + x_vu <= 1 on or off.
Definition: MinSteinerTreeDirectedCut.h:138
ogdf::MinSteinerTreeDirectedCut::useFlowBalanceConstraints
void useFlowBalanceConstraints(bool b)
Switch usage of flow balance constraints on or off.
Definition: MinSteinerTreeDirectedCut.h:143
ogdf::List::popFrontRet
E popFrontRet()
Removes the first element from the list and returns it.
Definition: List.h:1418
ogdf::MinSteinerTreeDirectedCut::Master::updateBestSolution
void updateBestSolution(double *values)
updates best found solution
Definition: MinSteinerTreeDirectedCut.h:1489
ogdf::MinSTCutMaxFlow::frontCutIsComplementOfBackCut
bool frontCutIsComplementOfBackCut() const
Returns whether the front cut is the complement of the backcut.
Definition: MinSTCutMaxFlow.h:121
ogdf::MinSteinerTreeDirectedCut::Master::m_callPrimalHeuristic
int m_callPrimalHeuristic
parameter: primal heuristic (PH) call strategy
Definition: MinSteinerTreeDirectedCut.h:674
ogdf::MinSteinerTreeDirectedCut::Master::Master
Master(const EdgeWeightedGraph< T > &wG, const List< node > &terminals, const NodeArray< bool > &isTerminal, double eps, bool relaxed=false)
Constructor of the master problem.
Definition: MinSteinerTreeDirectedCut.h:1038
ogdf::MinSTCutMaxFlow::isBackCutEdge
bool isBackCutEdge(const edge e) const
Returns whether this edge is entering the back cut.
Definition: MinSTCutMaxFlow.h:140
ogdf::MinSteinerTreeDirectedCut::DegreeEdgeConstraint::m_edge
edge m_edge
the associated edge
Definition: MinSteinerTreeDirectedCut.h:937
ogdf::MinSteinerTreeDirectedCut::Master::nrCutsTotal
int nrCutsTotal() const
total number of separated directed cuts
Definition: MinSteinerTreeDirectedCut.h:494
ogdf::MinSteinerTreeDirectedCut::DegreeEdgeConstraint::m_coeffEdge
double m_coeffEdge
coefficient of the edge
Definition: MinSteinerTreeDirectedCut.h:941
ogdf::EdgeElement::isParallelDirected
bool isParallelDirected(edge e) const
Returns true iff edge e is parallel to this (directed) edge (or if it is the same edge)
Definition: Graph_d.h:350
ogdf::MinSteinerTreeDirectedCut::DirectedCutConstraint::name
const char * name() const override
return the name of the cut; required method for nonduplpool
Definition: MinSteinerTreeDirectedCut.h:1014
ogdf::MinSteinerTreeDirectedCut::Sub::feasible
virtual bool feasible() override
checks if the current solution is feasible, i.e., calls mySeparate()
Definition: MinSteinerTreeDirectedCut.h:1601
ogdf::MinSteinerTreeDirectedCut::m_nestedCutComputation
bool m_nestedCutComputation
Definition: MinSteinerTreeDirectedCut.h:87
ogdf::MinSteinerTreeDirectedCut::EdgeVariable::theEdge
edge theEdge() const
the associated edge
Definition: MinSteinerTreeDirectedCut.h:794
abacus::Sub::master
Master * master()
Returns the master of the optimization.
Definition: sub.h:320
abacus
Definition: abacusroot.h:48
ogdf::MinSteinerTreeDirectedCut::EdgeConstraint::coeff
double coeff(const abacus::Variable *v) const override
coefficient of variable in constraint
Definition: MinSteinerTreeDirectedCut.h:831
ogdf::MinSteinerTreeDirectedCut::MinSteinerTreeDirectedCut
MinSteinerTreeDirectedCut()
Definition: MinSteinerTreeDirectedCut.h:199
ogdf::MinSteinerTreeDirectedCut::Master::m_maxFlowModule
MaxFlowModule< double > * m_maxFlowModule
Definition: MinSteinerTreeDirectedCut.h:535
ogdf::MinSteinerTreeDirectedCut::DirectedCutConstraint::m_marked
NodeArray< bool > m_marked
defines if a vertex is on the left side of the cut (false) or not
Definition: MinSteinerTreeDirectedCut.h:1025
ogdf::MinSteinerTreeDirectedCut::m_addDegreeConstraints
bool m_addDegreeConstraints
Definition: MinSteinerTreeDirectedCut.h:80
ogdf::MinSteinerTreeDirectedCut::Master::edgeGToWgPH
edge edgeGToWgPH(edge e) const
edge mapping m_pGraph -> m_pWeightedGraphPH
Definition: MinSteinerTreeDirectedCut.h:512
ogdf::Logger::Level
Level
supported log-levels from lowest to highest importance
Definition: Logger.h:103
ogdf::MinSteinerTreeDirectedCut::Master::m_terminals
node * m_terminals
terminal index -> terminal node
Definition: MinSteinerTreeDirectedCut.h:588
ogdf::MinSteinerTreeDirectedCut::Master::m_nEdgesU
int m_nEdgesU
number of undirected edges
Definition: MinSteinerTreeDirectedCut.h:559
ogdf::MinSteinerTreeDirectedCut::Master::m_edgeIDs
EdgeArray< int > m_edgeIDs
edge -> id
Definition: MinSteinerTreeDirectedCut.h:563
ogdf::MinSteinerTreeDirectedCut::m_separationStrategy
int m_separationStrategy
Definition: MinSteinerTreeDirectedCut.h:88
ogdf::EdgeWeightedGraphCopy::newEdge
edge newEdge(node u, node v, T weight)
Definition: EdgeWeightedGraphCopy.h:166
opensub.h
open subproblems.
ogdf::MinSteinerTreeDirectedCut::Master::useFlowBalanceConstraints
void useFlowBalanceConstraints(bool b)
Switch usage of flow balance constraints on or off.
Definition: MinSteinerTreeDirectedCut.h:305
ogdf::MinSteinerTreeDirectedCut::Master::relaxed
bool relaxed() const
solve relaxed LP or ILP
Definition: MinSteinerTreeDirectedCut.h:442
ogdf::MinSteinerTreeDirectedCut::setConfigFile
void setConfigFile(const char *configfile)
Set a configuration file to use. The contents of the configuration file can override all other used o...
Definition: MinSteinerTreeDirectedCut.h:112
ogdf::MinSteinerTreeDirectedCut::Sub::m_saturationStrategy
int m_saturationStrategy
Definition: MinSteinerTreeDirectedCut.h:748
ogdf::Logger::Level::Default
@ Default
ogdf::MinSteinerTreeDirectedCut::Master::terminals
const node * terminals() const
terminals in an array
Definition: MinSteinerTreeDirectedCut.h:401
ogdf::MinSteinerTreeDirectedCut::useBackCuts
void useBackCuts(bool b)
Switch computation of back-cuts on or off.
Definition: MinSteinerTreeDirectedCut.h:158
ogdf::MinSteinerTreeDirectedCut::Master::primalHeuristicTimer
StopwatchWallClock * primalHeuristicTimer()
timer for primal heuristics
Definition: MinSteinerTreeDirectedCut.h:524
ogdf::MaxFlowGoldbergTarjan
Computes a max flow via Preflow-Push (global relabeling and gap relabeling heuristic).
Definition: MaxFlowGoldbergTarjan.h:52
ogdf::MinSteinerTreeDirectedCut::Master::checkSetMaxPoolSize
void checkSetMaxPoolSize()
checks if current pool size is maximum and sets it if necessary
Definition: MinSteinerTreeDirectedCut.h:481
ogdf::MinSteinerTreeDirectedCut::Master::m_wG
const EdgeWeightedGraph< T > & m_wG
the original weighted graph
Definition: MinSteinerTreeDirectedCut.h:553
ogdf::MinSteinerTreeDirectedCut::Master::callPrimalHeuristicStrategy
int callPrimalHeuristicStrategy() const
strategy for calling primal heuristic (PH)
Definition: MinSteinerTreeDirectedCut.h:469
ogdf::MinSteinerTreeDirectedCut::DegreeEdgeConstraint::theEdge
edge theEdge() const
the associated edge
Definition: MinSteinerTreeDirectedCut.h:934
abacus::Sub::nIter_
int nIter_
The number of iterations in the cutting plane phase.
Definition: sub.h:1479
ogdf::MinSteinerTreeDirectedCut::Master::m_backCutComputation
bool m_backCutComputation
parameter: compute back cuts yes/no i.e., outgoing edges of the root-set
Definition: MinSteinerTreeDirectedCut.h:642
ogdf::MinSteinerTreeDirectedCut::Master::twin
edge twin(edge e) const
the twin edge, i.e. twin[(u,v)] = (v,u)
Definition: MinSteinerTreeDirectedCut.h:432
ogdf::MinSteinerTreeDirectedCut::Master::getVar
EdgeVariable * getVar(edge e) const
returns the variable assigned to edge e
Definition: MinSteinerTreeDirectedCut.h:437
ogdf::NodeArray< bool >
ogdf::MinSteinerTreeDirectedCut::DegreeConstraint::m_coeffOut
double m_coeffOut
coefficient of outgoing edges
Definition: MinSteinerTreeDirectedCut.h:893
ogdf::MinSteinerTreeDirectedCut::Sub::m_shuffleTerminals
bool m_shuffleTerminals
Definition: MinSteinerTreeDirectedCut.h:752
ogdf::MinSteinerTreeDirectedCut::m_maxFlowModuleOption
std::unique_ptr< MaxFlowModule< double > > m_maxFlowModuleOption
Definition: MinSteinerTreeDirectedCut.h:79
ogdf::MinSteinerTreeDirectedCut::setPrimalHeuristicCallStrategy
void setPrimalHeuristicCallStrategy(int b)
Set primal heuristic call strategy.
Definition: MinSteinerTreeDirectedCut.h:187
ogdf::MinSteinerTreeDirectedCut::DirectedCutConstraint::m_nMarkedNodes
int m_nMarkedNodes
number of marked nodes
Definition: MinSteinerTreeDirectedCut.h:1028
ogdf::EdgeArray< int >
ogdf::MinSteinerTreeDirectedCut::m_shuffleTerminals
bool m_shuffleTerminals
Definition: MinSteinerTreeDirectedCut.h:85
ogdf::MinSteinerTreeDirectedCut::Master::m_minCardinalityCuts
bool m_minCardinalityCuts
parameter: compute minimum cardinality cuts
Definition: MinSteinerTreeDirectedCut.h:666
ogdf::MinSteinerTreeDirectedCut::Master::m_mapToOrigGraph
EdgeArray< edge > m_mapToOrigGraph
the undirected edge in the original graph for each arc in m_pGraph
Definition: MinSteinerTreeDirectedCut.h:573
ogdf::MinSteinerTreeDirectedCut::Master::m_edgesGToWgPH
EdgeArray< edge > m_edgesGToWgPH
edge mapping m_pGraph -> m_pWeightedGraphPH
Definition: MinSteinerTreeDirectedCut.h:609
ogdf::MinSteinerTreeDirectedCut::DirectedCutConstraint::active
bool active(node n) const
returns true iff the node n is separated by this cut
Definition: MinSteinerTreeDirectedCut.h:998
ogdf::GraphCopy::copy
node copy(node v) const
Returns the node in the graph copy corresponding to v.
Definition: GraphCopy.h:341
ogdf::MinSteinerTreeDirectedCut::Master::nodeIDs
const NodeArray< int > & nodeIDs() const
lp variable ids of nodes
Definition: MinSteinerTreeDirectedCut.h:417
ogdf::MinSteinerTreeDirectedCut::Master::m_nIterRoot
int m_nIterRoot
statistics: nr of iterations in the root node of the b&b tree
Definition: MinSteinerTreeDirectedCut.h:550
ogdf::MinSteinerTreeDirectedCut::Master::m_mapToBidirectedGraph2
EdgeArray< edge > m_mapToBidirectedGraph2
the second directed arc in m_pGraph for an original edge
Definition: MinSteinerTreeDirectedCut.h:577
ogdf::Logger::Level::Medium
@ Medium
ogdf::MinSteinerTreeDirectedCut::Master::edgeWgToGPH
edge edgeWgToGPH(edge e) const
edge mapping m_pWeightedGraphPH -> m_pGraph
Definition: MinSteinerTreeDirectedCut.h:514
ogdf::MinSteinerTreeDirectedCut::Master::m_primalHeuristicTimer
StopwatchWallClock m_primalHeuristicTimer
timer for primal heuristics
Definition: MinSteinerTreeDirectedCut.h:681
ogdf::MinSteinerTreeDirectedCut::Master::maxNrAddedCuttingPlanes
int maxNrAddedCuttingPlanes() const
maximum nr of cutting planes
Definition: MinSteinerTreeDirectedCut.h:459
Logger.h
Contains logging functionality.
EdgeWeightedGraphCopy.h
Extends the GraphCopy concept to weighted graphs.
ogdf::MinSteinerTreeDirectedCut::Master::setPrimalHeuristicCallStrategy
void setPrimalHeuristicCallStrategy(int b)
Set primal heuristic call strategy.
Definition: MinSteinerTreeDirectedCut.h:351
ogdf::MinSteinerTreeDirectedCut::Master::m_maxNrAddedCuttingPlanes
int m_maxNrAddedCuttingPlanes
parameter: maximum nr of cutting planes per iteration
Definition: MinSteinerTreeDirectedCut.h:638
abacus::CSense::Equal
@ Equal
Definition: csense.h:51
abacus::Master::defaultLpSolver
OSISOLVER defaultLpSolver() const
returns the Lp Solver.
Definition: master.h:533
ogdf::AlgorithmFailureException
Exception thrown when an algorithm realizes an internal bug that prevents it from continuing.
Definition: exceptions.h:253
ogdf::MinSteinerTreeModule
Serves as an interface for various methods to compute or approximate minimum Steiner trees on undirec...
Definition: MinSteinerTreeModule.h:58
ogdf::MinSteinerTreeDirectedCut::setPrimalHeuristic
void setPrimalHeuristic(MinSteinerTreeModule< double > *b)
Set the module option for the primal heuristic (use MinSteinerTreeModule<double> types)....
Definition: MinSteinerTreeDirectedCut.h:183
ogdf::MinSteinerTreeDirectedCut::Master::incNrCutsTotal
void incNrCutsTotal()
increases the number of separated directed cuts by 1
Definition: MinSteinerTreeDirectedCut.h:492
ogdf::MinSteinerTreeDirectedCut::Master::edgeIDs
const EdgeArray< int > & edgeIDs() const
lp variable ids of edges
Definition: MinSteinerTreeDirectedCut.h:419
ogdf::MinSteinerTreeDirectedCut::Master::m_isTerminal
NodeArray< bool > m_isTerminal
node is terminal yes/no
Definition: MinSteinerTreeDirectedCut.h:584
ogdf::MinSteinerTreeDirectedCut::DirectedCutConstraint::coeff
double coeff(const abacus::Variable *v) const override
Returns the coefficient of the variable v in the constraint.
Definition: MinSteinerTreeDirectedCut.h:2172
ogdf::MinSteinerTreeDirectedCut::Master::m_mapToBidirectedGraph1
EdgeArray< edge > m_mapToBidirectedGraph1
the first directed arc in m_pGraph for an original edge
Definition: MinSteinerTreeDirectedCut.h:575
ogdf::MinSteinerTreeDirectedCut::EdgeVariable::m_id
int m_id
id of the edge
Definition: MinSteinerTreeDirectedCut.h:808
ogdf::MinSteinerTreeDirectedCut::Master::useDegreeConstraints
void useDegreeConstraints(bool b)
Switch usage of degree constraints (like indeg <= 1) on or off.
Definition: MinSteinerTreeDirectedCut.h:290
ogdf::MinSteinerTreeDirectedCut::Master::graph
const Graph & graph() const
the directed graph, i.e., the bidirection of the input graph
Definition: MinSteinerTreeDirectedCut.h:387
ogdf::MinSTCutMaxFlow::call
virtual bool call(const Graph &graph, const EdgeArray< TCost > &weight, node s, node t, List< edge > &edgeList, edge e_st=nullptr) override
The actual algorithm call.
Definition: MinSTCutMaxFlow.h:316
ogdf::MinSteinerTreeDirectedCut::DegreeConstraint
Constraint for nodes, e.g., in/outdegree stuff.
Definition: MinSteinerTreeDirectedCut.h:852
ogdf::MaxFlowModule::computeFlow
T computeFlow(EdgeArray< T > &cap, node &s, node &t, EdgeArray< T > &flow)
Only a shortcut for computeValue and computeFlowAfterValue.
Definition: MaxFlowModule.h:174
ogdf::MinSteinerTreeDirectedCut::Master::computeNestedCuts
bool computeNestedCuts() const
parameter: nested cut computation
Definition: MinSteinerTreeDirectedCut.h:461
ogdf::MinSteinerTreeDirectedCut::Sub::m_computeNestedCuts
bool m_computeNestedCuts
Definition: MinSteinerTreeDirectedCut.h:744
ogdf::AlgorithmFailureCode::Constraint
@ Constraint
r
int r[]
Definition: hierarchical-ranking.cpp:8
ogdf::Graph::nodes
internal::GraphObjectContainer< NodeElement > nodes
The container containing all node objects.
Definition: Graph_d.h:568
ogdf::MinSteinerTreeDirectedCut::DirectedCutConstraint::cutedge
bool cutedge(edge e) const
returns true iff the edge is contained in the cut
Definition: MinSteinerTreeDirectedCut.h:1002
ogdf::EdgeElement::isSelfLoop
bool isSelfLoop() const
Returns true iff the edge is a self-loop (source node = target node).
Definition: Graph_d.h:344
ogdf::MinSteinerTreeDirectedCut::Master::nTerminals
int nTerminals() const
number of terminals
Definition: MinSteinerTreeDirectedCut.h:399
ogdf::MinSteinerTreeDirectedCut::Master::shuffleTerminals
bool shuffleTerminals() const
shuffle ordering of terminals before each separation routine
Definition: MinSteinerTreeDirectedCut.h:476
ogdf::Graph::numberOfEdges
int numberOfEdges() const
Returns the number of edges in the graph.
Definition: Graph_d.h:604
ogdf::MinSteinerTreeDirectedCut::useTerminalShuffle
void useTerminalShuffle(bool b)
Switch terminal shuffling before separation on or off.
Definition: MinSteinerTreeDirectedCut.h:153
ogdf::MinSteinerTreeDirectedCut::Master::maxPoolSize
int maxPoolSize() const
the maximum pool size during the algorithm
Definition: MinSteinerTreeDirectedCut.h:479
ogdf::MinSteinerTreeDirectedCut::EdgeConstraint::m_e2
edge m_e2
twin of m_e1, i.e., if m_e1 = (u,v) it holds m_e2 = (v,u)
Definition: MinSteinerTreeDirectedCut.h:844
ogdf::MinSteinerTreeDirectedCut::Master::m_configfile
const char * m_configfile
problem dependent config file
Definition: MinSteinerTreeDirectedCut.h:538
ogdf::NodeElement::degree
int degree() const
Returns the degree of the node (indegree + outdegree).
Definition: Graph_d.h:210
ogdf::MinSteinerTreeDirectedCut::Master::poolSizeInit
int poolSizeInit() const
initial pool size
Definition: MinSteinerTreeDirectedCut.h:487
ogdf::MinSteinerTreeDirectedCut::Master::minCardinalityCuts
bool minCardinalityCuts() const
parameter: compute minimum cardinality cuts
Definition: MinSteinerTreeDirectedCut.h:465
ogdf::Graph::numberOfNodes
int numberOfNodes() const
Returns the number of nodes in the graph.
Definition: Graph_d.h:601
abacus::Master::OSISOLVER_
static const char * OSISOLVER_[]
Array for the literal values for possible Osi solvers.
Definition: master.h:212
ogdf::MinSteinerTreeDirectedCut::computeSteinerTree
virtual T computeSteinerTree(const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, EdgeWeightedGraphCopy< T > *&finalSteinerTree) override
Computes the actual Steiner tree.
Definition: MinSteinerTreeDirectedCut.h:2183
ogdf::MinSteinerTreeDirectedCut::EdgeConstraint
Constraint for edges, e.g., subtour elimination constraints of size 2 ((G)SEC2)
Definition: MinSteinerTreeDirectedCut.h:814
ogdf::EdgeWeightedGraph
Definition: EdgeWeightedGraph.h:39
ogdf::MinSteinerTreeDirectedCut::Master::m_isTerminalPH
NodeArray< bool > m_isTerminalPH
is terminal yes/no (in m_pWeightedGraphPH)
Definition: MinSteinerTreeDirectedCut.h:605
ogdf::MinSteinerTreeDirectedCut::Master::m_saturationStrategy
int m_saturationStrategy
parameter: saturation strategy, only important if nested cuts are computed
Definition: MinSteinerTreeDirectedCut.h:660
ogdf::MinSteinerTreeDirectedCut::Master::nNodes
int nNodes() const
number of nodes of the graph
Definition: MinSteinerTreeDirectedCut.h:390
ogdf::Array< node >
ogdf::MinSteinerTreeDirectedCut::Master::m_shuffleTerminals
bool m_shuffleTerminals
parameter: shuffle the list of terminals right before separation
Definition: MinSteinerTreeDirectedCut.h:640
ogdf::MinSteinerTreeDirectedCut::Master
Master problem of Steiner tree branch&cut algorithm
Definition: MinSteinerTreeDirectedCut.h:230
ogdf::MinSteinerTreeDirectedCut::Master::isTerminal
bool isTerminal(node n) const
true if n is a terminal
Definition: MinSteinerTreeDirectedCut.h:405
ogdf::MinSteinerTreeDirectedCut::Master::getVarTwin
EdgeVariable * getVarTwin(edge e) const
returns the variable assigned to the twin of edge e
Definition: MinSteinerTreeDirectedCut.h:439
ogdf::MinSteinerTreeDirectedCut::Master::useTerminalShuffle
void useTerminalShuffle(bool b)
Switch terminal shuffling before separation on or off.
Definition: MinSteinerTreeDirectedCut.h:317
ogdf::MaxFlowModule::useEpsilonTest
void useEpsilonTest(const double &eps)
Change the used EpsilonTest from StandardEpsilonTest to a user given EpsilonTest.
Definition: MaxFlowModule.h:117
ogdf::MinSteinerTreeDirectedCut::Master::m_nrCutsTotal
int m_nrCutsTotal
total number of separated directed cuts
Definition: MinSteinerTreeDirectedCut.h:626
ogdf::MinSteinerTreeDirectedCut::Sub::m_callPrimalHeuristic
int m_callPrimalHeuristic
Strategy for primal heuristic (PH) calls.
Definition: MinSteinerTreeDirectedCut.h:762
ogdf::MinSteinerTreeDirectedCut::Master::m_pWeightedGraphPH
EdgeWeightedGraph< double > * m_pWeightedGraphPH
edge weighted bidirected graph; used and modified for primal heuristics
Definition: MinSteinerTreeDirectedCut.h:601
ogdf::MinSteinerTreeDirectedCut::Master::saturationStrategy
int saturationStrategy() const
strategy for saturating edges during separation; Only relevant for nested cuts
Definition: MinSteinerTreeDirectedCut.h:473
ogdf::MinSteinerTreeDirectedCut::Master::capacities
double capacities(edge e) const
costs for edge e
Definition: MinSteinerTreeDirectedCut.h:429
ogdf::MinSteinerTreeDirectedCut::Master::m_pGraph
Graph * m_pGraph
the bidirected graph
Definition: MinSteinerTreeDirectedCut.h:556
ogdf::ArrayBuffer::push
void push(E e)
Puts a new element in the buffer.
Definition: ArrayBuffer.h:102
ogdf::MinSteinerTreeDirectedCut::Master::isTerminal
const NodeArray< bool > isTerminal() const
boolean array of terminal status
Definition: MinSteinerTreeDirectedCut.h:407
ogdf::MinSteinerTreeDirectedCut::m_backCutComputation
bool m_backCutComputation
Definition: MinSteinerTreeDirectedCut.h:86
ogdf::MinSteinerTreeDirectedCut::Sub::m_pMaster
Master * m_pMaster
the master problem of the b&c algorithm
Definition: MinSteinerTreeDirectedCut.h:736
ogdf::MinSteinerTreeDirectedCut::DegreeConstraint::coeff
virtual double coeff(const abacus::Variable *v) const override
coefficient of variable in constraint
Definition: MinSteinerTreeDirectedCut.h:869
ogdf::MinSteinerTreeDirectedCut::useMinCardinalityCuts
void useMinCardinalityCuts(bool b)
Switch usage of the cardinality heuristic (minimum-cardinality cuts) on or off.
Definition: MinSteinerTreeDirectedCut.h:178
ogdf::MinSteinerTreeDirectedCut::Master::m_nodeIDs
NodeArray< int > m_nodeIDs
node -> id
Definition: MinSteinerTreeDirectedCut.h:582
ogdf::MinSteinerTreeDirectedCut::Master::nEdges
int nEdges() const
returns the number of edges
Definition: MinSteinerTreeDirectedCut.h:392
abacus::Variable
Forms the virtual base class for all possible variables given in pool format.
Definition: variable.h:59
ogdf::EdgeElement::source
node source() const
Returns the source node of the edge.
Definition: Graph_d.h:326
ogdf::List
Doubly linked lists (maintaining the length of the list).
Definition: List.h:40
ogdf::MinSteinerTreeDirectedCut::Master::m_poolSizeInitFactor
int m_poolSizeInitFactor
parameter: factor for the initial size of the cutting pool
Definition: MinSteinerTreeDirectedCut.h:618
ogdf::Graph
Data type for general directed graphs (adjacency list representation).
Definition: Graph_d.h:495
abacus::VarType::Binary
@ Binary
A variable having value 0 or 1.
Definition: vartype.h:50
ogdf::MinSteinerTreeDirectedCut::Master::setMaxFlowModule
void setMaxFlowModule(MaxFlowModule< double > *module)
Set the maximum flow module to be used for separation.
Definition: MinSteinerTreeDirectedCut.h:279
ogdf::MinSteinerTreeDirectedCut::DirectedCutConstraint::m_hashKey
unsigned int m_hashKey
hashkey of the cut; required method for nonduplpool
Definition: MinSteinerTreeDirectedCut.h:1031
abacus::Constraint::sense
CSense * sense()
Returns a pointer to the sense of the constraint.
Definition: constraint.h:115
ogdf::Logger::Level::High
@ High
ogdf::MinSteinerTreeDirectedCut::DirectedCutConstraint::marked
bool marked(node n) const
returns status of node n
Definition: MinSteinerTreeDirectedCut.h:1008
abacus::Sub::id
int id() const
Returns the identity number of the subproblem.
Definition: sub.h:153
ogdf::MinSteinerTreeDirectedCut::EdgeConstraint::m_factor
int m_factor
factor for edge coefficients in the constraint
Definition: MinSteinerTreeDirectedCut.h:846
ogdf::MinSteinerTreeDirectedCut::DegreeEdgeConstraint::m_coeffIn
double m_coeffIn
coefficient of ingoing edges
Definition: MinSteinerTreeDirectedCut.h:939
ogdf::MinSteinerTreeDirectedCut::Master::rootNodePH
node rootNodePH() const
root node (in m_pWeightedGraphPH)
Definition: MinSteinerTreeDirectedCut.h:510
ogdf::MinSteinerTreeDirectedCut::Master::m_nodes
node * m_nodes
id -> node
Definition: MinSteinerTreeDirectedCut.h:580
ogdf::MinSteinerTreeDirectedCut::m_maxNrAddedCuttingPlanes
int m_maxNrAddedCuttingPlanes
Definition: MinSteinerTreeDirectedCut.h:84
ogdf::MinSteinerTreeDirectedCut::Master::useMinCardinalityCuts
void useMinCardinalityCuts(bool b)
Switch usage of the cardinality heuristic (minimum-cardinality cuts) on or off.
Definition: MinSteinerTreeDirectedCut.h:346
ogdf::MinSteinerTreeDirectedCut::Master::getEdge
edge getEdge(int i) const
id -> edge
Definition: MinSteinerTreeDirectedCut.h:422
ogdf::MinSteinerTreeDirectedCut::useIndegreeEdgeConstraints
void useIndegreeEdgeConstraints(bool b)
Switch usage of indegree edge constraints (indeg(v) >= outgoing edge(v,x) for all x) on or off.
Definition: MinSteinerTreeDirectedCut.h:133
ogdf::MinSteinerTreeDirectedCut::Sub::myImprove
void myImprove()
primal heuristic procedure
Definition: MinSteinerTreeDirectedCut.h:1979
ogdf::MinSteinerTreeDirectedCut::Master::m_root
node m_root
the virtual root of our graph. This node is a terminal.
Definition: MinSteinerTreeDirectedCut.h:591
ogdf::MinSteinerTreeDirectedCut::Master::m_timerMinSTCut
StopwatchWallClock m_timerMinSTCut
timer for minimum st-cut computations. Measures updates + algorithm
Definition: MinSteinerTreeDirectedCut.h:679
ogdf::MinSteinerTreeDirectedCut::EdgeVariable::m_edge
edge m_edge
the edge
Definition: MinSteinerTreeDirectedCut.h:806
ogdf::MinSteinerTreeDirectedCut::Master::m_bestSolution
double * m_bestSolution
best found solution
Definition: MinSteinerTreeDirectedCut.h:594
ogdf::MinSteinerTreeDirectedCut::setMaxFlowModule
void setMaxFlowModule(MaxFlowModule< double > *module)
Set the maximum flow module to be used for separation.
Definition: MinSteinerTreeDirectedCut.h:123
abacus::Master::optimize
STATUS optimize()
Performs the optimization by branch-and-bound.
ogdf::MinSteinerTreeDirectedCut::Master::callPrimalHeuristic
bool callPrimalHeuristic() const
parameter: call primal heuristic yes/no
Definition: MinSteinerTreeDirectedCut.h:467
ogdf::MinSteinerTreeDirectedCut::Master::m_rootPH
node m_rootPH
root node in m_pWeightedGraphPH
Definition: MinSteinerTreeDirectedCut.h:613
ogdf::MinSteinerTreeDirectedCut::m_saturationStrategy
int m_saturationStrategy
Definition: MinSteinerTreeDirectedCut.h:89
ogdf::MinSteinerTreeDirectedCut::Master::cutPool
abacus::NonDuplPool< abacus::Constraint, abacus::Variable > * cutPool()
the non-duplicate cutpool for the separated Steiner cuts
Definition: MinSteinerTreeDirectedCut.h:371
ogdf::MinSteinerTreeDirectedCut::m_poolSizeInitFactor
int m_poolSizeInitFactor
Definition: MinSteinerTreeDirectedCut.h:93
ogdf::MinSteinerTreeDirectedCut::Master::m_poolSizeInit
int m_poolSizeInit
size of initial pool
Definition: MinSteinerTreeDirectedCut.h:620
ogdf::MinSteinerTreeDirectedCut::m_addIndegreeEdgeConstraints
bool m_addIndegreeEdgeConstraints
Definition: MinSteinerTreeDirectedCut.h:81
ogdf::MaxFlowModule::init
virtual void init(const Graph &graph, EdgeArray< T > *flow=nullptr)
Initialize the problem with a graph and optional flow array. If no flow array is given,...
Definition: MaxFlowModule.h:93
ogdf::MinSteinerTreeDirectedCut::Sub::separate
virtual int separate() override
calls mySeparate() if mySeparate wasn't called in another procedure
Definition: MinSteinerTreeDirectedCut.h:711
ogdf::MinSteinerTreeDirectedCut::Sub
Subproblem of Steiner tree algorithm.
Definition: MinSteinerTreeDirectedCut.h:689
ogdf::MinSteinerTreeDirectedCut::Master::weightedGraphPH
EdgeWeightedGraph< double > & weightedGraphPH()
Definition: MinSteinerTreeDirectedCut.h:504
abacus::Constraint::coeff
virtual double coeff(const Variable *v) const =0
Returns the coefficient of the variable v in the constraint.
ogdf::MinSteinerTreeDirectedCut::Master::setMaxNumberAddedCuttingPlanes
void setMaxNumberAddedCuttingPlanes(int b)
Set maximum number of added cutting planes per iteration.
Definition: MinSteinerTreeDirectedCut.h:310
ogdf::MinSteinerTreeDirectedCut
This class implements the Directed Cut Integer Linear Program for the Steiner tree problem.
Definition: MinSteinerTreeDirectedCut.h:71
ogdf::MinSteinerTreeDirectedCut::Master::m_addFlowBalanceConstraints
bool m_addFlowBalanceConstraints
parameter: add flow balance constraints for Steiner nodes n: outdeg(n) >= indeg(n)
Definition: MinSteinerTreeDirectedCut.h:635
ogdf::MinSteinerTreeDirectedCut::Master::setSeparationStrategy
void setSeparationStrategy(int b)
Set separation strategy for nested cuts.
Definition: MinSteinerTreeDirectedCut.h:332
ogdf::Graph::edges
internal::GraphObjectContainer< EdgeElement > edges
The container containing all edge objects.
Definition: Graph_d.h:571
ogdf::MinSteinerTreeDirectedCut::Master::separationTimer
StopwatchWallClock * separationTimer()
timer for separation
Definition: MinSteinerTreeDirectedCut.h:520
ogdf::MinSteinerTreeDirectedCut::EdgeVariable::coefficient
double coefficient() const
objective function coefficient
Definition: MinSteinerTreeDirectedCut.h:798
ogdf::MinSteinerTreeDirectedCut::DirectedCutConstraint::hashKey
unsigned hashKey() const override
retuns an hashkey for the cut; required method for nonduplpool
Definition: MinSteinerTreeDirectedCut.h:1010
ogdf::MinSteinerTreeDirectedCut::setEpsilon
void setEpsilon(double eps)
Set the epsilon for the LP.
Definition: MinSteinerTreeDirectedCut.h:108
ogdf::Graph::newNode
node newNode()
Creates a new node and returns it.
ogdf::MinSteinerTreeDirectedCut::Master::useBackCuts
void useBackCuts(bool b)
Switch computation of back-cuts on or off.
Definition: MinSteinerTreeDirectedCut.h:322
ogdf::MinSteinerTreeTakahashi
This class implements the minimum Steiner tree 2-approximation algorithm by Takahashi and Matsuyama w...
Definition: MinSteinerTreeTakahashi.h:57
ogdf::AlgorithmFailureCode::Variable
@ Variable
ogdf::MinSTCutMaxFlow::cutType
cutType
The three types of cuts.
Definition: MinSTCutMaxFlow.h:101
ogdf::MinSteinerTreeDirectedCut::Master::firstSub
virtual abacus::Sub * firstSub() override
generates the first subproblem
Definition: MinSteinerTreeDirectedCut.h:374
ogdf::MinSteinerTreeDirectedCut::Master::m_nodesGToWgPH
NodeArray< node > m_nodesGToWgPH
node mapping m_pGraph -> m_pWeightedGraphPH
Definition: MinSteinerTreeDirectedCut.h:607
EdgeWeightedGraph.h
Declaration of class EdgeWeightedGraph.
ogdf::MinSteinerTreeDirectedCut::Master::terminal
node terminal(int i) const
get terminal with index i
Definition: MinSteinerTreeDirectedCut.h:403
ogdf::MinSteinerTreeDirectedCut::Master::useIndegreeEdgeConstraints
void useIndegreeEdgeConstraints(bool b)
Switch usage of indegree edge constraints (indeg(v) >= outgoing edge(v,x) for all x) on or off.
Definition: MinSteinerTreeDirectedCut.h:295
ogdf::MinSteinerTreeDirectedCut::DegreeConstraint::theNode
node theNode() const
the associated node
Definition: MinSteinerTreeDirectedCut.h:885
ogdf::MinSteinerTreeDirectedCut::Master::m_capacities
EdgeArray< double > m_capacities
edge costs
Definition: MinSteinerTreeDirectedCut.h:568
ogdf::MinSteinerTreeDirectedCut::Master::setNIterRoot
void setNIterRoot(int val)
nr of iterations in the root node
Definition: MinSteinerTreeDirectedCut.h:456
ogdf::MinSteinerTreeDirectedCut::m_eps
double m_eps
Definition: MinSteinerTreeDirectedCut.h:75
ogdf::MinSteinerTreeDirectedCut::Master::m_edgeToVar
EdgeArray< EdgeVariable * > m_edgeToVar
edge -> lp variable
Definition: MinSteinerTreeDirectedCut.h:570
ogdf::MinSteinerTreeDirectedCut::DirectedCutConstraint::DirectedCutConstraint
DirectedCutConstraint(abacus::Master *master, const Graph &g, const MinSTCutMaxFlow< double > *minSTCut, MinSTCutMaxFlow< double >::cutType _cutType)
Definition: MinSteinerTreeDirectedCut.h:950
abacus::Sub
The subproblem.
Definition: sub.h:68
abacus::Constraint
Forms the virtual base class for all possible constraints given in pool format.
Definition: constraint.h:56
ogdf::MinSteinerTreeDirectedCut::Master::initializeOptimization
virtual void initializeOptimization() override
insert variables and base constraints
Definition: MinSteinerTreeDirectedCut.h:1266
ogdf::Logger::lout
std::ostream & lout(Level level=Level::Default) const
stream for logging-output (local)
Definition: Logger.h:147
ogdf::MinSteinerTreeDirectedCut::EdgeConstraint::m_e1
edge m_e1
base edge and twin of m_e2, i.e., if m_e1 = (u,v) it holds m_e2 = (v,u)
Definition: MinSteinerTreeDirectedCut.h:842
ogdf::MaxFlowModule< double >
ogdf::MinSteinerTreeDirectedCut::Master::m_relaxed
bool m_relaxed
parameter: indicates whether we solve the relaxed problem (LP) or the ILP
Definition: MinSteinerTreeDirectedCut.h:544
ogdf::MinSteinerTreeDirectedCut::Master::m_maxPoolSize
int m_maxPoolSize
statistic number of cuts in pool
Definition: MinSteinerTreeDirectedCut.h:624
ogdf::EdgeWeightedGraphCopy
Definition: EdgeWeightedGraphCopy.h:40
ogdf::MinSteinerTreeDirectedCut::Master::setRelaxedSolValue
void setRelaxedSolValue(double val)
solution value of the root
Definition: MinSteinerTreeDirectedCut.h:454
ogdf::EdgeWeightedGraphCopy::createEmpty
void createEmpty(const Graph &wG)
Definition: EdgeWeightedGraphCopy.h:159
MinSTCutMaxFlow.h
Declaration of min-st-cut algorithms parameterized by max-flow alorithm.
ogdf::MinSteinerTreeDirectedCut::Master::setPrimalHeuristic
void setPrimalHeuristic(MinSteinerTreeModule< double > *pMinSteinerTreeModule)
Set the module option for the primal heuristic.
Definition: MinSteinerTreeDirectedCut.h:364
ogdf::MinSteinerTreeDirectedCut::Master::setPoolSizeInitFactor
void setPoolSizeInitFactor(int b)
Set factor for the initial size of the cutting pool.
Definition: MinSteinerTreeDirectedCut.h:358
ogdf::MinSteinerTreeDirectedCut::Master::nodeID
int nodeID(node n) const
npde -> id of lp variable
Definition: MinSteinerTreeDirectedCut.h:412
ogdf::EdgeElement
Class for the representation of edges.
Definition: Graph_d.h:292
ogdf::MinSteinerTreeDirectedCut::Master::isTerminalPH
const NodeArray< bool > & isTerminalPH() const
terminal yes/no (in m_pWeightedGraphPH)
Definition: MinSteinerTreeDirectedCut.h:508
ogdf::MinSteinerTreeDirectedCut::useDegreeConstraints
void useDegreeConstraints(bool b)
Switch usage of degree constraints (like indeg <= 1) on or off.
Definition: MinSteinerTreeDirectedCut.h:128
ogdf::MinSteinerTreeDirectedCut::Sub::generateSon
virtual Sub * generateSon(abacus::BranchRule *rule) override
generates a b&b node
Definition: MinSteinerTreeDirectedCut.h:765
Minisat::Internal::var
int var(Lit p)
Definition: SolverTypes.h:61
ogdf::EdgeWeightedGraph::newNode
node newNode()
Definition: EdgeWeightedGraph.h:62
ogdf::MinSteinerTreeDirectedCut::Master::m_nestedCutComputation
bool m_nestedCutComputation
parameter: compute nested cuts yes/no i.e., saturate all cut edges and recompute the mincut
Definition: MinSteinerTreeDirectedCut.h:644
ogdf::NodeArray::init
void init()
Reinitializes the array. Associates the array with no graph.
Definition: NodeArray.h:255
ogdf::MinSteinerTreeDirectedCut::Master::~Master
virtual ~Master()
destructor
Definition: MinSteinerTreeDirectedCut.h:249
ogdf::MinSteinerTreeDirectedCut::Master::separationStrategy
int separationStrategy() const
strategy for separating directed Steiner cuts; Only relevant for nested cuts
Definition: MinSteinerTreeDirectedCut.h:471
ogdf::MinSteinerTreeDirectedCut::Master::updateBestSolutionByEdges
void updateBestSolutionByEdges(const List< edge > &sol)
updates best found solution by list of edges
Definition: MinSteinerTreeDirectedCut.h:1506
ogdf::MinSteinerTreeDirectedCut::setSeparationStrategy
void setSeparationStrategy(int b)
Set separation strategy for nested cuts.
Definition: MinSteinerTreeDirectedCut.h:168
ogdf::MinSteinerTreeDirectedCut::EdgeVariable::EdgeVariable
EdgeVariable(abacus::Master *master, int id, edge e, double coeff, double lb=0.0, double ub=1.0, abacus::VarType::TYPE vartype=abacus::VarType::Binary)
Definition: MinSteinerTreeDirectedCut.h:776
ogdf::MinSteinerTreeDirectedCut::m_primalHeuristic
MinSteinerTreeModule< double > * m_primalHeuristic
Definition: MinSteinerTreeDirectedCut.h:92
abacus::VarType::TYPE
TYPE
The enumeration with the different variable types.
Definition: vartype.h:47
ogdf::MinSteinerTreeDirectedCut::Master::m_edges
edge * m_edges
id -> edge
Definition: MinSteinerTreeDirectedCut.h:561
ogdf::MinSteinerTreeDirectedCut::m_configFile
const char * m_configFile
Definition: MinSteinerTreeDirectedCut.h:74
ogdf::MinSteinerTreeDirectedCut::Master::timerMinSTCut
StopwatchWallClock * timerMinSTCut()
timer for minimum st-cut computations. Measures updates + algorithm
Definition: MinSteinerTreeDirectedCut.h:522
abacus::CSense::Less
@ Less
Definition: csense.h:51
ogdf::MinSteinerTreeDirectedCut::m_minCardinalityCuts
bool m_minCardinalityCuts
Definition: MinSteinerTreeDirectedCut.h:90
ogdf::MinSteinerTreeDirectedCut::DegreeEdgeConstraint::coeff
double coeff(const abacus::Variable *v) const override
coefficient of variable in constraint
Definition: MinSteinerTreeDirectedCut.h:916
ogdf::Level
Representation of levels in hierarchies.
Definition: Level.h:61
ogdf::MinSteinerTreeDirectedCut::Master::m_terminalListPH
List< node > m_terminalListPH
list of terminal nodes (in m_pWeightedGraphPH)
Definition: MinSteinerTreeDirectedCut.h:603
ogdf::MinSteinerTreeDirectedCut::setSaturationStrategy
void setSaturationStrategy(int b)
Set saturation strategy for nested cuts.
Definition: MinSteinerTreeDirectedCut.h:173
ogdf::MinSteinerTreeDirectedCut::Sub::~Sub
virtual ~Sub()
The destructor only deletes the sons of the node.
Definition: MinSteinerTreeDirectedCut.h:697
ogdf::MinSteinerTreeDirectedCut::Master::nodes
node * nodes() const
nodes of the graph
Definition: MinSteinerTreeDirectedCut.h:415
ogdf::ListIteratorBase
Encapsulates a pointer to a list element.
Definition: List.h:42
ogdf::MinSteinerTreeDirectedCut::EdgeVariable::id
int id() const
id of the edge (variable)
Definition: MinSteinerTreeDirectedCut.h:796
ogdf::MinSteinerTreeDirectedCut::setPoolSizeInitFactor
void setPoolSizeInitFactor(int b)
Set factor for the initial size of the cutting pool.
Definition: MinSteinerTreeDirectedCut.h:194
ogdf::MinSTCutMaxFlow::isInBackCut
bool isInBackCut(const node v) const
Returns whether this node is part of the back cut.
Definition: MinSTCutMaxFlow.h:163
ogdf::MinSteinerTreeDirectedCut::Master::setSaturationStrategy
void setSaturationStrategy(int b)
Set saturation strategy for nested cuts.
Definition: MinSteinerTreeDirectedCut.h:339
ogdf::MinSteinerTreeDirectedCut::Master::m_addGSEC2Constraints
bool m_addGSEC2Constraints
parameter: add GSEC2 constraints yes/no, i.e. x_uv + x_vu <= 1
Definition: MinSteinerTreeDirectedCut.h:629
ogdf::Logger
Centralized global and local logging facility working on streams like std::cout.
Definition: Logger.h:99
ogdf::MinSteinerTreeDirectedCut::Sub::m_maxNrCuttingPlanes
int m_maxNrCuttingPlanes
maximum nr of cutting planes to be added
Definition: MinSteinerTreeDirectedCut.h:742
ogdf::EdgeWeightedGraph::setWeight
void setWeight(const edge e, T weight)
Definition: EdgeWeightedGraph.h:78
ogdf::MinSteinerTreeDirectedCut::setMaxNumberAddedCuttingPlanes
void setMaxNumberAddedCuttingPlanes(int b)
Set maximum number of added cutting planes per iteration.
Definition: MinSteinerTreeDirectedCut.h:148
ogdf::MinSteinerTreeDirectedCut::Master::twins
const EdgeArray< edge > & twins() const
Definition: MinSteinerTreeDirectedCut.h:434
ogdf::MinSteinerTreeDirectedCut::Master::m_primalHeuristic
std::unique_ptr< MinSteinerTreeModule< double > > m_primalHeuristic
Algorithm used for the primal heuristic.
Definition: MinSteinerTreeDirectedCut.h:541
ogdf::EdgeElement::target
node target() const
Returns the target node of the edge.
Definition: Graph_d.h:328
ogdf::MinSteinerTreeDirectedCut::Sub::m_separationStrategy
int m_separationStrategy
Definition: MinSteinerTreeDirectedCut.h:746
ogdf::MinSteinerTreeDirectedCut::DirectedCutConstraint::m_name
const char * m_name
name of the cut; required method for nonduplpool
Definition: MinSteinerTreeDirectedCut.h:1033
ogdf::MinSteinerTreeDirectedCut::DirectedCutConstraint
Class for directed cuts (i.e., separated Steiner cuts)
Definition: MinSteinerTreeDirectedCut.h:947
ogdf::randomNumber
int randomNumber(int low, int high)
Returns random integer between low and high (including).
abacus::VarType::Continuous
@ Continuous
A continuous variable.
Definition: vartype.h:48
ogdf::MinSteinerTreeDirectedCut::EdgeVariable
Variable for directed edges.
Definition: MinSteinerTreeDirectedCut.h:773
ogdf::MinSteinerTreeDirectedCut::Sub::m_minCardinalityCuts
bool m_minCardinalityCuts
Definition: MinSteinerTreeDirectedCut.h:754
ogdf::MinSteinerTreeDirectedCut::Master::bestSolution
double * bestSolution() const
the best found solution
Definition: MinSteinerTreeDirectedCut.h:447
ogdf::MinSteinerTreeDirectedCut::Sub::mySeparate
int mySeparate()
separation procedure
Definition: MinSteinerTreeDirectedCut.h:1701
ogdf::MinSteinerTreeDirectedCut::Master::useNestedCuts
void useNestedCuts(bool b)
Switch computation of nested cuts on or off.
Definition: MinSteinerTreeDirectedCut.h:327
ogdf::NodeElement
Class for the representation of nodes.
Definition: Graph_d.h:169
ogdf::MinSteinerTreeDirectedCut::Master::m_twin
EdgeArray< edge > m_twin
the twin edges (u,v) <-> (v,u)
Definition: MinSteinerTreeDirectedCut.h:565
ogdf::GraphCopy::newNode
node newNode(node vOrig)
Creates a new node in the graph copy with original node vOrig.
Definition: GraphCopy.h:418
ogdf::MinSteinerTreeDirectedCut::Master::capacities
const EdgeArray< double > & capacities() const
edge costs
Definition: MinSteinerTreeDirectedCut.h:427
ogdf::MinSteinerTreeDirectedCut::DegreeConstraint::m_node
node m_node
the associated node
Definition: MinSteinerTreeDirectedCut.h:889
ogdf::MinSteinerTreeDirectedCut::Master::setConfigFile
void setConfigFile(const char *filename)
Set the config file to use that overrides all other settings.
Definition: MinSteinerTreeDirectedCut.h:261
ogdf::MinSteinerTreeDirectedCut::Master::m_nTerminals
int m_nTerminals
nr of terminals
Definition: MinSteinerTreeDirectedCut.h:586
abacus::CSense::SENSE
SENSE
Definition: csense.h:51
abacus::Master::OSISOLVER
OSISOLVER
This enumeration defines which solvers can be used to solve the LP-relaxations.
Definition: master.h:209
ogdf::MinSteinerTreeDirectedCut::Master::terminateOptimization
virtual void terminateOptimization() override
store solution in EdgeArray
Definition: MinSteinerTreeDirectedCut.h:1422
ogdf::MinSteinerTreeDirectedCut::useNestedCuts
void useNestedCuts(bool b)
Switch computation of nested cuts on or off.
Definition: MinSteinerTreeDirectedCut.h:163
ogdf::MinSteinerTreeDirectedCut::Master::m_isSolutionEdge
EdgeArray< bool > m_isSolutionEdge
Definition: MinSteinerTreeDirectedCut.h:595
ogdf::MinSteinerTreeDirectedCut::EdgeVariable::target
node target() const
target node
Definition: MinSteinerTreeDirectedCut.h:802
ogdf::MinSTCutMaxFlow
Min-st-cut algorithm, that calculates the cut via maxflow.
Definition: MinSTCutMaxFlow.h:48
ogdf::MinSteinerTreeDirectedCut::Master::useGSEC2Constraints
void useGSEC2Constraints(bool b)
Switch usage of constraints x_uv + x_vu <= 1 on or off.
Definition: MinSteinerTreeDirectedCut.h:300
ogdf::MinSteinerTreeDirectedCut::DirectedCutConstraint::m_pGraph
const Graph * m_pGraph
the graph
Definition: MinSteinerTreeDirectedCut.h:1018
ogdf::List::pushBack
iterator pushBack(const E &x)
Adds element x at the end of the list.
Definition: List.h:1374
ogdf::MinSteinerTreeDirectedCut::EdgeConstraint::EdgeConstraint
EdgeConstraint(abacus::Master *master, edge e1, edge e2, int factor=1.0, abacus::CSense::SENSE sense=abacus::CSense::Less, double rhs=1.0)
Definition: MinSteinerTreeDirectedCut.h:817
abacus::Master
The master of the optimization.
Definition: master.h:69
ogdf::MinSteinerTreeDirectedCut::Master::isSolutionEdge
bool isSolutionEdge(edge e) const
returns true iff original edge is contained in optimum solution
Definition: MinSteinerTreeDirectedCut.h:380
ogdf::MinSTCutMaxFlow::isInFrontCut
bool isInFrontCut(const node v) const
Returns whether this node is part of the front cut.
Definition: MinSTCutMaxFlow.h:151