The RelaxIV class derives from the abstract base class MCFClass, thus sharing its (standard) interface, and implements a Relaxation algorithm for solving (Linear) Min Cost Flow problems. More...

#include <RelaxIV.h>

Inheritance diagram for RelaxIV:

Public Types
enum	MCFRParam { kAuction = 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	RIVFlFrmt { kCLP = kMPS + 1 , kRIV }
	Public enum describing the more file formats in RelaxIV::WriteMCF(). More...

typedef bool *	Bool_Vec
	vector of booleans

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
	RelaxIV (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	SetPar (int par, int val) override
	set integer 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.

void	PreProcess (void) override
	If this method is called, a preprocessing phase is performed trying to reduce the arc capacities.

MCFStatePtr	MCFGetState (void) const override
	Same meaning as MCFClass::MCFGetState().

cIndex_Set	MCFSNdes (void) const override
	Same meaning as MCFClass::MCFSNdes().

cIndex_Set	MCFENdes (void) const override
	Same meaning as MCFClass::MCFENdes().

void	WriteMCF (ostream &oStrm, int frmt=0) const override
	Extends MCFClass::WriteMCF() to support two new formats:

int	MCFiter (void) const
	total number of (single-node or multinode) iterations

int	MCFaug (void) const
	number of flow augmentations

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

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 void	MCFQCoef (CRow Qv, cIndex_Set nms=0, Index strt=0, Index stp=Inf< Index >()) const
	write the quadratic coefficients of the arc costs into a vector

virtual CNumber	MCFQCoef (Index i) const
	return the quadratic coefficients of the cost of the i-th arc

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

virtual void	ChgQCoef (cCRow NQCoef=0, cIndex_Set nms=0, Index strt=0, Index stp=Inf< Index >())
	change the quadratic coefficients of the arc costs

virtual void	ChgQCoef (Index arc, CNumber NQCoef)
	change the quadratic coefficient of the cost of the i-th arc

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 RelaxIV class derives from the abstract base class MCFClass, thus sharing its (standard) interface, and implements a Relaxation algorithm for solving (Linear) Min Cost Flow problems.

Member Enumeration Documentation

◆ MCFRParam

enum MCFRParam

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

Enumerator
kAuction	crash initialization

◆ RIVFlFrmt

enum RIVFlFrmt

Public enum describing the more file formats in RelaxIV::WriteMCF().

Enumerator
kCLP	the "LP" format
kRIV	RelaxIV-specific format.

Member Function Documentation

◆ LoadNet()

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

overridevirtual

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

Arcs with pC[ i ] == Inf< CNumber >() do not "exist". If DYNMC_MCF_RIV > 0, these arcs are "closed".

If DYNMC_MCF_RIV == 0, these arcs are just removed from the formulation. However, they have some sort of a "special status" (after all, if the user wants to remove them completely he/she can just change the data), in that they are still counted into the number of arcs of the graph and they will always have 0 flow and Inf< CNumber >() reduced cost as "closed" or "deleted" arcs.

Implements MCFClass.

◆ SetPar()

void SetPar	(	int	par,
		int	val
	)

inlineoverridevirtual

set integer parameters of the algorithm

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:

kAuction: if set to kYes, the auction/shortest paths initialization is used in SolveMCF() to generate the starting solution; if set to kNo (default), then the default initialization based on special single-node relaxation iterations is used instead. Note that this parameter is ignored if AUCTION == 0.

Reimplemented from MCFClass.

References RelaxIV::kAuction, MCFClass::kYes, 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 kAuction.

Reimplemented from MCFClass.

References MCFClass::GetPar(), RelaxIV::kAuction, MCFClass::kNo, and MCFClass::kYes.

◆ 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 RelaxIV has no double parameters to report. However, without this being well-defined, template classes having RelaxIV 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().

◆ PreProcess()

void PreProcess ( void )

overridevirtual

If this method is called, a preprocessing phase is performed trying to reduce the arc capacities.

This may sometimes help in speeding up the solution of the problem, but may also change the capacities returned by MCFUCap[s]() [see below].

For this method to work properly, arc capacities, node deficits and the topology of the graph must have already been provided with LoadNet() [see above].

This method can be called more than once, for instance whenever the capacities of some arcs or the deficits of some nodes are changed; however, it destroys the provious optimal solution (if any), forcing the algorithm to restart from scratch.

Reimplemented from MCFClass.

◆ MCFGetState()

MCFStatePtr MCFGetState ( void ) const

overridevirtual

Same meaning as MCFClass::MCFGetState().

The state of the algorithm is the pair S = ( X[] , RC[] ) of the arc flows and reduced costs.

Reimplemented from MCFClass.

◆ MCFSNdes()

cIndex_Set MCFSNdes ( void ) const

inlineoverridevirtual

Same meaning as MCFClass::MCFSNdes().

Note: MCFSNdes() returns a pointers to a (read-only) vector containing the arc start nodes only if USENAME0 == 0; otherwise, it returns NULL.

Reimplemented from MCFClass.

◆ MCFENdes()

cIndex_Set MCFENdes ( void ) const

inlineoverridevirtual

Same meaning as MCFClass::MCFENdes().

Note: MCFENdes() returns a pointers to a (read-only) vector containing the arc end nodes only if USENAME0 == 0; otherwise, it returns NULL.

Reimplemented from MCFClass.

◆ WriteMCF()

void WriteMCF	(	ostream &	oStrm,
		int	frmt = `0`
	)		const

overridevirtual

Extends MCFClass::WriteMCF() to support two new formats:

kCLP is the "LP" format read by several LP solvers;

kRIV is the following RelaxIV-specific format:

 - < number of nodes > < number of arcs >

 - for( < each arc > )
   < start node > < end node > < reduced_capacity > < reduced_cost >

 - for( < each node > )
   < reduced flow deficit at node >

 \note the data of the problem in this format is not that of the
       original problem, but rather that of the "reduced" problem
       corresponding to the current pair (flow, potential) of the
  relaxation algorithm.

Reimplemented from MCFClass.

Public Types

Public Member Functions

Additional Inherited Members

Detailed Description

Member Enumeration Documentation

◆ MCFRParam

◆ RIVFlFrmt

Member Function Documentation

◆ LoadNet()

◆ SetPar()

◆ GetPar() [1/2]

◆ GetPar() [2/2]

◆ PreProcess()

◆ MCFGetState()

◆ MCFSNdes()

◆ MCFENdes()

◆ WriteMCF()