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
enum	SimplexParam { kAlgPrimal = kLastParam , kAlgPricing , kNumCandList , kHotListSize , kRecomputeFOLimits , kEpsOpt }
	Public enum describing the parameters of MCFSimplex. More...

enum	enumPrcngRl { kDantzig = 0 , kFirstEligibleArc , kCandidateListPivot }
	Public enum describing the pricing rules in MCFSimplex::SetAlg(). More...

Public Types inherited from MCFClass
enum	MCFParam { kMaxTime = 0 , kMaxIter , kEpsFlw , kEpsDfct , kEpsCst , kReopt , kLastParam }
	Public enum describing the possible parameters of the MCF solver, to be used with the methods SetPar() and GetPar(). More...

enum	MCFStatus { kUnSolved = -1 , kOK = 0 , kStopped , kUnfeasible , kUnbounded , kError }
	Public enum describing the possible status of the MCF solver. More...

enum	MCFAnswer { kNo = 0 , kYes }
	Public enum describing the possible reoptimization status of the MCF solver. More...

enum	MCFFlFrmt { kDimacs = 0 , kQDimacs , kMPS , kFWMPS }
	Public enum describing the possible file formats in WriteMCF(). More...

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 (Index nmx=0, Index mmx=0)
	constructor of the class, as in MCFClass::MCFClass()

void	LoadNet (Index nmx=0, Index mmx=0, Index pn=0, Index pm=0, cFRow pU=0, cCRow pC=0, cFRow pDfct=0, cIndex_Set pSn=0, cIndex_Set pEn=0) override
	inputs a new network, as in MCFClass::LoadNet()

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

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

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

virtual void	MCFGetX (FRow F, Index_Set nms=0, Index strt=0, Index stp=Inf< Index >()) const=0
	write the optimal flow solution in a vector

virtual cFRow	MCFGetX (void) const
	return a read-only pointer to the flow solution

virtual void	MCFGetRC (CRow CR, cIndex_Set nms=0, Index strt=0, Index stp=Inf< Index >()) const=0
	write the reduced costs in a vector

virtual cCRow	MCFGetRC (void) const
	return a read-only pointer to an the reduced costs

virtual CNumber	MCFGetRC (Index i) const=0
	return the reduced cost of the i-th arc

virtual void	MCFGetPi (CRow P, cIndex_Set nms=0, Index strt=0, Index stp=Inf< Index >()) const=0
	writes the optimal node potentials in a vector

virtual cCRow	MCFGetPi (void) const
	return a read-only pointer to the node potentials

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

virtual void	LoadDMX (istream &DMXs, bool IsQuad=false)
	read a MCF instance from a stream

virtual void	PreProcess (void)
	pre-process the instamce

virtual void	SetMCFTime (bool TimeIt=true)
	set the timer of the code

int	MCFGetStatus (void) const
	returns the solution status

virtual bool	HaveNewX (void)
	tells if a different flow solution is available

virtual bool	HaveNewPi (void)
	tells if a different dual solution is available

virtual FONumber	MCFGetDFO (void) const
	return the objective function value of the dual solution

virtual FNumber	MCFGetUnfCut (Index_Set Cut) const
	return an unfeasibility certificate

virtual Index	MCFGetUnbCycl (Index_Set Pred, Index_Set ArcPred) const
	return an unboundedness certificate

virtual MCFStatePtr	MCFGetState (void) const
	save the state of the MCF solver

virtual void	MCFPutState (MCFStatePtr S)
	restore the state of the solver

void	TimeMCF (double &t_us, double &t_ss) const
	time the code

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

void	CheckPSol (void) const
	checks the primal solution

void	CheckDSol (void) const
	checks the dual solution

Index	MCFnmax (void) const
	return the maximum number of nodes

Index	MCFmmax (void) const
	return the maximum number of arcs

Index	MCFn (void) const
	return the current number of nodes

Index	MCFm (void) const
	return the current number of arcs

virtual cIndex_Set	MCFSNdes (void) const
	return a read-only pointer to the vector of starting nodes

virtual cIndex_Set	MCFENdes (void) const
	return a read-only pointer to the vector of ending nodes

virtual cCRow	MCFCosts (void) const
	return a read-only pointer to the vector of arc costs

virtual cCRow	MCFQCoef (void) const
	return a read-only pointer to the vector of arc quadratic costs

virtual cFRow	MCFUCaps (void) const
	return a read-only pointer to an the vector of arc capacities

virtual cFRow	MCFDfcts (void) const
	return a read-only pointer to the vector of node deficits

virtual void	WriteMCF (ostream &oStrm, int frmt=0) const
	write the current MCF problem to an ostream

virtual bool	IsDeletedArc (Index name) const =0
	return true if and only if the arc is deleted

virtual	~MCFClass ()
	destructor of the class

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

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

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

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

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

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

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

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.

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.

Note: Unlike what it MCFClass declares as standard, Senstv is false by default in MCFSimplex since reoptimization has some issues that have not been ironed out yet. Set Senstv == true at your own risk.

Member Enumeration Documentation

◆ SimplexParam

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

◆ enumPrcngRl

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.

Member Function Documentation

◆ SetAlg()

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.

◆ SetPar() [1/2]

virtual void SetPar	(	int	par,
		int	val
	)

overridevirtual

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.

◆ SetPar() [2/2]

virtual void SetPar	(	int	par,
		double	val
	)

overridevirtual

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.

◆ MCFGetX() [1/2]

virtual void MCFGetX	(	FRow	F,
		Index_Set	nms = `0`,
		Index	strt = `0`,
		Index	stp = `Inf< Index >()`
	)		const

virtual

write the optimal flow solution in a vector

Write the optimal flow solution in the vector F[]. If nms == 0, F[] will be in "dense" format, i.e., the flow relative to arc ‘i’ (i in 0 .. m - 1) is written in F[ i ]. If nms != 0, F[] will be in "sparse" format, i.e., the indices of the nonzero elements in the flow solution are written in nms (that is then Inf< Index >()-terminated) and the flow value of arc nms[ i ] is written in F[ i ]. Note that nms is not* guaranteed to be ordered. Also, note that, unlike MCFGetRC() and MCFGetPi() [see below], nms is an output of the method.

The parameters ‘strt’ and ‘stp’ allow to restrict the output of the method to all and only the arcs ‘i’ with strt <= i < min( MCFm() , stp ).

Implements MCFClass.

◆ MCFGetX() [2/2]

virtual cFRow MCFGetX ( void ) const

inlinevirtual

return a read-only pointer to the flow solution

Return a read-only pointer to an internal data structure containing the flow solution in "dense" format. Since this may not always be available, depending on the implementation, this method can (uniformly) return 0. This is done by the base class already, so a derived class that does not have the information ready does not need to implement the method.

Reimplemented from MCFClass.

◆ MCFGetRC() [1/3]

virtual void MCFGetRC	(	CRow	CR,
		cIndex_Set	nms = `0`,
		Index	strt = `0`,
		Index	stp = `Inf< Index >()`
	)		const

virtual

write the reduced costs in a vector

Write the reduced costs corresponding to the current dual solution in RC[]. If nms == 0, the reduced cost of arc ‘i’ (i in 0 .. m - 1) is written in RC[ i ]; if nms != 0, it must point to a vector of indices in 0 .. m - 1 (ordered in increasing sense and Inf< Index >()-terminated), and the reduced cost of arc nms[ i ] is written in RC[ i ]. Note that, unlike MCFGetX() above, nms is an input of the method.

The parameters ‘strt’ and ‘stp’ allow to restrict the output of the method to all and only the arcs ‘i’ with strt <= i < min( MCFm() , stp ). ‘strt’ and ‘stp’ work in "&&" with nms; that is, if nms != 0 then only the values corresponding to arcs which are both in nms[] and whose index is in the correct range are returned.

Note: the output of MCFGetRC() will change after any call to HaveNewPi() [see above] which returns true.

Implements MCFClass.

◆ MCFGetRC() [2/3]

virtual cCRow MCFGetRC ( void ) const

inlinevirtual

return a read-only pointer to an the reduced costs

Return a read-only pointer to an internal data structure containing the reduced costs. Since this may not always be available, depending on the implementation, this method can (uniformly) return 0. This is done by the base class already, so a derived class that does not have the information ready does not need to implement the method.

Note: the output of MCFGetRC() will change after any call to HaveNewPi() which returns true.

Reimplemented from MCFClass.

◆ MCFGetRC() [3/3]

virtual CNumber MCFGetRC ( Index i ) const

virtual

return the reduced cost of the i-th arc

Return the reduced cost of the i-th arc. This information should be cheapily available in most implementations.

Note: the output of MCFGetRC() will change after any call to HaveNewPi() which returns true.

Implements MCFClass.

◆ MCFGetPi() [1/2]

virtual void MCFGetPi	(	CRow	P,
		cIndex_Set	nms = `0`,
		Index	strt = `0`,
		Index	stp = `Inf< Index >()`
	)		const

virtual

writes the optimal node potentials in a vector

Writes the optimal node potentials in the vector P[]. If nms == 0, the node potential of node ‘i’ (i in 0 .. n - 1) is written in P[ i ] (note that here node names always start from zero, regardless to the value of USENAME0). If nms != 0, it must point to a vector of indices in 0 .. n - 1 (ordered in increasing sense and Inf< Index >()-terminated), and the node potential of nms[ i ] is written in P[ i ]. Note that, unlike MCFGetX() above, nms is an input of the method.

The parameters ‘strt’ and ‘stp’ allow to restrict the output of the method to all and only the nodes ‘i’ with strt <= i < min( MCFn() , stp ). ‘strt’ and ‘stp’ work in "&&" with nms; that is, if nms != 0 then only the values corresponding to nodes which are both in nms[] and whose index is in the correct range are returned.

Implements MCFClass.

◆ MCFGetPi() [2/2]

virtual cCRow MCFGetPi ( void ) const

inlinevirtual

return a read-only pointer to the node potentials

Return a read-only pointer to an internal data structure containing the node potentials. Since this may not always be available, depending on the implementation, this method can (uniformly) return 0. This is done by the base class already, so a derived class that does not have the information ready does not need to implement the method.

Reimplemented from MCFClass.

Public Types

Public Member Functions

Additional Inherited Members

Detailed Description

Member Enumeration Documentation

◆ SimplexParam

◆ enumPrcngRl

Member Function Documentation

◆ SetAlg()

◆ SetPar() [1/2]

◆ SetPar() [2/2]

◆ MCFGetX() [1/2]

◆ MCFGetX() [2/2]

◆ MCFGetRC() [1/3]

◆ MCFGetRC() [2/3]

◆ MCFGetRC() [3/3]

◆ MCFGetPi() [1/2]

◆ MCFGetPi() [2/2]