* ************************************************************************* subroutine deact( fr, to, pr, depth, ftstem, nro, kandis, bep, + elvar, elptr, su, nsu, ba, nba, can, ncan, + optmal, xst, elst, ndacti, ndacts, nb, opt, + fnoise, rgra, gptr, gra, x, fuval, w2, nipst, + nip, naibs, iss, itmaj, iw1, iw2, info, iflag ) * ************************************************************************* * Purpose : * --------- * This routine selects the nonbasic variables that are candidate * to be deactivated. Then, a deactivation procedure is started. * Each nonbasic variable that is deactivated is stored in the * superbasic set. When the deactivation procedure is finished, a * partition of the variables in new independent sets is made. * Parameters : * ------------ * 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. * pr ( int ) * input : the predecessor data structure vector. * output : unmodified. * depth ( int ) * input : the depth data structure vector. * output : unmodified. * 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 : the components corresponding to the nonbasic * variables candidate to be deactivated are computed. * nro ( int ) * input : the sum of the lengths of the flow augmenting * paths of all the superbasic variables. * output : we add to NRO the length of the flow augmenting * path of the nonbasic variables candidate to be * deactivated. * kandis ( int ) * input : the length of the longest flow augmenting path. * output : it is updated when neccessary. * bep ( int ) * input : array used as workspace. * output : this array contains the flow augmenting paths of * the nonbasic variables candidate to be deactivated. * elvar ( int ) * input : array containing the indices of the variables * in the first element, followed by those in the * second element, etc. * output : unmodified. * elptr ( int ) * input : array whose kth value is the position of the * first variable of element k, in the list ELVAR. * output : unmodified. * su ( int ) * input : vector containing the indices of the superbasic * variables. * output : this vector increases by one each time a nonbasic * variable is deactivated. * nsu ( int ) * input : the number of superbasic variables. * output : this number increases by one each time a nonbasic * variable is deactivated. * ba ( int ) * input : vector containing the indices of the basic * variables. * output : unmodified. * nba ( int ) * input : the number of basic variables. * output : unmodified. * can ( int ) * input : meaningless. * output : vector containing the indices of the nonbasic * variables that are candidate to be deactivated. * ncan ( int ) * input : meaningless. * output : the number of nonbasic variables that are * candidate to be deactivated. * optmal ( int ) * input : = 0, no major iteration has been performed * yet, but a deactivation is done. * = 1, a quasi optimal solution was obtained * in the current subspace. * = 2, an optimal solution was obtained in * the current subspace. * output : when OPTMAL = 1, FNOISE = .true. and no * nonbasic variable can be deactivated, OPTMAL * is then set to 2. * In this case, a new deactivation is restarted * considering all the nonbasic variables as * candidate to be deactivated. * xst ( int ) * input : vector containing the status of the variables. * output : the status of the nonbasic variables that are * deactivated are modified to correspond to the * status of superbasic variables. * elst ( int ) * input : vector containing the status of the element * functions. * output : unmodified. * ndacti ( int ) * input : meaningless * output : the number of nonbasic variables that have been * deactivated. * ndacts ( int ) * input : the total number of nonbasic variables that have * been de-activated from the begin of the * minimization. * output : this number is increased by one each time a nonbasic * variable is deactivated. * nb ( int ) * input : the number of nonbasic variables. * output : this number is decreased by one each time a nonbasic * variable is deactivated. * opt ( int ) * input : meaningless. * output : = 2, the current point X is a local solution * of the problem. * = 3, a new major iteration will be started. * fnoise ( log ) * input : .true. iff the major iteration was stopped * because the difference between two * successive function values along the * current linesearch is insignificant * compared to the noise on these function * values. * .false. otherwise. * output : unmodified. * rgra ( dble ) * input : the reduced gradient vector. * output : the components corresponding to the indices * of the nonbasic variables candidate to be * deactivated are computed. * gptr ( int ) * input : array whose ith value is the position of the * first component of the ith element gradient * in FUVAL. * output : unmodified. * gra ( dble ) * input : meaningless * output : the gradient vector of the objective function. * x ( dble ) * input : the current iterate vector. * output : unmodified. * fuval ( dble ) * input : array used to store the function and derivative * values for the element functions. * output : unmodified. * w2 ( dble ) * input : array used as workspace. * output : meaningless. * nipst ( log ) * input : .true. if the user whishes to use the concept * of independent superbasic sets in order * to exploit the parrallelism in both the * constraints and the cost function structure. * .false. if no decomposition is achieved. * output : unmodified. * nip ( int ) * input : the number of independent sets before the * new partition of independent sets is done. * output : the number of independent sets after the * new partition of independent sets is done. * naibs ( int ) * input : vector containing the number of superbasic * variables in each independent set. * output : this vector is updated following the new partition * into independent sets. * iss ( int ) * input : vector containing for each variable, the indice * of the independent set in which it is included. * It is equal to zero when the variable does not * belongs to any independent set. * output : this vector is updated following the new partition * into independent sets. * itmaj ( int ) * input : the number of major iterations performed before * this routine is called. * output : unmodified. * iw1 ( int ) * input : integer array used as workspace. * output : meningless. * iw2 ( int ) * input : integer array used as workspace. * output : meningless. * info ( int ) * input : meaningless. * output : when IFLAG = 11, it contains the number of independent * sets created. * Otherwise, it is meaningless. * iflag ( int ) * input : should be equal to zero when the routine is called. * output : = 11, if the maximum number of independent sets * is reached. * Otherwise, it remains unmodified. * Routines used : * --------------- * snxcon, gxsu, gxnb, gxcon, sxcon, * dkstem, dealag, inset0, inset. * Programming : * ------------- * D. Tuyttens * ======================================================================== * Routine parameters integer fr(*), to(*), pr(*), depth(*), ftstem(*), + nro, kandis, bep(*), elvar(*), elptr(*), + su(*), nsu, ba(*), nba, can(*), ncan, + optmal, xst(*), elst(*), ndacti, ndacts, + nb, opt, gptr(*), nip, naibs(*), iss(*), + itmaj, iw1(*), iw2(*), info, iflag logical fnoise, nipst double precision rgra(*), gra(*), x(*), fuval(*), w2(*) * Internal variables integer k, xs, ok, opti, opnstp, opbeg, it logical gxsu, gxnb, gxcon * Common specifications integer arcs, nodes, elem common / prbdim / arcs, nodes, elem * * Meanings of variable OPT * ok = 1 opti = 2 opnstp = 3 opbeg = 4 * * Some initializations. * 1 continue opt = ok nsu = 0 ncan = 0 * * We select the nonbasic variables that * are candidate to be deactivated. We store * the corresponding indices in array CAN. * do 10 k = 1 , arcs xs = xst(k) if( optmal.eq.2 ) call snxcon(xs) * if( gxsu(xs) ) then nsu = nsu + 1 su(nsu) = k else if( gxnb(xs) .and. .not.gxcon(xs) ) then ncan = ncan + 1 can(ncan) = k call sxcon(xs) call dkstem( k, fr, to, pr, depth, ftstem, nro, kandis ) endif 10 continue * * We test if the candidate list is empty. * if( ncan.eq.0 ) then if( optmal.eq.2 ) then opt = opti else if( fnoise ) then optmal = 2 opt = opbeg else opt = opnstp endif else * * The deactivation procedure is started. * call dealag( can, ncan, nb, ndacti, ndacts, su, nsu, + ba, nba, ftstem, bep, gptr, elptr, elvar, + fr, to, pr, elst, xst, x, rgra, gra, fuval, + w2 ) * * We test the number of nonbasic variables * that have been deactivated. * if( ndacti.eq.0 ) then if( optmal.eq.2 ) then opt = opti else if( fnoise ) then optmal = 2 opt = opbeg else opt = opnstp endif endif endif * * We test if it is necessary * to make a new deactivation. * if( opt.eq.opbeg ) goto 1 * * When the deactivation is done, a new partition * of the variables into independent sets is made. * if( opt.eq.ok ) then if( itmaj.ne.0 ) then * * We dejoin the big old independent sets when, at * least some superbasic arc from the old independent * set has just been activated. * call inset0( nipst, nip, naibs, iss, optmal, + elvar, elptr, iw1, iw2, xst, + ftstem, pr, bep, fr, to, ba, nba, + info, iflag ) endif it = 1 if( itmaj.eq.0 .and. optmal.eq.2 ) it = 0 * * When IT = 0, it is the first time that the partition * of the variables into independent sets is done. The * independent superbasic sets are build from the just * deactivated set of variables. The superbasic set * corresponding to the initial solution was empty. * When IT = 1, we include the just-deactivated set of * variables in the old independent sets, and joins * independent sets if necessary. * call inset( nipst, nip, naibs, iss, it, ndacti, + elvar, elptr, iw1, iw2, xst, + ftstem, pr, bep, fr, to, ba, nba, + su, nsu, info, iflag ) opt = opnstp endif * return end