The mipgen class generates a Mixed Integer Program. More...
#include <mipgen.hh>
Public Member Functions | |
mipgen (const driver &d) | |
Constructor. | |
virtual | ~mipgen () |
Destructor. | |
void | formulate () |
Control problem formulation by calling different methods. | |
virtual void | write (const char *filename) |
Write data to filename. | |
Protected Member Functions | |
virtual void | make_matrix (size_t rows, size_t cols) |
Create a matrix data structure. | |
virtual void | set_element (size_t row, size_t col, int val) |
Set a single matrix element. | |
virtual void | fill_matrix () |
Copy elements to matrix data structure. | |
virtual void | write (std::ostream &out) |
Write data to stream. | |
Static Protected Member Functions | |
static int | realmod (int a, int b) |
Modulo arithmetic as the mathematician knows it. | |
Protected Attributes | |
const driver & | drv |
Reference to the driver. | |
size_t | modcount |
Number of generated columns. | |
std::vector< field > | fields |
Column data. | |
std::vector< constraint > | constraints |
Row descriptions. | |
std::vector< std::string > | col_names |
A list of column names. | |
std::vector< std::string > | row_names |
A list of row names. | |
std::vector< bounds > | col_bounds |
A list of column bounds. | |
std::vector< bounds > | row_bounds |
A list of row bounds. | |
std::vector< std::vector< int > > | matrix |
The final matrix elements. | |
Private Member Functions | |
void | modfields () |
Add columns to express modulo arithmetic. | |
void | multiply_k () |
Multiply all n_* by k . | |
void | append_gamma () |
Formulate gamma constraint. | |
void | comdenom () |
Use common denominator. | |
void | get_indices () |
Build list of component indices. | |
void | set_bounds () |
Store bounds for all rows and columns. | |
void | copy_row_names () |
Fill list of row names. | |
void | collect_fields () |
Transform using difference vectors. | |
void | copy_col_names () |
Fill list of column names. | |
void | unique_names (std::vector< std::string > &names) |
Ensure uniqueness of names in a list. | |
Private Attributes | |
std::vector< int > | indices |
Map row number to field component index. |
The mipgen class generates a Mixed Integer Program.
It is the base class for other output format drivers.
In the final form, the problem description will contain these rows:
_MaxOrder
restricting the number of fields which are part of any solutionThese rows are all represented in mipgen::row_names, mipgen::row_bounds and mipgen::matrix, but not in mipgen::constraints which contains only the input sonstraints.
In the final form, the problem description will contain these columns:
These columns are all represented in mipgen::col_names, mipgen::col_bounds and mipgen::matrix as well as mipgen::fields.
Definition at line 63 of file mipgen.hh.
mipgen::mipgen | ( | const driver & | d | ) |
mipgen::~mipgen | ( | ) | [virtual] |
void mipgen::append_gamma | ( | ) | [private] |
Formulate gamma constraint.
If driver::gamma_constraint is set, a special rule holds for the field component labeled gamma:
no solution may have a single fractional value as the only nonzero value in this column. All other combinations like all zeros, multiple frations or at least one integer are acceptable.
This is expressed in the MIP by assigning a new number to each field:
Now the constraint can be reformulated thus: the sum of all the in a solution may never be exactly 1. To express this, a new binary decision variable is introduced, where 0 stands for the all zero case, and 1 for a sum of at least 2. With this variable, the following two inequalities constrain the sum to be not exactly 1.
This method adds two new components to each existing field, and adds a new field to represent (called _gamma
in the output). Instead of , twice the maximum order is used, which is infinite enough here.
Definition at line 171 of file mipgen.cc.
References rational::denom, drv, fields, driver::indices, driver::max_order, modcount, driver::names, and rational::nom.
Referenced by formulate().
void mipgen::collect_fields | ( | ) | [private] |
Transform using difference vectors.
The input often contains multiple representations of the same field, a so called multiplet. These multipletts are represented as different field descriptions sharing a common name. For the solution it is unimportant, which element of a multiplet is actually used, as long as a valid solution does exist. Together with the fact that multiplets tend to follow certain patterns, the following encoding gan improve the problem description.
For every multiplet, its first description is used as representative. The others are encoded as differences in relation to this representative. If another multiplet follows the same pattern and thus results in the same set of difference vecotrs, the same difference vectors can be shared between the two multiplets. A new line for each set of difference vectors ensures that no solution will contain more difference vectors than matching multiplet representatives.
At the time this method is invoked, bounds have been set and row names filled in. This method will update the stored information.
Definition at line 326 of file mipgen.cc.
References col_bounds, drv, fields, bounds::hint, indices, driver::max_order, modcount, row_bounds, row_names, and bounds::strict.
Referenced by formulate().
void mipgen::comdenom | ( | ) | [private] |
Use common denominator.
The input is given in rational numbers, whereas the output will be in integers. This method calculates the common denominator of each row and expands all fractions to it. From now on, all calculations can take place on the nominators solely.
Definition at line 198 of file mipgen.cc.
References constraints, drv, fields, driver::indices, and lcm().
Referenced by formulate().
void mipgen::copy_col_names | ( | ) | [private] |
Fill list of column names.
These names are simply copied from mipgen::fields.
Definition at line 408 of file mipgen.cc.
References col_names, and fields.
Referenced by formulate().
void mipgen::copy_row_names | ( | ) | [private] |
Fill list of row names.
The names of the _MaxOrder
row and the gamma rows are hardcoded into this method. All other names come from the cooresponding constraints.
Difference vectors are not yet encoded at the time when this method is invoked.
Definition at line 291 of file mipgen.cc.
References constraints, drv, driver::gamma_constraint, and row_names.
Referenced by formulate().
void mipgen::fill_matrix | ( | ) | [protected, virtual] |
Copy elements to matrix data structure.
This class iterates over all matrix elements and calls mipgen::set_element() for each one.
Definition at line 456 of file mipgen.cc.
References col_names, fields, indices, modcount, row_names, and set_element().
Referenced by formulate().
void mipgen::formulate | ( | ) |
Control problem formulation by calling different methods.
Look at the implementation to see in which methods are called in which order.
Definition at line 81 of file mipgen.cc.
References append_gamma(), col_names, collect_fields(), comdenom(), driver::constraints, constraints, copy_col_names(), copy_row_names(), drv, fill_matrix(), driver::gamma_constraint, get_indices(), make_matrix(), modfields(), multiply_k(), driver::multiply_k, row_names, and set_bounds().
Referenced by driver::process().
void mipgen::get_indices | ( | ) | [private] |
Build list of component indices.
The order of values in the field descriptions does not follow the order of rows in the output. This method determines the corresponding index into field::values for every output row. For the first row, which constrains the maximum order, there is no corresponding component. -1 is stored instead.
Definition at line 221 of file mipgen.cc.
References driver::constraints, drv, driver::gamma_constraint, driver::indices, indices, and driver::names.
Referenced by formulate().
void mipgen::make_matrix | ( | size_t | rows, | |
size_t | cols | |||
) | [protected, virtual] |
Create a matrix data structure.
Derived classes may wish to override this method. The base implementation prepares mipgen::matrix by clearing any data it might contain and adjusting its size according to the request.
rows | the number of rows the coefficient matrix has. | |
cols | the number of columns the coefficient matrix has. |
Reimplemented in mpsgen.
Definition at line 445 of file mipgen.cc.
References matrix.
Referenced by formulate().
void mipgen::modfields | ( | ) | [private] |
Add columns to express modulo arithmetic.
For each constraint that has a nonzero constraint::mod, a field is added to mipgen::fields to express any integral multiple of the modulus.
Definition at line 104 of file mipgen.cc.
References driver::constraints, drv, driver::fields, fields, driver::indices, modcount, and driver::names.
Referenced by formulate().
void mipgen::multiply_k | ( | ) | [private] |
Multiply all n_*
by k
.
Every quantum number starting in n_
will be multiplied by the quantum number starting with k
. driver::set_names ensures that such a field k
exists whenever driver::multiply_k is set.
Definition at line 126 of file mipgen.cc.
References drv, fields, driver::indices, modcount, and driver::names.
Referenced by formulate().
int mipgen::realmod | ( | int | a, | |
int | b | |||
) | [static, protected] |
Modulo arithmetic as the mathematician knows it.
The C++ idea of modulo arithmetic is a bit different from most mathematicians' ideas when it comes to negative numbers. This function implements the mathematician's idea of a modulo operation.
a | the divisor, may be negative. | |
b | the dividend (modulus), must be positive. |
Definition at line 71 of file mipgen.cc.
Referenced by opbgen::write().
void mipgen::set_bounds | ( | ) | [private] |
Store bounds for all rows and columns.
The row bounds are set to these values:
The column bounds are set to these values:
For most unconstrained ends of a bounds pair, an implied loose bound is given as a hint, to allow derived classes to use ranges if they can be handled better.
Difference vectors are not yet encoded at the time when this method is invoked.
Definition at line 256 of file mipgen.cc.
References col_bounds, constraints, drv, fields, driver::gamma_constraint, bounds::hint, driver::max_order, driver::min_order, modcount, row_bounds, and bounds::strict.
Referenced by formulate().
void mipgen::set_element | ( | size_t | row, | |
size_t | col, | |||
int | val | |||
) | [protected, virtual] |
Set a single matrix element.
Derived classes may wish to override this method. The base implementation stores the value in mipgen::matrix. If a derived classes wishes to omit zero entries from its data structure, it should check that case itself. This method will be called for all matrix elements, zero and nonzero, in column major order.
row | the row index of the matrix element. | |
col | the column index of the matrix element. | |
val | the value of the matrix element. |
Reimplemented in mpsgen.
Definition at line 479 of file mipgen.cc.
References matrix.
Referenced by fill_matrix().
void mipgen::unique_names | ( | std::vector< std::string > & | names | ) | [private] |
Ensure uniqueness of names in a list.
Before mipgen::collect_fields() was introduced, this method used to ensure unique output names for the different columns of the same multiplet. At the moment this method is unused.
[in,out] | names | the list of names to be made unique. |
void mipgen::write | ( | std::ostream & | out | ) | [protected, virtual] |
Write data to stream.
The default implementation prints the problem in a tabulated form that can be opened using spreadsheet applications. This functionality is accessibly using the --format=cvs
command line switch. For this use, most data is read from the driver and not from the transformed data structures stored inside mipgen itself.
Reimplemented in opbgen.
Definition at line 511 of file mipgen.cc.
References driver::constraints, drv, driver::fields, and driver::names.
void mipgen::write | ( | const char * | filename | ) | [virtual] |
Write data to filename.
The default implementation relies on write(std::ostream&) to do the actual output. A derived class must override either method.
filename | the output file name, or 0 for standard output. |
Reimplemented in mpsgen.
Definition at line 491 of file mipgen.cc.
Referenced by driver::process().
std::vector<bounds> mipgen::col_bounds [protected] |
A list of column bounds.
These bounds on the variables are set by mipgen::set_bounds. They are intended for easy output generation in derived classes.
Definition at line 143 of file mipgen.hh.
Referenced by collect_fields(), set_bounds(), and mpsgen::write().
std::vector<std::string> mipgen::col_names [protected] |
A list of column names.
This is copied from the names of the mipgen::constraints by mipgen::copy_col_names. They are intended for easy output generation in derived classes.
Definition at line 128 of file mipgen.hh.
Referenced by copy_col_names(), fill_matrix(), formulate(), opbgen::write(), and mpsgen::write().
std::vector<constraint> mipgen::constraints [protected] |
Row descriptions.
This is a direct copy of driver::constraints at first and restricts most operations to the field components which are actually constrained in some way. In the final output, only these components will be included as rows, along with some special rows.
Preceding the equality constrained rows corresponding to these constraints, there will be one generated row for the maximum order, andâ€”if enabledâ€”two rows for gamma selection. These are not represented as constraint objects and thus not part of this list.
Definition at line 120 of file mipgen.hh.
Referenced by comdenom(), copy_row_names(), formulate(), and set_bounds().
const driver& mipgen::drv [protected] |
Reference to the driver.
This allows access to command line options and input data.
Definition at line 76 of file mipgen.hh.
Referenced by append_gamma(), collect_fields(), comdenom(), copy_row_names(), formulate(), get_indices(), modfields(), multiply_k(), set_bounds(), opbgen::write(), mpsgen::write(), and write().
std::vector<field> mipgen::fields [protected] |
Column data.
As the description of class field explains, a field is a colum description, including a name, the matrix elements of this column, and a pair of bounds on the variable associated with this column. This list contains original field descriptions from the input file, but preceding them there are generated columns.
Definition at line 101 of file mipgen.hh.
Referenced by append_gamma(), collect_fields(), comdenom(), copy_col_names(), fill_matrix(), modfields(), multiply_k(), and set_bounds().
std::vector<int> mipgen::indices [private] |
Map row number to field component index.
The rows in the output mostly correspond to mipgen::constraints, which identify the corresponding quantum number by name. The order of elements in the field::values might therefore be different from the output order. This vector gives the corresponding indices into field::values in order of output rows.
Definition at line 177 of file mipgen.hh.
Referenced by collect_fields(), fill_matrix(), and get_indices().
std::vector< std::vector<int> > mipgen::matrix [protected] |
The final matrix elements.
A list of list is used to represent the final integral two-dimensional matrix of coefficients of the integer program. They are intended for easy output generation in derived classes.
Reimplemented in mpsgen.
Definition at line 158 of file mipgen.hh.
Referenced by make_matrix(), set_element(), and opbgen::write().
size_t mipgen::modcount [protected] |
Number of generated columns.
Columns used to express modulo arithmetic, but also some other generated columns, preceed the actual field descriptions in the matrix. This number gives an indication as to how many generated columns there are, and thus allows different handling of the different types of columns without relying on the special naming convention that a generated column starts with an underscore.
Definition at line 88 of file mipgen.hh.
Referenced by append_gamma(), collect_fields(), fill_matrix(), modfields(), multiply_k(), set_bounds(), opbgen::write(), and mpsgen::write().
std::vector<bounds> mipgen::row_bounds [protected] |
A list of row bounds.
These bounds on the row values are set by mipgen::set_bounds. They are intended for easy output generation in derived classes.
Definition at line 150 of file mipgen.hh.
Referenced by collect_fields(), set_bounds(), opbgen::write(), and mpsgen::write().
std::vector<std::string> mipgen::row_names [protected] |
A list of row names.
This is copied from the names of the mipgen::fields by mipgen::copy_row_names, except for some special rows. They are intended for easy output generation in derived classes.
Definition at line 136 of file mipgen.hh.
Referenced by collect_fields(), copy_row_names(), fill_matrix(), formulate(), opbgen::write(), and mpsgen::write().