Stores an intermediate tableaux for the dual simplex method, and contains all of the core machinery for using the dual simplex method. More...
#include <enumerate/treelp.h>
Public Member Functions | |
| LPData () | |
| Constructs a new tableaux. More... | |
| LPData (LPData &&src) noexcept | |
| Moves the contents of the given tableaux into this new tableaux. More... | |
| ~LPData () | |
| Destroys this tableaux. More... | |
| LPData & | operator= (LPData &&src) noexcept |
| Moves the contents of the given tableaux into this tableaux. More... | |
| void | swap (LPData &other) noexcept |
| Swaps the contents of this and the given tableaux. More... | |
| void | reserve (const LPInitialTableaux< LPConstraint > &origTableaux) |
| Reserves enough memory for this tableaux to work with. More... | |
| void | initStart () |
| Initialises this tableaux by beginning at the original starting tableaux and working our way to any feasible basis. More... | |
| void | initClone (const LPData &parent) |
| Initialises this tableaux to be a clone of the given tableaux. More... | |
| unsigned | columns () const |
| Returns the number of columns in this tableaux. More... | |
| unsigned | coordinateColumns () const |
| Returns the number of columns in this tableaux that correspond to normal coordinates or angle structure coordinates. More... | |
| bool | isFeasible () const |
| Returns whether or not this system is feasible. More... | |
| bool | isActive (unsigned pos) const |
| Determines whether the given variable is currently active. More... | |
| int | sign (unsigned pos) const |
| Returns the sign of the given variable under the current basis. More... | |
| void | constrainZero (unsigned pos) |
| Constrains this system further by setting the given variable to zero and deactivating it. More... | |
| void | constrainPositive (unsigned pos) |
| Constrains this system further by constraining the given variable to be strictly positive. More... | |
| void | constrainOct (unsigned quad1, unsigned quad2) |
| Declares that two quadrilateral coordinates within a tetrahedron are to be combined into a single octagon coordinate, for use with almost normal surfaces, and constrains the system accordingly. More... | |
| void | dump (std::ostream &out) const |
| Deprecated routine that writes details of this tableaux to the given output stream. More... | |
| template<class RayClass > | |
| RayClass | extractSolution (const char *type) const |
| Extracts the values of the individual variables from the current basis, with some modifications (as described below). More... | |
| void | writeTextShort (std::ostream &out) const |
| Writes a short text representation of this object to the given output stream. More... | |
| void | writeTextLong (std::ostream &out) const |
| Writes a detailed text representation of this object to the given output stream. More... | |
| LPData (const LPData &)=delete | |
| LPData & | operator= (const LPData &)=delete |
| std::string | str () const |
| Returns a short text representation of this object. More... | |
| std::string | utf8 () const |
| Returns a short text representation of this object using unicode characters. More... | |
| std::string | detail () const |
| Returns a detailed text representation of this object. More... | |
Detailed Description
class regina::LPData< LPConstraint, IntType >
Stores an intermediate tableaux for the dual simplex method, and contains all of the core machinery for using the dual simplex method.
This class forms part of the tree traversal algorithms for enumerating and locating normal surfaces, as described in "A tree traversal algorithm for decision problems in knot theory and 3-manifold topology", Burton and Ozlen, Algorithmica 65:4 (2013), pp. 772-801, and "A fast branching algorithm for unknot recognition with experimental polynomial-time behaviour", Burton and Ozlen, arXiv:1211.1079. It is also used for locating a single strict angle structure, and for enumerating all taut angle structures.
This class is designed to represent a state partway through the tree traversal algorithm, where the tableaux has been altered to constrain some variables:
- Some variables have been "deactivated". This means we fix them to zero permanently, and pretend that the corresponding columns do not exist in the matrix. As a result, the rank of the matrix may smaller than it was when we began the tree traversal.
- Some variables have been constrained to be positive; as described in Burton and Ozlen, it is safe to do this using the non-strict inequality x_i >= 1 (instead of the strict inequality x_i > 0, which is more difficult to enforce). We enforce this constraing using a change of variable: we replace the variable x_i with (x_i - 1), which is then constrained to be non-negative as usual. The new variable (x_i - 1) uses the same column in the tableaux (we perform the actual change of variable by editing the tableaux itself using column operations). Be warned: as a result, when we arrive at a final solution and collect the values of the variables, we must remember to increment the values of any such variables by one.
We do not store the full tableaux (which is dense and slow to work with). Instead we store the matrix of row operations that were applied to the original starting tableaux (in the notation of Burton and Ozlen, we store the matrix M_beta^{-1}, where M is the original matrix stored in the class LPInitialTableaux, and beta is the current basis).
If the system is infeasible (because the constraints on variables as described above are too severe), then the contents of the internal data members are undefined (other than the data member feasible_, which is guaranteed to be false). This is because the code is optimised to abort any operation as soon as infeasibility is detected, which may leave the data members in a broken state. If you are not sure, you should always call isFeasible() before performing any other query or operation on this tableaux.
This class is designed to be used in a backtracking search, which means the API is cumbersome but we can quickly rewrite and copy data. The rules are as follows:
- Before using an LPData object, you must reserve the necessary memory by calling reserve() and passing the original starting tableaux.
- After this, you can reset the data by calling one of the initialisation routines initStart() or initClone(), and you can call these initialisation routines as often as you like.
Like LPInitialTableaux, this class can enforce additional linear constraints (such as positive Euler characteristic) through the template parameter LPConstraint. If there are no such constraints, simply use the template parameter LPConstraintNone.
In the context of normal surfaces (not angle structures): Although the underlying coordinate system is based on quadrilaterals and (optionally) triangles, this class has elementary support for octagons also, as seen in almost normal surface theory. For the purposes of this class, an octagon is represented as a pair of quadrilaterals of different types in the same tetrahedron: these meet the boundary of the tetrahedron in the same arcs as a single octagon, and therefore interact with the matching equations in the same way.
To declare that you will be using octagons in some tetrahedron, you must call constrainOct(quad1, quad2), where quad1 and quad2 are the two corresponding quadrilateral columns. This will have the following effects, all of which may alter the tableaux:
- There will be some changes of variable. One of the two variables x_i will be replaced with (x_i - 1), forcing the number of octagons to be positive. The other variable x_j will be replaced with (x_j - x_i), which will be set to zero and deactivated. There is no guarantee as to which of the two variables quad1 and quad2 will be kept and which will be deactivated: this will depend on the layout of the tableaux when constrainOct() is called.
- If you are imposing additional constraints through the LPConstraint template parameter, the corresponding linear constraint functions may change their values (since the coefficients they use for octagon types need not be related to the coefficients for the two corresponding quadrilateral columns). Any such changes, if necessary, are encoded by the constant LPConstraint::octAdjustment.
This class has been optimised to ensure that you only have one octagon type declared at any given time (which is consistent with the constraints of almost normal surface theory).
All tableaux elements are of the integer class IntType, which is supplied as a template argument. This same integer class will be used as a template argument for LPConstraint.
This class implements C++ move semantics and adheres to the C++ Swappable requirement. However, due to the unusual create-reserve-initialise procedure, it does not support copying (either by copy construction or copy assignment). Because of the move semantics, this class avoids deep copies, even when passing or returning objects by value.
- Precondition
- The template parameter LPConstraint must be one of the subclasses of LPConstraintBase. See the LPConstraintBase class notes for further details.
- The default constructor for the template class IntType must intialise each new integer to zero. The classes Integer and NativeInteger, for instance, have this property.
- Headers
- Parts of this template class are implemented in a separate header (treelp-impl.h), which is not included automatically by this file. Most end users should not need this extra header, since Regina's calculation engine already includes explicit instantiations for common combinations of template arguments.
- Python
- This is a heavily templated class; nevertheless, many variants are now made available to Python users. Each class name is of the form LPData_LPConstraint, where the suffix LPConstraint is an abbreviated version of the LPConstraint template parameter; this suffix is omitted entirely for the common case LPConstraintNone. An example of such a Python class name is
LPData_EulerPositive. You are encouraged to look through the Regina namespace to see which constraint classes are supported under Python. In all cases, the IntType parameter is taken to be regina::Integer.
- Warning
- The API for this class has not yet been finalised. This means that the class interface may change in new versions of Regina, without maintaining backward compatibility. If you use this class directly in your own code, please watch the detailed changelogs upon new releases to see if you need to make changes to your code.
Constructor & Destructor Documentation
◆ LPData() [1/2]
|
inline |
Constructs a new tableaux.
You must call reserve() before doing anything else with this tableaux.
◆ LPData() [2/2]
|
inlinenoexcept |
Moves the contents of the given tableaux into this new tableaux.
This is a fast (constant time) operation.
If the given tableaux is uninitialised, then this new tableaux will be uninitialised also.
The tableaux that is passed (src) will no longer be usable.
- Parameters
-
src the tableaux to move.
◆ ~LPData()
|
inline |
Destroys this tableaux.
This is safe even if reserve() was never called.
Member Function Documentation
◆ columns()
|
inline |
Returns the number of columns in this tableaux.
Note that, if we are imposing extra constraints through the template parameter LPConstraint, then there will be extra variables to enforce these, and so the number of columns will be larger than in the original matching equation matrix.
- Returns
- the number of columns.
◆ constrainOct()
| void regina::LPData< LPConstraint, IntType >::constrainOct | ( | unsigned | quad1, |
| unsigned | quad2 | ||
| ) |
Declares that two quadrilateral coordinates within a tetrahedron are to be combined into a single octagon coordinate, for use with almost normal surfaces, and constrains the system accordingly.
This constrains the system in several ways, as discussed in detail in the LPData class notes. In theory, we set the two quadrilateral coordinates to be equal, and also insist that the number of octagons be strictly positive. In practice, we do this through several changes of variable; see the LPData class notes for a detailed discussion of precisely how the variables and tableaux will change.
This routine will work even if one of the given quadrilateral variables has already been deactivated, but in this case the routine will immediately set the system to infeasible and return.
This routine is not used with angle structure coordinates.
- Precondition
- This is the first time constrainOct() has been called on this tableaux. This is because this class can only handle one octagon type in the entire system.
- Variables quad1 and quad2 represent different quadrilateral coordinates in the same tetrahedron of the underlying triangulation.
- Warning
- If you have previously called constrainPositive() or constrainOct() on one of the given variables, then these prior routines will have performed a change of variable. Any new call to constrainOct() involving this same variable will constrain the new variable, not the original, and so might not have the intended effect.
- Parameters
-
quad1 one of the two quadrilateral types that we combine to form the new octagon type. This should be a column index with respect to this tableaux (i.e., it must take into account any permutation of columns from the original matching equations). quad2 the other of the two quadrilateral types that we combine to form the new octagon type. Again this should be a column index with respect to this tableaux.
◆ constrainPositive()
| void regina::LPData< LPConstraint, IntType >::constrainPositive | ( | unsigned | pos | ) |
Constrains this system further by constraining the given variable to be strictly positive.
We do this using a change of variable that effectively replaces x_pos with the new variable x'_pos = x_pos - 1 (which we simply constrain to be non-negative as usual). See the LPData class notes for details.
This routine will work even if the given variable has already been deactivated, but in this case the routine will immediately set the system to infeasible and return.
- Warning
- If you have previously called constrainPositive() or constrainOct() on this variable, then these prior routines will have performed a change of variable. Any new call to constrainPositive() on this same variable will constrain the new variable, not the original, and so might not have the intended effect.
- Parameters
-
pos the index of the variable that is to be constrained as positive. This must be between 0 and origTableaux_->columns()-1 inclusive. The index should be with respect to this tableaux (i.e., it must take into account any permutation of columns from the original matching equations).
◆ constrainZero()
| void regina::LPData< LPConstraint, IntType >::constrainZero | ( | unsigned | pos | ) |
Constrains this system further by setting the given variable to zero and deactivating it.
See the LPData class notes for details.
This routine will work even if the given variable has already been deactivated (and it will do nothing in this case).
- Warning
- If you have previously called constrainPositive() or constrainOct() on this variable, then these prior routines will have performed a change of variable. Any new call to constraintZero() on this same variable will constraint the new variable, not the original, and so might not have the intended effect.
- Parameters
-
pos the index of the variable that is to be set to zero. This must be between 0 and origTableaux_->columns()-1 inclusive. The index should be with respect to this tableaux (i.e., it must take into account any permutation of columns from the original matching equations).
◆ coordinateColumns()
|
inline |
Returns the number of columns in this tableaux that correspond to normal coordinates or angle structure coordinates.
This is precisely the number of columns in the original matrix of matching equations.
- Returns
- the number of normal or angle structure coordinate columns.
◆ detail()
|
inherited |
Returns a detailed text representation of this object.
This text may span many lines, and should provide the user with all the information they could want. It should be human-readable, should not contain extremely long lines (which cause problems for users reading the output in a terminal), and should end with a final newline. There are no restrictions on the underlying character set.
- Returns
- a detailed text representation of this object.
◆ dump()
| void regina::LPData< LPConstraint, IntType >::dump | ( | std::ostream & | out | ) | const |
Deprecated routine that writes details of this tableaux to the given output stream.
The output is "rough" and wasteful, and is intended for debugging purposes only.
- Deprecated:
- This has been replaced by writeTextLong() (which uses a slightly tighter output format), for compatibility with Regina's usual text output facilities.
- Python
- Not present, but you can call detail() instead.
- Parameters
-
out the output stream to write to.
◆ extractSolution()
| RayClass regina::LPData< LPConstraint, IntType >::extractSolution | ( | const char * | type | ) | const |
Extracts the values of the individual variables from the current basis, with some modifications (as described below).
The values of the variables will be returned in vector form.
The modifications are as follows:
- We extract variables that correspond to the original matching equations obtained from the underlying triangulation, not the current tableaux and not even the original starting tableaux stored in origTableaux_. In other words, when we fill the resulting vector, we undo the column permutation described by LPInitialTableaux::columnPerm(), and we undo any changes of variable that were caused by calls to constrainPositive() and/or constrainOct().
- To ensure that the variables are all integers, we scale the resulting vector by the smallest positive rational multiple for which all elements of the vector are integers.
This routine is not used as an internal part of the tree traversal algorithm; instead it is offered as a helper routine for reconstructing the normal surfaces or angle structures that result.
- Precondition
- No individual coordinate column has had more than one call to either of constrainPositive() or constrainOct() (otherwise the coordinate will not be correctly reconstructed). Any additional columns arising from LPConstraint are exempt from this requirement.
- The precision of integers in RayClass is at least as large as the precision of IntType (as used by LPData).
- Template Parameters
-
RayClass the class used to hold the output vector. This should be Vector<T> where T is one of Regina's own integer types (Integer, LargeInteger or NativeInteger). In particular, this ensures that all elements of a newly-created output vector will be automatically initialised to zero.
- Python
- The type vector should be passed as a Python list of integers (for example, in the enumeration of normal surfaces, there would be one integer per tetrahedron, each equal to 0, 1, 2 or 3). The RayClass argument is taken to be Vector<Integer>.
- Parameters
-
type the type vector corresponding to the current state of this tableaux, indicating which variables were previously fixed as positive via calls to constrainPositive(). This is necessary because LPData does not keep such historical data on its own. The order of these types should be with respect to the permuted columns (i.e., it should reflect the columns as they are stored in this tableaux, not the original matching equations). As a special case, when extracting a strict angle structure one may pass type = null, in which case this routine will assume that every coordinate was constrained as positive.
- Returns
- a vector containing the values of all the variables. This vector will have length origTableaux_->coordinateColumns().
◆ initClone()
| void regina::LPData< LPConstraint, IntType >::initClone | ( | const LPData< LPConstraint, IntType > & | parent | ) |
Initialises this tableaux to be a clone of the given tableaux.
This is used in the tree traversal algorithm as we work our way down the search tree, and child nodes "inherit" tableaux from their parent nodes.
- Precondition
- reserve() has already been called.
- Parameters
-
parent the tableaux to clone.
◆ initStart()
| void regina::LPData< LPConstraint, IntType >::initStart | ( | ) |
Initialises this tableaux by beginning at the original starting tableaux and working our way to any feasible basis.
This routine also explicitly enforces the additional constraints from the template parameter LPConstraint (i.e., this routine is responsible for forcing the corresponding linear function(s) to be zero or strictly positive as appropriate).
It is possible that a feasible basis cannot be found; you should test isFeasible() after running this routine to see whether this is the case.
- Precondition
- reserve() has already been called.
◆ isActive()
|
inline |
Determines whether the given variable is currently active.
See the LPData class notes for details.
- Parameters
-
pos the index of the variable to query. This must be between 0 and origTableaux_->columns()-1 inclusive. The index should be with respect to this tableaux (i.e., it must take into account any permutation of columns from the original matching equations).
◆ isFeasible()
|
inline |
Returns whether or not this system is feasible.
A system may become infeasible when we add too many extra constraints on the variables (such as forcing them to be positive, or setting them to zero); see the LPData class notes for details on these constraints.
- Warning
- As explained in the class notes, if this system is infeasible then any queries or operations (other than calling isFeasible() itself) are undefined.
- Returns
trueif this system is feasible, orfalseif it is infeasible.
◆ operator=()
|
inlinenoexcept |
Moves the contents of the given tableaux into this tableaux.
This is a fast (constant time) operation.
If the given tableaux is uninitialised, then this tableaux will become uninitialised also.
The tableaux that is passed (src) will no longer be usable.
- Parameters
-
src the tableaux to move.
- Returns
- a reference to this tableaux.
◆ reserve()
|
inline |
Reserves enough memory for this tableaux to work with.
You must call this routine before doing anything else with this tableaux.
The data in this tableaux will not be initialised, and the contents and behaviour of this tableaux will remain undefined until you call one of the initialisation routines initStart() or initClone().
- Parameters
-
origTableaux the original starting tableaux that holds the adjusted matrix of matching equations, before the tree traversal algorithm began.
◆ sign()
|
inline |
Returns the sign of the given variable under the current basis.
This does not attempt to "undo" any changes of variable caused by prior calls to constrainPositive() or constrainOct(); it simply tests the sign of the variable in the given column of the tableaux in its current form.
Specifically: if the given variable is inactive or non-basic, this routine returns zero. If the given variable is in the basis, this routine returns the sign of the corresponding integer on the right-hand side of the tableaux.
- Parameters
-
pos the index of the variable to query. This must be between 0 and origTableaux_->columns()-1 inclusive. The index should be with respect to this tableaux (i.e., it must take into account any permutation of columns from the original matching equations).
- Returns
- the sign of the variable as described above; this will be either 1, 0 or -1.
◆ str()
|
inherited |
Returns a short text representation of this object.
This text should be human-readable, should use plain ASCII characters where possible, and should not contain any newlines.
Within these limits, this short text ouptut should be as information-rich as possible, since in most cases this forms the basis for the Python str() and repr() functions.
- Python
- The Python "stringification" function
str()will use precisely this function, and for most classes the Pythonrepr()function will incorporate this into its output.
- Returns
- a short text representation of this object.
◆ swap()
|
inlinenoexcept |
Swaps the contents of this and the given tableaux.
It does not matter if the two tableaux have different sizes, or if one or both is unintialised; if so then these properties will be swapped also.
- Parameters
-
other the tableaux whose contents should be swapped with this.
◆ utf8()
|
inherited |
Returns a short text representation of this object using unicode characters.
Like str(), this text should be human-readable, should not contain any newlines, and (within these constraints) should be as information-rich as is reasonable.
Unlike str(), this function may use unicode characters to make the output more pleasant to read. The string that is returned will be encoded in UTF-8.
- Returns
- a short text representation of this object.
◆ writeTextLong()
| void regina::LPData< LPConstraint, IntType >::writeTextLong | ( | std::ostream & | out | ) | const |
Writes a detailed text representation of this object to the given output stream.
- Python
- Not present; use detail() instead.
- Parameters
-
out the output stream to which to write.
◆ writeTextShort()
| void regina::LPData< LPConstraint, IntType >::writeTextShort | ( | std::ostream & | out | ) | const |
Writes a short text representation of this object to the given output stream.
- Python
- Not present; use str() instead.
- Parameters
-
out the output stream to which to write.
The documentation for this class was generated from the following files:
- enumerate/treeconstraint.h
- enumerate/treelp.h