The MCFClass Project
MCFClass Class Referenceabstract

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:
MCFCplex MCFSimplex RelaxIV SPTree

Classes

class  MCFException
 Small class for exceptions. 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.

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 IndexIndex_Set
 set (array) of indices
 
typedef const Index cIndex
 a read-only index
 
typedef cIndexcIndex_Set
 read-only index array
 
typedef double FNumber
 type of arc flow
 
typedef FNumberFRow
 vector of flows
 
typedef const FNumber cFNumber
 a read-only flow
 
typedef cFNumbercFRow
 read-only flow array
 
typedef double CNumber
 type of arc flow cost
 
typedef CNumberCRow
 vector of costs
 
typedef const CNumber cCNumber
 a read-only cost
 
typedef cCNumbercCRow
 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 MCFStateMCFStatePtr
 pointer to a MCFState
 

Public Member Functions

Constructors
 MCFClass (Index nmx=0, Index mmx=0)
 Constructor of the class.
 
Other initializations
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 SetPar (int par, int val)
 set integer parameters of the algorithm
 
virtual void SetPar (int par, double val)
 set float parameters of the algorithm.
 
virtual void GetPar (int par, int &val) const
 returns one of the integer parameters of the algorithm
 
virtual void GetPar (int par, double &val) const
 returns one of the double parameters of the algorithm
 
virtual void SetMCFTime (bool TimeIt=true)
 set the timer of the code
 
Solving the problem
virtual void SolveMCF (void)=0
 solve the problem
 
int MCFGetStatus (void) const
 returns the solution status
 
Reading flow solution
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 bool HaveNewX (void)
 tells if a different flow solution is available
 
Reading the dual solution
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
 
virtual bool HaveNewPi (void)
 tells if a different dual solution is available
 
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
 
Reading the objective function value
virtual FONumber MCFGetFO (void) const =0
 return the objective function value of the primal solution
 
virtual FONumber MCFGetDFO (void) const
 return the objective function value of the dual solution
 
Getting unfeasibility / unboundedness certificates
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
 
Saving/restoring the state of the solver
virtual MCFStatePtr MCFGetState (void) const
 save the state of the MCF solver
 
virtual void MCFPutState (MCFStatePtr S)
 restore the state of the solver
 
Time the code
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.
 
Check the solutions
void CheckPSol (void) const
 checks the primal solution
 
void CheckDSol (void) const
 checks the dual solution
 
Reading graph size and topology
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 MCFArcs (Index_Set Startv, Index_Set Endv, cIndex_Set nms=0, Index strt=0, Index stp=Inf< Index >()) const =0
 write the starting and ending nodes in vectors
 
virtual Index MCFSNde (Index i) const =0
 return the starting (tail) node of the arc ‘i’
 
virtual Index MCFENde (Index i) const =0
 return the ending (head) node of the arc ‘i’
 
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
 
Reading arc costs / capacities
virtual void MCFCosts (CRow Costv, cIndex_Set nms=0, Index strt=0, Index stp=Inf< Index >()) const =0
 write the arc costs into a vector
 
virtual CNumber MCFCost (Index i) const =0
 return the cost of the i-th arc
 
virtual cCRow MCFCosts (void) const
 return a read-only pointer to the vector of arc costs
 
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 MCFUCaps (FRow UCapv, cIndex_Set nms=0, Index strt=0, Index stp=Inf< Index >()) const =0
 write the arc capacities into a vector
 
virtual FNumber MCFUCap (Index i) const =0
 return the capacity of the i-th arc
 
virtual cFRow MCFUCaps (void) const
 return a read-only pointer to an the vector of arc capacities
 
Reading node deficits
virtual void MCFDfcts (FRow Dfctv, cIndex_Set nms=0, Index strt=0, Index stp=Inf< Index >()) const =0
 write the node deficits into a vector
 
virtual FNumber MCFDfct (Index i) const =0
 return the deficit of the i-th node
 
virtual cFRow MCFDfcts (void) const
 return a read-only pointer to the vector of node deficits
 
Write problem to file
virtual void WriteMCF (ostream &oStrm, int frmt=0) const
 write the current MCF problem to an ostream
 
Changing the arc costs / capacities
virtual void ChgCosts (cCRow NCost, cIndex_Set nms=0, Index strt=0, Index stp=Inf< Index >())=0
 change the arc costs
 
virtual void ChgCost (Index arc, CNumber NCost)=0
 change the cost of the i-th arc
 
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 void ChgUCaps (cFRow NCap, cIndex_Set nms=0, Index strt=0, Index stp=Inf< Index >())=0
 change the arc capacities
 
virtual void ChgUCap (Index arc, FNumber NCap)=0
 change the capacity of the i-th arc
 
Changing the node deficits
virtual void ChgDfcts (cFRow NDfct, cIndex_Set nms=0, Index strt=0, Index stp=Inf< Index >())=0
 change the node deficits
 
virtual void ChgDfct (Index node, FNumber NDfct)=0
 change the deficit of the i-th node
 
Changing graph topology
virtual void CloseArc (Index name)=0
 "close" one arc
 
virtual bool IsClosedArc (Index name) const =0
 returns true if and only if the arc ‘name’ is closed
 
virtual void DelNode (Index name)=0
 delete one node
 
virtual void OpenArc (Index name)=0
 re-opens a closed arc
 
virtual Index AddNode (FNumber aDfct)=0
 adds a ned node
 
virtual void ChangeArc (Index name, Index nSN=Inf< Index >(), Index nEN=Inf< Index >())=0
 change the starting and/or ending node of one arc
 
virtual void DelArc (Index name)=0
 deletes one arc
 
virtual bool IsDeletedArc (Index name) const =0
 return true if and only if the arc is deleted
 
virtual Index AddArc (Index Start, Index End, FNumber aU, CNumber aC)=0
 adds a new arc
 
Destructor
virtual ~MCFClass ()
 destructor of the class
 

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

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
 
OPTtimersMCFt
 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 \]

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

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

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 ] ) \]

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

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

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

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

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

◆ MCFParam

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.

◆ MCFStatus

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

◆ MCFAnswer

enum MCFAnswer

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

Enumerator
kNo 

no

kYes 

yes

◆ MCFFlFrmt

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

MCFClass ( Index  nmx = 0,
Index  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.

References MCFClass::EpsCst, MCFClass::EpsDfct, MCFClass::EpsFlw, MCFClass::kUnSolved, MCFClass::m, MCFClass::MaxIter, MCFClass::MaxTime, MCFClass::MCFt, MCFClass::mmax, MCFClass::n, MCFClass::nmax, MCFClass::Senstv, and MCFClass::status.

◆ ~MCFClass()

virtual ~MCFClass ( )
inlinevirtual

destructor of the class

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

References MCFClass::MCFt.

Member Function Documentation

◆ LoadNet()

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 
)
pure virtual

inputs a new network from memory

Inputs a new network from memory

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 MCFSimplex, RelaxIV, and SPTree.

Referenced by MCFClass::LoadDMX().

◆ LoadDMX()

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

read a MCF instance from a stream

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

References MCFClass::ChgQCoef(), and MCFClass::LoadNet().

◆ PreProcess()

virtual void PreProcess ( void  )
inlinevirtual

pre-process the instamce

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.

Reimplemented in RelaxIV.

◆ SetPar() [1/2]

virtual void SetPar ( int  par,
int  val 
)
inlinevirtual

set integer parameters of the algorithm

Set integer parameters of the algorithm.

Parameters
paris 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
valueis 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 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, MCFSimplex, and RelaxIV.

References MCFClass::kMaxIter, MCFClass::kReopt, MCFClass::kYes, MCFClass::MaxIter, and MCFClass::Senstv.

Referenced by MCFCplex::SetPar(), MCFCplex::SetPar(), and RelaxIV::SetPar().

◆ SetPar() [2/2]

virtual void SetPar ( int  par,
double  val 
)
inlinevirtual

set float parameters of the algorithm.

Set float parameters of the algorithm.

Parameters
paris 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
valueis 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. 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, 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. 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.

References MCFClass::EpsCst, MCFClass::EpsDfct, MCFClass::EpsFlw, MCFClass::kEpsCst, MCFClass::kEpsDfct, MCFClass::kEpsFlw, MCFClass::kMaxTime, MCFClass::kUnSolved, MCFClass::MaxTime, MCFClass::nmax, and MCFClass::status.

◆ GetPar() [1/2]

virtual void GetPar ( int  par,
int &  val 
) const
inlinevirtual

returns one of the integer parameters of the algorithm

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

Parameters
paris the parameter to return [see SetPar( int ) for comments];
valupon return, it will contain the value of the parameter.

The base class implementation handles the parameters kMaxIter and kReopt.

Reimplemented in MCFCplex, and RelaxIV.

References MCFClass::kMaxIter, MCFClass::kNo, MCFClass::kReopt, MCFClass::kYes, MCFClass::MaxIter, and MCFClass::Senstv.

Referenced by MCFCplex::GetPar(), RelaxIV::GetPar(), MCFCplex::GetPar(), and RelaxIV::GetPar().

◆ GetPar() [2/2]

virtual void GetPar ( int  par,
double &  val 
) const
inlinevirtual

returns one of the double parameters of the algorithm

This method returns one of the double parameters of the algorithm.

Parameters
paris the parameter to return [see SetPar( double ) for comments];
valupon return, it will contain the value of the parameter.

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

Reimplemented in MCFCplex, and RelaxIV.

References MCFClass::EpsCst, MCFClass::EpsDfct, MCFClass::EpsFlw, MCFClass::kEpsCst, MCFClass::kEpsDfct, MCFClass::kEpsFlw, MCFClass::kMaxTime, and MCFClass::MaxTime.

◆ SetMCFTime()

virtual void SetMCFTime ( bool  TimeIt = true)
inlinevirtual

set the timer of the code

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.

References MCFClass::MCFt, and OPTtimers::ReSet().

◆ SolveMCF()

virtual void SolveMCF ( void  )
pure virtual

solve the problem

Solver of the Min Cost Flow Problem. Attempts to solve the MCF instance currently loaded in the object.

◆ MCFGetStatus()

int MCFGetStatus ( void  ) const
inline

returns the solution status

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.

References MCFClass::status.

Referenced by MCFClass::MCFGetDFO().

◆ MCFGetX() [1/2]

virtual void MCFGetX ( FRow  F,
Index_Set  nms = 0,
Index  strt = 0,
Index  stp = Inf< Index >() 
) const
pure 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 ).

Implemented in MCFCplex, MCFSimplex, and SPTree.

◆ 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 in MCFCplex, MCFSimplex, and SPTree.

Referenced by MCFClass::CheckDSol(), and MCFClass::CheckPSol().

◆ HaveNewX()

virtual bool HaveNewX ( void  )
inlinevirtual

tells if a different flow solution is available

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

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.

◆ MCFGetPi() [1/2]

virtual void MCFGetPi ( CRow  P,
cIndex_Set  nms = 0,
Index  strt = 0,
Index  stp = Inf< Index >() 
) const
pure 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.

Implemented in MCFCplex, and MCFSimplex.

◆ 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 in MCFCplex, MCFSimplex, and SPTree.

Referenced by MCFClass::CheckDSol().

◆ HaveNewPi()

virtual bool HaveNewPi ( void  )
inlinevirtual

tells if a different dual solution is available

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.

◆ MCFGetRC() [1/3]

virtual void MCFGetRC ( CRow  CR,
cIndex_Set  nms = 0,
Index  strt = 0,
Index  stp = Inf< Index >() 
) const
pure 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.

Implemented in MCFCplex, MCFSimplex, and SPTree.

◆ 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 in MCFCplex, MCFSimplex, and SPTree.

Referenced by MCFClass::CheckDSol().

◆ MCFGetRC() [3/3]

virtual CNumber MCFGetRC ( Index  i) const
pure 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.

Implemented in MCFCplex, MCFSimplex, and SPTree.

◆ MCFGetFO()

virtual FONumber MCFGetFO ( void  ) const
pure virtual

return the objective function value of the primal solution

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.

Referenced by MCFClass::CheckDSol(), MCFClass::CheckPSol(), and MCFClass::MCFGetDFO().

◆ MCFGetDFO()

virtual FONumber MCFGetDFO ( void  ) const
inlinevirtual

return the objective function value of the dual solution

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

References MCFClass::kError, MCFClass::kStopped, MCFClass::kUnSolved, MCFClass::MCFGetFO(), and MCFClass::MCFGetStatus().

◆ MCFGetUnfCut()

virtual FNumber MCFGetUnfCut ( Index_Set  Cut) const
inlinevirtual

return an unfeasibility certificate

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.

◆ MCFGetUnbCycl()

virtual Index MCFGetUnbCycl ( Index_Set  Pred,
Index_Set  ArcPred 
) const
inlinevirtual

return an unboundedness certificate

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

◆ MCFGetState()

virtual MCFStatePtr MCFGetState ( void  ) const
inlinevirtual

save the state of the MCF solver

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.

Reimplemented in RelaxIV.

◆ MCFPutState()

virtual void MCFPutState ( MCFStatePtr  S)
inlinevirtual

restore the state of the solver

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.

◆ TimeMCF()

void TimeMCF ( double &  t_us,
double &  t_ss 
) const
inline

time the code

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

References MCFClass::MCFt, and OPTtimers::Read().

◆ CheckPSol()

void CheckPSol ( void  ) const
inline

checks the primal solution

Check that the primal solution returned by the solver is primal feasible. (to within the tolerances set by SetPar(kEps****), 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.

References MCFClass::EpsCst, MCFClass::EpsDfct, MCFClass::EpsFlw, MCFClass::ETZ(), MCFClass::GT(), MCFClass::GTZ(), MCFClass::IsClosedArc(), MCFClass::LTZ(), MCFClass::MCFCost(), MCFClass::MCFDfcts(), MCFClass::MCFENde(), MCFClass::MCFGetFO(), MCFClass::MCFGetX(), MCFClass::MCFm(), MCFClass::MCFn(), MCFClass::MCFQCoef(), MCFClass::MCFSNde(), and MCFClass::MCFUCap().

◆ CheckDSol()

void CheckDSol ( void  ) const
inline

checks the dual solution

Check that the dual solution returned by the solver is dual feasible. (to within the tolerances set by SetPar(kEps****), 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.

References MCFClass::EpsCst, MCFClass::EpsFlw, MCFClass::ETZ(), MCFClass::GTZ(), MCFClass::IsClosedArc(), MCFClass::LT(), MCFClass::LTZ(), MCFClass::MCFCost(), MCFClass::MCFDfct(), MCFClass::MCFENde(), MCFClass::MCFGetFO(), MCFClass::MCFGetPi(), MCFClass::MCFGetRC(), MCFClass::MCFGetX(), MCFClass::MCFm(), MCFClass::MCFn(), MCFClass::MCFQCoef(), MCFClass::MCFSNde(), and MCFClass::MCFUCap().

◆ MCFnmax()

Index MCFnmax ( void  ) const
inline

return the maximum number of nodes

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.

References MCFClass::nmax.

◆ MCFmmax()

Index MCFmmax ( void  ) const
inline

return the maximum number of arcs

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.

References MCFClass::mmax.

◆ MCFn()

Index MCFn ( void  ) const
inline

return the current number of nodes

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.

References MCFClass::n.

Referenced by MCFClass::CheckDSol(), MCFClass::CheckPSol(), and MCFClass::WriteMCF().

◆ MCFm()

Index MCFm ( void  ) const
inline

return the current number of arcs

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.

References MCFClass::m.

Referenced by MCFClass::CheckDSol(), MCFClass::CheckPSol(), and MCFClass::WriteMCF().

◆ MCFArcs()

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

write the starting and ending nodes in vectors

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.

◆ MCFSNde()

virtual Index MCFSNde ( Index  i) const
pure virtual

return the starting (tail) node of the arc ‘i’

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.

Referenced by MCFClass::CheckDSol(), MCFClass::CheckPSol(), and MCFClass::WriteMCF().

◆ MCFENde()

virtual Index MCFENde ( Index  i) const
pure virtual

return the ending (head) node of the arc ‘i’

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.

Referenced by MCFClass::CheckDSol(), MCFClass::CheckPSol(), and MCFClass::WriteMCF().

◆ MCFSNdes()

virtual cIndex_Set MCFSNdes ( void  ) const
inlinevirtual

return a read-only pointer to the vector of starting nodes

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.

Reimplemented in RelaxIV.

◆ MCFENdes()

virtual cIndex_Set MCFENdes ( void  ) const
inlinevirtual

return a read-only pointer to the vector of ending nodes

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.

Reimplemented in RelaxIV.

◆ MCFCosts() [1/2]

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

write the arc costs into a vector

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.

◆ MCFCosts() [2/2]

virtual cCRow MCFCosts ( void  ) const
inlinevirtual

return a read-only pointer to the vector of arc costs

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.

◆ MCFQCoef() [1/3]

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

write the quadratic coefficients of the arc costs into a vector

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.

References MCFClass::m.

◆ MCFQCoef() [2/3]

virtual CNumber MCFQCoef ( Index  i) const
inlinevirtual

return the quadratic coefficients of the cost of the i-th arc

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.

◆ MCFQCoef() [3/3]

virtual cCRow MCFQCoef ( void  ) const
inlinevirtual

return a read-only pointer to the vector of arc quadratic costs

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 MCFClass::CheckDSol(), MCFClass::CheckPSol(), and MCFClass::WriteMCF().

◆ MCFUCaps() [1/2]

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

write the arc capacities into a vector

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.

◆ MCFUCaps() [2/2]

virtual cFRow MCFUCaps ( void  ) const
inlinevirtual

return a read-only pointer to an the vector of arc capacities

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.

◆ MCFDfcts() [1/2]

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

write the node deficits into a vector

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

◆ MCFDfct()

virtual FNumber MCFDfct ( Index  i) const
pure virtual

return the deficit of the i-th node

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

Referenced by MCFClass::CheckDSol(), and MCFClass::WriteMCF().

◆ MCFDfcts() [2/2]

virtual cFRow MCFDfcts ( void  ) const
inlinevirtual

return a read-only pointer to the vector of node deficits

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

Referenced by MCFClass::CheckPSol().

◆ WriteMCF()

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

write the current MCF problem to an ostream

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.

Reimplemented in RelaxIV.

References MCFClass::IsClosedArc(), MCFClass::IsDeletedArc(), MCFClass::kDimacs, MCFClass::kFWMPS, MCFClass::kMPS, MCFClass::kQDimacs, MCFClass::MCFCost(), MCFClass::MCFDfct(), MCFClass::MCFENde(), MCFClass::MCFm(), MCFClass::MCFn(), MCFClass::MCFQCoef(), MCFClass::MCFSNde(), MCFClass::MCFUCap(), and USENAME0.

◆ ChgCosts()

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

change the arc costs

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.

◆ ChgCost()

virtual void ChgCost ( Index  arc,
CNumber  NCost 
)
pure virtual

change the cost of the i-th arc

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.

◆ ChgQCoef() [1/2]

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

change the quadratic coefficients of the arc costs

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.

Referenced by MCFClass::LoadDMX().

◆ ChgQCoef() [2/2]

virtual void ChgQCoef ( Index  arc,
CNumber  NQCoef 
)
inlinevirtual

change the quadratic coefficient of the cost of the i-th arc

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.

◆ ChgUCaps()

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

change the arc capacities

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.

◆ ChgUCap()

virtual void ChgUCap ( Index  arc,
FNumber  NCap 
)
pure virtual

change the capacity of the i-th arc

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.

◆ ChgDfcts()

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

change the node deficits

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

◆ ChgDfct()

virtual void ChgDfct ( Index  node,
FNumber  NDfct 
)
pure virtual

change the deficit of the i-th node

Change the deficit of the i-th node.

Note that the node "name" i 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 deficits 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.

◆ CloseArc()

virtual void CloseArc ( Index  name)
pure virtual

"close" one arc

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

◆ DelNode()

virtual void DelNode ( Index  name)
pure virtual

delete one node

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.

Note that deleting a node leaves a "hole" in the set of node names: the number of nodes as reported by MCFn() remains the same (save for the case described next). No attempt at keeping a consecutive set of valid node names is done: if this is important, it's the user who have to work towards such a goal by "moving" nodes, i.e., deleting and re-adding them, see AddNode(). The only exception is if ‘name’ here is the last node; in this case the number of nodes as reported by MCFn() is reduced by at least one, until the n-th node is not a deleted one.

◆ OpenArc()

virtual void OpenArc ( Index  name)
pure virtual

re-opens a closed arc

Restore the previously closed arc ‘name’. It is an error to open an arc that has not been previously closed.

◆ AddNode()

virtual Index AddNode ( FNumber  aDfct)
pure virtual

adds a ned node

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.

The handling of the set of node names should be arranged in a way that "tries as much as possible to have a consecutive set of small names without trying to hard". That is, if there are no deleted nodes (see DelNode()), then the new node name will be MCFn() + 1, with MCFn() being the value prior to the call, and MCFn() increasing by one after the call. If, instead, there are deleted nodes, then the new node name will be the name of the currently deleted node with smaller name, and MCFn() will remain the same.

◆ ChangeArc()

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

change the starting and/or ending node of one arc

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.

◆ DelArc()

virtual void DelArc ( Index  name)
pure virtual

deletes one arc

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

Note that deleting an arc leaves a "hole" in the set of node arcs: the number of arcs as reported by MCFm() remains the same (save for the case described next). No attempt at keeping a consecutive set of valid arc names is done: if this is important, it's the user who have to work towards such a goal by "moving" arcs, i.e., deleting and re-adding them, see AddArc(). The only exception is if ‘name’ here is the last arc; in this case the number of arcs as reported by MCFm() is reduced by at least one, until the m-th arc is not a deleted one.

◆ IsDeletedArc()

virtual bool IsDeletedArc ( Index  name) const
pure virtual

return true if and only if the arc is deleted

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. Note that a deleted arc is not closed, and vice-versa: to be closed an arc must exist, i.e., not be deleted.

Referenced by MCFClass::WriteMCF().

◆ AddArc()

virtual Index AddArc ( Index  Start,
Index  End,
FNumber  aU,
CNumber  aC 
)
pure virtual

adds a new arc

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.

The handling of the set of arc names should be arranged in a way that "tries as much as possible to have a consecutive set of small names without trying to hard". That is, if there are no deleted arcs (see DelArc()), then the new node name will be MCFm() + 1, with MCFm() being the value prior to the call, and MCFm() increasing by one after the call. If, instead, there are deleted nodes, then the new arc name will be the name of the currently deleted arc with smaller name, and MCFm() will remain the same.

Member Data Documentation

◆ status

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

Referenced by MCFClass::MCFClass(), MCFClass::MCFGetStatus(), SPTree::SetDest(), SPTree::SetOrigin(), and MCFClass::SetPar().