Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

lpsub.h
Go to the documentation of this file.
1 
30 #pragma once
31 
32 #include <ogdf/lib/abacus/lp.h>
33 
34 
35 namespace abacus {
36 
37 class InfeasCon;
38 class Sub;
39 class Master;
40 class FSVarStat;
41 class Constraint;
42 class Variable;
43 
44 
46 
61 class OGDF_EXPORT LpSub : public virtual LP {
62 
63  friend class Sub;
64  friend class SetBranchRule;
65  friend class BoundBranchRule;
66  friend class ValBranchRule;
67  friend class ConBranchRule;
68  friend class COPBRANCHRULE;
69 
70 public:
71 
73 
77  LpSub (Master *master, const Sub *sub);
78 
80 
86  virtual ~LpSub();
87 
88  const Sub *sub() const { return sub_; }
89 
91 
95  int trueNCol() const { return LP::nCol(); }
96 
98  int trueNnz() const { return LP::nnz(); }
99 
101 
107  double lBound(int i) const;
108 
110  /***
111  * \param i The number of a variable.
112  *
113  * \return The upper bound of variable \a i. If a variable is eliminated, we
114  * return the value the eliminated variable is fixed or set to.
115  */
116  double uBound(int i) const;
117 
119 
124  virtual double value() const override { return LP::value() + valueAdd_; }
125 
127 
130  virtual double xVal(int i) const override;
131 
133 
137  virtual double barXVal(int i) const override;
138 
140 
143  virtual double reco(int i) const override;
144 
146 
149  virtual LPVARSTAT::STATUS lpVarStat(int i) const override;
150 
151 
153 
164  virtual int getInfeas(int &infeasCon, int &infeasVar, double *bInvRow) const override;
165 
174  virtual bool infeasible() const override {
175  return (LP::infeasible() || infeasCons_.size());
176  }
177 
179  ArrayBuffer<InfeasCon*> *infeasCon() { return &infeasCons_; }
180 
182 
189  virtual void loadBasis(Array<LPVARSTAT::STATUS> &lpVarStat,
190  Array<SlackStat::STATUS> &slackStat) override;
191 
192 protected:
193 
195 
199  virtual void initialize();
200 
201 private:
202 
204 
218  virtual OPTSTAT optimize(METHOD method) override;
219 
221  virtual void removeCons(ArrayBuffer<int> &ind) {
222  LP::remRows(ind);
223  }
224 
226  virtual void removeVars(ArrayBuffer<int> &vars);
227 
229  virtual void addCons(ArrayBuffer<Constraint*> &newCons);
230 
237  virtual void addVars(
239  ArrayBuffer<FSVarStat*> &fsVarStat,
241  ArrayBuffer<double> &ub);
242 
244 
248  virtual void changeLBound(int i, double newLb) override;
249 
251 
255  virtual void changeUBound(int i, double newUb) override;
256 
258  virtual void varRealloc(int newSize);
259 
261  virtual void conRealloc(int newSize);
262 
264  void constraint2row(ArrayBuffer<Constraint*> &newCons,
265  ArrayBuffer<Row*> &newRows);
266 
268 
273  bool eliminable(int i) const;
274 
276 
281  bool eliminated(int i) const {
282  return (orig2lp_[i] == -1);
283  }
284 
286 
292  virtual double elimVal(int i) const;
293 
295 
300  virtual double elimVal(FSVarStat *stat, double lb, double ub) const;
301 
302  void initialize(
303  OptSense sense,
304  int nRow,
305  int maxRow,
306  int nCol,
307  int maxCol,
308  Array<double> &obj,
309  Array<double> &lBound,
310  Array<double> &uBound,
311  Array<Row*> &rows);
312 
313  void initialize(
314  OptSense sense,
315  int nRow,
316  int maxRow,
317  int nCol,
318  int maxCol,
319  Array<double> &obj,
320  Array<double> &lBound,
321  Array<double> &uBound,
322  Array<Row*> &rows,
323  Array<LPVARSTAT::STATUS> &lpVarStat,
324  Array<SlackStat::STATUS> &slackStat);
325 
326  int nCol() const;
327  int maxCol() const;
328  int nnz() const;
329  double obj(int i) const;
330 
331  void rowRealloc(int newSize);
332  void colRealloc(int newSize);
333 
334 
336  const Sub *sub_;
337 
345 
348 
351 
353  double valueAdd_;
354 
357 
358  LpSub(const LpSub &rhs);
359  const LpSub &operator=(const LpSub &rhs);
360 };
361 
362 }
363 
364 #include <ogdf/lib/abacus/sub.h>
365 
366 namespace abacus {
367 
368 inline LpSub::LpSub (Master *master, const Sub *sub)
369  :
370  LP(master),
371  sub_(sub),
372  orig2lp_(sub->maxVar()),
373  lp2orig_(sub->maxVar()),
374  infeasCons_(sub->maxCon(),false)
375 { }
376 
377 }
ogdf::ArrayBuffer
An array that keeps track of the number of inserted elements; also usable as an efficient stack.
Definition: Array.h:45
abacus::LpSub::sub
const Sub * sub() const
Definition: lpsub.h:88
sub.h
abacus::SetBranchRule
Implements a branching rule for setting a binary variable to its lower or upper bound.
Definition: setbranchrule.h:42
abacus::LpSub::nOrigVar_
int nOrigVar_
The number of original variables of the linear program.
Definition: lpsub.h:356
abacus::LpSub::orig2lp_
Array< int > orig2lp_
After the elimination of variables the internal variables are again numbered consecutively starting w...
Definition: lpsub.h:344
abacus::LpSub::sub_
const Sub * sub_
A pointer to the corresponding subproblem.
Definition: lpsub.h:336
abacus::OptSense
Sense of optimization.
Definition: optsense.h:44
abacus::FSVarStat
Status of fixed and set variables.
Definition: fsvarstat.h:46
abacus
Definition: abacusroot.h:48
abacus::LPVARSTAT::STATUS
STATUS
The enumeration of the statuses a variable gets from the linear program solver.
Definition: lpvarstat.h:54
abacus::LpSub::infeasCons_
ArrayBuffer< InfeasCon * > infeasCons_
Buffer storing the infeasible constraints found be the constructor.
Definition: lpsub.h:350
abacus::BoundBranchRule
Implements a branching rule for modifying the lower and the upper bound of a variable.
Definition: boundbranchrule.h:40
abacus::LP::nnz
int nnz() const
Definition: lp.h:227
abacus::LpSub::removeCons
virtual void removeCons(ArrayBuffer< int > &ind)
Removes all constraints listed in the buffer ind from the linear program.
Definition: lpsub.h:221
abacus::ValBranchRule
Implements a branching rule for setting a variable to a certain value.
Definition: valbranchrule.h:41
abacus::LpSub::trueNnz
int trueNnz() const
Returns the number of nonzeros which are currently present in the constraint matrix of the LP-solver.
Definition: lpsub.h:98
abacus::LpSub::LpSub
LpSub(Master *master, const Sub *sub)
The constructor.
Definition: lpsub.h:368
abacus::LpSub::infeasCon
ArrayBuffer< InfeasCon * > * infeasCon()
Returns a pointer to the buffer holding the infeasible constraints.
Definition: lpsub.h:179
abacus::ConBranchRule
Implements the branching by adding a constraint to the set of active constraints.
Definition: conbranchrule.h:44
abacus::LpSub::lp2orig_
Array< int > lp2orig_
Original number of a (non-eliminated) variable.
Definition: lpsub.h:347
ogdf::AlgorithmFailureCode::Constraint
@ Constraint
abacus::LpSub::trueNCol
int trueNCol() const
Returns the number of columns which are passed to the LP-solver.
Definition: lpsub.h:95
lp.h
linear program.
abacus::LpSub::eliminated
bool eliminated(int i) const
Returns true if the variable i is actually eliminated from the LP.
Definition: lpsub.h:281
ogdf::Array
The parameterized class Array implements dynamic arrays of type E.
Definition: Array.h:204
abacus::LP
Linear programs.
Definition: lp.h:70
ogdf::AlgorithmFailureCode::InfeasCon
@ InfeasCon
abacus::LP::nCol
int nCol() const
Definition: lp.h:223
abacus::LpSub
The linear program of a subproblem.
Definition: lpsub.h:61
abacus::LP::value
virtual double value() const
Definition: lp.h:264
abacus::LP::infeasible
virtual bool infeasible() const
Definition: lp.h:315
abacus::LP::remRows
void remRows(ArrayBuffer< int > &ind)
Removes rows of the linear program.
Definition: lp.h:376
ogdf::AlgorithmFailureCode::Variable
@ Variable
OGDF_EXPORT
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition: config.h:99
abacus::Sub
The subproblem.
Definition: sub.h:68
abacus::LpSub::value
virtual double value() const override
Returns the objective function value of the linear program.
Definition: lpsub.h:124
abacus::LpSub::infeasible
virtual bool infeasible() const override
Definition: lpsub.h:174
abacus::LpSub::valueAdd_
double valueAdd_
The constant which has been added to the objective function value due to the elimination of variables...
Definition: lpsub.h:353
abacus::Master
The master of the optimization.
Definition: master.h:69