* ************************************************************************* subroutine analys( k, nip, nipst, iss, naibs, ftstem, + pr, bep, elvar, elptr, varin, ptrel, + xst, fr, to, ba, nba, iflag, info ) * ************************************************************************* * Purpose : * --------- * This routine includes the superbasic arc K in a new * independent set KP. * All the arcs, say KK, in the flow augmenting path of * arc K and their independent sets are included in * independent set KP. * All the arcs linked by the Hessian matrix to the * superbasic arc K and to the basic arcs KK, and their * independent sets are also included in independent * set KP. * Parameters : * ------------ * k ( int ) * input : the indice of the superbasic variable we * want to include in a new independent set. * output : unmodified. * nip ( int ) * input : the number of independent sets before the * routine is called. * output : the number of independent sets after the * the routine is called. * 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. * 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. * naibs ( int ) * input : vector containing the number of superbasic * variables in each independent set. * output : this vector is updated following the new partition. * ftstem ( int ) * input : vector containing for each superbasic variable, * the length from its origine node to the stem * node, and the length of its flow augmenting path. * output : unmodified. * pr ( int ) * input : the predecessor vector. * output : unmodified. * bep ( int ) * input : meaningless. * output : array used to store the flow augmenting path * of the superbasic arc K. * 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. * varin ( int ) * input : meaningless. * output : array containing the indices of the element including * the first variable, followed by those including the * second variable, etc. * ptrel ( int ) * input : meaningless. * output : array whose kth value is the position of the first * element including variable k, in the list VARIN. * xst ( int ) * input : vector containing the status of the variables. * output : this vector is updated following the new partition. * 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. * ba ( int ) * input : vector containing the indices of the basic * variables. * output : unmodified. * nba ( int ) * input : the number of basic variables. * output : unmodified. * 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. * info ( int ) * input : meaningless. * output : when IFLAG = 11, it contains the number of independent * sets created. * Otherwise, it is meaningless. * Routines used : * --------------- * Anhess, fapbep, gxsu, snxdej. * Programming : * ------------- * D. Tuyttens * ========================================================================= * Routine parameters integer k, nip, iss(*), naibs(*), ftstem(*), pr(*), bep(*), + elvar(*), elptr(*), varin(*), ptrel(*), xst(*), + fr(*), to(*), ba(*), nba, iflag, info logical nipst * Internal variables integer kdis, ik, kk, k1, kp, isk logical gxsu * Common specifications integer arcs, nodes, elem common / prbdim / arcs, nodes, elem * Parameter definition integer maxins parameter( maxins = 100 ) * * We search the first empty independent set. * When the concept of independent set is not * used, only one independent set is created. * if( nipst ) then * * We loop on the existent independent sets. * do 10 kp = 1 , nip if( naibs(kp).eq.0 ) go to 20 10 continue * * A new independent set is created. * kp = nip + 1 nip = kp * * We check the maximum number of * independent sets created. * if( nip.gt.maxins ) then info = maxins iflag = 11 return endif endif 20 continue * * Is the concept of independent sets used ? * if( nipst ) then * * The concept of independent sets is used. * Variable K is set in the new independent * set KP. * iss(k) = kp naibs(kp) = 1 * * We analyse the Hessian dependencies of * the variable K. * call anhess( elvar, elptr, varin, ptrel, + iss, k, kp, naibs, xst ) else * * The concept of independence sets is not * used. Variable K is set in the independent * set one. * iss(k) = 1 naibs(1) = naibs(1) + 1 endif * * We build the flow augmenting path of the superbasic arc K. * call fapbep( k, kdis, ftstem, pr, fr, to, ba, nba, bep ) * * We go over the flow augmenting path of the superbasic arc K. * do 30 ik = 1 , kdis kk = abs(bep(ik)) isk = iss(kk) * * Is the concept of independent sets used ? * if( nipst ) then * * The concept of independent sets is used. * Variable KK is set in the new independent * set KP. * iss(kk) = kp * * We test if the variable KK was already included * in one independent set different of KP. * if( isk.ne.kp .and. isk.ne.0 ) then * * We include in independent set KP all the variables * that were in the same independent set as variable KK. * do 40 k1 = 1 , arcs if( k1.ne.kk .and. iss(k1).eq.isk ) then iss(k1) = kp if( gxsu(xst(k1)) ) naibs(kp) = naibs(kp) + 1 endif 40 continue * * The independent set ISK vanishes. * naibs(isk) = 0 call snxdej(xst(isk)) endif * * We analyse the Hessian dependencies of * the variable K. * call anhess( elvar, elptr, varin, ptrel, + iss, kk, kp, naibs, xst ) else * * The concept of independence sets is not * used. Variable KK is set in the independent * set one. * iss(kk) = 1 endif * * We visit the next element in the flow augmenting * path of the superbasic arc K. * 30 continue * return end