CoinPresolveMatrix Class Reference

Augments CoinPrePostsolveMatrix with information about the problem that is only needed during presolve. More...

#include <CoinPresolveMatrix.hpp>

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

List of all members.

Public Member Functions

 CoinPresolveMatrix (int ncols_alloc, int nrows_alloc, CoinBigIndex nelems_alloc)
 `Native' constructor
 CoinPresolveMatrix (int ncols0, double maxmin, ClpSimplex *si, int nrows, CoinBigIndex nelems, bool doStatus, double nonLinearVariable, double bulkRatio)
 Clp OSI constructor.
void update_model (ClpSimplex *si, int nrows0, int ncols0, CoinBigIndex nelems0)
 Update the model held by a Clp OSI.
 CoinPresolveMatrix (int ncols0, double maxmin, OsiSolverInterface *si, int nrows, CoinBigIndex nelems, bool doStatus, double nonLinearVariable, const char *prohibited)
 Generic OSI constructor.
void update_model (OsiSolverInterface *si, int nrows0, int ncols0, CoinBigIndex nelems0)
 Update the model held by a generic OSI.
 ~CoinPresolveMatrix ()
 Destructor.
void change_bias (double change_amount)
 Adjust objective function constant offset.
void statistics ()
 Say we want statistics - also set time.
double feasibilityTolerance ()
 Return feasibility tolerance.
void setFeasibilityTolerance (double val)
 Set feasibility tolerance.
int status ()
 Returns problem status (0 = feasible, 1 = infeasible, 2 = unbounded).
void setStatus (int status)
 Set problem status.
void setPass (int pass=0)
 Set pass number.
void setMaximumSubstitutionLevel (int level)
 Set Maximum substitution level (normally 3).
Functions to load the problem representation



void setMatrix (const CoinPackedMatrix *mtx)
 Load the cofficient matrix.
int countEmptyRows ()
 Count number of empty rows.
void setVariableType (int i, int variableType)
 Set variable type information for a single variable.
void setVariableType (const unsigned char *variableType, int lenParam)
 Set variable type information for all variables.
void setVariableType (bool allIntegers, int lenParam)
 Set the type of all variables.
void setAnyInteger (bool anyInteger=true)
 Set a flag for presence (true) or absence (false) of integer variables.
Functions to retrieve problem information



const CoinBigIndexgetRowStarts () const
 Get row start vector for row-major packed matrix.
const int * getColIndicesByRow () const
 Get vector of column indices for row-major packed matrix.
const double * getElementsByRow () const
 Get vector of elements for row-major packed matrix.
bool isInteger (int i) const
 Check for integrality of the specified variable.
bool anyInteger () const
 Check if there are any integer variables.
int presolveOptions () const
 Picks up any special options.
void setPresolveOptions (int value)
 Sets any special options.
Functions to manipulate row and column processing status



void initColsToDo ()
 Initialise the column ToDo lists.
int stepColsToDo ()
 Step column ToDo lists.
int numberColsToDo ()
 Return the number of columns on the colsToDo_ list.
bool colChanged (int i) const
 Has column been changed?
void unsetColChanged (int i)
 Mark column as not changed.
void setColChanged (int i)
 Mark column as changed.
void addCol (int i)
 Mark column as changed and add to list of columns to process next.
bool colProhibited (int i) const
 Test if column is eligible for preprocessing.
bool colProhibited2 (int i) const
 Test if column is eligible for preprocessing.
void setColProhibited (int i)
 Mark column as ineligible for preprocessing.
bool colUsed (int i) const
 Test if column is marked as used.
void setColUsed (int i)
 Mark column as used.
void unsetColUsed (int i)
 Mark column as unused.
void initRowsToDo ()
 Initialise the row ToDo lists.
int stepRowsToDo ()
 Step row ToDo lists.
int numberRowsToDo ()
 Return the number of rows on the rowsToDo_ list.
bool rowChanged (int i) const
 Has row been changed?
void unsetRowChanged (int i)
 Mark row as not changed.
void setRowChanged (int i)
 Mark row as changed.
void addRow (int i)
 Mark row as changed and add to list of rows to process next.
bool rowProhibited (int i) const
 Test if row is eligible for preprocessing.
bool rowProhibited2 (int i) const
 Test if row is eligible for preprocessing.
void setRowProhibited (int i)
 Mark row as ineligible for preprocessing.
bool rowUsed (int i) const
 Test if row is marked as used.
void setRowUsed (int i)
 Mark row as used.
void unsetRowUsed (int i)
 Mark row as unused.
bool anyProhibited () const
 Check if there are any prohibited rows or columns.
void setAnyProhibited (bool val=true)
 Set a flag for presence of prohibited rows or columns.

Public Attributes

double dobias_
 Objective function offset introduced during presolve.
unsigned char * integerType_
 Tracks integrality of columns (1 for integer, 0 for continuous).
bool anyInteger_
 Flag to say if any variables are integer.
bool tuning_
 Print statistics for tuning.
double startTime_
 Start time of presolve.
double feasibilityTolerance_
 Bounds can be moved by this to retain feasibility.
int status_
 Output status: 0 = feasible, 1 = infeasible, 2 = unbounded.
int pass_
 Pass number.
int maxSubstLevel_
 Maximum substitution level.
Matrix storage management links

Linked lists, modelled after the linked lists used in OSL factorization. They are used for management of the bulk coefficient and minor index storage areas.



presolvehlinkclink_
 Linked list for the column-major representation.
presolvehlinkrlink_
 Linked list for the row-major representation.
Row-major representation

Common row-major format: A pair of vectors with positional correspondence to hold coefficients and column indices, and a second pair of vectors giving the starting position and length of each row in the first pair.



CoinBigIndexmrstrt_
 Vector of row start positions in hcol, rowels_.
int * hinrow_
 Vector of row lengths.
double * rowels_
 Coefficients (positional correspondence with hcol_).
int * hcol_
 Column indices (positional correspondence with rowels_).
Row and column processing status

Information used to determine if rows or columns can be changed and if they require further processing due to changes.

There are four major lists: the [row,col]ToDo list, and the [row,col]NextToDo list. In general, a transform processes entries from the ToDo list and adds entries to the NextToDo list.

There are two vectors, [row,col]Changed, which track the status of individual rows and columns.



unsigned char * colChanged_
 Column change status information.
int * colsToDo_
 Input list of columns to process.
int numberColsToDo_
 Length of colsToDo_.
int * nextColsToDo_
 Output list of columns to process next.
int numberNextColsToDo_
 Length of nextColsToDo_.
unsigned char * rowChanged_
 Row change status information.
int * rowsToDo_
 Input list of rows to process.
int numberRowsToDo_
 Length of rowsToDo_.
int * nextRowsToDo_
 Output list of rows to process next.
int numberNextRowsToDo_
 Length of nextRowsToDo_.
int presolveOptions_
 Presolve options 1 set if allow duplicate column tests for integer variables 2 set to allow code to try and fix infeasibilities 4 set to inhibit x+y+z=1 mods.
bool anyProhibited_

Friends

void assignPresolveToPostsolve (CoinPresolveMatrix *&preObj)
 Initialize a CoinPostsolveMatrix object, destroying the CoinPresolveMatrix object.

Related Functions

(Note that these are not member functions.)



void presolve_no_dups (const CoinPresolveMatrix *preObj, bool doCol=true, bool doRow=true)
 Check column-major and/or row-major matrices for duplicate entries in the major vectors.
void presolve_links_ok (const CoinPresolveMatrix *preObj, bool doCol=true, bool doRow=false)
 Check the links which track storage order for major vectors in the bulk storage area.
void presolve_no_zeros (const CoinPresolveMatrix *preObj, bool doCol=true, bool doRow=true)
 Check for explicit zeros in the column- and/or row-major matrices.
void presolve_consistent (const CoinPresolveMatrix *preObj, bool chkvals=true)
 Checks for equivalence of the column- and row-major matrices.
void presolve_check_sol (const CoinPresolveMatrix *preObj, int chkColSol=2, int chkRowAct=1, int chkStatus=1)
 Check primal solution and architectural variable status.

Detailed Description

Augments CoinPrePostsolveMatrix with information about the problem that is only needed during presolve.

For problem manipulation, this class adds a row-major matrix representation, linked lists that allow for easy manipulation of the matrix when applying presolve transforms, and vectors to track row and column processing status (changed, needs further processing, change prohibited)

For problem representation, this class adds information about variable type (integer or continuous), an objective offset, and a feasibility tolerance.

NOTE that the anyInteger_ and anyProhibited_ flags are independent of the vectors used to track this information for individual variables (integerType_ and rowChanged_ and colChanged_, respectively).

NOTE also that at the end of presolve the column-major and row-major matrix representations are loosely packed (i.e., there may be gaps between columns in the bulk storage arrays).

Definition at line 765 of file CoinPresolveMatrix.hpp.


Constructor & Destructor Documentation

CoinPresolveMatrix::CoinPresolveMatrix ( int  ncols_alloc,
int  nrows_alloc,
CoinBigIndex  nelems_alloc 
)

`Native' constructor

This constructor creates an empty object which must then be loaded. On the other hand, it doesn't assume that the client is an OsiSolverInterface.

CoinPresolveMatrix::CoinPresolveMatrix ( int  ncols0,
double  maxmin,
ClpSimplex si,
int  nrows,
CoinBigIndex  nelems,
bool  doStatus,
double  nonLinearVariable,
double  bulkRatio 
)

Clp OSI constructor.

See Clp code for the definition.

CoinPresolveMatrix::CoinPresolveMatrix ( int  ncols0,
double  maxmin,
OsiSolverInterface si,
int  nrows,
CoinBigIndex  nelems,
bool  doStatus,
double  nonLinearVariable,
const char *  prohibited 
)

Generic OSI constructor.

See OSI code for the definition.

CoinPresolveMatrix::~CoinPresolveMatrix (  ) 

Destructor.


Member Function Documentation

void CoinPresolveMatrix::update_model ( ClpSimplex si,
int  nrows0,
int  ncols0,
CoinBigIndex  nelems0 
)

Update the model held by a Clp OSI.

void CoinPresolveMatrix::update_model ( OsiSolverInterface si,
int  nrows0,
int  ncols0,
CoinBigIndex  nelems0 
)

Update the model held by a generic OSI.

void CoinPresolveMatrix::setMatrix ( const CoinPackedMatrix mtx  ) 

Load the cofficient matrix.

Load the coefficient matrix before loading the other vectors (bounds, objective, variable type) required to define the problem.

int CoinPresolveMatrix::countEmptyRows (  )  [inline]

Count number of empty rows.

Definition at line 844 of file CoinPresolveMatrix.hpp.

void CoinPresolveMatrix::setVariableType ( int  i,
int  variableType 
) [inline]

Set variable type information for a single variable.

Set variableType to 0 for continous, 1 for integer. Does not manipulate the anyInteger_ flag.

Definition at line 854 of file CoinPresolveMatrix.hpp.

void CoinPresolveMatrix::setVariableType ( const unsigned char *  variableType,
int  lenParam 
)

Set variable type information for all variables.

Set variableType[i] to 0 for continuous, 1 for integer. Does not manipulate the anyInteger_ flag.

void CoinPresolveMatrix::setVariableType ( bool  allIntegers,
int  lenParam 
)

Set the type of all variables.

allIntegers should be true to set the type to integer, false to set the type to continuous.

void CoinPresolveMatrix::setAnyInteger ( bool  anyInteger = true  )  [inline]

Set a flag for presence (true) or absence (false) of integer variables.

Definition at line 873 of file CoinPresolveMatrix.hpp.

const CoinBigIndex* CoinPresolveMatrix::getRowStarts (  )  const [inline]

Get row start vector for row-major packed matrix.

Definition at line 882 of file CoinPresolveMatrix.hpp.

const int* CoinPresolveMatrix::getColIndicesByRow (  )  const [inline]

Get vector of column indices for row-major packed matrix.

Definition at line 885 of file CoinPresolveMatrix.hpp.

const double* CoinPresolveMatrix::getElementsByRow (  )  const [inline]

Get vector of elements for row-major packed matrix.

Definition at line 888 of file CoinPresolveMatrix.hpp.

bool CoinPresolveMatrix::isInteger ( int  i  )  const [inline]

Check for integrality of the specified variable.

Consults the integerType_ vector if present; fallback is the anyInteger_ flag.

Definition at line 896 of file CoinPresolveMatrix.hpp.

bool CoinPresolveMatrix::anyInteger (  )  const [inline]

Check if there are any integer variables.

Consults the anyInteger_ flag

Definition at line 909 of file CoinPresolveMatrix.hpp.

int CoinPresolveMatrix::presolveOptions (  )  const [inline]

Picks up any special options.

Definition at line 912 of file CoinPresolveMatrix.hpp.

void CoinPresolveMatrix::setPresolveOptions ( int  value  )  [inline]

Sets any special options.

Definition at line 915 of file CoinPresolveMatrix.hpp.

void CoinPresolveMatrix::change_bias ( double  change_amount  )  [inline]

Adjust objective function constant offset.

Definition at line 936 of file CoinPresolveMatrix.hpp.

void CoinPresolveMatrix::statistics (  ) 

Say we want statistics - also set time.

double CoinPresolveMatrix::feasibilityTolerance (  )  [inline]

Return feasibility tolerance.

Definition at line 983 of file CoinPresolveMatrix.hpp.

void CoinPresolveMatrix::setFeasibilityTolerance ( double  val  )  [inline]

Set feasibility tolerance.

Definition at line 986 of file CoinPresolveMatrix.hpp.

int CoinPresolveMatrix::status (  )  [inline]

Returns problem status (0 = feasible, 1 = infeasible, 2 = unbounded).

Definition at line 996 of file CoinPresolveMatrix.hpp.

void CoinPresolveMatrix::setStatus ( int  status  )  [inline]

Set problem status.

Definition at line 999 of file CoinPresolveMatrix.hpp.

void CoinPresolveMatrix::setPass ( int  pass = 0  )  [inline]

Set pass number.

Definition at line 1009 of file CoinPresolveMatrix.hpp.

void CoinPresolveMatrix::setMaximumSubstitutionLevel ( int  level  )  [inline]

Set Maximum substitution level (normally 3).

Definition at line 1018 of file CoinPresolveMatrix.hpp.

void CoinPresolveMatrix::initColsToDo (  ) 

Initialise the column ToDo lists.

Places all columns in the colsToDo_ list except for columns marked as prohibited (viz. colChanged_).

int CoinPresolveMatrix::stepColsToDo (  ) 

Step column ToDo lists.

Moves columns on the nextColsToDo_ list to the colsToDo_ list, emptying nextColsToDo_. Returns the number of columns transferred.

int CoinPresolveMatrix::numberColsToDo (  )  [inline]

Return the number of columns on the colsToDo_ list.

Definition at line 1104 of file CoinPresolveMatrix.hpp.

bool CoinPresolveMatrix::colChanged ( int  i  )  const [inline]

Has column been changed?

Definition at line 1108 of file CoinPresolveMatrix.hpp.

void CoinPresolveMatrix::unsetColChanged ( int  i  )  [inline]

Mark column as not changed.

Definition at line 1112 of file CoinPresolveMatrix.hpp.

void CoinPresolveMatrix::setColChanged ( int  i  )  [inline]

Mark column as changed.

Definition at line 1116 of file CoinPresolveMatrix.hpp.

void CoinPresolveMatrix::addCol ( int  i  )  [inline]

Mark column as changed and add to list of columns to process next.

Definition at line 1120 of file CoinPresolveMatrix.hpp.

bool CoinPresolveMatrix::colProhibited ( int  i  )  const [inline]

Test if column is eligible for preprocessing.

Definition at line 1127 of file CoinPresolveMatrix.hpp.

bool CoinPresolveMatrix::colProhibited2 ( int  i  )  const [inline]

Test if column is eligible for preprocessing.

The difference between this method and colProhibited() is that this method first tests anyProhibited_ before examining the specific entry for the specified column.

Definition at line 1136 of file CoinPresolveMatrix.hpp.

void CoinPresolveMatrix::setColProhibited ( int  i  )  [inline]

Mark column as ineligible for preprocessing.

Definition at line 1143 of file CoinPresolveMatrix.hpp.

bool CoinPresolveMatrix::colUsed ( int  i  )  const [inline]

Test if column is marked as used.

This is for doing faster lookups to see where two columns have entries in common.

Definition at line 1151 of file CoinPresolveMatrix.hpp.

void CoinPresolveMatrix::setColUsed ( int  i  )  [inline]

Mark column as used.

Definition at line 1155 of file CoinPresolveMatrix.hpp.

void CoinPresolveMatrix::unsetColUsed ( int  i  )  [inline]

Mark column as unused.

Definition at line 1159 of file CoinPresolveMatrix.hpp.

void CoinPresolveMatrix::initRowsToDo (  ) 

Initialise the row ToDo lists.

Places all rows in the rowsToDo_ list except for rows marked as prohibited (viz. rowChanged_).

int CoinPresolveMatrix::stepRowsToDo (  ) 

Step row ToDo lists.

Moves rows on the nextRowsToDo_ list to the rowsToDo_ list, emptying nextRowsToDo_. Returns the number of rows transferred.

int CoinPresolveMatrix::numberRowsToDo (  )  [inline]

Return the number of rows on the rowsToDo_ list.

Definition at line 1178 of file CoinPresolveMatrix.hpp.

bool CoinPresolveMatrix::rowChanged ( int  i  )  const [inline]

Has row been changed?

Definition at line 1182 of file CoinPresolveMatrix.hpp.

void CoinPresolveMatrix::unsetRowChanged ( int  i  )  [inline]

Mark row as not changed.

Definition at line 1186 of file CoinPresolveMatrix.hpp.

void CoinPresolveMatrix::setRowChanged ( int  i  )  [inline]

Mark row as changed.

Definition at line 1190 of file CoinPresolveMatrix.hpp.

void CoinPresolveMatrix::addRow ( int  i  )  [inline]

Mark row as changed and add to list of rows to process next.

Definition at line 1194 of file CoinPresolveMatrix.hpp.

bool CoinPresolveMatrix::rowProhibited ( int  i  )  const [inline]

Test if row is eligible for preprocessing.

Definition at line 1201 of file CoinPresolveMatrix.hpp.

bool CoinPresolveMatrix::rowProhibited2 ( int  i  )  const [inline]

Test if row is eligible for preprocessing.

The difference between this method and rowProhibited() is that this method first tests anyProhibited_ before examining the specific entry for the specified row.

Definition at line 1210 of file CoinPresolveMatrix.hpp.

void CoinPresolveMatrix::setRowProhibited ( int  i  )  [inline]

Mark row as ineligible for preprocessing.

Definition at line 1217 of file CoinPresolveMatrix.hpp.

bool CoinPresolveMatrix::rowUsed ( int  i  )  const [inline]

Test if row is marked as used.

This is for doing faster lookups to see where two rows have entries in common. It can be used anywhere as long as it ends up zeroed out.

Definition at line 1225 of file CoinPresolveMatrix.hpp.

void CoinPresolveMatrix::setRowUsed ( int  i  )  [inline]

Mark row as used.

Definition at line 1229 of file CoinPresolveMatrix.hpp.

void CoinPresolveMatrix::unsetRowUsed ( int  i  )  [inline]

Mark row as unused.

Definition at line 1233 of file CoinPresolveMatrix.hpp.

bool CoinPresolveMatrix::anyProhibited (  )  const [inline]

Check if there are any prohibited rows or columns.

Definition at line 1239 of file CoinPresolveMatrix.hpp.

void CoinPresolveMatrix::setAnyProhibited ( bool  val = true  )  [inline]

Set a flag for presence of prohibited rows or columns.

Definition at line 1242 of file CoinPresolveMatrix.hpp.


Friends And Related Function Documentation

void assignPresolveToPostsolve ( CoinPresolveMatrix *&  preObj  )  [friend]

Member Data Documentation

Linked list for the column-major representation.

Definition at line 927 of file CoinPresolveMatrix.hpp.

Linked list for the row-major representation.

Definition at line 929 of file CoinPresolveMatrix.hpp.

Objective function offset introduced during presolve.

Definition at line 933 of file CoinPresolveMatrix.hpp.

Vector of row start positions in hcol, rowels_.

Definition at line 956 of file CoinPresolveMatrix.hpp.

Vector of row lengths.

Definition at line 958 of file CoinPresolveMatrix.hpp.

Coefficients (positional correspondence with hcol_).

Definition at line 960 of file CoinPresolveMatrix.hpp.

Column indices (positional correspondence with rowels_).

Definition at line 962 of file CoinPresolveMatrix.hpp.

Tracks integrality of columns (1 for integer, 0 for continuous).

Definition at line 966 of file CoinPresolveMatrix.hpp.

Flag to say if any variables are integer.

Note that this flag is not manipulated by the various setVariableType routines.

Definition at line 972 of file CoinPresolveMatrix.hpp.

Print statistics for tuning.

Definition at line 974 of file CoinPresolveMatrix.hpp.

Start time of presolve.

Definition at line 978 of file CoinPresolveMatrix.hpp.

Bounds can be moved by this to retain feasibility.

Definition at line 981 of file CoinPresolveMatrix.hpp.

Output status: 0 = feasible, 1 = infeasible, 2 = unbounded.

Actually implemented as single bit flags: 1^0 = infeasible, 1^1 = unbounded.

Definition at line 994 of file CoinPresolveMatrix.hpp.

Pass number.

Used to control the execution of testRedundant (evoked by the implied_free transform).

Definition at line 1007 of file CoinPresolveMatrix.hpp.

Maximum substitution level.

Used to control the execution of subst from implied_free

Definition at line 1016 of file CoinPresolveMatrix.hpp.

Column change status information.

Coded using the following bits:

  • 0x01: Column has changed
  • 0x02: preprocessing prohibited
  • 0x04: Column has been used

Definition at line 1044 of file CoinPresolveMatrix.hpp.

Input list of columns to process.

Definition at line 1046 of file CoinPresolveMatrix.hpp.

Length of colsToDo_.

Definition at line 1048 of file CoinPresolveMatrix.hpp.

Output list of columns to process next.

Definition at line 1050 of file CoinPresolveMatrix.hpp.

Length of nextColsToDo_.

Definition at line 1052 of file CoinPresolveMatrix.hpp.

Row change status information.

Coded using the following bits:

  • 0x01: Row has changed
  • 0x02: preprocessing prohibited
  • 0x04: Row has been used

Definition at line 1063 of file CoinPresolveMatrix.hpp.

Input list of rows to process.

Definition at line 1065 of file CoinPresolveMatrix.hpp.

Length of rowsToDo_.

Definition at line 1067 of file CoinPresolveMatrix.hpp.

Output list of rows to process next.

Definition at line 1069 of file CoinPresolveMatrix.hpp.

Length of nextRowsToDo_.

Definition at line 1071 of file CoinPresolveMatrix.hpp.

Presolve options 1 set if allow duplicate column tests for integer variables 2 set to allow code to try and fix infeasibilities 4 set to inhibit x+y+z=1 mods.

Definition at line 1077 of file CoinPresolveMatrix.hpp.

Flag to say if any rows or columns are marked as prohibited

Note that this flag is not manipulated by any of the various set*Prohibited routines.

Definition at line 1083 of file CoinPresolveMatrix.hpp.


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

Generated on 15 Mar 2015 for Coin-All by  doxygen 1.6.1