The MCFClass Project
|
This abstract base class defines a standard interface for (linear or convex quadartic separable) Min Cost Flow (MCF) problem solvers. More...
#include <MCFClass.h>
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:
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 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 (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 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 | |
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) | |
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.
enum MCFParam |
Public enum describing the possible parameters of the MCF solver, to be used with the methods SetPar() and GetPar().
enum MCFStatus |
enum MCFAnswer |
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 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.
|
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.
|
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:
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().
|
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.
References MCFClass::ChgQCoef(), and MCFClass::LoadNet().
|
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.
|
inlinevirtual |
set integer parameters of the algorithm
Set integer parameters of the algorithm.
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:
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().
|
inlinevirtual |
set float parameters of the algorithm.
Set float parameters of the algorithm.
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:
\[ 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.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.
|
inlinevirtual |
returns one of the integer parameters of the algorithm
This method returns one of the integer parameters of the algorithm.
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, 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().
|
inlinevirtual |
returns one of the double parameters of the algorithm
This method returns one of the double parameters of the algorithm.
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.
Reimplemented in MCFCplex, and RelaxIV.
References MCFClass::EpsCst, MCFClass::EpsDfct, MCFClass::EpsFlw, MCFClass::kEpsCst, MCFClass::kEpsDfct, MCFClass::kEpsFlw, MCFClass::kMaxTime, and MCFClass::MaxTime.
|
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.
References MCFClass::MCFt, and OPTtimers::ReSet().
|
pure virtual |
solve the problem
Solver of the Min Cost Flow Problem. Attempts to solve the MCF instance currently loaded in the object.
|
inline |
returns the solution status
Returns an int describing the current status of the MCF solver. Possible return values are:
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().
|
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.
|
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().
|
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.
|
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.
|
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().
|
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.
|
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.
Implemented in MCFCplex, MCFSimplex, and SPTree.
|
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.
Reimplemented in MCFCplex, MCFSimplex, and SPTree.
Referenced by MCFClass::CheckDSol().
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.
Implemented in MCFCplex, MCFSimplex, and SPTree.
|
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
Implemented in SPTree.
Referenced by MCFClass::CheckDSol(), MCFClass::CheckPSol(), and MCFClass::MCFGetDFO().
|
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().
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:
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.
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.
|
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.
|
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:
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.
|
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().
|
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().
|
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().
|
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.
|
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.
|
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().
|
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().
|
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.
return the starting (tail) node of the arc ‘i’
Return the starting (tail) node of the arc ‘i’.
Referenced by MCFClass::CheckDSol(), MCFClass::CheckPSol(), and MCFClass::WriteMCF().
return the ending (head) node of the arc ‘i’
Return the ending (head) node of the arc ‘i’.
Referenced by MCFClass::CheckDSol(), MCFClass::CheckPSol(), and MCFClass::WriteMCF().
|
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.
|
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.
|
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.
|
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.
|
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.
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.
|
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().
|
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.
|
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.
|
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.
return the deficit of the i-th node
Return the deficit of the i-th node.
Referenced by MCFClass::CheckDSol(), and MCFClass::WriteMCF().
|
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.
Referenced by MCFClass::CheckPSol().
|
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:
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.
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.
|
pure virtual |
change the arc costs
Change the arc costs. In particular, change the costs that are:
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.
change the cost of the i-th arc
Change the cost of the i-th arc.
|
inlinevirtual |
change the quadratic coefficients of the arc costs
Change the quadratic coefficients of the arc costs. In particular, change the coefficients that are:
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.
Referenced by MCFClass::LoadDMX().
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.
|
pure virtual |
change the arc capacities
Change the arc capacities. In particular, change the capacities that are:
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.
change the capacity of the i-th arc
Change the capacity of the i-th arc.
|
pure virtual |
change the node deficits
Change the node deficits. In particular, change the deficits that are:
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 ).
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 ).
|
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.
|
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.
|
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.
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.
|
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.
|
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.
|
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().
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.
|
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().