LAP::CglLandPSimplex Class Reference

#include <CglLandPSimplex.hpp>

Collaboration diagram for LAP::CglLandPSimplex:

Classes
struct	extraInfo
struct	TabRow
Public Member Functions
	CglLandPSimplex (const OsiSolverInterface &si, const CglLandP::CachedData &cached, bool reducedSpace, int numPivots)
	Usefull onstructor.
	~CglLandPSimplex ()
	Destructor.
void	cacheUpdate (const CglLandP::CachedData &cached, bool reducedSpace=0)
	Update cached information in case of basis change in a round.
bool	resetSolver (const CoinWarmStartBasis *basis)
	reset the solver to optimal basis
bool	findBestCut (int var, OsiRowCut &cut, const CglLandP::CachedData &cached, const CglLandP::Parameters &params)
	Perfom pivots to find the best cuts.
bool	generateMig (int row, OsiRowCut &cut, const CglLandP::CachedData &cached, const CglLandP::Parameters &params) const
	Find Gomory cut (i.e.
	CglLandPSimplex ()
	No default constructor.
void	setLogLevel (int level)
void	setSi (OsiSolverInterface *si)
void	freeSi ()
Public Attributes
extraInfo	extra
Protected Member Functions
bool	changeBasis (int incoming, int leaving, int direction)
	Perform a change in the basis (direction is 1 if leaving variable is going to ub, 0 otherwise).
int	findCutImprovingPivotRow (int &direction, int &gammaSign, double tolerance)
	Find a row which can be used to perform an improving pivot return index of the cut or -1 if none exists (i.e., find the leaving variable).
int	fastFindCutImprovingPivotRow (int &direction, int &gammaSign, double tolerance)
	Find a row which can be used to perform an improving pivot the fast way (i.e., find the leaving variable).
int	rescanReducedCosts (int &direction, int &gammaSign, double tolerance)
	Rescan reduced costs tables.
int	fastFindBestPivotColumn (int direction, int gammaSign, double pivotTol, double rhsTol, bool reducedSpace, bool allowNonImproving, double &bestSigma)
	Find the column which leads to the best cut (i.e., find incoming variable).
int	findBestPivotColumn (int direction, double pivotTol, bool reducedSpace, bool allowDegeneratePivot, bool modularize)
	Find the column which leads to the best cut (i.e., find incoming variable).
int	findBestPivot (int &leaving, int &direction, const CglLandP::Parameters &params)
	Find incoming and leaving variables which lead to the most violated adjacent normalized lift-and-project cut.
double	computeCglpObjective (double gamma, bool strengthen)
	Compute the objective value of the Cglp with linear combintation of the two rows by gamma.
double	computeCglpObjective (TabRow &row) const
	Compute the objective value of the Cglp for given row and rhs (if strengthening shall be applied row should have been modularized).
double	intersectionCutCoef (double alpha_i, double beta) const
	return the coefficients of the intersection cut
double	strengthenedIntersectionCutCoef (int i, double alpha_i, double beta) const
	return the coefficients of the strengthened intersection cut takes one extra argument seens needs to consider variable type.
double	newRowCoefficient (int j, double gamma) const
	return the coefficient of the new row (combining row_k + gamma row_i).
double	modularizedCoef (double alpha, double beta) const
	compute the modularized row coefficient for an integer variable (does not check integrity
double	computeCglpRedCost (int direction, int gammaSign)
	Compute the reduced cost of Cglp.
void	computeRedCostConstantsInRow ()
	Compute the value of sigma and thau (which are constants for a row i as defined in Mike Perregaard thesis.
void	createIntersectionCut (const TabRow &row, OsiRowCut &cut) const
	Create the intersection cut of row k.
void	createMIG (TabRow &row, OsiRowCut &cut) const
	Create strenghtened row.
double	normCoef (TabRow &row)
	Compute normalization coefficient corresponding to sum of multipliers for cuts derived from row.
void	scale (OsiRowCut &cut, double norma)
	scale the cut passed as argument using provided normalization factor
void	scale (OsiRowCut &cut)
	scale the cut passed as argument
void	modularizeRow (TabRow &row)
	Modularize row.
void	pullTableauRow (TabRow &row) const
	Get the row i of the tableau.
void	adjustTableauRow (int var, TabRow &row, int direction)
	Adjust the row of the tableau to reflect leaving variable direction.
void	resetOriginalTableauRow (int var, TabRow &row, int direction)
	reset the tableau row after a call to adjustTableauRow
double	getLoBound (int index)
	Get lower bound for variable or constraint.
double	getUpBound (int index)
	Get upper bound for variable or constraint.
void	printTableau (std::ostream &os)
	print the tableau of current basis.
Private Types
enum	lpSolver { clp, cplex, xpress }
Private Member Functions
void	updateM1_M2_M3 (TabRow &row, double tolerance, bool recucedSpace, bool alwaysComputeCheap)
Private Attributes
lpSolver	solver_
bool	own_
	Own the data or not?
int	nNegativeRc_
	number of negative reduced costs in current iteration
int	nNegativeRcRows_
	number of rows with a <0 rc in current iteration
CoinMessageHandler *	handler_
	Message handler.
CoinMessages	messages_
	Messages.
Work infos

CglLandPSimplex::TabRow	row_k_
	Source row for cut.
CglLandPSimplex::TabRow	perturbed_row_k_
	Perturbed source row.
CglLandPSimplex::TabRow	row_i_
	Row of leaving candidate.
CglLandPSimplex::TabRow	newRow_
	Stores the new row.
CoinPackedVector	gammas_
	vector to sort the gammas
double *	rWk1_
	first work vector in row space.
double *	rWk2_
	scond work vector in row space.
double *	rWk3_
	third work vector in row space.
double *	rWk4_
	fourth work vector in row space.
int *	rIntWork_
	integer valued work vector on the rows
bool *	rowFlags_
	Flag rows which we don't want to try anymore.
bool *	colHasToComputeContrib_
	Flag columns for which contribution has to be computed in reduced cost(if in reduced space remove nonbasic structurals).
bool *	colCandidateToLeave_
	Flag columns which have to be considered for leaving the basis.
int *	basics_
	Store the basics variable.
int *	nonBasics_
	Stores the nonBasicVariables.
int *	inM1_
	Stores the variables which are always in M1 for a given k.
int *	inM2_
	Stores the variables which are always in M2 for a given k.
int *	inM3_
	Stores the variables which could be either in M1 or M2.
double	tau_
	temporarily stores the value of thau for the current row
double	sigma_
	stores the cglp value of the normalized cut obtained from row k_
CoinWarmStartBasis	basis_
	Keep track of basis status.
double *	colsolToCut_
	Pointer to the solution to cut (need to be modified after each pivot because we are only considering slacks).
double *	colsol_
	Pointer to the current basic solution.
int	numcols_
	cached numcols
int	numrows_
	cached numrows
double *	loBounds_
	Source row for cut.
double *	upBounds_
	Source row for cut.
bool	inDegenerateSequence_
	Say if we are in a sequence of degenerate pivots.
double	chosenReducedCostVal_
	Value for the reduced cost chosen for pivoting.
const bool *	integers_
	pointer to array of integer info for both structural and slacks
Interfaces to the solver

OsiSolverInterface *	si_
	Pointer to the solver interface.

Detailed Description

Definition at line 53 of file CglLandPSimplex.hpp.

Member Enumeration Documentation

enum LAP::CglLandPSimplex::lpSolver [private]

Enumerator:

clp
cplex
xpress

Definition at line 248 of file CglLandPSimplex.hpp.

Constructor & Destructor Documentation

LAP::CglLandPSimplex::CglLandPSimplex	(	const OsiSolverInterface &	si,
		const CglLandP::CachedData &	cached,
		bool	reducedSpace,
		int	numPivots
	)

Usefull onstructor.

LAP::CglLandPSimplex::~CglLandPSimplex ( )

Destructor.

LAP::CglLandPSimplex::CglLandPSimplex ( ) [inline]

No default constructor.

Definition at line 115 of file CglLandPSimplex.hpp.

Member Function Documentation

void LAP::CglLandPSimplex::cacheUpdate	(	const CglLandP::CachedData &	cached,
		bool	reducedSpace = `0`
	)

Update cached information in case of basis change in a round.

bool LAP::CglLandPSimplex::resetSolver ( const CoinWarmStartBasis * basis )

reset the solver to optimal basis

bool LAP::CglLandPSimplex::findBestCut	(	int	var,
		OsiRowCut &	cut,
		const CglLandP::CachedData &	cached,
		const CglLandP::Parameters &	params
	)

Perfom pivots to find the best cuts.

bool LAP::CglLandPSimplex::generateMig	(	int	row,
		OsiRowCut &	cut,
		const CglLandP::CachedData &	cached,
		const CglLandP::Parameters &	params
	)			const

Find Gomory cut (i.e.

don't do extra setup required for pivots).

void LAP::CglLandPSimplex::setLogLevel ( int level ) [inline]

Definition at line 123 of file CglLandPSimplex.hpp.

void LAP::CglLandPSimplex::setSi ( OsiSolverInterface * si ) [inline]

Definition at line 127 of file CglLandPSimplex.hpp.

void LAP::CglLandPSimplex::freeSi ( ) [inline]

Definition at line 129 of file CglLandPSimplex.hpp.

bool LAP::CglLandPSimplex::changeBasis	(	int	incoming,
		int	leaving,
		int	direction
	)			`[protected]`

Perform a change in the basis (direction is 1 if leaving variable is going to ub, 0 otherwise).

int LAP::CglLandPSimplex::findCutImprovingPivotRow	(	int &	direction,
		int &	gammaSign,
		double	tolerance
	)			`[protected]`

Find a row which can be used to perform an improving pivot return index of the cut or -1 if none exists (i.e., find the leaving variable).

int LAP::CglLandPSimplex::fastFindCutImprovingPivotRow	(	int &	direction,
		int &	gammaSign,
		double	tolerance
	)			`[protected]`

Find a row which can be used to perform an improving pivot the fast way (i.e., find the leaving variable).

Returns:: index of the cut or -1 if none exists.

int LAP::CglLandPSimplex::rescanReducedCosts	(	int &	direction,
		int &	gammaSign,
		double	tolerance
	)			`[protected]`

Rescan reduced costs tables.

int LAP::CglLandPSimplex::fastFindBestPivotColumn	(	int	direction,
		int	gammaSign,
		double	pivotTol,
		double	rhsTol,
		bool	reducedSpace,
		bool	allowNonImproving,
		double &	bestSigma
	)			`[protected]`

Find the column which leads to the best cut (i.e., find incoming variable).

int LAP::CglLandPSimplex::findBestPivotColumn	(	int	direction,
		double	pivotTol,
		bool	reducedSpace,
		bool	allowDegeneratePivot,
		bool	modularize
	)			`[protected]`

Find the column which leads to the best cut (i.e., find incoming variable).

int LAP::CglLandPSimplex::findBestPivot	(	int &	leaving,
		int &	direction,
		const CglLandP::Parameters &	params
	)			`[protected]`

Find incoming and leaving variables which lead to the most violated adjacent normalized lift-and-project cut.

Remarks:: At this point reduced costs should be already computed.

Returns:: incoming variable variable,

Parameters:

	leaving	variable
	direction	leaving direction
	numTryRows	number rows tried
	pivotTol	pivot tolerance
	reducedSpace	separaration space (reduced or full)
	allowNonStrictlyImproving	wether or not to allow non stricly improving pivots.

double LAP::CglLandPSimplex::computeCglpObjective	(	double	gamma,
		bool	strengthen
	)			`[protected]`

Compute the objective value of the Cglp with linear combintation of the two rows by gamma.

double LAP::CglLandPSimplex::computeCglpObjective ( TabRow & row ) const [protected]

Compute the objective value of the Cglp for given row and rhs (if strengthening shall be applied row should have been modularized).

double LAP::CglLandPSimplex::intersectionCutCoef	(	double	alpha_i,
		double	beta
	)			const `[inline, protected]`

return the coefficients of the intersection cut

Definition at line 407 of file CglLandPSimplex.hpp.

double LAP::CglLandPSimplex::strengthenedIntersectionCutCoef	(	int	i,
		double	alpha_i,
		double	beta
	)			const `[inline, protected]`

return the coefficients of the strengthened intersection cut takes one extra argument seens needs to consider variable type.

return the coefficients of the strengthened intersection cut

Definition at line 415 of file CglLandPSimplex.hpp.

double LAP::CglLandPSimplex::newRowCoefficient	(	int	j,
		double	gamma
	)			const `[inline, protected]`

return the coefficient of the new row (combining row_k + gamma row_i).

Definition at line 433 of file CglLandPSimplex.hpp.

double LAP::CglLandPSimplex::modularizedCoef	(	double	alpha,
		double	beta
	)			const `[inline, protected]`

compute the modularized row coefficient for an integer variable (does not check integrity

compute the modularized row coefficient for an integer variable

Bug:: not the same as in Ionut's pseudo code, it is not the same

Definition at line 440 of file CglLandPSimplex.hpp.

double LAP::CglLandPSimplex::computeCglpRedCost	(	int	direction,
		int	gammaSign
	)			`[protected]`

Compute the reduced cost of Cglp.

void LAP::CglLandPSimplex::computeRedCostConstantsInRow ( ) [protected]

Compute the value of sigma and thau (which are constants for a row i as defined in Mike Perregaard thesis.

void LAP::CglLandPSimplex::createIntersectionCut	(	const TabRow &	row,
		OsiRowCut &	cut
	)			const `[protected]`

Create the intersection cut of row k.

void LAP::CglLandPSimplex::createMIG	(	TabRow &	row,
		OsiRowCut &	cut
	)			const `[protected]`

Create strenghtened row.

Create MIG cut from row k

double LAP::CglLandPSimplex::normCoef ( TabRow & row ) [protected]

Compute normalization coefficient corresponding to sum of multipliers for cuts derived from row.

void LAP::CglLandPSimplex::scale	(	OsiRowCut &	cut,
		double	norma
	)			`[protected]`

scale the cut passed as argument using provided normalization factor

void LAP::CglLandPSimplex::scale ( OsiRowCut & cut ) [protected]

scale the cut passed as argument

void LAP::CglLandPSimplex::modularizeRow ( TabRow & row ) [protected]

Modularize row.

void LAP::CglLandPSimplex::pullTableauRow ( TabRow & row ) const [protected]

Get the row i of the tableau.

void LAP::CglLandPSimplex::adjustTableauRow	(	int	var,
		TabRow &	row,
		int	direction
	)			`[protected]`

Adjust the row of the tableau to reflect leaving variable direction.

void LAP::CglLandPSimplex::resetOriginalTableauRow	(	int	var,
		TabRow &	row,
		int	direction
	)			`[protected]`

reset the tableau row after a call to adjustTableauRow

double LAP::CglLandPSimplex::getLoBound ( int index ) [inline, protected]

Get lower bound for variable or constraint.

Definition at line 241 of file CglLandPSimplex.hpp.

double LAP::CglLandPSimplex::getUpBound ( int index ) [inline, protected]

Get upper bound for variable or constraint.

Definition at line 243 of file CglLandPSimplex.hpp.

void LAP::CglLandPSimplex::printTableau ( std::ostream & os ) [protected]

print the tableau of current basis.

void LAP::CglLandPSimplex::updateM1_M2_M3	(	TabRow &	row,
		double	tolerance,
		bool	recucedSpace,
		bool	alwaysComputeCheap
	)			`[private]`

Member Data Documentation

extraInfo LAP::CglLandPSimplex::extra [mutable]

Definition at line 156 of file CglLandPSimplex.hpp.

lpSolver LAP::CglLandPSimplex::solver_ [private]

Definition at line 249 of file CglLandPSimplex.hpp.

CglLandPSimplex::TabRow LAP::CglLandPSimplex::row_k_ [mutable, private]

Source row for cut.

Definition at line 255 of file CglLandPSimplex.hpp.

CglLandPSimplex::TabRow LAP::CglLandPSimplex::perturbed_row_k_ [private]

Perturbed source row.

Definition at line 257 of file CglLandPSimplex.hpp.

CglLandPSimplex::TabRow LAP::CglLandPSimplex::row_i_ [private]

Row of leaving candidate.

Definition at line 259 of file CglLandPSimplex.hpp.

CglLandPSimplex::TabRow LAP::CglLandPSimplex::newRow_ [private]

Stores the new row.

Definition at line 261 of file CglLandPSimplex.hpp.

CoinPackedVector LAP::CglLandPSimplex::gammas_ [private]

vector to sort the gammas

Definition at line 263 of file CglLandPSimplex.hpp.

double* LAP::CglLandPSimplex::rWk1_ [private]

first work vector in row space.

Definition at line 265 of file CglLandPSimplex.hpp.

double* LAP::CglLandPSimplex::rWk2_ [private]

scond work vector in row space.

Definition at line 267 of file CglLandPSimplex.hpp.

double* LAP::CglLandPSimplex::rWk3_ [private]

third work vector in row space.

Definition at line 269 of file CglLandPSimplex.hpp.

double* LAP::CglLandPSimplex::rWk4_ [private]

fourth work vector in row space.

Definition at line 271 of file CglLandPSimplex.hpp.

int* LAP::CglLandPSimplex::rIntWork_ [private]

integer valued work vector on the rows

Definition at line 273 of file CglLandPSimplex.hpp.

bool* LAP::CglLandPSimplex::rowFlags_ [private]

Flag rows which we don't want to try anymore.

Definition at line 275 of file CglLandPSimplex.hpp.

bool* LAP::CglLandPSimplex::colHasToComputeContrib_ [private]

Flag columns for which contribution has to be computed in reduced cost(if in reduced space remove nonbasic structurals).

Definition at line 277 of file CglLandPSimplex.hpp.

bool* LAP::CglLandPSimplex::colCandidateToLeave_ [private]

Flag columns which have to be considered for leaving the basis.

Definition at line 279 of file CglLandPSimplex.hpp.

int* LAP::CglLandPSimplex::basics_ [private]

Store the basics variable.

Definition at line 281 of file CglLandPSimplex.hpp.

int* LAP::CglLandPSimplex::nonBasics_ [private]

Stores the nonBasicVariables.

Definition at line 283 of file CglLandPSimplex.hpp.

int* LAP::CglLandPSimplex::inM1_ [private]

Stores the variables which are always in M1 for a given k.

Definition at line 285 of file CglLandPSimplex.hpp.

int* LAP::CglLandPSimplex::inM2_ [private]

Stores the variables which are always in M2 for a given k.

Definition at line 287 of file CglLandPSimplex.hpp.

int* LAP::CglLandPSimplex::inM3_ [private]

Stores the variables which could be either in M1 or M2.

Definition at line 289 of file CglLandPSimplex.hpp.

double LAP::CglLandPSimplex::tau_ [private]

temporarily stores the value of thau for the current row

Definition at line 291 of file CglLandPSimplex.hpp.

double LAP::CglLandPSimplex::sigma_ [private]

stores the cglp value of the normalized cut obtained from row k_

Definition at line 293 of file CglLandPSimplex.hpp.

CoinWarmStartBasis LAP::CglLandPSimplex::basis_ [private]

Keep track of basis status.

Definition at line 295 of file CglLandPSimplex.hpp.

double* LAP::CglLandPSimplex::colsolToCut_ [private]

Pointer to the solution to cut (need to be modified after each pivot because we are only considering slacks).

Definition at line 297 of file CglLandPSimplex.hpp.

double* LAP::CglLandPSimplex::colsol_ [private]

Pointer to the current basic solution.

Definition at line 299 of file CglLandPSimplex.hpp.

int LAP::CglLandPSimplex::numcols_ [private]

cached numcols

Definition at line 301 of file CglLandPSimplex.hpp.

int LAP::CglLandPSimplex::numrows_ [private]

cached numrows

Definition at line 303 of file CglLandPSimplex.hpp.

double* LAP::CglLandPSimplex::loBounds_ [private]

Source row for cut.

Definition at line 305 of file CglLandPSimplex.hpp.

double* LAP::CglLandPSimplex::upBounds_ [private]

Source row for cut.

Definition at line 307 of file CglLandPSimplex.hpp.

bool LAP::CglLandPSimplex::inDegenerateSequence_ [private]

Say if we are in a sequence of degenerate pivots.

Definition at line 309 of file CglLandPSimplex.hpp.

double LAP::CglLandPSimplex::chosenReducedCostVal_ [private]

Value for the reduced cost chosen for pivoting.

Definition at line 311 of file CglLandPSimplex.hpp.

const bool* LAP::CglLandPSimplex::integers_ [private]

pointer to array of integer info for both structural and slacks

Definition at line 313 of file CglLandPSimplex.hpp.

OsiSolverInterface* LAP::CglLandPSimplex::si_ [private]

Pointer to the solver interface.

Definition at line 318 of file CglLandPSimplex.hpp.

bool LAP::CglLandPSimplex::own_ [private]

Own the data or not?

Definition at line 321 of file CglLandPSimplex.hpp.

int LAP::CglLandPSimplex::nNegativeRc_ [private]

number of negative reduced costs in current iteration

Definition at line 325 of file CglLandPSimplex.hpp.

int LAP::CglLandPSimplex::nNegativeRcRows_ [private]

number of rows with a <0 rc in current iteration

Definition at line 327 of file CglLandPSimplex.hpp.

CoinMessageHandler* LAP::CglLandPSimplex::handler_ [private]

Message handler.

Definition at line 400 of file CglLandPSimplex.hpp.

CoinMessages LAP::CglLandPSimplex::messages_ [private]

Messages.

Definition at line 402 of file CglLandPSimplex.hpp.

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

/home/coin/svn-release/OptimizationSuite-1.1.0/Cgl/src/CglLandP/CglLandPSimplex.hpp

LAP::CglLandPSimplex Class Reference

Classes

Public Member Functions

Public Attributes

Protected Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation