The MCFCplex class derives from the abstract base class MCFClass, thus sharing its (standard) interface, and solves (Linear) Min Cost Flow problems via calls to Cplex Callable Library functions. More...

#include <MCFCplex.h>

Inheritance diagram for MCFCplex:

Public Types
enum	MCFCParam { kQPMethod = kLastParam }
	Public enum describing the possible parameters of the MCF solver, "extended" from MCFClass::MCFParam, to be used with the methods SetPar() and GetPar(). More...

enum	QPMethod
	enum describing possible ways for solving QP problem: see the Cplex manual for details

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
	MCFCplex (cIndex nmx=0, cIndex mmx=0)
	Constructor of the class.

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) override
	Inputs a new network, as in MCFClass::LoadNet().

void	SetPar (int par, int val) override
	Set integer parameters of the algorithm.

void	SetPar (int par, double val) override
	Set float parameters of the algorithm.

void	GetPar (int par, int &val) const override
	Returns one of the integer parameters of the algorithm.

void	GetPar (int par, double &val) const override
	Returns one of the double parameters of the algorithm.

CPXENVptr	GetCplexEnv (void) const
	returns a pointer to the internal Cplex environment

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	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)=0
	inputs a new network from memory

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 void	ChgDfct (Index node, FNumber NDfct)=0
	change the deficit of the i-th node

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 MCFCplex class derives from the abstract base class MCFClass, thus sharing its (standard) interface, and solves (Linear) Min Cost Flow problems via calls to Cplex Callable Library functions.

Member Enumeration Documentation

◆ MCFCParam

enum MCFCParam

Public enum describing the possible parameters of the MCF solver, "extended" from MCFClass::MCFParam, to be used with the methods SetPar() and GetPar().

Enumerator
kQPMethod	solution method

Constructor & Destructor Documentation

◆ MCFCplex()

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

Constructor of the class.

For the meaning of nmx and mmx see MCFClass::MCFClass().

Member Function Documentation

◆ LoadNet()

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`
	)

override

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

Passing pC[ i ] == C_INF means that the arc ‘i’ does not exist in the problem. These arcs are just "closed" and their cost is set to 0: this is done for being (if DYNMC_MCF_CPX > 0) subsequently capable of "opening" them back with OpenArc(). If the corresponding pU[ i ] is == F_INF then the arc is just "deleted".

◆ SetPar() [1/2]

void SetPar	(	int	par,
		int	val
	)

inlineoverridevirtual

Set integer parameters of the algorithm.

Parameters

par	is the parameter to be set;
value	is the value to assign to the parameter.

Apart from the parameters of the base class, this method handles:

kQPMethod: the alorithm used to solve the QP, possible values are defined in the enum QPMethod.
<any other>: any unrecognized value is taken to be one of the the many "int" algorithmic parameters of Cplex and passed right away via CPXsetintparam() [see the documentation in the Cplex manual for details.

Reimplemented from MCFClass.

References MCFClass::kMaxIter, MCFCplex::kQPMethod, and MCFClass::SetPar().

◆ SetPar() [2/2]

void SetPar	(	int	par,
		double	val
	)

inlineoverridevirtual

Set float parameters of the algorithm.

Parameters

par	is the parameter to be set;
value	is the value to assign to the parameter.

Apart from the parameters of the base class, this method handles:

<any other>: any unrecognized value is taken to be one of the the many "int" algorithmic parameters of Cplex and passed right away via CPXsetintparam(); see the documentation in the Cplex manual for details.

Reimplemented from MCFClass.

References MCFClass::kMaxTime, and MCFClass::SetPar().

◆ GetPar() [1/2]

void GetPar	(	int	par,
		int &	val
	)		const

inlineoverridevirtual

Returns one of the integer parameters of the algorithm.

Parameters

par	is the parameter to return [see SetPar( int ) for comments];
val	upon return, it will contain the value of the parameter.

Apart from the parameters of the base class, this method handles kQPMethod.

Reimplemented from MCFClass.

References MCFClass::GetPar(), and MCFCplex::kQPMethod.

◆ GetPar() [2/2]

void GetPar	(	int	par,
		double &	val
	)		const

inlineoverridevirtual

Returns one of the double parameters of the algorithm.

This should in princible not be necessary, as MCFCplex has no double parameters to report. However, without this being well-defined, template classes having MCFCplex as template type may fail to be able to use the base class method in its stead (no idea why), so this useless method has to be kept here.

Reimplemented from MCFClass.

References MCFClass::GetPar().

◆ 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

◆ MCFCParam

Constructor & Destructor Documentation

◆ MCFCplex()

Member Function Documentation

◆ LoadNet()

◆ SetPar() [1/2]

◆ SetPar() [2/2]

◆ GetPar() [1/2]

◆ GetPar() [2/2]

◆ MCFGetX() [1/2]

◆ MCFGetX() [2/2]

◆ MCFGetRC() [1/3]

◆ MCFGetRC() [2/3]

◆ MCFGetRC() [3/3]

◆ MCFGetPi() [1/2]

◆ MCFGetPi() [2/2]