bande::IntegerProgram Class Reference

Linear program with integer bounds, coefficients and solutions. More...

#include <IntegerProgram.hh>

Collaboration diagram for bande::IntegerProgram:
Collaboration graph
[legend]

List of all members.

Public Member Functions

 IntegerProgram ()
 Constructor.
virtual ~IntegerProgram ()
 Destructor.
void readMps (const char *fileName)
 Read the problem instance from an MPS file.
void setColLower (UndoManager &um, int col, int val)
 Set lower bound of a column.
void setColUpper (UndoManager &um, int col, int val)
 Set upper bound of a column.
void mkIntSolution ()
 Convert solution values to integers.
bool checkIntSolution () const
 Check the current integral solution.
int getNumRows () const
 Get the number of rows.
int getNumCols () const
 Get the number of columns.
bool solve ()
 Find optimal solution to current linear program.
double getColSolution (int index) const
 Get one variable of the solution.
void dumpSolution (std::ostream &out=std::cerr) const
 Dump the current solution for debugging purposes.
int getColLower (int col) const
 Get the current lower bound of a column.
int getColUpper (int col) const
 Get the current upper bound of a column.
const std::pair< int, int > & getColBounds (int col) const
 Get both bounds of a column.
void randomizeObjective ()
 Choose a random objective function.
std::string getColName (int col) const
 Get the name of a column.
std::string getRowName (int row) const
 Get the name of a row.
int getIntSolution (int index) const
 Get one variable of the solution as an integer.

Protected Member Functions

int mkInt (double d)
 Cast to integer by rounding.
int & m (int row, int col)
 Provide read-write access to the integral matrix elements.

Protected Attributes

LinearProgram lp
 The linear program wrapped inside this integer program.
std::vector< std::pair< int,
int > > 
rowBounds
 The row bounds as integers.
std::vector< std::pair< int,
int > > 
colBounds
 The column bounds as integers.
std::vector< int > matrix
 The matrix elements as integers.
std::vector< int > iSol
 The solution vector rounded to integers.

Detailed Description

Linear program with integer bounds, coefficients and solutions.

This class is mainly a wrapper around LinearProgram which changes many of its data types from double to integer. In order to not interfere with the LP, the integral bookkeeping is done using duplicate data structures within this IP.

In order to keep these dual structures synchronized, there is no direct access to the protected linear program. All access must be made through the corresponding integer program.

Definition at line 41 of file IntegerProgram.hh.


Member Function Documentation

bool bande::IntegerProgram::checkIntSolution (  )  const

Check the current integral solution.

After mkIntSolutions() has been invoked, there should be a solution to the all-integer problem. This method checks that assumption by verifying each bound using only integer arithmetic, with never a chance for rounding issues.

Returns:
whether the current solution is a valid integral solution.

Definition at line 169 of file IntegerProgram.cc.

References colBounds, getColName(), getNumCols(), getNumRows(), getRowName(), iSol, matrix, and rowBounds.

Referenced by bande::BranchControl::branch().

void bande::IntegerProgram::dumpSolution ( std::ostream &  out = std::cerr  )  const [inline]

Dump the current solution for debugging purposes.

Parameters:
out the output stream to which the solution will be dumped.

Definition at line 86 of file IntegerProgram.hh.

References bande::LinearProgram::dumpSolution(), and lp.

Referenced by bande::BranchControl::branch().

const std::pair<int, int>& bande::IntegerProgram::getColBounds ( int  col  )  const [inline]

Get both bounds of a column.

Parameters:
col the index of the column.
Returns:
a pair of the lower (first) and upper (second) bound of that column.

Definition at line 110 of file IntegerProgram.hh.

References colBounds.

Referenced by bande::BranchControl::branchCol().

int bande::IntegerProgram::getColLower ( int  col  )  const [inline]

Get the current lower bound of a column.

Parameters:
col the index of the column.
Returns:
the current lower bound of that column.

Definition at line 95 of file IntegerProgram.hh.

References colBounds.

Referenced by bande::BranchControl::branch().

std::string bande::IntegerProgram::getColName ( int  col  )  const [inline]

Get the name of a column.

This is also the name of the associated variable.

Parameters:
col the index of the column.
Returns:
the name of that column.

Definition at line 125 of file IntegerProgram.hh.

References bande::LinearProgram::getColName(), and lp.

Referenced by bande::BranchControl::branch(), checkIntSolution(), and bande::Solutions::writeSolution().

double bande::IntegerProgram::getColSolution ( int  index  )  const [inline]

Get one variable of the solution.

Parameters:
index the index of the variable.
Returns:
the value of that variable in the current solution.

Definition at line 79 of file IntegerProgram.hh.

References bande::LinearProgram::getColSolution(), and lp.

Referenced by bande::BranchControl::branch(), bande::BranchControl::branchCol(), and mkIntSolution().

int bande::IntegerProgram::getColUpper ( int  col  )  const [inline]

Get the current upper bound of a column.

Parameters:
col the index of the column.
Returns:
the current upper bound of that column.

Definition at line 102 of file IntegerProgram.hh.

References colBounds.

Referenced by bande::BranchControl::branch().

int bande::IntegerProgram::getIntSolution ( int  index  )  const [inline]

Get one variable of the solution as an integer.

This function will only return the current values after mkIntSolution() has been called.

Parameters:
index the index of the variable.
Returns:
the value of that variable in the current solution.

Definition at line 143 of file IntegerProgram.hh.

References iSol.

Referenced by bande::Solutions::writeSolution().

int bande::IntegerProgram::getNumCols (  )  const [inline]

Get the number of columns.

Each column corresponds to one variable of the solution.

Returns:
the number of columns in the problem.

Definition at line 66 of file IntegerProgram.hh.

References bande::LinearProgram::getNumCols(), and lp.

Referenced by bande::BranchControl::branchCol(), checkIntSolution(), m(), mkIntSolution(), readMps(), and bande::Solutions::writeSolution().

int bande::IntegerProgram::getNumRows (  )  const [inline]

Get the number of rows.

Each row represents zero to two inequalities, depending on the row bounds.

Returns:
the number of rows in the problem.

Definition at line 59 of file IntegerProgram.hh.

References bande::LinearProgram::getNumRows(), and lp.

Referenced by checkIntSolution(), and readMps().

std::string bande::IntegerProgram::getRowName ( int  row  )  const [inline]

Get the name of a row.

Parameters:
row the index of the row.
Returns:
the name of that row.

Definition at line 132 of file IntegerProgram.hh.

References bande::LinearProgram::getRowName(), and lp.

Referenced by checkIntSolution().

int& bande::IntegerProgram::m ( int  row,
int  col 
) [inline, protected]

Provide read-write access to the integral matrix elements.

Parameters:
row the row index of the matrix element.
col the column index of the matrix element.
Returns:
a writable reference to the addressed matrix element.

Definition at line 186 of file IntegerProgram.hh.

References getNumCols(), and matrix.

Referenced by readMps().

int bande::IntegerProgram::mkInt ( double  d  )  [protected]

Cast to integer by rounding.

The argument is assumed to be conceptually integral, so there is no check to ensure that the value is really integral or anywhere close to an integer. What is checked, however, is the range. The valid output range of this method is almost the whole range of int, with only a little bit removed as a safety margin. Values exceeding this range will be clipped to the neares range boundary. Values *.5 are always rounded up by this method.

Parameters:
d the double value to be converted to an integer.
Returns:
the nearest integer to d inside the result range.

Definition at line 57 of file IntegerProgram.cc.

Referenced by mkIntSolution(), and readMps().

void bande::IntegerProgram::mkIntSolution (  ) 

Convert solution values to integers.

The solution is assumed to be integral already. After this method has been invoked, getIntSolution() will return the requested integral solution without casting for every call.

Definition at line 152 of file IntegerProgram.cc.

References getColSolution(), getNumCols(), iSol, and mkInt().

Referenced by bande::BranchControl::branch().

void bande::IntegerProgram::readMps ( const char *  fileName  ) 

Read the problem instance from an MPS file.

After reading the linear program using LinearProgram::readMps(), the internal integer-based data structures are filled from that problem instance.

Parameters:
fileName the name of the file to be read in.
Bug:
there is no check that the columns are constrained to integer values. Neither are there checks to ensure that all bounds and matrix elements are integral. A non-integral input file may lead to strange behaviour without a warning.

Definition at line 78 of file IntegerProgram.cc.

References colBounds, bande::LinearProgram::getColLower(), bande::LinearProgram::getColUpper(), CoinPackedMatrix::getElements(), CoinPackedMatrix::getIndices(), OsiSolverInterface::getMatrixByRow(), getNumCols(), getNumRows(), bande::LinearProgram::getRowLower(), bande::LinearProgram::getRowUpper(), bande::LinearProgram::getSolver(), CoinPackedMatrix::getVectorFirst(), CoinPackedMatrix::getVectorLast(), iSol, lp, m(), matrix, mkInt(), bande::LinearProgram::readMps(), and rowBounds.

Referenced by bande::Settings::run().

void bande::IntegerProgram::setColLower ( UndoManager um,
int  col,
int  val 
)

Set lower bound of a column.

This modification is registered with an undo manager so it can be rewound when switching to a different branch. The bounds may only be tightened, never loosened except through an undo.

Parameters:
um the undo manager to track the modification.
col the index of the column to adjust.
val the new lower bound on the specified column.

Definition at line 113 of file IntegerProgram.cc.

References colBounds, lp, bande::UndoManager::record(), and bande::LinearProgram::setColLower().

Referenced by bande::BranchControl::branch().

void bande::IntegerProgram::setColUpper ( UndoManager um,
int  col,
int  val 
)

Set upper bound of a column.

This modification is registered with an undo manager so it can be rewound when switching to a different branch. The bounds may only be tightened, never loosened except through an undo.

Parameters:
um the undo manager to track the modification.
col the index of the column to adjust.
val the new upper bound on the specified column.

Definition at line 134 of file IntegerProgram.cc.

References colBounds, lp, bande::UndoManager::record(), and bande::LinearProgram::setColUpper().

Referenced by bande::BranchControl::branch().

bool bande::IntegerProgram::solve (  )  [inline]

Find optimal solution to current linear program.

Returns:
whether an optimal solution has been found.

Definition at line 72 of file IntegerProgram.hh.

References lp, and bande::LinearProgram::solve().

Referenced by bande::BranchControl::branch().


Member Data Documentation

std::vector<int> bande::IntegerProgram::iSol [protected]

The solution vector rounded to integers.

This vector is not automatically filled in, but only when mkIntSolution() is called.

Definition at line 176 of file IntegerProgram.hh.

Referenced by checkIntSolution(), getIntSolution(), mkIntSolution(), and readMps().

std::vector<int> bande::IntegerProgram::matrix [protected]

The matrix elements as integers.

The matrix elements are stored in row major mode, and can be accessed through the m() function by giving twodimensional coordinates.

Definition at line 169 of file IntegerProgram.hh.

Referenced by checkIntSolution(), m(), and readMps().


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

Generated on Fri Aug 21 08:17:19 2009 for bande by  doxygen 1.6.0