Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

constraint.h
Go to the documentation of this file.
1 
30 #pragma once
31 
32 #include <ogdf/lib/abacus/convar.h>
33 
35 #include <ogdf/lib/abacus/csense.h>
37 
38 
39 #pragma GCC visibility push(default)
40 namespace abacus {
41 
42 class Row;
43 class Master;
44 class Variable;
45 class LpSub;
46 
47 template<class BaseType, class CoType> class Active;
48 
49 
51 
57 class OGDF_EXPORT Constraint : public ConVar {
58 
59  friend class LpSub;
60 
61 public:
62 
64 
80  Constraint (
81  Master *master,
82  const Sub *sub,
83  CSense::SENSE sense,
84  double rhs,
85  bool dynamic,
86  bool local,
87  bool liftable);
88 
89 
91 
98  Constraint (Master *master);
99 
100 
102 
105  Constraint(const Constraint &rhs)
106  : ConVar(rhs), sense_(rhs.sense_), rhs_(rhs.rhs_), conClass_(nullptr), liftable_(rhs.liftable_)
107  {
108  if (rhs.conClass_) conClass_ = new ConClass(*(rhs.conClass_));
109  }
110 
111 
112  virtual ~Constraint() { delete conClass_; }
113 
114 
116  CSense *sense() { return &sense_; }
117 
119  const CSense *sense() const { return &sense_; }
120 
121 
123 
128  virtual double coeff(const Variable *v) const = 0;
129 
131  virtual double rhs() const { return rhs_; }
132 
133 
135 
141  bool liftable() const { return liftable_; }
142 
143 
145 
154  virtual bool valid(Sub *sub) const;
155 
156 
158 
171  virtual int genRow(Active<Variable, Constraint> *var,
172  Row &row) const;
173 
175 
181  virtual double slack(Active<Variable, Constraint> *variables,
182  double *x) const;
183 
185 
193  virtual bool violated(
194  Active<Variable, Constraint> *variables, double *x, double *sl = nullptr) const;
195 
197 
205  virtual bool violated(double slack) const;
206 
208 
212  void printRow(std::ostream &out, Active<Variable, Constraint> *var) const;
213 
215 
228  virtual double distance(double *x, Active<Variable, Constraint> *actVar) const;
229 
230  //Constraint *duplicate() { return 0; }
231 
233 
240  ConClass *classification(Active<Variable, Constraint> *var = nullptr) const;
241 
242 protected:
243 
256  virtual InfeasCon::INFEAS voidLhsViolated(double newRhs) const;
257 
262  return nullptr;
263  }
264 
265 
267 
268  double rhs_;
269 
270  mutable ConClass *conClass_; //this is just s cached-value, and hence can be set in const classify-call (it's nullptr initially, and computed upon first call
271 
276  bool liftable_;
277 
278 private:
279  const Constraint &operator=(const Constraint &rhs);
280 };
281 
282 }
283 #pragma GCC visibility pop
284 
285 #include <ogdf/lib/abacus/sub.h>
286 #include <ogdf/lib/abacus/master.h>
287 
288 #pragma GCC visibility push(default)
289 namespace abacus {
290 
292  Master *master,
293  const Sub *sub,
294  CSense::SENSE sense,
295  double rhs,
296  bool dynamic,
297  bool local,
298  bool liftable)
299  : ConVar(master, sub, dynamic, local), sense_(sense), rhs_(rhs), conClass_(nullptr), liftable_(liftable)
300 {
301  if (local && sub == nullptr) {
302  Logger::ifout() << "Constraint::Constraint(): subtree of local item must not be 0\n";
304  }
305 }
306 
307 
309  : ConVar(master, nullptr, true, true), conClass_(nullptr) { }
310 
311 
312 inline bool Constraint::valid(Sub *sub) const {
313  OGDF_ASSERT(!local_ || sub != nullptr);
314 
315  return (!local_ || sub_->ancestor(sub));
316 }
317 
318 }
319 #pragma GCC visibility pop
abacus::Constraint::classify
virtual ConClass * classify(Active< Variable, Constraint > *var) const
The default implementation returns a 0 pointer.
Definition: constraint.h:261
abacus::Active
Implements the sets of active constraints and variables which are associated with each subproblem.
Definition: active.h:44
abacus::ConVar::local
bool local() const
Returns true if the constraint/variable is only locally valid, false otherwise.
Definition: convar.h:114
sub.h
abacus::ConVar::sub
const Sub * sub() const
Returns a const pointer to the subproblem associated with the constraint/variable.
Definition: convar.h:200
OGDF_ASSERT
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition: basic.h:66
abacus::Constraint::rhs
virtual double rhs() const
Returns the right hand side of the constraint.
Definition: constraint.h:131
convar.h
constraints and variables.
abacus::Constraint::conClass_
ConClass * conClass_
Definition: constraint.h:270
abacus::Constraint::valid
virtual bool valid(Sub *sub) const
Checks if the constraint is valid for the subproblem sub.
Definition: constraint.h:312
abacus::Constraint::Constraint
Constraint(Master *master, const Sub *sub, CSense::SENSE sense, double rhs, bool dynamic, bool local, bool liftable)
Initializes a constraint.
Definition: constraint.h:291
abacus::Constraint::rhs_
double rhs_
The right hand side of the constraint.
Definition: constraint.h:268
abacus::Constraint::sense
const CSense * sense() const
Returns a const pointer to the sense of the constraint.
Definition: constraint.h:119
abacus
Definition: ILPClusterPlanarity.h:50
abacus::ConVar::sub_
const Sub * sub_
A pointer to the subproblem associated with the constraint/variable.
Definition: convar.h:290
abacus::Constraint::liftable
bool liftable() const
Checks if the constraint is liftable.
Definition: constraint.h:141
abacus::Constraint::~Constraint
virtual ~Constraint()
Definition: constraint.h:112
ogdf::AlgorithmFailureCode::LpSub
@ LpSub
ogdf::AlgorithmFailureException
Exception thrown when an algorithm realizes an internal bug that prevents it from continuing.
Definition: exceptions.h:247
ogdf::AlgorithmFailureCode::Constraint
@ Constraint
abacus::ConVar
Common base class for constraints (Constraint) and variables (Variable).
Definition: convar.h:66
abacus::Row
Representation of constraints in the row format.
Definition: row.h:52
csense.h
csense.
abacus::Variable
Forms the virtual base class for all possible variables given in pool format.
Definition: variable.h:60
ogdf::AlgorithmFailureCode::Active
@ Active
abacus::Constraint::sense
CSense * sense()
Returns a pointer to the sense of the constraint.
Definition: constraint.h:116
abacus::ConClass
Constraint classification.
Definition: conclass.h:45
OGDF_THROW_PARAM
#define OGDF_THROW_PARAM(CLASS, PARAM)
Replacement for throw.
Definition: exceptions.h:71
abacus::LpSub
The linear program of a subproblem.
Definition: lpsub.h:62
infeascon.h
infeasible constraints.
abacus::ConVar::local_
bool local_
true if the constraint/variable is only locally valid
Definition: convar.h:313
ogdf::Logger::ifout
static std::ostream & ifout()
stream for forced output (global; used by internal libraries, e.g. Abacus)
Definition: Logger.h:218
master.h
the master of the optimization.
abacus::Constraint::sense_
CSense sense_
The sense of the constraint.
Definition: constraint.h:266
ogdf::AlgorithmFailureCode::Variable
@ Variable
abacus::Constraint::Constraint
Constraint(const Constraint &rhs)
Copy constructor.
Definition: constraint.h:105
OGDF_EXPORT
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF dynamic library (shared object / DLL),...
Definition: config.h:117
abacus::Sub
The subproblem.
Definition: sub.h:69
abacus::Constraint
Forms the virtual base class for all possible constraints given in pool format.
Definition: constraint.h:57
Minisat::Internal::var
int var(Lit p)
Definition: SolverTypes.h:62
conclass.h
constraint classification.
abacus::Constraint::liftable_
bool liftable_
This member is true if also coefficients of variables which have been inactive at generation time can...
Definition: constraint.h:276
abacus::CSense
Sense of constraints.
Definition: csense.h:49
abacus::Sub::ancestor
bool ancestor(const Sub *sub) const
Returns true if this subproblem is an ancestor of the subproblem sub, false otherwise.
abacus::CSense::SENSE
SENSE
Definition: csense.h:52
abacus::InfeasCon::INFEAS
INFEAS
The different ways of infeasibility of a constraint.
Definition: infeascon.h:56
abacus::Master
The master of the optimization.
Definition: master.h:70