summaryrefslogtreecommitdiff
path: root/impl/MCFSimplex.h
diff options
context:
space:
mode:
Diffstat (limited to 'impl/MCFSimplex.h')
-rw-r--r--impl/MCFSimplex.h1086
1 files changed, 1086 insertions, 0 deletions
diff --git a/impl/MCFSimplex.h b/impl/MCFSimplex.h
new file mode 100644
index 0000000..a8d84f6
--- /dev/null
+++ b/impl/MCFSimplex.h
@@ -0,0 +1,1086 @@
+/*--------------------------------------------------------------------------*/
+/*------------------------- File MCFSimplex.h ------------------------------*/
+/*--------------------------------------------------------------------------*/
+/** @file
+ * Linear and Quadratic Min Cost Flow problems solver based on the (primal and
+ * dual) simplex algorithm. Conforms to the standard MCF interface defined in
+ * MCFClass.h.
+ *
+ * \Version 1.00
+ *
+ * \date 29 - 08 - 2011
+ *
+ * \author Alessandro Bertolini \n
+ * Antonio Frangioni \n
+ * Operations Research Group \n
+ * Dipartimento di Informatica \n
+ * Universita' di Pisa \n
+ *
+ * Copyright &copy 2008 - 2011 by Alessandro Bertolini, Antonio Frangioni
+ */
+/*--------------------------------------------------------------------------*/
+/*--------------------------------------------------------------------------*/
+/*----------------------------- DEFINITIONS --------------------------------*/
+/*--------------------------------------------------------------------------*/
+/*--------------------------------------------------------------------------*/
+
+#ifndef __MCFSimplex
+ #define __MCFSimplex /* self-identification: #endif at the end of the file */
+
+/*--------------------------------------------------------------------------*/
+/*------------------------------ INCLUDES ----------------------------------*/
+/*--------------------------------------------------------------------------*/
+
+#include "MCFClass.h"
+
+/*@} -----------------------------------------------------------------------*/
+/*--------------------------- NAMESPACE ------------------------------------*/
+/*--------------------------------------------------------------------------*/
+
+#if( OPT_USE_NAMESPACES )
+namespace MCFClass_di_unipi_it
+{
+#endif
+
+/*--------------------------------------------------------------------------*/
+/*-------------------------------- MACROS ----------------------------------*/
+/*--------------------------------------------------------------------------*/
+/** @defgroup MCFSimplex_MACROS Compile-time switches in MCFSimplex.h
+ There is only one macro in MCFSimplex, but it is very important!
+ @{ */
+
+#define QUADRATICCOST 0
+
+/**< Setting QUADRATICCOST == 1 the solver can solve problems with linear and
+ quadratic costs too (but the latter only with the Primal Simplex).
+ The reason for having a macro is that when quadratic costs are present the
+ "arcType" struct has the additional field "quadraticCost" to hold it.
+ Furthermore, the field "ident" is not created because the solver doesn't
+ use the classical TLU tripartition. Instead, closed arcs and deleted arcs
+ are characterized as follows:
+ - closed arcs have the field "cost" to INFINITY (Inf<FNumber>());
+ - deleted arcs have the field "upper" to INFINITY and the "tail" and
+ "head" field are NULL.
+ Furthermore, the solver needs the variables "ignoredEnteringArc" and
+ "firstIgnoredEnteringArc", used to avoid nasty loops during the execution
+ of the Quadratic Primal Simplex algorithm.
+ If, instead, QUADRATICCOST == 0 then the solver can solve only problems
+ with linear costs. Hence, the field "quadraticCost" is useless and it
+ isn't created. Furthermore, Primal Simplex and Dual Simplex use the
+ tripartition TLU to divide the arcs, so the solver creates the field
+ "ident", which differentiates the set of the arcs in among deleted arcs,
+ closed arcs, arcs in T, arcs in L, arcs in U.
+ Thus, with QUADRATICCOST == 0 the solver cannot solve problems with
+ quadratic costs, but it does solve problems with linear costs faster. */
+
+/*@} end( group( MCFCLASS_MACROS ) ) */
+
+/*--------------------------------------------------------------------------*/
+/*---------------------------- CLASSES -------------------------------------*/
+/*--------------------------------------------------------------------------*/
+/** @defgroup MCFSimplex_CLASSES Classes in MCFSimplex.h
+ @{ */
+
+/** The MCFSimplex class derives from the abstract base class MCFClass, thus
+ sharing its (standard) interface, and implements both the Primal and
+ Dual network simplex algorithms for solving (Linear and Quadratic)
+ Min Cost Flow problems */
+
+class MCFSimplex: public MCFClass
+{
+
+/*--------------------------------------------------------------------------*/
+/*----------------------- PUBLIC PART OF THE CLASS -------------------------*/
+/*--------------------------------------------------------------------------*/
+/*-- --*/
+/*-- The following methods and data are the actual interface of the --*/
+/*-- class: the standard user should use these methods and data only. --*/
+/*-- --*/
+/*--------------------------------------------------------------------------*/
+
+ public:
+
+/*--------------------------------------------------------------------------*/
+/*---------------------------- PUBLIC TYPES --------------------------------*/
+/*--------------------------------------------------------------------------*/
+
+/** Public enum describing the parameters of MCFSimplex. */
+
+ enum SimplexParam
+ {
+ kAlgPrimal = kLastParam , ///< parameter to set algorithm (Primal/Dual):
+ kAlgPricing , ///< parameter to set algorithm of pricing
+ kNumCandList , /**< parameter to set the number of candidate
+ list for Candidate List Pivot method */
+ kHotListSize , /**< parameter to set the size of Hot List
+ for Candidate List Pivot method */
+ kRecomputeFOLimits , /**< parameter to set the number of iterations
+ in which quadratic Primal Simplex computes
+ "manually" the f.o. value */
+ kEpsOpt /**< parameter to set the precision of the
+ objective function value for the
+ quadratic Primal Simplex */
+ };
+
+/** Public enum describing the pricing rules in MCFSimplex::SetAlg(). */
+
+ enum enumPrcngRl
+ {
+ kDantzig = 0, ///< Dantzig's rule (most violated constraint)
+ kFirstEligibleArc , ///< First eligible arc in round-robin
+ kCandidateListPivot ///< Candidate List Pivot Rule
+ };
+
+/*--------------------------------------------------------------------------*/
+/*--------------------------- PUBLIC METHODS -------------------------------*/
+/*--------------------------------------------------------------------------*/
+/*---------------------------- CONSTRUCTOR ---------------------------------*/
+/*--------------------------------------------------------------------------*/
+
+ MCFSimplex( cIndex nmx = 0 , cIndex mmx = 0 );
+
+/**< Constructor of the class, as in MCFClass::MCFClass(). */
+
+/*--------------------------------------------------------------------------*/
+/*-------------------------- OTHER INITIALIZATIONS -------------------------*/
+/*--------------------------------------------------------------------------*/
+
+ void LoadNet( cIndex nmx = 0 , cIndex mmx = 0 , cIndex pn = 0 ,
+ cIndex pm = 0 , cFRow pU = NULL , cCRow pC = NULL ,
+ cFRow pDfct = NULL , cIndex_Set pSn = NULL ,
+ cIndex_Set pEn = NULL );
+
+/**< Inputs a new network, as in MCFClass::LoadNet(). */
+
+/*--------------------------------------------------------------------------*/
+
+ void SetAlg( bool UsPrml , char WhchPrc );
+
+/**< Selects which algorithm (Primal vs Dual Network Simplex), and which
+ pricing rule within the algorithm, is used.
+
+ If UsPrml == TRUE then the Primal Network Simplex algorithm is used,
+ otherwise the Dual Network Simplex is used.
+
+ The allowed values for WhchPrc are:
+
+ - kDantzig Dantzig's pricing rule, i.e., most violated dual
+ constraint; this can only be used with the Primal
+ Network Simplex
+
+ - kFirstEligibleArcA "dumb" rule, first eligible arc in round-robin;
+
+ - kCandidateListPivot Candidate List Pivot Rule
+
+ If this method is *not* called, the Primal Network Simplex with the
+ Candidate List Pivot Rule (the best setting on most instances) is
+ used. */
+
+/*--------------------------------------------------------------------------*/
+
+ void SetPar( int par , int val );
+
+/**< Set general integer parameters.
+
+ @param par is the parameter to set; since this method accepts an int
+ value, the enum SimplexParam can be used in addition to the
+ enum MCFParam to specify the integer parameters (every enum
+ is an int).
+
+ @param value is the value to assign to the parameter. */
+
+/*-------------------------------------------------------------------------*/
+
+ void SetPar( int par , double val );
+
+/**< Set general float parameters.
+
+ @param par is the parameter to set; since this method accepts an int
+ value, the enum SimplexParam can be used in addition to the
+ enum MCFParam to specify the float parameters (every enum
+ is an int).
+
+ @param value is the value to assign to the parameter. */
+
+/*--------------------------------------------------------------------------*/
+/*-------------------- METHODS FOR SOLVING THE PROBLEM ---------------------*/
+/*--------------------------------------------------------------------------*/
+
+ void SolveMCF( void );
+
+/*--------------------------------------------------------------------------*/
+/*---------------------- METHODS FOR READING RESULTS -----------------------*/
+/*--------------------------------------------------------------------------*/
+
+ void MCFGetX( FRow F , Index_Set nms = NULL ,
+ cIndex strt = 0 , Index stp = Inf<Index>() );
+
+/*--------------------------------------------------------------------------*/
+
+ void MCFGetRC( CRow CR , cIndex_Set nms = NULL ,
+ cIndex strt = 0 , Index stp = Inf<Index>() ) ;
+
+ CNumber MCFGetRC( cIndex i );
+
+/*--------------------------------------------------------------------------*/
+
+ void MCFGetPi( CRow P , cIndex_Set nms = NULL ,
+ cIndex strt = 0 , Index stp = Inf<Index>() );
+
+/*--------------------------------------------------------------------------*/
+
+ FONumber MCFGetFO( void );
+
+/*--------------------------------------------------------------------------*/
+/*-------------- METHODS FOR READING THE DATA OF THE PROBLEM ---------------*/
+/*--------------------------------------------------------------------------*/
+
+ virtual void MCFArcs( Index_Set Startv , Index_Set Endv ,
+ cIndex_Set nms = NULL , cIndex strt = 0 ,
+ Index stp = Inf<Index>() );
+
+ inline Index MCFSNde( cIndex i );
+
+ inline Index MCFENde( cIndex i );
+
+/*--------------------------------------------------------------------------*/
+
+ void MCFCosts( CRow Costv , cIndex_Set nms = NULL ,
+ cIndex strt = 0 , Index stp = Inf<Index>() );
+
+ inline CNumber MCFCost( cIndex i );
+
+/*--------------------------------------------------------------------------*/
+
+ void MCFQCoef( CRow Qv , cIndex_Set nms = NULL ,
+ cIndex strt = 0 , Index stp = Inf<Index>() );
+
+ inline CNumber MCFQCoef( cIndex i );
+
+/*--------------------------------------------------------------------------*/
+
+ void MCFUCaps( FRow UCapv , cIndex_Set nms = NULL ,
+ cIndex strt = 0 , Index stp = Inf<Index>() );
+
+ inline FNumber MCFUCap( cIndex i );
+
+/*--------------------------------------------------------------------------*/
+
+ void MCFDfcts( FRow Dfctv , cIndex_Set nms = NULL ,
+ cIndex strt = 0 , Index stp = Inf<Index>() );
+
+ inline FNumber MCFDfct( cIndex i );
+
+/*--------------------------------------------------------------------------*/
+/*------------- METHODS FOR ADDING / REMOVING / CHANGING DATA --------------*/
+/*--------------------------------------------------------------------------*/
+/*------- Changing the costs, QCoef, deficits and upper capacities ---------*/
+/*--------------------------------------------------------------------------*/
+
+ void ChgCosts( cCRow NCost , cIndex_Set nms = NULL ,
+ cIndex strt = 0 , Index stp = Inf<Index>() );
+
+ void ChgCost( Index arc , cCNumber NCost );
+
+/*--------------------------------------------------------------------------*/
+
+ void ChgQCoef( cCRow NQCoef = NULL , cIndex_Set nms = NULL ,
+ cIndex strt = 0 , Index stp = Inf<Index>() );
+
+ void ChgQCoef( Index arc , cCNumber NQCoef );
+
+/*--------------------------------------------------------------------------*/
+
+ void ChgDfcts( cFRow NDfct , cIndex_Set nms = NULL ,
+ cIndex strt = 0 , Index stp = Inf<Index>() );
+
+ void ChgDfct( Index nod , cFNumber NDfct );
+
+/*--------------------------------------------------------------------------*/
+
+ void ChgUCaps( cFRow NCap , cIndex_Set nms = NULL ,
+ cIndex strt = 0 , Index stp = Inf<Index>() );
+
+ void ChgUCap( Index arc , cFNumber NCap );
+
+/*--------------------------------------------------------------------------*/
+/*--------------- Modifying the structure of the graph ---------------------*/
+/*--------------------------------------------------------------------------*/
+
+ void CloseArc( cIndex name );
+
+ void DelNode( cIndex name );
+
+ bool IsClosedArc( cIndex name );
+
+ void OpenArc( cIndex name ) ;
+
+ Index AddNode( cFNumber aDfct );
+
+ void ChangeArc( cIndex name , cIndex nSS = Inf<Index>() ,
+ cIndex nEN = Inf<Index>() );
+
+ void DelArc( cIndex name );
+
+ Index AddArc( cIndex Start , cIndex End , cFNumber aU , cCNumber aC );
+
+ bool IsDeletedArc( cIndex name );
+
+/*--------------------------------------------------------------------------*/
+/*------------------------------ DESTRUCTOR --------------------------------*/
+/*--------------------------------------------------------------------------*/
+
+ ~MCFSimplex();
+
+/*--------------------------------------------------------------------------*/
+/*--------------------- PRIVATE PART OF THE CLASS --------------------------*/
+/*--------------------------------------------------------------------------*/
+/*-- --*/
+/*-- Nobody should ever look at this part: everything that is under this --*/
+/*-- advice may be changed without notice in any new release of the code. --*/
+/*-- --*/
+/*--------------------------------------------------------------------------*/
+
+ private:
+
+/*--------------------------------------------------------------------------*/
+/*-------------------------- PRIVATE DATA TYPES ----------------------------*/
+/*--------------------------------------------------------------------------*/
+/*-- --*/
+/*-- Let T \subseteq A be a spanning tree, and consider some node v \in V --*/
+/*-- \setminus { 0 }. There is an unique (undirected) path, denoted by --*/
+/*-- P(v), defined by T from v to the root node 0. The arc in P(v), which --*/
+/*-- is incident to v, is called the *basic arc* of v. The other terminal --*/
+/*-- node u of this basic arc is called the *father node* of v. The --*/
+/*-- spanning tree T is represented saving the basic arc of every node, --*/
+/*-- and maintaining the order of the nodes and the depth as to T root --*/
+/*-- after a Post-Visit of T. This order is saved in a bidirectional list --*/
+/*-- written in the node. --*/
+/*-- --*/
+/*-- The Primal Simplex uses a different data structure than the Dual --*/
+/*-- Simplex, because the Dual Simplex needs additional data (mainly the --*/
+/*-- Backward Star and Forward Star. Furthermore, the Primal Simplex uses --*/
+/*-- different data structures in the quadratic case. --*/
+/*-- --*/
+/*--------------------------------------------------------------------------*/
+
+ struct arcPType; // pre-declaration of the arc structure (pointers to arcs
+ // are contained in the node structure) for Primal Simplex
+
+ struct arcDType; // pre-declaration of the arc structure (pointers to arcs
+ // are contained in the node structure) for Dual Simplex
+
+ typedef double iteratorType; // type for the iteration counter and array
+ // "whenInT2"
+
+ struct nodePType { // node structure for Primal Simplex - - - - - - - -
+ nodePType *prevInT; // previous node in the order of the Post-Visit on T
+
+ nodePType *nextInT; // next node in the order of the Post-Visit on T
+
+ arcPType *enteringTArc; // entering basic arc of this node
+
+ FNumber balance; // supply/demand of this node; a node is called a
+ // supply node, a demand node, or a transshipment
+ // node depending upon whether balance is larger
+ // than, smaller than, or equal to zero
+ #if( QUADRATICCOST )
+ CNumber sumQuadratic; // the sum of the quadratic coefficients of the tree's arcs
+ // from root of T to the node
+
+ FONumber potential; // the node potential corresponding with the flow
+ // conservation constrait of this node
+ #else
+ CNumber potential; // the node potential corresponding with the flow
+ // conservation constrait of this node
+ #endif
+
+ int subTreeLevel; // the depth of the node in T as to T root
+
+ }; // end( struct( nodePType ) )
+
+ struct nodeDType { // node structure for Dual Simplex - - - - - - - - -
+ nodeDType *prevInT; // previous node in the order of the Post-Visit on T
+
+ nodeDType *nextInT; // next node in the order of the Post-Visit on T
+
+ arcDType *enteringTArc; // entering basic arc of this node
+
+ FNumber balance; // supply/demand of this node; a node is called a
+ // supply node, a demand node, or a transshipment
+ // node depending upon whether balance is larger
+ // than, smaller than, or equal to zero
+
+ #if( QUADRATICCOST )
+ CNumber sumQuadratic; // the sum of the quadratic coefficients of the tree's arcs
+ // from root of T to the node
+
+ FONumber potential; // the node potential corresponding with the flow
+ // conservation constrait of this node
+ #else
+ CNumber potential; // the node potential corresponding with the flow
+ // conservation constrait of this node
+ #endif
+
+ int subTreeLevel; // the depth of the node in T as to T root
+ iteratorType whenInT2; // the last iteration where a node is in subtree T2
+
+ Index numArcs; // the number of the arcs which enter/exit from node
+ arcDType *firstBs; // the first arc in the node's Backward Star
+ arcDType *firstFs; // the first arc in the node's Forward Star
+
+ }; // end( struct( nodeDType ) )
+
+ struct arcPType { // arc structure for Primal Simplex - - - - - - - -
+ nodePType *tail; // tail node
+ nodePType *head; // head node
+ FNumber flow; // arc flow
+ CNumber cost; // arc linear cost
+
+ #if( QUADRATICCOST )
+ CNumber quadraticCost; // arc quadratic cost
+ #else
+ char ident; // tells if arc is deleted, closed, in T, L, or U
+ #endif
+
+ FNumber upper; // arc upper bound
+ }; // end( struct( arcPType ) )
+
+ struct arcDType { // arc structure for Primal Simplex - - - - - - - -
+ nodeDType *tail; // tail node
+ nodeDType *head; // head node
+ FNumber flow; // arc flow
+ CNumber cost; // arc linear cost
+
+ #if( QUADRATICCOST )
+ CNumber quadraticCost; // arc quadratic cost
+ #else
+ char ident; // indicates if arc is deleted, closed, in T, in L, or in U
+ #endif
+
+ FNumber upper; // arc upper bound
+ arcDType *nextBs; // the next arc in the Backward Star of the arc's head
+ arcDType *nextFs; // the next arc in the Forward Star of the arc's tail
+
+ }; // end( struct( arcDType ) )
+
+ struct primalCandidType { // Primal Candidate List- - - - - - - - - - - - -
+ arcPType *arc; // pointer to the violating primal bound arc
+
+ #if(QUADRATICCOST )
+ FONumber absRC; // absolute value of the arc's reduced cost
+ #else
+ CNumber absRC; // absolute value of the arc's reduced cost
+ #endif
+ }; // end( struct( primalCandidateType ) )
+
+ struct dualCandidType { // Dual Candidate List- - - - - - - - - - - - - -
+ nodeDType *node; // deepest node violating the dual bound arc
+ FNumber absInfeas; // absolute value of the arc's flow infeasibility
+ }; // end( struct( dualCandidateType ) )
+
+/*--------------------------------------------------------------------------*/
+/*----------------------- PRIVATE DATA STRUCTURES -------------------------*/
+/*--------------------------------------------------------------------------*/
+
+ bool usePrimalSimplex; // TRUE if the Primal Network Simplex is used
+
+ char pricingRule; // which pricing rule is used
+
+ nodePType *nodesP; // vector of nodes: points to the n + 1 node
+ // structs (including the dummy root node)
+ // where the first node is indexed by zero
+ // and the last node is the dummy root node
+
+ nodePType *dummyRootP; // the dummy root node
+
+ nodePType *stopNodesP; // first infeasible node address = nodes + n
+
+ arcPType *arcsP; // vector of arcs; this variable points to
+ // the m arc structs.
+
+ arcPType *dummyArcsP; // vector of artificial dummy arcs: points
+ // to the artificial dummy arc variables and
+ // contains n arc structs. The artificial
+ // arcs are used to build artificial feasible
+ // starting bases. For each node i, there is
+ // exactly one dummy arc defined to connect
+ // the node i with the dummy root node.
+
+ arcPType *stopArcsP; // first infeasible arc address = arcs + m
+
+ arcPType *stopDummyP; // first infeasible dummy arc address
+ // = arcs + m + n
+
+ arcPType *arcToStartP; // Dantzig Rule and First Eligible Arc Rule
+ // start their search from this arc
+
+ nodeDType *nodesD; // vector of nodes: points to the n + 1 node
+ // structs (including the dummy root node)
+ // where the first node is indexed by zero
+ // and the last node is the dummy root node
+
+ nodeDType *dummyRootD; // the dummy root node
+
+ nodeDType *stopNodesD; // first infeasible node address = nodes + n
+
+ arcDType *arcsD; // vector of arcs; this variable points to
+ // the m arc structs.
+
+ arcDType *dummyArcsD; // vector of artificial dummy arcs: points to
+ // to the artificial dummy arc variables and
+ // contains n arc structs. The artificial
+ // arcs are used to build artificial feasible
+ // starting bases. For each node i, there is
+ // exactly one dummy arc defined to connect
+ // the node i with the dummy root node.
+
+ arcDType *stopArcsD; // first infeasible arc address = arcs + m
+
+ arcDType *stopDummyD; // first infeasible dummy arc address
+ // = arcs + m + n
+
+ arcDType *arcToStartD; // Dantzig Rule and First Eligible Arc Rule
+ // start their search from this arc
+
+ iteratorType iterator; // the current number of iterations
+
+ primalCandidType *candP; // every element points to an element of the
+ // arcs vector which contains an arc violating
+ // dual bound
+
+ dualCandidType *candD; // every element points to an element of the
+ // arcs vector which contains an arc violating
+ // primal bond
+
+ Index numGroup; // number of the candidate lists
+
+ Index tempCandidateListSize; // hot list dimension (it is variable)
+
+ Index groupPos; // contains the actual candidate list
+
+ Index numCandidateList; // number of candidate lists
+
+ Index hotListSize; // number of candidate lists and hot list dimension
+
+ Index forcedNumCandidateList; // value used to force the number of candidate list
+
+ Index forcedHotListSize; // value used to force the number of candidate list
+ // and hot list dimension
+
+ bool newSession; // true if algorithm is just started
+
+ CNumber MAX_ART_COST; // large cost for artificial arcs
+
+ FNumber *modifiedBalance; // vector of balance used by the PostVisit
+
+ FONumber EpsOpt; // the precision of the objective function value
+ // for the quadratic case of the Primal Simplex
+
+ int recomputeFOLimits; // after how many iterations the quadratic Primal
+ // Simplex computes "manually" the o.f. value
+
+ #if( QUADRATICCOST )
+ FONumber foValue; // the temporary objective function value
+ #endif
+
+/*--------------------------------------------------------------------------*/
+/*-------------------------- PRIVATE METHODS -------------------------------*/
+/*--------------------------------------------------------------------------*/
+
+ void MemAlloc( void );
+
+/**< Method to allocate memory for the main data structures. It creates the
+ vector of nodes, the vector of arcs (real and dummy). If the algorithm is
+ using the Dual Simplex, it creates also the vectors whenInT2, firstIn and
+ nextIn, usefull to identify the next entering. */
+
+/*--------------------------------------------------------------------------*/
+
+ void MemDeAlloc( bool whatDeAlloc );
+
+/**< Method to deallocate memory for the main data structures created in
+ MemAlloc(). */
+
+/*--------------------------------------------------------------------------*/
+
+ void MemAllocCandidateList( void );
+
+/**< Method to allocate memory for the data structure used by the Candidate
+ List Pivot Rule. It creates the vector of candP (or candD in the Dual
+ Simplex case), determining the size of this vector on the basis of number
+ of arcs or nodes. */
+
+/*--------------------------------------------------------------------------*/
+
+ void MemDeAllocCandidateList( void );
+
+/**< Method to deallocate memory for the data structures created in
+ MemAllocCandidateList(). */
+
+/*--------------------------------------------------------------------------*/
+
+ void CreateInitialPrimalBase( void );
+
+/**< Method to create an initial feasible primal base. Add one node (dummyRoot)
+ to the network and connect this dummy root to each real node with n dummy
+ arcs. For each source node i, a dummy arc (i, r) exists. For each sink or
+ transit node j, a dummy arc (r, j) exists. The source nodes send their flows
+ to the dummy root through their dummy arcs, so the dummy root send all to
+ the sink nodes. The dummy root balance is 0, the costs of dummy arcs are
+ fixed to "infinity". */
+
+/*--------------------------------------------------------------------------*/
+
+ void CreateInitialDualBase( void );
+
+/**< Method to create an initial feasible dual base. Add one node (dummyRoot)
+ to the network and connect this dummy root to each real node with n dummy
+ arcs. The source nodes send their flows to the dummy root through their
+ dummy arcs, so the dummy root send all to the sink nodes. The dummy root
+ balance is 0, the costs of dummy arcs are fixed to "infinity". */
+
+/*--------------------------------------------------------------------------*/
+
+ void CreateAdditionalDualStructures( void );
+
+/**< The Dual Simplex needs nodes' Backward and Forward Star to work. So when
+ the Primal Simplex runs, these structures don't exist. When the Dual
+ Simplex starts, these structure are created in this method. */
+
+/*--------------------------------------------------------------------------*/
+
+ void PrimalSimplex( void );
+
+/**< Main method to implement the Primal Simplex algorithm. */
+
+/*--------------------------------------------------------------------------*/
+
+ void DualSimplex( void );
+
+/**< Main method to implement the Dual Simplex algorithm. */
+
+/*--------------------------------------------------------------------------*/
+
+ template<class N, class A>
+ void UpdateT( A *h , A *k , N *h1 , N *h2 , N *k1 , N *k2 );
+
+ /**< Method to update the spanning tree T every iteration.
+ The spanning tree T is implemented with a bidirectional list stored
+ in the node structure, which represents the nodes' order after a
+ Post-Visit. The parameter of the method are the outgoing arc "h", the
+ incoming arc "k", and the four nodes on the extremity of these arcs
+ (for example h2 is the deepest node of the outgoing arc). Removing the
+ arc "h" splits T in two subtrees: T1 (which contains the root of T) and
+ T2, which will be re-connected by the incoming arc "k".
+ T2 will be reordered; in fact, the node "k2" becomes the root of T2
+ instead of "h2" and the hierarchy of T2 will be overturned. Then T2 will
+ be moved; the root of T2 is changed, therefore the predecessor of the
+ root will become the node "k1".
+
+ This method uses the methods cutAndUpdateSubtree() and pasteSubtree().
+ First it cuts the node "k2" and its subtree from T using
+ cutAndUpdateSubtree(). Moreover the method cutAndUpdateSubtree()
+ updates the field "subTreeLevel" of every subtree's nodes, since k2's
+ subtree will be moved from the bottom to the top of T2. Then the method
+ pasteSubtree() puts this subtree in the bidirectional list after the node
+ "k1". The same operations will be applied to the old precedessor of "k2"
+ (which will become one of the childs of "k2"). This second subtree will
+ be cut, the subTreeLevel fields will be updated, and it will be inserted
+ in the bidirectional list after the k2's subtree. This is iterated until
+ the node "h2" is reached. */
+
+/*--------------------------------------------------------------------------*/
+
+ template<class N>
+ N* CutAndUpdateSubtree( N *root, int delta );
+
+/**< This method cuts a generic subtree from the spanning tree T. Then it
+ updates the field "subTreeLevel" of every subtree's nodes adding the value
+ "delta". This method returns the last node of the subtree. */
+
+/*--------------------------------------------------------------------------*/
+
+ template<class N>
+ void PasteSubtree( N *root , N *lastNode , N *previousNode );
+
+/**< This method inserts a generic subtree with root passed by parameter into
+ the spanning tree T, between the nodes "previousNode" and "lastNode". */
+
+/*--------------------------------------------------------------------------*/
+
+ arcPType* RuleDantzig( void );
+
+/**< This method returns an arc which violates the dual conditions. It searchs
+ the arc with most violation of dual conditions in the entire set of real
+ arcs. It can be used only by the Primal Simplex in the case of networks
+ with linear costs. */
+
+/*--------------------------------------------------------------------------*/
+
+ arcPType* PRuleFirstEligibleArc( void );
+
+/**< This method returns the first found arc which violates the dual conditions
+ in the case of Primal Simplex, the primal condition in the case of Dual
+ Simplex. It can be used only in the case of networks with linear costs. */
+
+/*--------------------------------------------------------------------------*/
+
+ arcDType* DRuleFirstEligibleArc( void );
+
+/**< This method returns the first found arc which violates the dual conditions
+ in the case of Primal Simplex, the primal condition in the case of Dual
+ Simplex. It can be used only in the case of networks with linear costs. */
+
+/*--------------------------------------------------------------------------*/
+
+ arcPType* RulePrimalCandidateListPivot( void );
+
+/**< This method returns an arc which violates the dual conditions. It searches
+ the arc with most violation of dual conditions in a small set of candidate
+ arcs. In every iteration the method rebuilds this set of arcs executing three
+ phases:
+
+ - in the first phase it analyzes the remaining arcs and delete the arcs which
+ don't violate the dual condition any more;
+
+ - in the second phase it tries to fill the set, so it searchs other arcs
+ which violate the dual condition: the set of arcs is divided into "buckets"
+ which are searched sequentially until the candidate list is full; the
+ last visited bucket is retained, and the search is restarted from that
+ one at later iterations
+
+ - in the third phase the small set of candidate arcs is ordered according
+ to the violation of dual condition by the method SortPrimalCandidateList()
+ using an implementation of the algorithm "quicksort".
+
+ At last the method returns the first arc in the ordered small set. If the
+ arc doesn't exist (the set is empty), it returns NULL. */
+
+/*--------------------------------------------------------------------------*/
+
+ inline void InitializePrimalCandidateList( void );
+
+/**< Method to initialize some important details for Primal Candidate List
+ Rule. */
+
+/*--------------------------------------------------------------------------*/
+
+ inline void SortPrimalCandidateList( Index min , Index max );
+
+/**< Method to order the little set of candidate arcs according to
+ infeasibility of dual conditions. It implements the "quicksort"
+ algorithm. */
+
+/*--------------------------------------------------------------------------*/
+
+ arcDType* RuleDualCandidateListPivot( void );
+
+/**< Similar to RulePrimalCandidateListPivot() for the Dual Simplex. */
+
+/*--------------------------------------------------------------------------*/
+
+ inline void InitializeDualCandidateList( void );
+
+/**< Method to initialize some important details for Dual Candidate List Rule.
+ */
+
+/*--------------------------------------------------------------------------*/
+
+ inline void SortDualCandidateList( Index min , Index max );
+
+/**< Similar to SortPrimalCandidateList() for the Dual Simplex. */
+
+/*--------------------------------------------------------------------------*/
+
+ template<class N, class RCT>
+ inline void AddPotential( N *r , RCT delta );
+
+/**< Method to quickly update the dual solutions. During the change of the
+ base, the potential of node "k2" (deepest node in T of incoming arc "k",
+ and new root of T2) changes according to the new structure of T. In fact,
+ the precedessor of "k2" changes: now the predecessor of "k2"is "k1" (the
+ other node of the incoming arc "k"). This change of predecessor causes a
+ change of potential of "k2". The change of potential of "k2" causes the
+ changes of potential of all nodes of T2. This method computes the change
+ of potential of "k2" and applies it on all the nodes of T2. */
+
+/*--------------------------------------------------------------------------*/
+
+ template<class N>
+ inline void ComputePotential( N *r );
+
+/**< Method to update the dual solutions. It computes all the potential of the
+ nodes of the subtree which has r as root. */
+
+/*--------------------------------------------------------------------------*/
+
+ inline void ResetWhenInT2( void );
+
+/**< Method to order the small set of candidate arcs according to dual
+ infeasibility. It implements the algorithm "quicksort". */
+
+/*--------------------------------------------------------------------------*/
+
+ void CreateInitialPModifiedBalanceVector( void );
+
+/**< Method to initialize the vector of modified balance for the postvisit on
+ T in the Primal Simplex data structure. */
+
+/*--------------------------------------------------------------------------*/
+
+ void PostPVisit( nodePType *r );
+
+/**< Method to calculate the flow on the basic arcs with the Primal Simplex's
+ data structure. It uses the set of the upper bound arcs, the construction
+ of a modified balance vector and the postvisit on T. */
+
+/*--------------------------------------------------------------------------*/
+
+ void BalanceFlow( nodePType *r );
+
+/**< This method works after the method PostPVisit (in a Primal context). It
+ restores primal admissimibility on the r's subtree. It starts from the leaf
+ of the subtree and goes up to the root, using the method AdjustFlow. */
+
+/*--------------------------------------------------------------------------*/
+
+ void AdjustFlow( nodePType *r );
+
+/**< This method checks the primal admissibility of the r's basic entering arc.
+ If it is out of bounds, the method removes it from the tree (and keeps the
+ relative dummy arc) and push flow in the cycle (some tree's arc and the old
+ entering arc) to restores the right balances of the node. */
+
+/*--------------------------------------------------------------------------*/
+
+ void CreateInitialDModifiedBalanceVector( void );
+
+/**< Method to initialize the vector of modified balance for the postvisit on
+ T in the Dual Simplex data structure. */
+
+/*--------------------------------------------------------------------------*/
+
+ void PostDVisit( nodeDType *r );
+
+/**< Method to calculate the flow on the basic arcs with the Dual Simplex's data
+ structure, using the set of the upper bound arcs, the construction of a
+ modified balance vector and the postvisit on T. */
+
+/*--------------------------------------------------------------------------*/
+
+ template<class N, class A>
+ inline N* Father( N *n, A *a );
+
+/**< Method to find the predecessor of the node in the tree. */
+
+/*--------------------------------------------------------------------------*/
+
+ #if(QUADRATICCOST)
+ template<class A>
+ inline FONumber ReductCost( A *a );
+ #else
+ template<class A>
+ inline CNumber ReductCost( A *a );
+ #endif
+
+/**< Method to calculate the reduct cost of the arc. */
+
+/*--------------------------------------------------------------------------*/
+
+ inline FONumber GetFO( void );
+
+/**< Method to calculate the temporary (or the final) objective function
+ value. */
+
+/*--------------------------------------------------------------------------*/
+
+ void PrintPNode( nodePType *nodo );
+
+/**< Method to print the "name" of the node in the Primal Simplex. */
+
+/*--------------------------------------------------------------------------*/
+
+ void PrintPArc( arcPType *arc );
+
+/**< Method to print the "name" of the arc in the Primal Simplex. */
+
+/*--------------------------------------------------------------------------*/
+
+ void PrintDNode( nodeDType *nodo );
+
+/**< Method to print the "name" of the node in the Dual Simplex. */
+
+/*--------------------------------------------------------------------------*/
+
+ void PrintDArc( arcDType *arc );
+
+/**< Method to print the "name" of the arc in the Dual Simplex. */
+
+/*--------------------------------------------------------------------------*/
+
+ nodePType* RecoverPNode( Index ind );
+
+/**< Method to find a node (in the Primal Simplex) using its index. */
+
+/*--------------------------------------------------------------------------*/
+
+ arcPType* RecoverPArc( nodePType *tail , nodePType *head );
+
+/**< Method to find an arc (in the Primal Simplex) using 2 pointers to tail
+ node and head node. */
+
+/*--------------------------------------------------------------------------*/
+
+ nodeDType* RecoverDNode( Index ind );
+
+/**< Method to find a node (in the Dual Simplex) using its index. */
+
+/*--------------------------------------------------------------------------*/
+
+ arcDType* RecoverDArc( nodeDType *tail , nodeDType *head );
+
+/**< Method to find an arc (in the Dual Simplex) using 2 pointers to tail
+ node and head node. */
+
+/*--------------------------------------------------------------------------*/
+
+ void infoPNode( nodePType *node , int tab );
+
+/**< Method to print some information of the node (in the Primal Simplex). */
+
+/*--------------------------------------------------------------------------*/
+
+ void infoPArc( arcPType *arc , int ind , int tab );
+
+/**< Method to print some information of the arc (in the Primal Simplex). */
+
+/*--------------------------------------------------------------------------*/
+
+ void infoDNode( nodeDType *node , int tab );
+
+/**< Method to print some information of the node (in the Dual Simplex). */
+
+/*--------------------------------------------------------------------------*/
+
+ void infoDArc( arcDType *arc , int ind , int tab );
+
+/**< Method to print some information of the arc (in the Dual Simplex). */
+
+/*--------------------------------------------------------------------------*/
+
+ void ShowSituation( int tab );
+
+/**< Method to show the actual complete situation. */
+
+/*--------------------------------------------------------------------------*/
+
+ }; // end( class MCFSimplex )
+
+/* @} end( group( MCFSimplex_CLASSES ) ) */
+
+#endif /* MCFSimplex.h included */
+
+/*-------------------------------------------------------------------------*/
+/*-------------------inline methods implementation-------------------------*/
+/*-------------------------------------------------------------------------*/
+
+inline MCFClass::Index MCFSimplex::MCFSNde( MCFClass::cIndex i )
+{
+ if( usePrimalSimplex )
+ return( Index( ( (arcsP + i)->tail - nodesP + 1 ) - USENAME0 ) );
+ else
+ return( Index( ( (arcsD + i)->tail - nodesD + 1 ) - USENAME0 ) );
+ }
+
+/*-------------------------------------------------------------------------*/
+
+inline MCFClass::Index MCFSimplex::MCFENde( MCFClass::cIndex i )
+{
+ if( usePrimalSimplex )
+ return( Index( ( (arcsP + i)->head - nodesP + 1 ) - USENAME0 ) );
+ else
+ return( Index( ( (arcsD + i)->head - nodesD + 1 ) - USENAME0 ) );
+ }
+
+/*-------------------------------------------------------------------------*/
+
+inline MCFClass::CNumber MCFSimplex::MCFCost( MCFClass::cIndex i )
+{
+ if( usePrimalSimplex )
+ return( (arcsP + i)->cost );
+ else
+ return( (arcsD + i)->cost );
+ }
+
+/*-------------------------------------------------------------------------*/
+
+inline MCFClass::CNumber MCFSimplex::MCFQCoef( MCFClass::cIndex i )
+{
+ #if( QUADRATICCOST )
+ if( usePrimalSimplex )
+ return( (arcsP + i)->quadraticCost );
+ else
+ return( (arcsD + i)->quadraticCost );
+ #else
+ return( 0 );
+ #endif
+ }
+
+/*-------------------------------------------------------------------------*/
+
+inline MCFClass::FNumber MCFSimplex::MCFUCap( MCFClass::cIndex i )
+{
+ if( usePrimalSimplex )
+ return( (arcsP + i)->upper );
+ else
+ return( (arcsD + i)->upper );
+ }
+
+/*-------------------------------------------------------------------------*/
+
+inline MCFClass::FNumber MCFSimplex::MCFDfct( MCFClass::cIndex i )
+{
+ if( usePrimalSimplex )
+ return( (nodesP + i)->balance );
+ else
+ return( (nodesD + i)->balance );
+ }
+
+/*-------------------------------------------------------------------------*/
+
+#if( QUADRATICCOST )
+
+template <class A>
+inline MCFSimplex::FONumber MCFSimplex::ReductCost( A *a )
+{
+ FONumber redc = (a->tail)->potential - (a->head)->potential;
+ redc = redc + a->cost;
+ redc = redc + a->quadraticCost * a->flow;
+ return( redc );
+ }
+
+#else
+
+template <class A>
+inline MCFSimplex::CNumber MCFSimplex::ReductCost( A *a )
+{
+ CNumber redc = (a->tail)->potential - (a->head)->potential;
+ redc = redc + a->cost;
+ return( redc );
+ }
+
+#endif
+
+/*-------------------------------------------------------------------------*/
+
+#if( OPT_USE_NAMESPACES )
+}; // end( namespace MCFClass_di_unipi_it )
+#endif
+
+/*-------------------------------------------------------------------------*/
+/*-------------------------------------------------------------------------*/
+
+/*-------------------------------------------------------------------------*/
+/*---------------------- End File MCFSimplex.h ----------------------------*/
+/*-------------------------------------------------------------------------*/