This abstract base class defines a standard interface for (linear or convex quadartic separable) Min Cost Flow (MCF) problem solvers. More...

#include <MCFClass.h>

Inheritance diagram for MCFClass:

Classes
class	MCFException
	Very small class to simplify extracting the "+ infinity" value for a basic type (FNumber, CNumber, Index); just use Inf<type>(). More...

class	MCFState
	Base class for representing the internal state of the MCF algorithm. More...

Public Types
Public types
The MCFClass defines four main public types: Index, the type of arc and node indices; FNumber, the type of flow variables, arc capacities, and node deficits; CNumber, the type of flow costs, node potentials, and arc reduced costs; FONumber, the type of objective function value. By re-defining the types in this section, most MCFSolver should be made to work with any reasonable choice of data type (= one that is capable of properly representing the data of the instances to be solved). This may be relevant due to an important property of MCF problems: if all arc capacities and node deficits are integer, then there exists an integral optimal primal solution, and if all arc costs are integer, then there exists an integral optimal dual solution. Even more importantly, many solution algorithms will in fact produce an integral primal/dual solution for free, because every primal/dual solution they generate during the solution process is naturally integral. Therefore, one can use integer data types to represent everything connected with flows and/or costs if the corresponding data is integer in all instances one needs to solve. This directly translates in significant memory savings and/or speed improvements. It is the user's responsibility to ensure that these types are set to reasonable values. So, the experienced user may want to experiment with setting this data properly if memory footprint and/or speed is a primary concern. Note, however, that not all solution algorithms will happily accept integer data; one example are Interior-Point approaches, which require both flow and cost variables to be continuous (float). So, the viability of setting integer data (as well as its impact on performances) is strictly related to the specific kind of algorithm used. Since these types are common to all derived classes, they have to be set taking into account the needs of all the solvers that are going to be used, and adapting to the "worst case"; of course, FNumber == CNumber == double is going to always be an acceptable "worst case" setting. MCFClass may in a future be defined as a template class, with these as template parameters, but this is currently deemed overkill and avoided. Finally, note that the above integrality property only holds for linear* MCF problems. If any arc has a nonzero quadratic cost coefficient, optimal flows and potentials may be fractional even if all the data of the problem (comprised quadratic cost coefficients) is integer. Hence, for quadratic MCF solvers, a setting like FNumber == CNumber == double is actually mandatory*, for any reasonable algorithm will typically misbehave otherwise.
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
Constructors
	MCFClass (cIndex nmx=0, cIndex mmx=0)
	Constructor of the class. More...

Other initializations
virtual void	LoadNet (cIndex nmx=0, cIndex mmx=0, cIndex pn=0, cIndex pm=0, cFRow pU=0, cCRow pC=0, cFRow pDfct=0, cIndex_Set pSn=0, cIndex_Set pEn=0)=0
	Inputs a new network. 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	SetPar (int par, int val)
	Set integer parameters of the algorithm. More...

virtual void	SetPar (int par, double val)
	Set float parameters of the algorithm. 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...

Solving the problem
virtual void	SolveMCF (void)=0
	Solver of the Min Cost Flow Problem. More...

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

Reading flow solution
virtual void	MCFGetX (FRow F, Index_Set nms=0, cIndex strt=0, Index stp=Inf< Index >())=0
	Write the optimal flow solution in the vector F[]. 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...

Reading potentials
virtual void	MCFGetPi (CRow P, cIndex_Set nms=0, cIndex strt=0, Index stp=Inf< Index >())=0
	Writes the optimal node potentials in the vector P[]. 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...

Reading reduced costs
virtual void	MCFGetRC (CRow CR, cIndex_Set nms=0, cIndex strt=0, Index stp=Inf< Index >())=0
	Write the reduced costs corresponding to the current dual solution in RC[]. More...

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

virtual CNumber	MCFGetRC (cIndex i)=0
	Return the reduced cost of the i-th arc. More...

Reading the objective function value
virtual FONumber	MCFGetFO (void)=0
	Return the objective function value of the primal solution currently returned by MCFGetX(). More...

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

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

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

Saving/restoring the state of the solver
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...

Time the code
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...

Check the solutions
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...

Reading graph size
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...

Reading graph topology
virtual void	MCFArcs (Index_Set Startv, Index_Set Endv, cIndex_Set nms=0, cIndex strt=0, Index stp=Inf< Index >())=0
	Write the starting (tail) and ending (head) nodes of the arcs in Startv[] and Endv[]. More...

virtual Index	MCFSNde (cIndex i)=0
	Return the starting (tail) node of the arc `i'. More...

virtual Index	MCFENde (cIndex i)=0
	Return the ending (head) node of the arc `i'. 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...

Reading arc costs
virtual void	MCFCosts (CRow Costv, cIndex_Set nms=0, cIndex strt=0, Index stp=Inf< Index >())=0
	Write the arc costs into Costv[]. More...

virtual CNumber	MCFCost (cIndex i)=0
	Return the cost of the i-th arc. More...

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

virtual void	MCFQCoef (CRow Qv, cIndex_Set nms=0, cIndex strt=0, Index stp=Inf< Index >())

virtual CNumber	MCFQCoef (cIndex i)

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

Reading arc capacities
virtual void	MCFUCaps (FRow UCapv, cIndex_Set nms=0, cIndex strt=0, Index stp=Inf< Index >())=0
	Write the arc capacities into UCapv[]. More...

virtual FNumber	MCFUCap (cIndex i)=0
	Return the capacity of the i-th arc. More...

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

Reading node deficits
virtual void	MCFDfcts (FRow Dfctv, cIndex_Set nms=0, cIndex strt=0, Index stp=Inf< Index >())=0
	Write the node deficits into Dfctv[]. More...

virtual FNumber	MCFDfct (cIndex i)=0
	Return the deficit of the i-th node. More...

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

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

Changing the costs
virtual void	ChgCosts (cCRow NCost, cIndex_Set nms=0, cIndex strt=0, Index stp=Inf< Index >())=0
	Change the arc costs. More...

virtual void	ChgCost (Index arc, cCNumber NCost)=0
	Change the cost of the i-th arc. More...

virtual void	ChgQCoef (cCRow NQCoef=0, cIndex_Set nms=0, cIndex strt=0, Index stp=Inf< Index >())

virtual void	ChgQCoef (Index arc, cCNumber NQCoef)

Changing the capacities
virtual void	ChgUCaps (cFRow NCap, cIndex_Set nms=0, cIndex strt=0, Index stp=Inf< Index >())=0
	Change the arc capacities. More...

virtual void	ChgUCap (Index arc, cFNumber NCap)=0
	Change the capacity of the i-th arc. More...

Changing the deficits
virtual void	ChgDfcts (cFRow NDfct, cIndex_Set nms=0, cIndex strt=0, Index stp=Inf< Index >())=0
	Change the node deficits. More...

virtual void	ChgDfct (Index node, cFNumber NDfct)=0
	Change the deficit of the i-th node. More...

Changing graph topology
virtual void	CloseArc (cIndex name)=0
	"Close" the arc `name'. More...

virtual bool	IsClosedArc (cIndex name)=0
	IsClosedArc() returns true if and only if the arc `name' is closed. More...

virtual void	DelNode (cIndex name)=0
	Delete the node `name'. More...

virtual void	OpenArc (cIndex name)=0
	Restore the previously closed arc `name'. More...

virtual Index	AddNode (cFNumber aDfct)=0
	Add a new node with deficit aDfct, returning its name. More...

virtual void	ChangeArc (cIndex name, cIndex nSN=Inf< Index >(), cIndex nEN=Inf< Index >())=0
	Change the starting and/or ending node of arc `name' to nSN and nEN. More...

virtual void	DelArc (cIndex name)=0
	Delete the arc `name'. More...

virtual bool	IsDeletedArc (cIndex name)=0
	Return true if and only if the arc `name' is deleted. More...

virtual Index	AddArc (cIndex Start, cIndex End, cFNumber aU, cCNumber aC)=0
	Add the new arc ( Start , End ) with cost aC and capacity aU, returning its name. More...

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

Protected Member Functions
Managing comparisons.
The following methods are provided for making it easier to perform comparisons, with and without tolerances.
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
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

This abstract base class defines a standard interface for (linear or convex quadartic separable) Min Cost Flow (MCF) problem solvers.

The data of the problem consist of a (directed) graph G = ( N , A ) with n = |N| nodes and m = |A| (directed) arcs. Each node `i' has a deficit b[ i ], i.e., the amount of flow that is produced/consumed by the node: source nodes (which produce flow) have negative deficits and sink nodes (which consume flow) have positive deficits. Each arc `(i, j)' has an upper capacity U[ i , j ], a linear cost coefficient C[ i , j ] and a (non negative) quadratic cost coefficient Q[ i , j ]. Flow variables X[ i , j ] represents the amount of flow to be sent on arc (i, j). Parallel arcs, i.e., multiple copies of the same arc `(i, j)' (with possibily different costs and/or capacities) are in general allowed. The formulation of the problem is therefore:

$\min \sum_{ (i, j) \in A } C[ i , j ] X[ i, j ] + Q[ i , j ] X[ i, j ]^2 / 2$

$(1) \sum_{ (j, i) \in A } X[ j , i ] - \sum_{ (i, j) \in A } X[ i , j ] = b[ i ] \hspace{1cm} i \in N$

$(2) 0 \leq X[ i , j ] \leq U[ i , j ] \hspace{1cm} (i, j) \in A$

The n equations (1) are the flow conservation constraints and the 2m inequalities (2) are the flow nonnegativity and capacity constraints. At least one of the flow conservation constraints is redundant, as the demands must be balanced ( $\sum_{ i \in N } b[ i ] = 0$ ); indeed, exactly n - ConnectedComponents( G ) flow conservation constraints are redundant, as demands must be balanced in each connected component of G. Let us denote by QA and LA the disjoint subsets of A containing, respectively, "quadratic" arcs (with Q[ i , j ] > 0) and "linear" arcs (with Q[ i , j ] = 0); the (MCF) problem is linear if QA is empty, and nonlinear (convex quadratic) if QA is nonempty.

The dual of the problem is:

$\max \sum_{ i \in N } Pi[ i ] b[ i ] - \sum_{ (i, j) \in A } W[ i , j ] U[ i , j ] - \sum_{ (i, j) \in AQ } V[ i , j ]^2 / ( 2 * Q[ i , j ] )$

$(3.a) C[ i , j ] - Pi[ j ] + Pi[ i ] + W[ i , j ] - Z[ i , j ] = 0 \hspace{1cm} (i, j) \in AL$

$(3.b) C[ i , j ] - Pi[ j ] + Pi[ i ] + W[ i , j ] - Z[ i , j ] = V[ i , j ] \hspace{1cm} (i, j) \in AQ$

$(4.a) W[ i , j ] \geq 0 \hspace{1cm} (i, j) \in A$

$(4.b) Z[ i , j ] \geq 0 \hspace{1cm} (i, j) \in A$

Pi[] is said the vector of node potentials for the problem, W[] are bound variables and Z[] are slack variables. Given Pi[], the quantities

$RC[ i , j ] = C[ i , j ] + Q[ i , j ] * X[ i , j ] - Pi[ j ] + Pi[ i ]$

are said the "reduced costs" of arcs.

A primal and dual feasible solution pair is optimal if and only if the complementary slackness conditions

$RC[ i , j ] > 0 \Rightarrow X[ i , j ] = 0$

$RC[ i , j ] < 0 \Rightarrow X[ i , j ] = U[ i , j ]$

are satisfied for all arcs (i, j) of A.

The MCFClass class provides an interface with methods for managing and solving problems of this kind. Actually, the class can also be used as an interface for more general NonLinear MCF problems, where the cost function either nonseparable ( C( X ) ) or arc-separable ( $\sum_{ (i, j) \in A } C_{i,j}( X[ i, j ] )$ ). However, solvers for NonLinear MCF problems are typically objective-function-specific, and there is no standard way for inputting a nonlinear function different from a separable convex quadratic one, so only the simplest form is dealt with in the interface, leaving more complex NonLinear parts to the interface of derived classes.

Member Enumeration Documentation

enum MCFParam

Public enum describing the possible parameters of the MCF solver, to be used with the methods SetPar() and GetPar().

Enumerator
kMaxTime	max time
kMaxIter	max number of iteration
kEpsFlw	tolerance for flows
kEpsDfct	tolerance for deficits
kEpsCst	tolerance for costs
kReopt	whether or not to reoptimize
kLastParam	dummy parameter: this is used to allow derived classes to "extend" the set of parameters.

enum MCFStatus

Public enum describing the possible status of the MCF solver.

Enumerator
kUnSolved	no solution available
kOK	optimal solution found
kStopped	optimization stopped
kUnfeasible	problem is unfeasible
kUnbounded	problem is unbounded
kError	error in the solver

enum MCFAnswer

Public enum describing the possible reoptimization status of the MCF solver.

Enumerator
kNo	no
kYes	yes

enum MCFFlFrmt

Public enum describing the possible file formats in WriteMCF().

Enumerator
kDimacs	DIMACS file format for MCF.
kQDimacs	quadratic DIMACS file format for MCF
kMPS	MPS file format for LP.
kFWMPS	"Fixed Width" MPS format

Constructor & Destructor Documentation

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

inline

Constructor of the class.

nmx and mmx, if provided, are taken to be respectively the maximum number of nodes and arcs in the network. If nonzero values are passed, memory allocation can be anticipated in the constructor, which is sometimes desirable. The maximum values are stored in the protected fields nmax and mmax, and can be changed with LoadNet() [see below]; however, changing them typically requires memory allocation/deallocation, which is sometimes undesirable outside the constructor.

After that an object has been constructed, no problem is loaded; this has to be done with LoadNet() [see below]. Thus, it is an error to invoke any method which requires the presence of a problem (typicall all except those in the initializations part). The base class provides two protected fields n and m for the current number of nodes and arcs, respectively, that are set to 0 in the constructor precisely to indicate that no instance is currently loaded.

virtual ~MCFClass ( )

inlinevirtual

Destructor of the class.

The implementation in the base class only deletes the MCFt field. It is virtual, as it should be.

Member Function Documentation

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

pure virtual

Inputs a new network.

The parameters nmx and mmx are the new max number of nodes and arcs, possibly overriding those set in the constructor [see above], altough at the likely cost of memory allocation and deallocation. Passing nmx == mmx == 0 is intended as a signal to the solver to deallocate everything and wait for new orders; in this case, all the other parameters are ignored.

Otherwise, in principle all the other parameters have to be provided. Actually, some of them may not be needed for special classes of MCF problems (e.g., costs in a MaxFlow problem, or start/end nodes in a problem defined over a graph with fixed topology, such as a complete graph). Also, passing 0 is allowed to set default values.

The meaning of the parameters is the following:

pn is the current number of nodes of the network (<= nmax).
pm is the number of arcs of the network (<= mmax).
pU is the m-vector of the arc upper capacities; capacities must be nonnegative, but can in principle be infinite (== F_INF); passing pU == 0 means that all capacities are infinite;
pC is the m-vector of the arc costs; costs must be finite (< C_INF); passing pC == 0 means that all costs must be 0.
pDfct is the n-vector of the node deficits; source nodes have negative deficits and sink nodes have positive deficits; passing pDfct == 0 means that all deficits must be 0 (a circulation problem);
pSn is the m-vector of the arc starting nodes; pSn == 0 is in principle not allowed, unless the topology of the graph is fixed;
pEn is the m-vector of the arc ending nodes; same comments as for pSn.

Note that node "names" in the arrays pSn and pEn must go from 1 to pn if the macro USANAME0 [see above] is set to 0, while they must go from 0 to pn - 1 if USANAME0 is set to 1. In both cases, however, the deficit of the first node is read from the first (0-th) position of pDfct, that is if USANAME0 == 0 then the deficit of the node with name `i' is read from pDfct[ i - 1 ].

The data passed to LoadNet() can be used to specify that the arc `i' must not "exist" in the problem. This is done by passing pC[ i ] == C_INF; solvers which don't read costs are forced to read them in order to check this, unless they provide alternative solver-specific ways to accomplish the same tasks. These arcs are "closed", as for the effect of CloseArc() [see below]. "invalid" costs (== C_INF) are set to 0 in order to being subsequently capable of "opening" them back with OpenArc() [see below]. The way in which these non-existent arcs are phisically dealt with is solver-specific; in some solvers, for instance, this could be obtained by simply putting their capacity to zero. Details about these issues should be found in the interface of derived classes.

Note that the quadratic part of the objective function, if any, is not dealt with in LoadNet(); it can only be separately provided with ChgQCoef() [see below]. By default, the problem is linear, i.e., all coefficients of the second-order terms in the objective function are assumed to be zero.

Implemented in SPTree, MCFCplex, and MCFSimplex.

void LoadDMX	(	istream &	DMXs,
		bool	IsQuad = `false`
	)

inlinevirtual

Read a MCF instance in DIMACS standard format from the istream.

The format is the following. The first line must be

p min <number of="" nodes>=""> <number of="" arcs>="">

Then the node definition lines must be found, in the form

n <node number>=""> <node supply>="">

Not all nodes need have a node definition line; these are given zero supply, i.e., they are transhipment nodes (supplies are the inverse of deficits, i.e., a node with positive supply is a source node). Finally, the arc definition lines must be found, in the form

a <start node>=""> <end node>=""> <lower bound>=""> <upper bound>=""> <flow cost>="">

There must be exactly <number of="" arcs>=""> arc definition lines in the file.

This method is not pure virtual because an implementation is provided by the base class, using the LoadNet() method (which is pure virtual). However, the method is virtual to allow derived classes to implement more efficient versions, should they have any reason to do so.

Note: Actually, the file format accepted by LoadDMX (at least in the base class implementation) is more general than the DIMACS standard format, in that it is allowed to mix node and arc definitions in any order, while the DIMACS file requires all node information to appear before all arc information.; Other than for the above, this method is assumed to allow for quadratic* Dimacs files, encoding for convex quadratic separable Min Cost Flow instances. This is a simple extension where each arc descriptor has a sixth field, <quadratic cost>="">. The provided istream is assumed to be quadratic Dimacs file if IsQuad is true, and a regular linear Dimacs file otherwise.

virtual void PreProcess ( void )

inlinevirtual

Extract a smaller/easier equivalent MCF problem.

The data of the instance is changed and the easier one is solved instead of the original one. In the MCF case, preprocessing may involve reducing bounds, identifying disconnected components of the graph etc. However, proprocessing is solver-specific.

This method can be implemented by derived classes in their solver-specific way. Preprocessing may reveal unboundedness or unfeasibility of the problem; if that happens, PreProcess() should properly set the `status' field, that can then be read with MCFGetStatus() [see below].

Note that preprocessing may destroy all the solution information. Also, it may be allowed to change the data of the problem, such as costs/capacities of the arcs.

A valid preprocessing is doing nothing, and that's what the default implementation of this method (that is not pure virtual) does.

void SetPar	(	int	par,
		int	val
	)

inlinevirtual

Set integer parameters of the algorithm.

Parameters

par	is the parameter to be set; the enum MCFParam can be used, but 'par' is an int (every enum is an int) so that the method can be extended by derived classes for the setting of their parameters
value	is the value to assign to the parameter.

The base class implementation handles these parameters:

kMaxIter: the max number of iterations in which the MCF Solver can find an optimal solution (default 0, which means no limit)
kReopt: tells the solver if it has to reoptimize. The implementation in the base class sets a flag, the protected bool field Senstv; if true (default) this field instructs the MCF solver to to try to exploit the information about the latest optimal solution to speedup the optimization of the current problem, while if the field is false the MCF solver should restart the optimization "from scratch" discarding any previous information. Usually reoptimization speeds up the computation considerably, but this is not always true, especially if the data of the problem changes a lot.

Reimplemented in MCFCplex, and MCFSimplex.

Referenced by MCFCplex::SetPar().

void SetPar	(	int	par,
		double	val
	)

inlinevirtual

Set float parameters of the algorithm.

Parameters

par	is the parameter to be set; the enum MCFParam can be used, but 'par' is an int (every enum is an int) so that the method can be extended by derived classes for the setting of their parameters
value	is the value to assign to the parameter.

The base class implementation handles these parameters:

kEpsFlw: sets the tolerance for controlling if the flow on an arc is zero to val. This also sets the tolerance for controlling if a node deficit is zero (see kEpsDfct) to val * < max number of nodes >; this value should be safe for graphs in which any node has less than < max number of nodes > adjacent nodes, i.e., for all graphs but for very dense ones with "parallel arcs"
kEpsDfct: sets the tolerance for controlling if a node deficit is zero to val, in case a better value than that autmatically set by kEpsFlw (see above) is available (e.g., val * k would be good if no node has more than k neighbours)
kEpsCst: sets the tolerance for controlling if the reduced cost of an arc is zero to val. A feasible solution satisfying eps-complementary slackness, i.e., such that
$RC[ i , j ] < - eps \Rightarrow X[ i , j ] = U[ ij ]$
and
$RC[ i , j ] > eps \Rightarrow X[ i , j ] == 0 ,$
is known to be ( eps * n )-optimal.
kMaxTime: sets the max time (in seconds) in which the MCF Solver can find an optimal solution (default 0, which means no limit).

Reimplemented in MCFCplex, and MCFSimplex.

void GetPar	(	int	par,
		int &	val
	)

inlinevirtual

This method returns one of the integer parameter 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.

The base class implementation handles the parameters kMaxIter and kReopt.

Reimplemented in MCFCplex.

Referenced by MCFCplex::GetPar().

void GetPar	(	int	par,
		double &	val
	)

inlinevirtual

This method returns one of the integer parameter of the algorithm.

Parameters

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

The base class implementation handles the parameters kEpsFlw, kEpsDfct, kEpsCst, and kMaxTime.

virtual void SetMCFTime ( bool TimeIt = true )

inlinevirtual

Allocate an OPTtimers object [see OPTtypes.h] to be used for timing the methods of the class.

The time can be read with TimeMCF() [see below]. By default, or if SetMCFTime( false ) is called, no timing is done. Note that, since all the relevant methods ot the class are pure virtual, MCFClass can only manage the OPTtimers object, but it is due to derived classes to actually implement the timing.

Note: time accumulates over the calls: calling SetMCFTime(), however, resets the counters, allowing to time specific groups of calls.; of course, setting kMaxTime [see SetPar() above] to any nonzero value has no effect unless SetMCFTime( true ) has been called.

virtual void SolveMCF ( void )

pure virtual

Solver of the Min Cost Flow Problem.

Attempts to solve the MCF instance currently loaded in the object.

int MCFGetStatus ( void )

inline

Returns an int describing the current status of the MCF solver.

Possible return values are:

kUnSolved SolveMCF() has not been called yet, or the data of the problem has been changed since the last call;
kOK optimization has been carried out succesfully;
kStopped optimization have been stopped before that the stopping conditions of the solver applied, e.g. because of the maximum allowed number of "iterations" [see SetPar( int )] or the maximum allowed time [see SetPar( double )] has been reached; this is not necessarily an error, as it might just be required to re-call SolveMCF() giving it more "resources" in order to solve the problem;
kUnfeasible if the current MCF instance is (primal) unfeasible;
kUnbounded if the current MCF instance is (primal) unbounded (this can only happen if the solver actually allows F_INF capacities, which is nonstandard in the interface);
kError if there was an error during the optimization; this typically indicates that computation cannot be resumed, although solver-dependent ways of dealing with solver-dependent errors may exist.

MCFClass has a protected int member status that can be used by derived classes to hold status information and that is returned by the standard implementation of this method. Note that status is an int and not an enum , and that an int is returned by this method, in order to allow the derived classes to extend the set of return values if they need to do so.

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

pure virtual

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

virtual cFRow MCFGetX ( void )

inlinevirtual

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.

virtual bool HaveNewX ( void )

inlinevirtual

Return true if a different (approximately) optimal primal solution is available.

If the method returns true, then any subsequent call to (any form of) MCFGetX() will return a different primal solution w.r.t. the one that was being returned before the call to HaveNewX(). This solution need not be optimal (although, ideally, it has to be "good); this can be checked by comparing its objective function value, that will be returned by a call to MCFGetFO() [see below].

Any subsequent call of HaveNewX() that returns true produces a new solution, until the first that returns false; from then on, no new solutions will be generated until something changes in the problem's data.

Note that a default implementation of HaveNewX() is provided which is good for those solvers that only produce one optimal primal solution.

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

pure virtual

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.

virtual cCRow MCFGetPi ( void )

inlinevirtual

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 in SPTree.

virtual bool HaveNewPi ( void )

inlinevirtual

Return true if a different (approximately) optimal dual solution is available.

If the method returns true, then any subsequent call to (any form of) MCFGetPi() will return a different dual solution, and MCFGetRC() [see below] will return the corresponding reduced costs. The new solution need not be optimal (although, ideally, it has to be "good); this can be checked by comparing its objective function value, that will be returned by a call to MCFGetDFO() [see below].

Any subsequent call of HaveNewPi() that returns true produces a new solution, until the first that returns false; from then on, no new solutions will be generated until something changes in the problem's data.

Note that a default implementation of HaveNewPi() is provided which is good for those solvers that only produce one optimal dual solution.

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

pure virtual

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.

virtual cCRow MCFGetRC ( void )

inlinevirtual

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() [see above] which returns true.

virtual CNumber MCFGetRC ( cIndex i )

pure virtual

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() [see above] which returns true.

virtual FONumber MCFGetFO ( void )

pure virtual

Return the objective function value of the primal solution currently returned by MCFGetX().

If MCFGetStatus() == kOK, this is guaranteed to be the optimal objective function value of the problem (to within the optimality tolerances), but only prior to any call to HaveNewX() that returns true. MCFGetFO() typically returns Inf<FONumber>() if MCFGetStatus() == kUnfeasible and

Inf<FONumber>() if MCFGetStatus() == kUnbounded. If MCFGetStatus() == kStopped and MCFGetFO() returns a finite value, it must be an upper bound on the optimal objective function value (typically, the objective function value of one primal feasible solution).

Implemented in SPTree.

virtual FONumber MCFGetDFO ( void )

inlinevirtual

Return the objective function value of the dual solution currently returned by MCFGetPi() / MCFGetRC().

This value (possibly) changes after any call to HaveNewPi() that returns true. The relations between MCFGetStatus() and MCFGetDFO() are analogous to these of MCFGetFO(), except that a finite value corresponding to kStopped must be a lower bound on the optimal objective function value (typically, the objective function value one dual feasible solution).

A default implementation is provided for MCFGetDFO(), which is good for MCF solvers where the primal and dual optimal solution values always are identical (except if the problem is unfeasible/unbounded).

virtual FNumber MCFGetUnfCut ( Index_Set Cut )

inlinevirtual

Return an unfeasibility certificate.

In an unfeasible MCF problem, unfeasibility can always be reduced to the existence of a cut (subset of nodes of the graph) such as either:

the inverse of the deficit of the cut (the sum of all the deficits of the nodes in the cut) is larger than the forward capacity of the cut (sum of the capacities of forward arcs in the cut); that is, the nodes in the cut globally produce more flow than can be routed to sinks outside the cut;
the deficit of the cut is larger than the backward capacity of the cut (sum of the capacities of backward arcs in the cut); that is, the nodes in the cut globally require more flow than can be routed to them from sources outside the cut.

When detecting unfeasibility, MCF solvers are typically capable to provide one such cut. This information can be useful - typically, the only way to make the problem feasible is to increase the capacity of at least one of the forward/backward arcs of the cut -, and this method is provided for getting it. It can be called only if MCFGetStatus() == kUnfeasible, and should write in Cut the set of names of nodes in the unfeasible cut (note that node names depend on USENAME0), Inf<Index>()-terminated, returning the deficit of the cut (which allows to distinguish which of the two cases above hold). In general, no special properties can be expected from the returned cut, but solvers should be able to provide e.g. "small" cuts.

However, not all solvers may be (easily) capable of providing this information; thus, returning 0 (no cut) is allowed, as in the base class implementation, to signify that this information is not available.

virtual Index MCFGetUnbCycl	(	Index_Set	Pred,
		Index_Set	ArcPred
	)

inlinevirtual

Return an unboundedness certificate.

In an unbounded MCF problem, unboundedness can always be reduced to the existence of a directed cycle with negative cost and all arcs having infinite capacity. When detecting unboundedness, MCF solvers are typically capable to provide one such cycle. This information can be useful, and this method is provided for getting it. It can be called only if MCFGetStatus() == kUnbounded, and writes in Pred[] and ArcPred[], respectively, the node and arc predecessor function of the cycle. That is, if node `i' belongs to the cycle then `Pred[ i ]' contains the name of the predecessor of `j' of `i' in the cycle (note that node names depend on USENAME0), and `ArcPred[ i ]' contains the index of the arc joining the two (note that in general there may be multiple copies of each arc). Entries of the vectors for nodes not belonging to the cycle are in principle undefined, and the name of one node belonging to the cycle is returned by the method. Note that if there are multiple cycles with negative costs this method will return just one of them (finding the cycle with most negative cost is an NO-hard problem), although solvers should be able to produce cycles with "large negative" cost.

However, not all solvers may be (easily) capable of providing this information; thus, returning Inf<Index>() is allowed, as in the base class implementation, to signify that this information is not available.

virtual MCFStatePtr MCFGetState ( void )

inlinevirtual

Save the state of the MCF solver.

The MCFClass interface supports the notion of saving and restoring the state of the MCF solver, such as the current/optimal basis in a simplex solver. The "empty" class MCFState is defined as a placeholder for state descriptions.

MCFGetState() creates and returns a pointer to an object of (a proper derived class of) class MCFState which describes the current state of the MCF solver.

virtual void MCFPutState ( MCFStatePtr S )

inlinevirtual

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

The typical use of this method is the following: a MCF problem is solved and the "optimal state" is set aside. Then the problem changes and it is re-solved. Then, the problem has to be changed again to a form that is close to the original one but rather different from the second one (think of a long backtracking in a Branch & Bound) to which the current "state" referes. Then, the old optimal state can be expected to provide a better starting point for reoptimization [see ReOptimize() below].

Note, however, that the state is only relative to the optimization process, i.e., this operation is meaningless if the data of the problem has changed in the meantime. So, if a state has to be used for speeding up reoptimization, the following has to be done:

first, the data of the solver is brought back to exactly the same as it was at the moment where the state `S' was created (prior than this operation a ReOptimize( false ) call is probably advisable);
then, MCFPutState() is called (and ReOptimize( true ) is called);
only afterwards the data of the problem is changed to the final state and the problem is solved.

A "put state" operation does not "deplete" the state, which can therefore be used more than once. Indeed, a state is constructed inside the solver for each call to MCFGetState(), but the solver never deletes statuses; this has to be done on the outside when they are no longer needed (the solver must be "resistent" to deletion of the state at any moment).

Since not all the MCF solvers reoptimize (efficiently enough to make these operations worth), an "empty" implementation that does nothing is provided by the base class.

void TimeMCF	(	double &	t_us,
		double &	t_ss
	)

inline

Time the code.

If called within any of the methods of the class that are "actively timed" (this depends on the subclasses), this method returns the user and sistem time (in seconds) since the start of that method. If methods that are actively timed call other methods that are actively timed, TimeMCF() returns the (...) time since the beginning of the outer* actively timed method. If called outside of any actively timed method, this method returns the (...) time spent in all the previous executions of all the actively timed methods of the class.

Implementing the proper calls to MCFt->Start() and MCFt->Stop() is due to derived classes; these should at least be placed at the beginning and at the end, respectively, of SolveMCF() and presumably the Chg***() methods, that is, at least these methods should be "actively timed".

double TimeMCF ( void )

inline

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

void CheckPSol ( void )

inline

Check that the primal solution returned by the solver is primal feasible.

(to within the tolerances set by SetPar(kEps****) [see above], if any). Also, check that the objective function value is correct.

This method is implemented by the base class, using the above methods for collecting the solutions and the methods of the next section for reading the data of the problem; as such, they will work for any derived class that properly implements all these methods.

void CheckDSol ( void )

inline

Check that the dual solution returned by the solver is dual feasible.

(to within the tolerances set by SetPar(kEps****) [see above], if any). Also, check that the objective function value is correct.

This method is implemented by the base class, using the above methods for collecting the solutions and the methods of the next section for reading the data of the problem; as such, they will work for any derived class that properly implements all these methods.

Index MCFnmax ( void )

inline

Return the maximum number of nodes for this instance of MCFClass.

The implementation of the method in the base class returns the protected fields nmax, which is provided for derived classes to hold this information.

Index MCFmmax ( void )

inline

Return the maximum number of arcs for this instance of MCFClass.

The implementation of the method in the base class returns the protected fields mmax, which is provided for derived classes to hold this information.

Index MCFn ( void )

inline

Return the number of nodes in the current graph.

The implementation of the method in the base class returns the protected fields n, which is provided for derived classes to hold this information.

Index MCFm ( void )

inline

Return the number of arcs in the current graph.

The implementation of the method in the base class returns the protected fields m, which is provided for derived classes to hold this information.

virtual void MCFArcs	(	Index_Set	Startv,
		Index_Set	Endv,
		cIndex_Set	nms = `0`,
		cIndex	strt = `0`,
		Index	stp = `Inf< Index >()`
	)

pure virtual

Write the starting (tail) and ending (head) nodes of the arcs in Startv[] and Endv[].

If nms == 0, then the information relative to all arcs is written into Startv[] and Endv[], otherwise Startv[ i ] and Endv[ i ] contain the information relative to arc nms[ i ] (nms[] must be Inf<Index>()-terminated).

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.

Startv or Endv can be 0, meaning that only the other information is required.

Note: If USENAME0 == 0 then the returned node names will be in the range 1 .. n, while if USENAME0 == 1 the returned node names will be in the range 0 .. n - 1.; If the graph is "dynamic", be careful to use MCFn() e MCFm() to properly choose the dimension of nodes and arcs arrays.

virtual Index MCFSNde ( cIndex i )

pure virtual

Return the starting (tail) node of the arc `i'.

Note: If USENAME0 == 0 then the returned node names will be in the range 1 .. n, while if USENAME0 == 1 the returned node names will be in the range 0 .. n - 1.

virtual Index MCFENde ( cIndex i )

pure virtual

Return the ending (head) node of the arc `i'.

Note: If USENAME0 == 0 then the returned node names will be in the range 1 .. n, while if USENAME0 == 1 the returned node names will be in the range 0 .. n - 1.

virtual cIndex_Set MCFSNdes ( void )

inlinevirtual

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

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.

virtual cIndex_Set MCFENdes ( void )

inlinevirtual

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

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.

virtual void MCFCosts	(	CRow	Costv,
		cIndex_Set	nms = `0`,
		cIndex	strt = `0`,
		Index	stp = `Inf< Index >()`
	)

pure virtual

Write the arc costs into Costv[].

If nms == 0, then all the costs are written, otherwise Costv[ i ] contains the information relative to arc nms[ i ] (nms[] must be Inf<Index>()-terminated).

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.

virtual CNumber MCFCost ( cIndex i )

pure virtual

Return the cost of the i-th arc.

virtual cCRow MCFCosts ( void )

inlinevirtual

Return a read-only pointer to an internal vector containing the arc 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.

virtual void MCFQCoef	(	CRow	Qv,
		cIndex_Set	nms = `0`,
		cIndex	strt = `0`,
		Index	stp = `Inf<Index>()`
	)

inlinevirtual

Parameters

stp	Write the quadratic coefficients of the arc costs into Qv[]. If nms == 0, then all the costs are written, otherwise Costv[ i ] contains the information relative to arc nms[ i ] (nms[] must be Inf<Index>()-terminated).

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 that the method is not pure virtual: an implementation is provided for "pure linear" MCF solvers that only work with all zero quadratic coefficients.

virtual CNumber MCFQCoef ( cIndex i )

inlinevirtual

Parameters

i	Return the quadratic coefficients of the cost of the i-th arc. Note that the method is not pure virtual: an implementation is provided for "pure linear" MCF solvers that only work with all zero quadratic coefficients.

virtual cCRow MCFQCoef ( void )

inlinevirtual

Return a read-only pointer to an internal vector containing the arc 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 (such as "pure linear" MCF solvers that only work with all zero quadratic coefficients) does not need to implement the method.

Referenced by MCFCplex::GetCplexEnv().

virtual void MCFUCaps	(	FRow	UCapv,
		cIndex_Set	nms = `0`,
		cIndex	strt = `0`,
		Index	stp = `Inf< Index >()`
	)

pure virtual

Write the arc capacities into UCapv[].

If nms == 0, then all the capacities are written, otherwise UCapv[ i ] contains the information relative to arc nms[ i ] (nms[] must be Inf<Index>()-terminated).

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.

virtual FNumber MCFUCap ( cIndex i )

pure virtual

Return the capacity of the i-th arc.

virtual cFRow MCFUCaps ( void )

inlinevirtual

Return a read-only pointer to an internal vector containing the arc capacities.

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.

virtual void MCFDfcts	(	FRow	Dfctv,
		cIndex_Set	nms = `0`,
		cIndex	strt = `0`,
		Index	stp = `Inf< Index >()`
	)

pure virtual

Write the node deficits into Dfctv[].

If nms == 0, then all the defcits are written, otherwise Dfctvv[ i ] contains the information relative to node nms[ i ] (nms[] must be Inf<Index>()-terminated).

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.

Note: Here node "names" (strt and stp, those contained in nms[] or `i' in MCFDfct()) go from 0 to n - 1, regardless to the value of USENAME0; hence, if USENAME0 == 0 then the first node is "named 1", but its deficit is returned by MCFDfcts( Dfctv , 0 , 0 , 1 ).

virtual FNumber MCFDfct ( cIndex i )

pure virtual

Return the deficit of the i-th node.

Note: Here node "names" go from 0 to n - 1, regardless to the value of USENAME0; hence, if USENAME0 == 0 then the first node is "named 1", but its deficit is returned by MCFDfct( 0 ).

virtual cFRow MCFDfcts ( void )

inlinevirtual

Return a read-only pointer to an internal vector containing the node deficits.

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: Here node "names" go from 0 to n - 1, regardless to the value of USENAME0; hence, if USENAME0 == 0 then the first node is "named 1", but its deficit is contained in MCFDfcts()[ 0 ].

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

inlinevirtual

Write the current MCF problem to an ostream.

This may be useful e.g. for debugging purposes.

The base MCFClass class provides output in two different formats, depending on the value of the parameter frmt:

kDimacs the problem is written in DIMACS standard format, read by most MCF codes available;
kMPS the problem is written in the "modern version" (tab-separated) of the MPS format, read by most LP/MIP solvers;
- kFWMPS the problem is written in the "old version" (fixed width fields) of the MPS format; this is read by most LP/MIP solvers, but some codes still require the old format.

The implementation of WriteMCF() in the base class uses all the above methods for reading the data; as such it will work for any derived class that properly implements this part of the interface, but it may not be very efficient. Thus, the method is virtual to allow the derived classes to either re-implement WriteMCF() for the above two formats in a more efficient way, and/or to extend it to support other solver-specific formats.

Note: None of the above two formats supports quadratic MCFs, so if nonzero quadratic coefficients are present, they are just ignored.

References USENAME0.

virtual void ChgCosts	(	cCRow	NCost,
		cIndex_Set	nms = `0`,
		cIndex	strt = `0`,
		Index	stp = `Inf< Index >()`
	)

pure virtual

Change the arc costs.

In particular, change the costs that are:

listed in into the vector of indices `nms' (ordered in increasing sense and Inf<Index>()-terminated),
and whose name belongs to the interval [`strt', `stp').

That is, if strt <= nms[ i ] < stp, then the nms[ i ]-th cost will be changed to NCost[ i ]. If nms == 0 (as the default), all the entries in the given range will be changed; if stp > MCFm(), then the smaller bound is used.

Note: changing the costs of arcs that do not exist is not allowed; only arcs which have not been closed/deleted [see CloseArc() / DelArc() below and LoadNet() above about C_INF costs] can be touched with these methods.

virtual void ChgCost	(	Index	arc,
		cCNumber	NCost
	)

pure virtual

Change the cost of the i-th arc.

Note: changing the costs of arcs that do not exist is not allowed; only arcs which have not been closed/deleted [see CloseArc() / DelArc() below and LoadNet() above about C_INF costs] can be touched with these methods.

virtual void ChgQCoef	(	cCRow	NQCoef = `0`,
		cIndex_Set	nms = `0`,
		cIndex	strt = `0`,
		Index	stp = `Inf<Index>()`
	)

inlinevirtual

Parameters

stp	Change the quadratic coefficients of the arc costs. In particular, change the coefficients that are:

listed in into the vector of indices `nms' (ordered in increasing sense and Inf<Index>()-terminated),
and whose name belongs to the interval [`strt', `stp').

That is, if strt <= nms[ i ] < stp, then the nms[ i ]-th cost will be changed to NCost[ i ]. If nms == 0 (as the default), all the entries in the given range will be changed; if stp > MCFm(), then the smaller bound is used. If NQCoef == 0, all the specified coefficients are set to zero.

Note that the method is not pure virtual: an implementation is provided for "pure linear" MCF solvers that only work with all zero quadratic coefficients.

Note: changing the costs of arcs that do not exist is not allowed; only arcs which have not been closed/deleted [see CloseArc() / DelArc() below and LoadNet() above about C_INF costs] can be touched with these methods.

virtual void ChgQCoef	(	Index	arc,
		cCNumber	NQCoef
	)

inlinevirtual

Parameters

NQCoef Change the quadratic coefficient of the cost of the i-th arc.

Note that the method is not pure virtual: an implementation is provided for "pure linear" MCF solvers that only work with all zero quadratic coefficients.

Note: changing the costs of arcs that do not exist is not allowed; only arcs which have not been closed/deleted [see CloseArc() / DelArc() below and LoadNet() above about C_INF costs] can be touched with these methods.

virtual void ChgUCaps	(	cFRow	NCap,
		cIndex_Set	nms = `0`,
		cIndex	strt = `0`,
		Index	stp = `Inf< Index >()`
	)

pure virtual

Change the arc capacities.

In particular, change the capacities that are:

listed in into the vector of indices `nms' (ordered in increasing sense and Inf<Index>()-terminated),
and whose name belongs to the interval [`strt', `stp').

That is, if strt <= nms[ i ] < stp, then the nms[ i ]-th capacity will be changed to NCap[ i ]. If nms == 0 (as the default), all the entries in the given range will be changed; if stp > MCFm(), then the smaller bound is used.

Note: changing the capacities of arcs that do not exist is not allowed; only arcs that have not been closed/deleted [see CloseArc() / DelArc() below and LoadNet() above about C_INF costs] can be touched with these methods.

virtual void ChgUCap	(	Index	arc,
		cFNumber	NCap
	)

pure virtual

Change the capacity of the i-th arc.

Note: changing the capacities of arcs that do not exist is not allowed; only arcs that have not been closed/deleted [see CloseArc() / DelArc() below and LoadNet() above about C_INF costs] can be touched with these methods.

virtual void ChgDfcts	(	cFRow	NDfct,
		cIndex_Set	nms = `0`,
		cIndex	strt = `0`,
		Index	stp = `Inf< Index >()`
	)

pure virtual

Change the node deficits.

In particular, change the deficits that are:

listed in into the vector of indices `nms' (ordered in increasing sense and Inf<Index>()-terminated),
and whose name belongs to the interval [`strt', `stp').

That is, if strt <= nms[ i ] < stp, then the nms[ i ]-th deficit will be changed to NDfct[ i ]. If nms == 0 (as the default), all the entries in the given range will be changed; if stp > MCFn(), then the smaller bound is used.

Note that, in ChgDfcts(), node "names" (strt, stp or those contained in nms[]) go from 0 to n - 1, regardless to the value of USENAME0; hence, if USENAME0 == 0 then the first node is "named 1", but its deficit can be changed e.g. with ChgDfcts( &new_deficit , 0 , 0 , 1 ).

Note: changing the capacities of nodes that do not exist is not allowed; only nodes that have not been deleted [see DelNode() below] can be touched with these methods.

virtual void ChgDfct	(	Index	node,
		cFNumber	NDfct
	)

pure virtual

Change the deficit of the i-th node.

Note that, in ChgDfct[s](), node "names" (i, strt/ stp or those contained in nms[]) go from 0 to n - 1, regardless to the value of USENAME0; hence, if USENAME0 == 0 then the first node is "named 1", but its deficit can be changed e.g. with ChgDfcts( 0 , new_deficit ).

Note: changing the capacities of nodes that do not exist is not allowed; only nodes that have not been deleted [see DelNode() below] can be touched with these methods.

virtual void CloseArc ( cIndex name )

pure virtual

"Close" the arc `name'.

Although all the associated information (name, cost, capacity, end and start node) is kept, the arc is removed from the problem until OpenArc( i ) [see below] is called.

"closed" arcs always have 0 flow, but are otherwise counted as any other arc; for instance, MCFm() does not decrease as an effect of a call to CloseArc(). How this closure is implemented is solver-specific.

virtual bool IsClosedArc ( cIndex name )

pure virtual

IsClosedArc() returns true if and only if the arc `name' is closed.

virtual void DelNode ( cIndex name )

pure virtual

Delete the node `name'.

For any value of `name', all incident arcs to that node are closed [see CloseArc() above] (not Deleted, see DelArc() below) and the deficit is set to zero.

Il furthermore `name' is the last node, the number of nodes as reported by MCFn() is reduced by at least one, until the n-th node is not a deleted one.

virtual void OpenArc ( cIndex name )

pure virtual

Restore the previously closed arc `name'.

It is an error to open an arc that has not been previously closed.

virtual Index AddNode ( cFNumber aDfct )

pure virtual

Add a new node with deficit aDfct, returning its name.

Inf<Index>() is returned if there is no room for a new node. Remember that the node names are either { 0 .. nmax - 1 } or { 1 .. nmax }, depending on the value of USENAME0.

virtual void ChangeArc	(	cIndex	name,
		cIndex	nSN = `Inf< Index >()`,
		cIndex	nEN = `Inf< Index >()`
	)

pure virtual

Change the starting and/or ending node of arc `name' to nSN and nEN.

Each parameter being Inf<Index>() means to leave the previous starting or ending node untouched. When this method is called `name' can be either the name of a "normal" arc or that of a "closed" arc [see CloseArc() above]: in the latter case, at the end of ChangeArc() the arc is still closed, and it remains so until OpenArc( name ) [see above] is called.

virtual void DelArc ( cIndex name )

pure virtual

Delete the arc `name'.

Unlike "closed" arcs, all the information associated with a deleted arc is lost and `name' is made available as a name for new arcs to be created with AddArc() [see below].

Il furthermore `name' is the last arc, the number of arcs as reported by MCFm() is reduced by at least one, until the m-th arc is not a deleted one. Otherwise, the flow on the arc is always ensured to be 0.

virtual bool IsDeletedArc ( cIndex name )

pure virtual

Return true if and only if the arc `name' is deleted.

It should only be called with name < MCFm(), as every other arc is deleted by definition.

virtual Index AddArc	(	cIndex	Start,
		cIndex	End,
		cFNumber	aU,
		cCNumber	aC
	)

pure virtual

Add the new arc ( Start , End ) with cost aC and capacity aU, returning its name.

Inf<Index>() is returned if there is no room for a new arc. Remember that arc names go from 0 to mmax - 1.

bool ETZ	(	T	x,
		const T	eps
	)

inlineprotected

true if flow x is equal to zero (possibly considering tolerances).

bool GTZ	(	T	x,
		const T	eps
	)

inlineprotected

true if flow x is greater than zero (possibly considering tolerances).

bool GEZ	(	T	x,
		const T	eps
	)

inlineprotected

true if flow x is greater than or equal to zero (possibly considering tolerances).

bool LTZ	(	T	x,
		const T	eps
	)

inlineprotected

true if flow x is less than zero (possibly considering tolerances).

bool LEZ	(	T	x,
		const T	eps
	)

inlineprotected

true if flow x is less than or equal to zero (possibly considering tolerances).

bool LT	(	T	x,
		T	y,
		const T	eps
	)

inlineprotected

true if flow x is less than flow y (possibly considering tolerances).

Member Data Documentation

int status

protected

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

Note that the variable is defined int to allow derived classes to return their own specialized status codes

Classes

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation