The MCFSimplex class derives from the abstract base class MCFClass, thus sharing its (standard) interface, and implements both the Primal and Dual network simplex algorithms for solving (Linear and Quadratic) Min Cost Flow problems. More...

#include <MCFSimplex.h>

Inheritance diagram for MCFSimplex:

Public Types
Public Types inherited from MCFClass
typedef unsigned int	Index
	index of a node or arc ( >= 0 )

typedef Index *	Index_Set
	set (array) of indices

typedef const Index	cIndex
	a read-only index

typedef cIndex *	cIndex_Set
	read-only index array

typedef double	FNumber
	type of arc flow

typedef FNumber *	FRow
	vector of flows

typedef const FNumber	cFNumber
	a read-only flow

typedef cFNumber *	cFRow
	read-only flow array

typedef double	CNumber
	type of arc flow cost

typedef CNumber *	CRow
	vector of costs

typedef const CNumber	cCNumber
	a read-only cost

typedef cCNumber *	cCRow
	read-only cost array

typedef double	FONumber
	type of the objective function: has to hold sums of products of FNumber(s) by CNumber(s)

typedef const FONumber	cFONumber
	a read-only o.f. value

typedef MCFState *	MCFStatePtr
	pointer to a MCFState

Public Member Functions
	MCFSimplex (cIndex nmx=0, cIndex mmx=0)
	Constructor of the class, as in MCFClass::MCFClass(). More...

void	LoadNet (cIndex nmx=0, cIndex mmx=0, cIndex pn=0, cIndex pm=0, cFRow pU=NULL, cCRow pC=NULL, cFRow pDfct=NULL, cIndex_Set pSn=NULL, cIndex_Set pEn=NULL)
	Inputs a new network, as in MCFClass::LoadNet(). More...

void	SetAlg (bool UsPrml, char WhchPrc)
	Selects which algorithm (Primal vs Dual Network Simplex), and which pricing rule within the algorithm, is used. More...

void	SetPar (int par, int val)
	Set general integer parameters. More...

void	SetPar (int par, double val)
	Set general float parameters. More...

Public Member Functions inherited from MCFClass
	MCFClass (cIndex nmx=0, cIndex mmx=0)
	Constructor of the class. More...

virtual void	LoadDMX (istream &DMXs, bool IsQuad=false)
	Read a MCF instance in DIMACS standard format from the istream. More...

virtual void	PreProcess (void)
	Extract a smaller/easier equivalent MCF problem. More...

virtual void	GetPar (int par, int &val)
	This method returns one of the integer parameter of the algorithm. More...

virtual void	GetPar (int par, double &val)
	This method returns one of the integer parameter of the algorithm. More...

virtual void	SetMCFTime (bool TimeIt=true)
	Allocate an OPTtimers object [see OPTtypes.h] to be used for timing the methods of the class. More...

int	MCFGetStatus (void)
	Returns an int describing the current status of the MCF solver. More...

virtual cFRow	MCFGetX (void)
	Return a read-only pointer to an internal data structure containing the flow solution in "dense" format. More...

virtual bool	HaveNewX (void)
	Return true if a different (approximately) optimal primal solution is available. More...

virtual cCRow	MCFGetPi (void)
	Return a read-only pointer to an internal data structure containing the node potentials. More...

virtual bool	HaveNewPi (void)
	Return true if a different (approximately) optimal dual solution is available. More...

virtual cCRow	MCFGetRC (void)
	Return a read-only pointer to an internal data structure containing the reduced costs. More...

virtual FONumber	MCFGetDFO (void)
	Return the objective function value of the dual solution currently returned by MCFGetPi() / MCFGetRC(). More...

virtual FNumber	MCFGetUnfCut (Index_Set Cut)
	Return an unfeasibility certificate. More...

virtual Index	MCFGetUnbCycl (Index_Set Pred, Index_Set ArcPred)
	Return an unboundedness certificate. More...

virtual MCFStatePtr	MCFGetState (void)
	Save the state of the MCF solver. More...

virtual void	MCFPutState (MCFStatePtr S)
	Restore the solver to the state in which it was when the state `S' was created with MCFGetState() [see above]. More...

void	TimeMCF (double &t_us, double &t_ss)
	Time the code. More...

double	TimeMCF (void)
	Like TimeMCF(double,double) [see above], but returns the total time. More...

void	CheckPSol (void)
	Check that the primal solution returned by the solver is primal feasible. More...

void	CheckDSol (void)
	Check that the dual solution returned by the solver is dual feasible. More...

Index	MCFnmax (void)
	Return the maximum number of nodes for this instance of MCFClass. More...

Index	MCFmmax (void)
	Return the maximum number of arcs for this instance of MCFClass. More...

Index	MCFn (void)
	Return the number of nodes in the current graph. More...

Index	MCFm (void)
	Return the number of arcs in the current graph. More...

virtual cIndex_Set	MCFSNdes (void)
	Return a read-only pointer to an internal vector containing the starting (tail) nodes for each arc. More...

virtual cIndex_Set	MCFENdes (void)
	Return a read-only pointer to an internal vector containing the ending (head) nodes for each arc. More...

virtual cCRow	MCFCosts (void)
	Return a read-only pointer to an internal vector containing the arc costs. More...

virtual cCRow	MCFQCoef (void)
	Return a read-only pointer to an internal vector containing the arc costs. More...

virtual cFRow	MCFUCaps (void)
	Return a read-only pointer to an internal vector containing the arc capacities. More...

virtual cFRow	MCFDfcts (void)
	Return a read-only pointer to an internal vector containing the node deficits. More...

virtual void	WriteMCF (ostream &oStrm, int frmt=0)
	Write the current MCF problem to an ostream. More...

virtual	~MCFClass ()
	Destructor of the class. More...

Additional Inherited Members
Protected Member Functions inherited from MCFClass
template<class T >
bool	ETZ (T x, const T eps)
	true if flow x is equal to zero (possibly considering tolerances). More...

template<class T >
bool	GTZ (T x, const T eps)
	true if flow x is greater than zero (possibly considering tolerances). More...

template<class T >
bool	GEZ (T x, const T eps)
	true if flow x is greater than or equal to zero (possibly considering tolerances). More...

template<class T >
bool	LTZ (T x, const T eps)
	true if flow x is less than zero (possibly considering tolerances). More...

template<class T >
bool	LEZ (T x, const T eps)
	true if flow x is less than or equal to zero (possibly considering tolerances). More...

template<class T >
bool	GT (T x, T y, const T eps)
	true if flow x is greater than flow y (possibly considering tolerances).

template<class T >
bool	LT (T x, T y, const T eps)
	true if flow x is less than flow y (possibly considering tolerances). More...

Protected Attributes inherited from MCFClass
Index	n
	total number of nodes

Index	nmax
	maximum number of nodes

Index	m
	total number of arcs

Index	mmax
	maximum number of arcs

int	status
	return status, see the comments to MCFGetStatus() above. More...

bool	Senstv
	true <=> the latest optimal solution should be exploited

OPTtimers *	MCFt
	timer for performances evaluation

FNumber	EpsFlw
	precision for comparing arc flows / capacities

FNumber	EpsDfct
	precision for comparing node deficits

CNumber	EpsCst
	precision for comparing arc costs

double	MaxTime
	max time (in seconds) in which MCF Solver can find an optimal solution (0 = no limits)

int	MaxIter
	max number of iterations in which MCF Solver can find an optimal solution (0 = no limits)

Detailed Description

The MCFSimplex class derives from the abstract base class MCFClass, thus sharing its (standard) interface, and implements both the Primal and Dual network simplex algorithms for solving (Linear and Quadratic) Min Cost Flow problems.

Member Enumeration Documentation

enum SimplexParam

Public enum describing the parameters of MCFSimplex.

Enumerator
kAlgPrimal	parameter to set algorithm (Primal/Dual):
kAlgPricing	parameter to set algorithm of pricing
kNumCandList	parameter to set the number of candidate list for Candidate List Pivot method
kHotListSize	parameter to set the size of Hot List for Candidate List Pivot method
kRecomputeFOLimits	parameter to set the number of iterations in which quadratic Primal Simplex computes "manually" the f.o. value
kEpsOpt	parameter to set the precision of the objective function value for the quadratic Primal Simplex

enum enumPrcngRl

Public enum describing the pricing rules in MCFSimplex::SetAlg().

Enumerator
kDantzig	Dantzig's rule (most violated constraint)
kFirstEligibleArc	First eligible arc in round-robin.
kCandidateListPivot	Candidate List Pivot Rule.

Constructor & Destructor Documentation

MCFSimplex	(	cIndex	nmx = `0`,
		cIndex	mmx = `0`
	)

Constructor of the class, as in MCFClass::MCFClass().

Member Function Documentation

void LoadNet	(	cIndex	nmx = `0`,
		cIndex	mmx = `0`,
		cIndex	pn = `0`,
		cIndex	pm = `0`,
		cFRow	pU = `NULL`,
		cCRow	pC = `NULL`,
		cFRow	pDfct = `NULL`,
		cIndex_Set	pSn = `NULL`,
		cIndex_Set	pEn = `NULL`
	)

virtual

Inputs a new network, as in MCFClass::LoadNet().

Implements MCFClass.

void SetAlg	(	bool	UsPrml,
		char	WhchPrc
	)

Selects which algorithm (Primal vs Dual Network Simplex), and which pricing rule within the algorithm, is used.

If UsPrml == TRUE then the Primal Network Simplex algorithm is used, otherwise the Dual Network Simplex is used.

The allowed values for WhchPrc are:

kDantzig Dantzig's pricing rule, i.e., most violated dual constraint; this can only be used with the Primal Network Simplex
kFirstEligibleArcA "dumb" rule, first eligible arc in round-robin;
kCandidateListPivot Candidate List Pivot Rule

If this method is not called, the Primal Network Simplex with the Candidate List Pivot Rule (the best setting on most instances) is used.

void SetPar	(	int	par,
		int	val
	)

virtual

Set general integer parameters.

Parameters

par	is the parameter to set; since this method accepts an int value, the enum SimplexParam can be used in addition to the enum MCFParam to specify the integer parameters (every enum is an int).
value	is the value to assign to the parameter.

Reimplemented from MCFClass.

void SetPar	(	int	par,
		double	val
	)

virtual

Set general float parameters.

Parameters

par	is the parameter to set; since this method accepts an int value, the enum SimplexParam can be used in addition to the enum MCFParam to specify the float parameters (every enum is an int).
value	is the value to assign to the parameter.

Reimplemented from MCFClass.

Public Types

Public Member Functions

Additional Inherited Members

Detailed Description

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation