* ************************************************************************* subroutine status( bound, pr, thr, rthr, depth, pivstr, npiv, + pivot, lib, ba, nba, su, nsu, x, xst, nroot, + nro, kandis, ftstem, fr, to, bep, beptr, kdist, + iss, naibs, ip, nb, nacti ) * ************************************************************************* * Purpose : * --------- * This routine updates the status of the variables. When a * superbasic variable strikes a bound then it becomes nonbasic. * When a basic variable strikes a bound then it is exchanged * with an appropriate superbasic variable, and the resulting new * superbasic variable is made nonbasic. The related pivoting and * the new maximal basis spanning tree are easily obtained by * using the four data structure vectors PR, THR, RTHR and DEPTH. * Parameters : * ------------ * bound ( int ) * input : 0 iff no basic and superbasic variable strike a bound. * 1 iff at least one basic variable strike a bound. * 2 iff no basic variable hit a bound and a least one * superbasic variable strikes a bound. * output : unmodified. * pr ( int ) * input : the predecessor data structure vector. * output : this data structure vector is updated each time a * pivoting is performed. * thr ( int ) * input : the traversal data structure vector. * output : this data structure vector is updated each time a * pivoting is performed. * rthr ( int ) * input : the reverse data structure vector. * output : this data structure vector is updated each time a * pivoting is performed. * depth ( int ) * input : the depth data structure vector. * output : this data structure vector is updated each time a * pivoting is performed. * pivstr ( int ) * input : = 0, the candidate with the maximum smallest * distance form its value to its nearest * bound is choosen, * = 1, the candidate with the smallest flow * augmenting path length is choosen, * = 2, the first candidate is choosen. * output : unmodified. * npiv ( int ) * input : the number of minor iterations involving a pivoting. * output : this number is increased by one if at least one pivoting * is performed during this procedure. * pivot ( log ) * input : meaningless. * output : .true. iff at least one pivoting has been performed * during the current iteration. * .false. otherwise. * lib ( int ) * input : this vector contains the indices of the * basic variables composing the maximal * basis spanning tree. The ith component * corresponds to the indice of the basic * arc whose endnodes are i and PR(i). * output : this vector is updated each time a * pivoting is performed. * ba ( int ) * input : vector containing the indices of the basic variables. * output : for each bounded basic variable, this vector is updated * by a pivoting or by removing the basic variable when * no pivoting is possible. * nba ( int ) * input : the number of basic variables. * output : this number is decreased by one each time a basic * variable is bounded and no pivoting is possible. * su ( int ) * input : vector containing the indices of the superbasic * variables. * output : the vector contains only the indices of the * superbasic variables that are not bounded. * nsu ( int ) * input : the number of superbasic variables. * output : the number of superbasic variables that are not * bounded. * x ( dble ) * input : the current iterate vector. * output : unmodified. * xst ( int ) * input : vector containing the status of the variables. * output : if a pivoting is performed, the status of the * basic outgoing arc KOUT is modified and corresponds * to the status of a superbasic variable, the status * of the superbasic ingoing arc is modified and * corresponds to the status of a basic variable. * The status of the superbasic variables that are * bounded are modified and correspond to the status * of nonbasic variables. * nroot ( int ) * input : the root of the subtree defined by the basic * variables whose indices are in BA. * output : when a pivoting has been performed, the root * is updated. * nro ( int ) * input : the sum of the lengths of the flow augmenting * paths of all the superbasic variables. * output : this value is updated after each pivoting. * kandis ( int ) * input : the length of the longest flow augmenting path. * output : this length is updated after each pivoting. * ftstem ( int ) * input : vector containing for each superbasic variable * the length of its origine node to the stem node * and the length of its flow augmenting path. * output : this vector is updated after each pivoting. * fr ( int ) * input : vector containing the origine nodes of the arcs. * output : unmodified. * to ( int ) * input : vector containing the end nodes of the arcs. * output : unmodified. * bep ( int ) * input : it contains the flow augmenting paths of all * the superbasic variables in the current subspace. * output : when a pivoting has been performed, this vector * is updated. * beptr ( int ) * output : array whose kth value is the position of the * first element of the the flow augmenting path * of the superbasic variable K, in array BEP. * output : when a pivoting has been performed, this array * is updated. * kdist ( int ) * input : vector containing for each superbasic variable * the length of its flow augmenting path. * output : only the components of the superbasic variables * that are not bounded are updated and maintained. * iss ( int ) * input : vector whose kth component contains the indice of * independent superbasic set in which the kth variable * is included. If the kth component is zero, then * variable k is not included in one independent set. * output : the components corresponding to the indices of the * superbasic variables that are bounded are set to zero. * If the superbasic set becomes empty, the components * corresponding to the indices of the basic variables are * also set to zero. * If a basic variable is bounded and no non bounded * superbasic variable is found to pivot with it, then * the component corresponding to the indice of the basic * variable is set to zero. * naibs ( int ) * input : vector whose IPth component contains the number * of superbasic variables in independent set IP. * output : the component decreases by one each time a * superbasic variable is detected as bounded. * ip ( int ) * input : the indice of the independent superbasic set * in which where are working. * output : unmodified. * nb ( int ) * input : the number of nonbasic variables. * output : this number increases by one each time a * superbasic variable is detected as bounded. * nacti ( int ) * input : the number of variables that have been activated. * output : this number increases by one each time a * superbasic variable is detected as bounded. * Routines used : * --------------- * gxbdg, super, hpivot, sxba, * sxsu, dkstem, nbstat, robs. * Programming : * ------------- * D. Tuyttens * ======================================================================== * Routine parameters integer bound, pr(*), thr(*), rthr(*), depth(*), npiv, + pivstr, kdist(*), lib(*), ba(*), nba, su(*),nsu, + xst(*), nroot, nro, kandis, ftstem(*), fr(*), + to(*), bep(*), beptr(*), iss(*), naibs(*), ip, + nb, nacti logical pivot double precision x(*) * Internal variables integer ik, k, j, inkout, indkin, iaux, kin, kout, + nsi, nsj, nbj logical susel, gxbdg * * Initialization. * pivot = .false. * * We test if at least one variable strikes a bound. * if( bound.ne.0 ) then * * At least one variable strikes a bound. * if( bound.ne.2 ) then * * A basic variable strikes a bound. * do 10 ik = 1 , nba k = ba(ik) * * We select the bounded basic variables. * if( gxbdg(xst(k)) ) then susel = .false. inkout = ik kout = k * * We select a non bounded superbasic variable candidate * for pivoting with the bounded basic variable KOUT. * call super( kout, indkin, nsi, nsj, nbj, susel, + pivot, pivstr, fr, to, su, nsu, x, + xst, ftstem, bep, beptr, pr ) * * We test if a candidate is found. * if( susel ) then * * KIN is the non bounded superbasic variable candidate * for pivoting with the bounded basic variable KOUT. * kin = su(indkin) * * A pivoting is performed. The four data * structure vectors PR, THR, RTHR and DEPTH * are updated. * call hpivot( kin, pr, thr, rthr, depth, + lib, nsi, nsj, nbj ) * * Variable KIN becomes basic and variable * KOUT becomes temporarily superbasic. * pivot = .true. call sxba(xst(kin)) call sxsu(xst(kout)) iaux = ba(inkout) ba(inkout) = su(indkin) su(indkin) = iaux * * For each superbasic variable, we compute the * length from its endnodes to the stem node. The * lenght of its flow augmenting path is also computed. * nro = 0 kandis = 0 do 20 j = 1 , nsu call dkstem( su(j), fr, to, pr, depth, + ftstem, nro, kandis ) 20 continue else * * No candidate is found for pivoting. * The basic variable KOUT is removed * from the basic variable list BA. * iss(kout) = 0 ba(ik) = ba(nba) nba = nba - 1 nacti = nacti + 1 endif endif 10 continue endif * * We modify the status of the superbasic variables * that are bounded. These variables become nonbasic. * The superbasic set SU is reordered. * call nbstat( x, xst, su, nsu, ba, nba, nb, nacti, + naibs, iss, ip, kdist ) * * When a pivoting is performed, we store in array BEP the * flow augmenting paths for all the superbasic variables * whose indices are in SU. The root of the subtree defined * by the basic variables whose indices are in BA is also obtained. * if( pivot ) then call robs( nroot, fr, to, lib, ba, nba, su, nsu, + bep, beptr, ftstem, pr, depth, xst, kdist ) npiv = npiv + 1 endif endif * return end