Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
MaxCPlanarSub.h
Go to the documentation of this file.
1
35#pragma once
36
40
42#include <ogdf/lib/abacus/sub.h>
43
44namespace ogdf {
45namespace cluster_planarity {
46
47class MaxCPlanarSub : public abacus::Sub {
48public:
52
53 virtual ~MaxCPlanarSub();
54
55 // Creation of a child-node in the Branch&Bound tree according to the
56 // branching rule #rule
58
59
60protected:
61 // Checks if the current solution of the LP relaxation is also a feasible solution to the ILP,
62 // i.e. Integer-feasible + satisfying all Kuratowski- and Cut-constraints.
63 virtual bool feasible() override;
64
65 // to trick Sub::solveLp...
66 virtual int makeFeasible() override { return 0; }
67#if 0
68 // to trick Sub::solveLp into returning 2
69 virtual int removeNonLiftableCons() { return 0; }
70#endif
71 int repair();
72
73 virtual int optimize() override {
74 Logger::slout() << "OPTIMIZE BEGIN\tNode=" << this->id() << "\n";
76 Logger::slout() << "OPTIMIZE END\tNode=" << this->id() << " db=" << dualBound()
77 << "\tReturn=" << (ret ? "(error)" : "(ok)") << "\n";
78 return ret;
79 }
80
81 //functions for testing properties of the clustered graph
82
85 bool checkCConnectivity(const GraphCopy& support);
86 bool checkCConnectivityOld(const GraphCopy& support);
87
91 while (v != parent[v]) {
92 v = parent[v];
93 }
94 return v;
95 }
96
97 // Todo: Think about putting this into extended_graph_alg.h to make it
98 // publically available
100
101#if 0
102 // using the below two functions iunstead (and instead of solveLp) we would get a more traditional situation
103 virtual int separate() {
104 return separateRealO(0.001);
105 }
106 virtual int pricing() {
107 return pricingRealO(0.001);
108 }
109#endif
110
117#if 0
118 int pricingReal(double minViolate);
119#endif
120
121 inline int separateRealO(double minViolate) {
122 Logger::slout() << "\tSeparate (minViolate=" << minViolate << ")..";
124 Logger::slout() << "..done: " << r << "\n";
125 return r;
126 }
127#if 0
128 inline int pricingRealO(double minViolate) {
129 Logger::slout() << "\tPricing (minViolate=" << minViolate << ")..";
130 int r = pricingReal(minViolate);
131 master()->m_varsPrice += r;
132 Logger::slout() << "..done: " << r << "\n";
133 return r;
134 }
135#endif
136
137 virtual int separate() override {
139 << "\tReporting Separation: " << ((m_reportCreation > 0) ? m_reportCreation : 0)
140 << "\n";
141 return (m_reportCreation > 0) ? m_reportCreation : 0;
142 }
143
144 virtual int pricing() override {
145 if (inOrigSolveLp) {
146 return 1;
147 }
149 << "\tReporting Prizing: " << ((m_reportCreation < 0) ? -m_reportCreation : 0)
150 << "\n";
151 return (m_reportCreation < 0) ? -m_reportCreation : 0;
152 }
153
154 virtual int solveLp() override;
155
156 // Implementation of virtual function improve() inherited from ABA::SUB.
157 // Invokes the function heuristicImprovePrimalBound().
158 // Tthis function belongs to the ABACUS framework. It is invoked after each separation-step.
159 // Since the heuristic is rather time consuming and because it is not very advantageous
160 // to run the heuristic even if additional constraints have been found, the heuristic
161 // is run "by hand" each time no further constraints coud be found, i.e. after having solved
162 // the LP-relaxation optimally.
163 virtual int improve(double& primalValue) override;
164
165 // Two functions inherited from ABACUS and overritten to manipulate the branching behaviour.
167 virtual int selectBranchingVariable(int& variable) override;
168
174
179
180private:
181 MaxCPlanarMaster* master() const { return static_cast<MaxCPlanarMaster*>(master_); }
182
183 // A flag indicating if constraints have been found in the current separation step.
184 // Is used to check, if the primal heuristic should be run or not.
189
190 // used for the steering in solveLp
196
198 int num = b.size();
199 ArrayBuffer<bool> keep(num, false);
200 for (int i = num; i-- > 0;) {
201 keep.push(true);
202 }
203#ifdef OGDF_DEBUG
204 int r =
205#endif
206 addVars(b, nullptr, &keep);
207 OGDF_ASSERT(r == num);
208 }
209
210 // Computes the support graph for Kuratowski- constraints according to the current LP-solution.
211 // Parameter \p low defines a lower threshold, i.e all edges having value at most \p low
212 // are not added to the support graph.
213 // Parameter \p high defines an upper threshold, i.e all edges having value at least \p high,
214 // are added to the support graph.
215 // Edges having LP-value k that lies between \p low and \p high are added to the support graph
216 // randomly with a probability of k.
217 void kuratowskiSupportGraph(GraphCopy& support, double low, double high);
218
219 // Computes the support graph for Connectivity- constraints according to the current LP-solution.
221
222 // Computes the integer solution induced Graph.
224
225 // Computes and returns the value of the lefthand side of the Kuratowski constraint
226 // induced by \p it and given support graph \p gc.
228
229 // Updates the best known solution according to integer solution of this subproblem.
231
232
233 // The following four functions are used by the primal heuristic.
234
235 int getArrayIndex(double lpValue);
236
239
242
243 // Tries to improve the best primal solution by means of the current fractional LP-solution.
246
249 return addPoolCons(cons, static_cast<MaxCPlanarMaster*>(master_)->getCutConnPool());
250 }
251
254 return addPoolCons(cons, static_cast<MaxCPlanarMaster*>(master_)->getCutKuraPool());
255 }
256
257 //tries to regenerate connectivity cuts
258 inline int separateConnPool(double minViolation) {
259 return separateCutPool(static_cast<MaxCPlanarMaster*>(master_)->getCutConnPool(),
261 }
262
263 //tries to regenerate kuratowski cuts
264 inline int separateKuraPool(double minViolation) {
265 return separateCutPool(static_cast<MaxCPlanarMaster*>(master_)->getCutKuraPool(),
267 }
268#if 0
270 GraphCopy &GC,
273
275 ClusterGraph &C,
276 cluster c,
279 List<node> &clusterNodes);
280
284 List<NodePair> &delEdges);
285#endif
286};
287
288}
289}
Declaration and implementation of ArrayBuffer class.
Declaration of the wrapper class of the Boyer-Myrvold planarity test.
Declaration of the master class for the Branch&Cut algorithm for the Maximum C-Planar SubGraph proble...
Abstract base class for all branching rules.
Definition branchrule.h:59
The master of the optimization.
Definition master.h:69
Standard pools.
The subproblem.
Definition sub.h:68
BranchRule * branchRule() const
Returns a pointer to the branching rule of the subproblem.
Definition sub.h:355
int id() const
Returns the identity number of the subproblem.
Definition sub.h:153
Variable * variable(int i) const
Returns a pointer to the i-th active variable.
Definition sub.h:1863
virtual int optimize()
Performs the optimization of the subproblem.
virtual int addCons(ArrayBuffer< Constraint * > &constraints, Pool< Constraint, Variable > *pool=nullptr, ArrayBuffer< bool > *keepInPool=nullptr, ArrayBuffer< double > *rank=nullptr)
Tries to add new constraints to the constraint buffer and a pool.
double dualBound() const
Returns a bound which is "better" than the optimal solution of the subproblem w.r....
Definition sub.h:181
virtual int constraintPoolSeparation(int ranking=0, Pool< Constraint, Variable > *pool=nullptr, double minViolation=0.001)
Tries to generate inactive constraints from a pool.
Master * master_
A pointer to the corresponding master of the optimization.
Definition sub.h:1436
virtual bool removeNonLiftableCons()
virtual int addVars(ArrayBuffer< Variable * > &variables, Pool< Variable, Constraint > *pool=nullptr, ArrayBuffer< bool > *keepInPool=nullptr, ArrayBuffer< double > *rank=nullptr)
Tries to add new variables to the variable buffer and a pool.
const Sub * father() const
Returns a pointer to the father of the subproblem in the branch-and-bound tree.
Definition sub.h:198
An array that keeps track of the number of inserted elements; also usable as an efficient stack.
Definition ArrayBuffer.h:56
INDEX size() const
Returns number of elements in the buffer.
Dynamic arrays indexed with clusters.
Representation of clusters in a clustered graph.
Representation of clustered graphs.
Dynamic arrays indexed with edges.
Definition EdgeArray.h:125
Copies of graphs supporting edge splitting.
Definition GraphCopy.h:254
Doubly linked lists (maintaining the length of the list).
Definition List.h:1435
static std::ostream & slout(Level level=Level::Default)
stream for logging-output (global)
Definition Logger.h:167
Dynamic arrays indexed with nodes.
Definition NodeArray.h:125
Class for the representation of nodes.
Definition Graph_d.h:177
Encapsulates a pointer to an ogdf::SList element.
Definition SList.h:92
virtual int makeFeasible() override
The default implementation of makeFeasible()does nothing.
MaxCPlanarSub(abacus::Master *master, abacus::Sub *father, abacus::BranchRule *branchRule, List< abacus::Constraint * > &criticalConstraints)
MaxCPlanarMaster * master() const
int separateConnPool(double minViolation)
virtual int optimize() override
Performs the optimization of the subproblem.
virtual int selectBranchingVariableCandidates(ArrayBuffer< int > &candidates) override
Selects candidates for branching variables.
double heuristicImprovePrimalBound(List< NodePair > &originalEdges, List< NodePair > &connectionEdges, List< edge > &deletedEdges)
virtual abacus::Sub * generateSon(abacus::BranchRule *rule) override
Returns a pointer to an object of a problem specific subproblem, which is generated from the current ...
void myAddVars(ArrayBuffer< abacus::Variable * > &b)
virtual int solveLp() override
Solves the LP-relaxation of the subproblem.
double subdivisionLefthandSide(SListConstIterator< KuratowskiWrapper > it, GraphCopy *gc)
void connectivitySupportGraph(GraphCopy &support, EdgeArray< double > &weight)
int clusterBags(ClusterGraph &CG, cluster c)
void intSolutionInducedGraph(GraphCopy &support)
void kuratowskiSupportGraph(GraphCopy &support, double low, double high)
int addPoolCons(ArrayBuffer< abacus::Constraint * > &cons, abacus::StandardPool< abacus::Constraint, abacus::Variable > *pool)
Adds the given constraints to the given pool.
bool checkCConnectivity(const GraphCopy &support)
Checks if the cluster induced graphs and their complement are connected in the current solution.
virtual bool feasible() override
Must check the feasibility of a solution of the LP-relaxation.
virtual int improve(double &primalValue) override
Can be redefined in order to implement primal heuristics for finding feasible solutions.
int addCutCons(ArrayBuffer< abacus::Constraint * > cons)
Adds the given constraints to the connectivity cut pool.
List< abacus::Constraint * > criticalSinceBranching
int addKuraCons(ArrayBuffer< abacus::Constraint * > cons)
Adds the given constraints to the planarity cut pool.
virtual int separate() override
Must be redefined in derived classes for the generation of cutting planes.
node getRepresentative(node v, NodeArray< node > &parent)
run through the pointer list parent and return the representative i.e. the node with parent[v] == v
void clusterSpanningTree(ClusterGraph &C, cluster c, ClusterArray< List< NodePair > > &treeEdges, ClusterArray< List< edgeValue > > &clusterEdges)
virtual int selectBranchingVariable(int &variable) override
Chooses a branching variable.
void childClusterSpanningTree(GraphCopy &GC, List< edgeValue > &clusterEdges, List< NodePair > &MSTEdges)
MaxCPlanarSub(abacus::Master *master)
int separateReal(double minViolate)
these functions are mainly reporting to let abacus think everthing is normal.
bool checkCConnectivityOld(const GraphCopy &support)
ArrayBuffer< abacus::Constraint * > bufferedForCreation
int separateKuraPool(double minViolation)
int separateCutPool(abacus::StandardPool< abacus::Constraint, abacus::Variable > *pool, double minViolation)
virtual int pricing() override
Should generate inactive variables which do not price out correctly.
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition basic.h:41
int r[]
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.
standard pool.