mipgen Class Reference

The mipgen class generates a Mixed Integer Program. More...

#include <mipgen.hh>

Inheritance diagram for mipgen:
Inheritance graph
[legend]
Collaboration diagram for mipgen:
Collaboration graph
[legend]

List of all members.

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 driverdrv
 Reference to the driver.
size_t modcount
 Number of generated columns.
std::vector< fieldfields
 Column data.
std::vector< constraintconstraints
 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< boundscol_bounds
 A list of column bounds.
std::vector< boundsrow_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.

Detailed Description

The mipgen class generates a Mixed Integer Program.

It is the base class for other output format drivers.

Order of problem data

Order of Rows

In the final form, the problem description will contain these rows:

  1. one row _MaxOrder restricting the number of fields which are part of any solution
  2. two rows for gamma selection if driver::gamma_constraint is set
  3. one row for each constraint specified in the input file
  4. rows for difference vectors from mipgen::collect_fields()

These 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.

Order of Columns

In the final form, the problem description will contain these columns:

  1. one column for gamma selection from mipgen::append_gamma() if driver::gamma_constraint is set, otherwise omitted
  2. modulo arithmetic columns from mipgen::modfields()
  3. difference vectors from mipgen::collect_fields()
  4. original input fields from driver::fields

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.


Constructor & Destructor Documentation

mipgen::mipgen ( const driver d  ) 

Constructor.

Parameters:
d the driver which will be accessed read-only for settings and input data.

Definition at line 48 of file mipgen.cc.

mipgen::~mipgen (  )  [virtual]

Destructor.

It is only present so that derived classes can be destructed cleanly in the presence of polymorphism.

Definition at line 56 of file mipgen.cc.


Member Function Documentation

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 $ n_\gamma $ to each field:

\[ n_\gamma = \begin{cases} 0 & \quad q_\gamma = 0 \\ 1 & \quad q_\gamma \in \mathbb Q\setminus\mathbb Z \\ 2 & \quad q_\gamma \in \mathbb Z\setminus\{0\} \end{cases} \]

Now the constraint can be reformulated thus: the sum of all the $ n_\gamma $ in a solution may never be exactly 1. To express this, a new binary decision variable $ x_\gamma \in \{0,1\} $ 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.

\begin{align*} -2x_\gamma+\sum_an_\gamma^{(a)} &\geq 0 \\ -\infty x_\gamma+\sum_an_\gamma^{(a)} &\leq 0 \end{align*}

This method adds two new components to each existing field, and adds a new field to represent $ x_\gamma $ (called _gamma in the output). Instead of $ \infty $, 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.

Parameters:
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.

Parameters:
a the divisor, may be negative.
b the dividend (modulus), must be positive.
Returns:
a number c such that $ 0 \leq c < b $ and $ a = b \cdot d + c $ for some integer d.

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:

  1. the order is constrained between driver::min_order and driver::max_order
  2. the gamma rows are constrained as described in append_gamma()
  3. the input constraints are copied as strict equalities

The column bounds are set to these values:

  1. the gamma column is constrained between 0 and 1
  2. the modulo columns are unconstrained
  3. the columns for input fields are constrained to be nonnegative.

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.

Parameters:
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.

Parameters:
[in,out] names the list of names to be made unique.

Definition at line 424 of file mipgen.cc.

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.

Parameters:
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().


Member Data Documentation

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.

See also:
Order of Rows

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.

See also:
Order of 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().


The documentation for this class was generated from the following files:

Generated on Fri Aug 21 08:15:08 2009 for mqn2mps by  doxygen 1.6.0