Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
sub.h
Go to the documentation of this file.
1
30#pragma once
31
32#include <ogdf/lib/abacus/lp.h>
35
37
38
39namespace abacus {
40
41class LpSub;
42class TailOff;
43class BranchRule;
44class LPVARSTAT;
45class Variable;
46class Master;
47class InfeasCon;
48class Constraint;
49
50template<class BaseType, class CoType> class CutBuffer;
51template<class BaseType, class CoType> class Active;
52template<class BaseType, class CoType> class Pool;
53template<class BaseType, class CoType> class PoolSlot;
54template<class BaseType, class CoType> class LpSolution;
55
56
58
68class OGDF_EXPORT Sub : public AbacusRoot {
69
70 friend class Master;
71 friend class BoundBranchRule;
72 friend class OpenSub;
73 friend class LpSolution<Constraint, Variable>;
74 friend class LpSolution<Variable, Constraint>;
75
76public:
77
79 enum STATUS {
82 Dormant,
85 Fathomed
86 };
87
89 enum PHASE {
91 Cutting,
94 Fathoming
95 };
96
98
116 Master *master,
117 double conRes,
118 double varRes,
119 double nnzRes,
120 bool relativeRes = true,
123
125
131 Sub(Master *master, Sub *father, BranchRule *branchRule);
132
134
144 virtual ~Sub();
145
147 bool forceExactSolver() const { return forceExactSolver_; }
148
150 int level() const { return level_; }
151
153 int id() const { return id_; }
154
156 STATUS status() const { return status_; }
157
159 int nVar() const;
160
162 int maxVar() const;
163
165 int nCon() const;
166
168 int maxCon() const;
169
171 double lowerBound() const;
172
174 double upperBound() const;
175
177
181 double dualBound() const { return dualBound_; }
182
184
195 void dualBound(double x);
196
198 const Sub *father() const { return father_; }
199
201 LpSub *lp() const { return lp_; }
202
204
210 void maxIterations(int max);
211
213 Active<Constraint, Variable> *actCon() const { return actCon_; }
214
216 Active<Variable, Constraint> *actVar() const { return actVar_; }
217
219
222 Constraint *constraint(int i) const;
223
225
228 SlackStat *slackStat(int i) const { return (*slackStat_)[i]; }
229
231
234 Variable *variable(int i) const;
235
237
245 double lBound(int i) const { return (*lBound_)[i]; }
246
248
255 void lBound(int i, double l);
256
258
266 double uBound(int i) const { return (*uBound_)[i]; }
267
269
276 void uBound(int i, double u);
277
279
291 FSVarStat *fsVarStat(int i) const { return (*fsVarStat_)[i]; }
292
294
297 LPVARSTAT *lpVarStat(int i) const { return (*lpVarStat_)[i]; }
298
300
303 double xVal(int i) const { return xVal_[i]; }
304
306
309 double yVal(int i) const { return yVal_[i]; }
310
312
317 bool ancestor(const Sub *sub) const;
318
320 Master *master() { return master_; }
321
323 const Master *master() const { return master_; }
324
326
334
336
343 void removeVar(int i) { removeVarBuffer_->push(i); }
344
346 double nnzReserve() const { return nnzReserve_; }
347
352 bool relativeReserve() const { return relativeReserve_; }
353
355 BranchRule *branchRule() const { return branchRule_; }
356
358
371 bool objAllInteger() const;
372
374
379 virtual void removeCons(ArrayBuffer<int> &remove);
380
382
385 virtual void removeCon(int i);
386
388
395 int addConBufferSpace() const;
396
398
405 int addVarBufferSpace() const;
406
408 int nDormantRounds() const { return nDormantRounds_; }
409
411
424
426
435 virtual int addBranchingConstraint(PoolSlot<Constraint, Variable> *slot);
436
437protected:
438
440
459 ArrayBuffer<bool> *keepInPool = nullptr,
460 ArrayBuffer<double> *rank = nullptr);
461
463
468 virtual int addCons(
470
472
491 ArrayBuffer<bool> *keepInPool = nullptr,
492 ArrayBuffer<double> *rank = nullptr);
493
495
506 virtual int addVars(
508
510
525 int ranking = 0,
527 double minViolation = 0.001);
528
530
547 int ranking = 0,
549 double minViolation = 0.001);
550
552
555 virtual void activate() { }
556
558
563 virtual void deactivate () { }
564
566
576 return branchingOnVariable(rules);
577 }
578
580
591
593
606 virtual int selectBranchingVariable(int &variable);
607
609
640
642
656
658
664 Array<double> &rank);
665
667
676 virtual double rankBranchingRule(BranchRule *branchRule);
677
679
693 double lpRankBranchingRule(BranchRule *branchRule, int iterLimit = -1);
694
696
709
711
721
723 /***
724 * Those variables with fractional part close to \f$0.5\f$ and high absolute objective function
725 * coefficient are selected..
726 *
727 * \param variables Holds the numbers of possible branching variables if
728 * at least one is found. We try to find as many
729 * candidates as fit into this buffer. We abort
730 * the function with a fatal error if the size
731 * of the buffer is 0.
732 * \param branchVarType The type of the branching variable can be restricted either
733 * to VarType::Binary or VarType::Integer.
734 *
735 * \return 0 If at least one branching variable is found, 1 otherwise.
736 */
739
741
749
751
759
761
770
772
780
782
797 virtual int initMakeFeas(
798 ArrayBuffer<InfeasCon*> &infeasCon,
799 ArrayBuffer<Variable*> &newVars,
801 {
802 return 1;
803 }
804
806
822 virtual int makeFeasible() { return 1; }
823
835 virtual bool goodCol(Column &col, Array<double> &row,
836 double x, double lb, double ub);
837
839
845 virtual void setByLogImp(ArrayBuffer<int> &variable,
846 ArrayBuffer<FSVarStat*> &status) { }
847
849
856 virtual bool feasible() = 0;
857
859
867
869
879 virtual bool primalSeparation();
880
882
887 virtual int separate();
888
890
899 virtual void conEliminate(ArrayBuffer<int> &remove);
900
902
906
908
911 virtual void basicConEliminate(ArrayBuffer<int> &remove);
912
914
920 virtual void varEliminate(ArrayBuffer<int> &remove);
921
923
927
929
934 virtual int pricing() { return 0; }
935
937
945 virtual int improve(double &primalValue);
946
948
952
954 bool boundCrash() const;
955
968 virtual bool pausing() { return false; }
969
972
974
977 virtual void varRealloc(int newSize);
978
980
983 virtual void conRealloc(int newSize);
984
986
1000 int nVarAdded, int nConAdded);
1001
1003
1014 virtual bool tailingOff() { return true; }
1015
1017 bool betterDual(double x) const;
1018
1020
1024 virtual void selectVars() { }
1025
1027
1031 virtual void selectCons() { }
1032
1034
1045 virtual int fixByRedCost(bool &newValues, bool saveCand);
1046
1048 /***
1049 * The default implementation of \a fixByLogImp() does nothing. This
1050 * function has to be redefined if variables should be fixed by logical
1051 * implications in derived classes.
1052 *
1053 * \param variables The variables which should be fixed.
1054 * \param status The statuses these variables should be fixed to.
1055 */
1058
1060
1073 virtual int fixAndSet(bool &newValues);
1074
1076
1086 virtual int fixing(bool &newValues, bool saveCand = false);
1087
1089
1098 virtual int setting(bool &newValues);
1099
1101
1104 virtual int setByRedCost();
1105
1107
1130 virtual void fathom(bool reoptimize);
1131
1133
1138 virtual bool fixAndSetTime() { return true; }
1139
1141
1156 virtual int fix(int i, FSVarStat *newStat, bool &newValue);
1157
1159
1169 virtual int set(int i, FSVarStat *newStat, bool &newValue);
1170
1172
1181 virtual int set(int i, FSVarStat::STATUS newStat, bool &newValue);
1182
1184
1194 virtual int set(int i, FSVarStat::STATUS newStat, double value,
1195 bool &newValue);
1196
1206 virtual double dualRound(double x);
1207
1209
1212 virtual double guarantee() const;
1213
1218 virtual bool guaranteed() const;
1219
1228
1230
1237
1239
1250 virtual void fathomTheSubTree();
1251
1253
1271 virtual int optimize();
1272
1274
1290 virtual void reoptimize();
1291
1293
1296 virtual void initializeVars(int maxVar);
1297
1299
1302 virtual void initializeCons(int maxCon);
1303
1305
1325 virtual PHASE branching();
1326
1328
1352 virtual PHASE fathoming();
1353
1355
1365 virtual PHASE cutting();
1366
1368
1376 virtual LpSub *generateLp();
1377
1379
1390 virtual int initializeLp();
1391
1393
1407 virtual int solveLp();
1408
1410
1415 virtual bool exceptionFathom() { return false; }
1416
1418
1424 virtual bool exceptionBranch() { return false; }
1425
1432 virtual bool solveApproxNow() { return false; }
1433
1434
1437
1440
1443
1446
1449
1451
1459
1462
1465
1468
1471
1474
1477
1480
1483
1486
1489
1495
1498
1501
1504
1507
1510
1512 double *xVal_;
1513
1515 double *yVal_;
1516
1518 double *bInvRow_;
1519
1522
1525
1528
1529private:
1530
1532 virtual int _separate();
1533
1535
1540 virtual int _conEliminate();
1541
1543
1546 virtual int _varEliminate();
1547
1572 virtual int _pricing(bool &newValues, bool doFixSet = true);
1573
1575
1587 virtual int _improve(double &primalValue);
1588
1590
1594 virtual int _fixByLogImp(bool &newValues);
1595
1597
1601 virtual void updateBoundInLp(int i);
1602
1604 virtual double fixSetNewBound(int i);
1605
1607
1611 virtual void newDormantRound() { ++nDormantRounds_; }
1612
1614
1647 virtual PHASE _activate();
1648
1650
1659 virtual void _deactivate();
1660
1662
1674 virtual int _initMakeFeas();
1675
1684 virtual int _makeFeasible();
1685
1687
1696 virtual int _setByLogImp(bool &newValues);
1697
1699
1702 virtual void infeasibleSub();
1703
1705 virtual void getBase();
1706
1708
1713
1715
1722
1724
1728
1731
1733 virtual int _removeVars(ArrayBuffer<int> &remove);
1734
1736 virtual int _removeCons(ArrayBuffer<int> &remove);
1737
1739 bool _atUpperBound(int i);
1740
1742 bool _atLowerBound(int i);
1743
1744
1747
1749 int id_;
1750
1753
1756
1759
1762
1772
1775
1778
1781
1784
1786
1791
1793
1798
1801
1803
1806
1807 Sub(const Sub &rhs);
1808 const Sub &operator=(const Sub &rhs);
1809};
1810
1811}
1812
1813// NOW declaration of sub is complete. its definitions below need full declarations of the below types...
1814
1817#include <ogdf/lib/abacus/active.h>
1819#include <ogdf/lib/abacus/lpsub.h>
1820
1821namespace abacus {
1822
1824{
1825 return addConBuffer_->insert(slot, true);
1826}
1827
1828inline int Sub::addConBufferSpace() const
1829{
1830 return addConBuffer_->space();
1831}
1832
1833inline int Sub::addVarBufferSpace() const
1834{
1835 return addVarBuffer_->space();
1836}
1837
1838inline int Sub::nVar() const
1839{
1840 return actVar_->number();
1841}
1842
1843inline int Sub::nCon() const
1844{
1845 return actCon_->number();
1846}
1847
1848inline int Sub::maxVar() const
1849{
1850 return actVar_->max();
1851}
1852
1853inline int Sub::maxCon() const
1854{
1855 return actCon_->max();
1856}
1857
1858inline Constraint *Sub::constraint(int i) const
1859{
1860 return (*actCon_)[i];
1861}
1862
1863inline Variable *Sub::variable(int i) const
1864{
1865 return (*actVar_)[i];
1866}
1867
1872
1873inline double Sub::lowerBound() const
1874{
1875 if (master_->optSense()->max())
1876 return master_->primalBound();
1877 else
1878 return dualBound_;
1879}
1880
1881inline double Sub::upperBound() const
1882{
1883 if (master_->optSense()->min())
1884 return master_->primalBound();
1885 else
1886 return dualBound_;
1887}
1888
1889inline bool Sub::betterDual(double x) const
1890{
1891 if (master_->optSense()->max())
1892 return x < dualBound_ ? true : false;
1893 else
1894 return x > dualBound_ ? true : false;
1895}
1896
1897inline bool Sub::boundCrash() const
1898{
1900}
1901
1902inline void Sub::removeCon(int i)
1903{
1905}
1906
1907inline void Sub::lBound(int i, double l)
1908{
1909 (*lBound_)[i] = l;
1910 if (lp_)
1911 lp_->changeLBound(i, l);
1912}
1913
1914inline void Sub::uBound(int i, double u)
1915{
1916 (*uBound_)[i] = u;
1917 if (lp_)
1918 lp_->changeUBound(i, u);
1919}
1920
1921}
Declaration of stopwatch classes.
Base class of all other classes of ABACUS.
Definition abacusroot.h:68
Implements the sets of active constraints and variables which are associated with each subproblem.
Definition active.h:62
Implements a branching rule for modifying the lower and the upper bound of a variable.
Abstract base class for all branching rules.
Definition branchrule.h:59
Representation of variables in column format.
Definition column.h:47
Forms the virtual base class for all possible constraints given in pool format.
Definition constraint.h:56
Cut buffers.
Definition cutbuffer.h:52
Status of fixed and set variables.
Definition fsvarstat.h:46
STATUS
The enumeration defining the different statuses of variables from the point of view of fixing and set...
Definition fsvarstat.h:50
METHOD
The solution method for the linear program.
Definition lp.h:93
status of variables.
Definition lpvarstat.h:50
LP solutions.
Definition lpsolution.h:64
The linear program of a subproblem.
Definition lpsub.h:61
virtual void changeUBound(int i, double newUb) override
Sets the upper bound of variable i to newUb.
virtual void changeLBound(int i, double newLb) override
Sets the lower bound of variable i to newLb.
The master of the optimization.
Definition master.h:69
int nStrongBranchingIterations() const
The number of simplex iterations that are performed when testing candidates for branching variables w...
Definition master.h:554
bool primalViolated(double x) const
Can be used to compare a value with the one of the best known primal bound.
double primalBound() const
Returns the value of the primal bound.
Definition master.h:278
const OptSense * optSense() const
Returns a pointer to the object holding the optimization sense of the problem.
Definition master.h:442
Maintains open subproblems.
Definition opensub.h:49
bool min() const
Returns true If it is minimization problem,, false otherwise.
Definition optsense.h:84
bool max() const
Returns true if it is maximization problem,, false otherwise.
Definition optsense.h:90
Base class for constraint/variabe pools.
Definition pool.h:62
Stores constraints and variables.
Definition poolslot.h:77
Status of slack variables.
Definition slackstat.h:47
The subproblem.
Definition sub.h:68
const Sub & operator=(const Sub &rhs)
virtual void setByLogImp(ArrayBuffer< int > &variable, ArrayBuffer< FSVarStat * > &status)
The default implementation of setByLogImp() does nothing.
Definition sub.h:845
virtual int makeFeasible()
The default implementation of makeFeasible()does nothing.
Definition sub.h:822
virtual int selectBranchingVariable(int &variable)
Chooses a branching variable.
double uBound(int i) const
Can be used to access the upper of an active variable of the subproblem.
Definition sub.h:266
ArrayBuffer< int > * removeVarBuffer_
The buffer of the variables which are removed at the beginning of the next iteration.
Definition sub.h:1506
int maxVar() const
Returns the maximum number of variables which can be handled without reallocation.
Definition sub.h:1848
Sub(const Sub &rhs)
void dualBound(double x)
Sets the dual bound of the subproblem.
virtual void removeCon(int i)
Adds a single constraint to the set of constraints which are removed from the active set at the begin...
Definition sub.h:1902
bool infeasible()
Returns true if the subproblem does not contain a feasible solution, false otherwise.
LP::METHOD lpMethod_
The solution method for the next linear program.
Definition sub.h:1497
virtual bool tailingOff()
Called when a tailing off effect according to the parameters TailOffPercent and TailOffNLps is observ...
Definition sub.h:1014
int lastIterConAdd_
The last iteration in which constraints have been added.
Definition sub.h:1482
virtual int _pricing(bool &newValues, bool doFixSet=true)
If doFixSet is true, then we try to fix and set variables, if all inactive variables price out correc...
int infeasVar_
The number of an infeasible variable.
Definition sub.h:1524
virtual void addVarsToLp(ArrayBuffer< PoolSlot< Variable, Constraint > * > &newVars, ArrayBuffer< FSVarStat * > *localStatus=nullptr)
Adds the variables stored in the pool slots of newVars to the linear program. localStatus can specify...
virtual void fathom(bool reoptimize)
Fathoms a node and recursively tries to fathom its father.
virtual int separate()
Must be redefined in derived classes for the generation of cutting planes.
Array< double > * uBound_
A pointer to an array with the local upper bounds of the active variables.
Definition sub.h:1467
virtual void initializeCons(int maxCon)
Initializes the active constraint set.
virtual int selectBestBranchingSample(int nSamples, ArrayBuffer< BranchRule * > **samples)
Evaluates branching samples.
virtual void conRealloc(int newSize)
Reallocates memory that at most newSize constraints can be handled in the subproblem.
virtual int fixing(bool &newValues, bool saveCand=false)
Tries to fix variables by reduced cost criteria and logical implications.
double yVal(int i) const
Returns the value of the i-th dual variable in the last solved linear program.
Definition sub.h:309
BranchRule * branchRule_
The branching rule for the subproblem.
Definition sub.h:1488
virtual void nonBindingConEliminate(ArrayBuffer< int > &remove)
Retrieves the dynamic constraints with slack exceeding the value given by the parameter ConElimEps.
virtual ~Sub()
The destructor only deletes the sons of the node.
virtual int selectBranchingVariableCandidates(ArrayBuffer< int > &candidates)
Selects candidates for branching variables.
int closeHalf(ArrayBuffer< int > &branchVar, VarType::TYPE branchVarType)
Searches searches several possible branching variable of type branchVarType, with fraction as close t...
virtual int _fixByLogImp(bool &newValues)
Returns 1, if a contradiction has been found, 0 otherwise.
virtual bool primalSeparation()
Controls if during the cutting plane phase a (primal) separation step or a pricing step (dual separat...
virtual int fixByRedCost(bool &newValues, bool saveCand)
Tries to fix variables according to the reduced cost criterion.
virtual int fixAndSet(bool &newValues)
Tries to fix and set variables both by logical implications and reduced cost criteria.
virtual void deactivate()
Can be used as entrance point for problem specific deactivations after the subproblem optimization.
Definition sub.h:563
bool boundCrash() const
Returns true if the dual bound is worse than the best known primal bound, false otherwise.
Definition sub.h:1897
virtual PHASE cutting()
Iteratively solves the LP-relaxation, generates constraints and/or variables.
virtual void fixByLogImp(ArrayBuffer< int > &variables, ArrayBuffer< FSVarStat * > &status)
Should collect the numbers of the variables to be fixed in variable and the respective statuses in st...
Definition sub.h:1056
virtual double rankBranchingRule(BranchRule *branchRule)
Computes the rank of a branching rule.
Definition sub.h:1868
virtual void conEliminate(ArrayBuffer< int > &remove)
Can be used as an entry point for application specific elimination of constraints.
virtual void activateVars(ArrayBuffer< PoolSlot< Variable, Constraint > * > &newVars)
Adds the variables stored in the pool slots of newVars to the set of active variables,...
int level_
The level of the subproblem in the enumeration tree.
Definition sub.h:1746
BranchRule * branchRule() const
Returns a pointer to the branching rule of the subproblem.
Definition sub.h:355
bool activated_
The variable is true if the function activate() has been called from the function _activate().
Definition sub.h:1790
virtual PHASE _activate()
Allocates and initializes memory of the subproblem at the beginning of the optimization.
virtual int _improve(double &primalValue)
Tries to find a better feasible solution.
virtual int set(int i, FSVarStat::STATUS newStat, double value, bool &newValue)
Sets a variable.
virtual void rankBranchingSample(ArrayBuffer< BranchRule * > &sample, Array< double > &rank)
Computes for each branching rule of a branching sample a rank with the function rankBranchingRule().
STATUS
A subproblem can have different statuses.
Definition sub.h:79
@ Unprocessed
The status after generation, but before optimization of the subproblem.
Definition sub.h:80
@ Processed
The subproblem is completely processed but could not be fathomed.
Definition sub.h:84
@ ActiveSub
The subproblem is currently processed.
Definition sub.h:81
bool relativeReserve() const
Definition sub.h:352
Constraint * constraint(int i) const
Returns a pointer to the i-th active constraint.
Definition sub.h:1858
virtual int improve(double &primalValue)
Can be redefined in order to implement primal heuristics for finding feasible solutions.
virtual Sub * generateSon(BranchRule *rule)=0
Returns a pointer to an object of a problem specific subproblem, which is generated from the current ...
STATUS status_
The status of the subproblem.
Definition sub.h:1752
virtual int compareBranchingSampleRanks(Array< double > &rank1, Array< double > &rank2)
Compares the ranks of two branching samples.
virtual void updateBoundInLp(int i)
Adapts the bound of a fixed or set variable i also in the linear program.
virtual void varEliminate(ArrayBuffer< int > &remove)
Entry point for application specific variable elimination.
virtual int branchingOnVariable(ArrayBuffer< BranchRule * > &rules)
Generates branching rules for two new subproblems by selecting a branching variable with the function...
bool _atUpperBound(int i)
Returns true iff the current value of variable i in the primal lp is equal to its upper bound.
bool betterDual(double x) const
Returns true if x is better than the best known dual bound of the subproblem, false otherwise.
Definition sub.h:1889
bool forceExactSolver() const
Returns whether using the exact solver is forced.
Definition sub.h:147
virtual bool exceptionBranch()
Can be used to specify a problem specific criteria for enforcing a branching step.
Definition sub.h:1424
virtual PHASE branching()
Performs branching.
double dualBound_
The dual bound of the subproblem.
Definition sub.h:1476
virtual int set(int i, FSVarStat::STATUS newStat, bool &newValue)
Sets a variable.
virtual void _deactivate()
Deallocates the memory which is not required after the optimization of the subproblem.
int addVarBufferSpace() const
Can be used to determine the maximal number of the variables which still can be added to the variable...
Definition sub.h:1833
bool objAllInteger() const
Tests if all active variables and objective function coefficients are integer.
virtual int _removeCons(ArrayBuffer< int > &remove)
Removes the constraints with numbers remove from the set of active constraints.
const Master * master() const
Returns the const master of the optimization.
Definition sub.h:323
bool allBranchOnSetVars_
If true, then the branching rule of the subproblem and of all ancestor on the path to the root node a...
Definition sub.h:1494
ArrayBuffer< int > * removeConBuffer_
The buffer of the constraints which are removed at the beginning of the next iteration.
Definition sub.h:1509
void redCostVarEliminate(ArrayBuffer< int > &remove)
Retrieves all variables with "wrong" reduced costs.
int id() const
Returns the identity number of the subproblem.
Definition sub.h:153
double lBound(int i) const
Can be used to access the lower of an active variable of the subproblem.
Definition sub.h:245
LpSub * lp_
A pointer to the corresponding linear program.
Definition sub.h:1448
double * bInvRow_
A row of the basis inverse associated with the infeasible variable infeasVar_ or slack variable infea...
Definition sub.h:1518
int nIter_
The number of iterations in the cutting plane phase.
Definition sub.h:1479
int findNonFixedSet(ArrayBuffer< int > &branchVar, VarType::TYPE branchVarType)
Selects the first variables that are neither fixed nor set.
virtual int initializeLp()
Initializes the linear program.
virtual void selectCons()
Is called before constraint are selected from the constraint buffer.
Definition sub.h:1031
Variable * variable(int i) const
Returns a pointer to the i-th active variable.
Definition sub.h:1863
int lastIterVarAdd_
The last iteration in which variables have been added.
Definition sub.h:1485
CutBuffer< Variable, Constraint > * addVarBuffer_
The buffer of the newly generated variables.
Definition sub.h:1500
virtual int pricing()
Should generate inactive variables which do not price out correctly.
Definition sub.h:934
virtual int optimize()
Performs the optimization of the subproblem.
Array< LPVARSTAT * > * lpVarStat_
A pointer to an array storing the status of each active variable in the linear program.
Definition sub.h:1461
virtual void reoptimize()
Repeats the optimization of an already optimized subproblem.
int nOpt_
The number of optimizations of the subproblem.
Definition sub.h:1761
int findNonFixedSet(int &branchVar, VarType::TYPE branchVarType)
Selects the first variable that is neither fixed nor set.
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.
bool relativeReserve_
If this member is true then the space reserve of the following three members varReserve_,...
Definition sub.h:1771
virtual LP::METHOD chooseLpMethod(int nVarRemoved, int nConRemoved, int nVarAdded, int nConAdded)
Controls the method used to solve a linear programming relaxation.
TailOff * tailOff_
A pointer to the tailing off manager.
Definition sub.h:1473
FSVarStat * fsVarStat(int i) const
Returns a pointer to the status of fixing/setting of the i-th variable.
Definition sub.h:291
virtual void _selectCons(ArrayBuffer< PoolSlot< Constraint, Variable > * > &newCons)
Selects the master_->maxConAdd() best constraints from the buffered constraints and stores them in ne...
int id_
The number of the subproblem.
Definition sub.h:1749
double dualBound() const
Returns a bound which is "better" than the optimal solution of the subproblem w.r....
Definition sub.h:181
virtual PHASE fathoming()
Fathoms the node, and if certain conditions are satisfied, also its ancestor.
virtual void initializeVars(int maxVar)
Initializes the active variable set.
virtual int _setByLogImp(bool &newValues)
Tries to set variables according to logical implications of already set and fixed variables.
virtual void getBase()
Updates the status of the variables and the slack variables.
virtual bool exceptionFathom()
Can be used to specify a problem specific fathoming criterium that is checked before the separation o...
Definition sub.h:1415
virtual int _conEliminate()
Returns the number of eliminated constraints.
bool forceExactSolver_
Indicates whether to force the use of an exact solver to prepare branching etc.
Definition sub.h:1805
virtual int addCons(ArrayBuffer< PoolSlot< Constraint, Variable > * > &newCons)
Adds constraints to the active constraints and the linear program.
virtual bool pausing()
Sometimes it is appropriate to put a subproblem back into the list of open subproblems.
Definition sub.h:968
virtual int _makeFeasible()
Is called if the LP is infeasible and adds inactive variables, which can make the LP feasible again,...
int addConBufferSpace() const
Can be used to determine the maximal number of the constraints which still can be added to the constr...
Definition sub.h:1828
bool ancestor(const Sub *sub) const
Returns true if this subproblem is an ancestor of the subproblem sub, false otherwise.
ArrayBuffer< Sub * > * sons_
The sons of the node in the branch-and-cut tree.
Definition sub.h:1755
bool integerFeasible()
Can be used to check if the solution of the LP-relaxation is primally feasible if integrality is sufi...
bool genNonLiftCons_
If true, then the management of non-liftable constraints is performed.
Definition sub.h:1527
double upperBound() const
Returns an upper bound on the optimal solution of the subproblem.
Definition sub.h:1881
virtual void selectVars()
Is called before variables are selected from the variable buffer.
Definition sub.h:1024
Sub(Master *master, double conRes, double varRes, double nnzRes, bool relativeRes=true, ArrayBuffer< PoolSlot< Constraint, Variable > * > *constraints=nullptr, ArrayBuffer< PoolSlot< Variable, Constraint > * > *variables=nullptr)
Creates the root node of the enumeration tree.
LPVARSTAT * lpVarStat(int i) const
Returns a pointer to the status of the variable i in the last solved linear program.
Definition sub.h:297
double nnzReserve() const
Returns the additional space for nonzero elements of the constraint matrix when it is passed to the L...
Definition sub.h:346
virtual int initMakeFeas(ArrayBuffer< InfeasCon * > &infeasCon, ArrayBuffer< Variable * > &newVars, Pool< Variable, Constraint > **pool)
The default implementation of the virtual initMakeFeas() does nothing.
Definition sub.h:797
virtual void newDormantRound()
Increments the counter for the number of rounds the subproblem is dormant.
Definition sub.h:1611
PHASE
The optimization of the subproblem can be in one of the following phases.
Definition sub.h:89
@ Done
The optimization is done.
Definition sub.h:90
@ Branching
We try to generate further subproblems as sons of this subproblem.
Definition sub.h:93
virtual int fix(int i, FSVarStat *newStat, bool &newValue)
Fixes a variable.
virtual int generateBranchRules(ArrayBuffer< BranchRule * > &rules)
Tries to find rules for splitting the current subproblem in further subproblems.
Definition sub.h:575
ogdf::StopwatchCPU localTimer_
Definition sub.h:1802
Active< Variable, Constraint > * actVar_
The active variables of the subproblem.
Definition sub.h:1442
virtual int addBranchingConstraint(PoolSlot< Constraint, Variable > *slot)
Adds a branching constraint to the constraint buffer.
Definition sub.h:1823
Array< FSVarStat * > * fsVarStat_
A pointer to an array storing the status of fixing and setting of the active variables.
Definition sub.h:1458
STATUS status() const
Returns the status of the subproblem optimization.
Definition sub.h:156
Sub * father_
A pointer to the father in the branch-and-cut tree.
Definition sub.h:1445
double * xVal_
The last LP-solution.
Definition sub.h:1512
virtual int _varEliminate()
Returns the number of eliminated variables.
int nVar() const
Returns the number of active variables.
Definition sub.h:1838
virtual int _separate()
Returns the number of generated cutting planes.
CutBuffer< Constraint, Variable > * addConBuffer_
The buffer of the newly generated constraints.
Definition sub.h:1503
virtual int solveLp()
Solves the LP-relaxation of the subproblem.
int closeHalfExpensive(int &branchVar, VarType::TYPE branchVarType)
Selects a single branching variable of type branchVarType, with fractional part close to and high ab...
int nCon() const
Returns the number of active constraints.
Definition sub.h:1843
void ignoreInTailingOff()
Can be used to control better the tailing-off effect.
virtual void removeCons(ArrayBuffer< int > &remove)
Adds constraints to the buffer of the removed constraints.
virtual int variablePoolSeparation(int ranking=0, Pool< Variable, Constraint > *pool=nullptr, double minViolation=0.001)
Tries to generate inactive variables from a pool.
int closeHalf(int &branchVar, VarType::TYPE branchVarType)
Searches a branching variable of type branchVarType, with fraction as close to as possible.
int nDormantRounds() const
Definition sub.h:408
double lowerBound() const
Returns a lower bound on the optimal solution of the subproblem.
Definition sub.h:1873
Active< Variable, Constraint > * actVar() const
Returns a pointer to the currently active variables.
Definition sub.h:216
virtual int constraintPoolSeparation(int ranking=0, Pool< Constraint, Variable > *pool=nullptr, double minViolation=0.001)
Tries to generate inactive constraints from a pool.
int infeasCon_
The number of an infeasible constraint.
Definition sub.h:1521
virtual int _removeVars(ArrayBuffer< int > &remove)
Removes the variables with numbers remove from the set of active variables.
Array< double > * lBound_
A pointer to an array with the local lower bound of the active variables.
Definition sub.h:1464
Sub(Master *master, Sub *father, BranchRule *branchRule)
Creates a non-root node of the enumeration tree.
double lpRankBranchingRule(BranchRule *branchRule, int iterLimit=-1)
Computes the rank of a branching rule by modifying the linear programming relaxation of the subproble...
LP::METHOD lastLP_
The method that was used to solve the last LP.
Definition sub.h:1800
virtual int set(int i, FSVarStat *newStat, bool &newValue)
Sets a variable.
virtual double fixSetNewBound(int i)
Returns the value which the upper and lower bounds of a variable should take after it is fixed or set...
Array< SlackStat * > * slackStat_
A pointer to an array storing the statuses of the slack variables of the last solved linear program.
Definition sub.h:1470
virtual int _initMakeFeas()
Tries to add variables to restore infeasibilities detected at initialization time.
virtual int prepareBranching(bool &lastIteration)
Is called before a branching step to remove constraints.
virtual void varRealloc(int newSize)
Reallocates memory that at most newSize variables can be handled in the subproblem.
virtual void _selectVars(ArrayBuffer< PoolSlot< Variable, Constraint > * > &newVars)
Selects the master_->maxVarAdd() best variables from the buffered variables.
int maxIterations_
The maximum number of iterations in the cutting plane phase.
Definition sub.h:1758
virtual bool goodCol(Column &col, Array< double > &row, double x, double lb, double ub)
virtual bool solveApproxNow()
The default implementation always returns false.
Definition sub.h:1432
virtual int setByRedCost()
Tries to set variables according to the reduced cost criterion.
virtual LpSub * generateLp()
Instantiates an LP for the solution of the LP-relaxation in this subproblem.
Master * master_
A pointer to the corresponding master of the optimization.
Definition sub.h:1436
virtual void basicConEliminate(ArrayBuffer< int > &remove)
Retrieves all dynamic constraints having basic slack variable.
Active< Constraint, Variable > * actCon_
The active constraints of the subproblem.
Definition sub.h:1439
bool _atLowerBound(int i)
Returns true iff the current value of variable i in the primal lp is equal to its lower bound.
int level() const
Returns the level of the subproblem in the branch-and-bound tree.
Definition sub.h:150
double varReserve_
The additional space for variables.
Definition sub.h:1774
double nnzReserve_
The additional space for nonzeros.
Definition sub.h:1780
virtual void fathomTheSubTree()
Fathoms all nodes in the subtree rooted at this subproblem.
double * yVal_
The dual variables of the last linear program.
Definition sub.h:1515
Active< Constraint, Variable > * actCon() const
Returns a pointer to the currently active constraints.
Definition sub.h:213
virtual void activate()
Can be used as an entrance point for problem specific activations.
Definition sub.h:555
double conReserve_
The additional space for constraints.
Definition sub.h:1777
virtual bool fixAndSetTime()
Controls if variables should be fixed or set when all variables price out correctly.
Definition sub.h:1138
void removeVar(int i)
Remove variable i from the set of active variables.
Definition sub.h:343
virtual double guarantee() const
May not be called if the lower bound is 0 and upper bound not equal to 0.
void removeVars(ArrayBuffer< int > &remove)
Removes the variables in remove from the set of active variables.
int closeHalfExpensive(ArrayBuffer< int > &variables, VarType::TYPE branchVarType)
Selects several candidates for branching variables of type branchVarType.
virtual bool removeNonLiftableCons()
virtual int addVars(ArrayBuffer< PoolSlot< Variable, Constraint > * > &newVars)
Adds both the variables in newVars to the set of active variables and to the linear program of the su...
void maxIterations(int max)
Sets the maximal number of iterations in the cutting plane phase.
double xVal(int i) const
Returns the value of the i-th variable in the last solved linear program.
Definition sub.h:303
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.
int nDormantRounds_
The number of subproblem optimizations the subproblem has already the status Dormant.
Definition sub.h:1783
virtual int setting(bool &newValues)
Tries to set variables by reduced cost criteria and logical implications like fixing().
bool ignoreInTailingOff_
If this flag is set to true then the next LP-solution is ignored in the tailing-off control.
Definition sub.h:1797
virtual void infeasibleSub()
Should be called if a subproblem turns out to be infeasible.
virtual bool feasible()=0
Must check the feasibility of a solution of the LP-relaxation.
SlackStat * slackStat(int i) const
Returns a pointer to the status of the slack variable i in the last solved linear program.
Definition sub.h:228
Master * master()
Returns the master of the optimization.
Definition sub.h:320
int maxCon() const
Returns the maximum number of constraints which can be handled without reallocation.
Definition sub.h:1853
virtual bool guaranteed() const
virtual double dualRound(double x)
LpSub * lp() const
Returns a pointer to the linear program of the subproblem.
Definition sub.h:201
const Sub * father() const
Returns a pointer to the father of the subproblem in the branch-and-bound tree.
Definition sub.h:198
Tailing off manager.
Definition tailoff.h:57
TYPE
The enumeration with the different variable types.
Definition vartype.h:47
Forms the virtual base class for all possible variables given in pool format.
Definition variable.h:59
An array that keeps track of the number of inserted elements; also usable as an efficient stack.
Definition ArrayBuffer.h:56
void push(E e)
Puts a new element in the buffer.
The parameterized class Array implements dynamic arrays of type E.
Definition Array.h:214
Implements a stopwatch measuring CPU time.
Definition Stopwatch.h:154
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition config.h:101
constraint.
cutbuffer.
status of fixed and set variables.
linear program.
linear program of a subproblem.
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
variable.
vartype.