## File: econ_order.w

package info (click to toggle)
sgb 1:20030623-3
 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318 % This file is part of the Stanford GraphBase (c) Stanford University 1993 @i boilerplate.w %<< legal stuff: PLEASE READ IT BEFORE MAKING ANY CHANGES! @i gb_types.w \def\title{ECON\_\,ORDER} \def\<#1>{$\langle${\rm#1}$\rangle$} \prerequisite{GB\_\,ECON} @* Near-triangular ordering. This demonstration program takes a matrix of data constructed by the {\sc GB\_\,ECON} module and permutes the economic sectors so that the first sectors of the ordering tend to be producers of primary materials for other industries, while the last sectors tend to be final-product industries that deliver their output mostly to end users. More precisely, suppose the rows of the matrix represent the outputs of a sector and the columns represent the inputs. This program attempts to find a permutation of rows and columns that minimizes the sum of the elements below the main diagonal. (If this sum were zero, the matrix would be upper triangular; each supplier of a sector would precede it in the ordering, while each customer of that sector would follow it.) The general problem of finding a minimizing permutation is NP-complete; it includes, as a very special case, the {\sc FEEDBACK ARC SET} problem discussed in Karp's classic paper [{\sl Complexity of Computer @^Karp, Richard Manning@> Computations} (Plenum Press, 1972), 85--103]. But sophisticated branch and cut'' methods have been developed that work well in practice on problems of reasonable size. Here we use a simple heuristic downhill method to find a permutation that is locally optimum, in the sense that the below-diagonal sum does not decrease if any individual sector is moved to another position while preserving the relative order of the other sectors. We start with a random permutation and repeatedly improve it, choosing the improvement that gives the least positive gain at each step. A primary motive for the present implementation was to get further experience with this method of cautious descent, which was proposed by A. M. Gleason in {\sl AMS Proceedings of Symposia in Applied @^Gleason, Andrew Mattei@> Mathematics\/ \bf10} (1958), 175--178. (See the comments following the program below.) @ As explained in {\sc GB\_\,ECON}, the subroutine call |econ(n,2,0,s)| constructs a graph whose |n<=79| vertices represent sectors of the U.S. economy and whose arcs $u\to v$ are assigned numbers corresponding to the flow of products from sector~|u| to sector~|v|. When |n<79|, the |n| sectors are obtained from a basic set of 79 sectors by combining related commodities. If |s=0|, the combination is done in a way that tends to equalize the row sums, while if |s>0|, the combination is done by choosing a random subtree of a given 79-leaf tree; the randomness'' is fully determined by the value of~|s|. This program uses two random number seeds, one for |econ| and one for choosing the random initial permutation. The former is called~|s| and the latter is called~|t|. A further parameter, |r|, governs the number of repetitions to be made; the machine will try |r|~different starting permutations on the same matrix. When |r>1|, new solutions are displayed only when they improve on the previous best. By default, |n=79|, |r=1|, and |s=t=0|. The user can change these default parameters by specifying options on the command line, at least in a \UNIX/ implementation, thereby obtaining a variety of special effects. The relevant command-line options are \.{-n}\, \.{-r}\, \.{-s}\, and/or \.{-t}\. Additional options \.{-v} (verbose), \.{-V} (extreme verbosity), and \.{-g} (greedy or steepest descent instead of cautious descent) are also provided. @^UNIX dependencies@> Here is the overall layout of this \CEE/ program: @p #include "gb_graph.h" /* the GraphBase data structures */ #include "gb_flip.h" /* the random number generator */ #include "gb_econ.h" /* the |econ| routine */ @h@# @@; main(argc,argv) int argc; /* the number of command-line arguments */ char *argv[]; /* an array of strings containing those arguments */ {@+unsigned long n=79; /* the desired number of sectors */ long s=0; /* random \\{seed} for |econ| */ long t=0; /* random \\{seed} for initial permutation */ unsigned long r=1; /* the number of repetitions */ long greedy=0; /* should we use steepest descent? */ register long j,k; /* all-purpose indices */ @; g=econ(n,2L,0L,s); if (g==NULL) { fprintf(stderr,"Sorry, can't create the matrix! (error code %ld)\n", panic_code); return -1; } printf("Ordering the sectors of %s, using seed %ld:\n",g->id,t); printf(" (%s descent method)\n",greedy?"Steepest":"Cautious"); @; @; gb_init_rand(t); while (r--) @; return 0; /* normal exit */ } @ Besides the matrix $M$ of input/output coefficients, we will find it convenient to use the matrix $\Delta$, where $\Delta_{jk}=M_{jk}-M_{kj}$. @d INF 0x7fffffff /* infinity (or darn near) */ @= Graph *g; /* the graph we will work on */ long mat[79][79]; /* the corresponding matrix */ long del[79][79]; /* skew-symmetric differences */ long best_score=INF; /* the smallest below-diagonal sum we've seen so far */ @ @= while (--argc) { @^UNIX dependencies@> if (sscanf(argv[argc],"-n%lu",&n)==1) ; else if (sscanf(argv[argc],"-r%lu",&r)==1) ; else if (sscanf(argv[argc],"-s%ld",&s)==1) ; else if (sscanf(argv[argc],"-t%ld",&t)==1) ; else if (strcmp(argv[argc],"-v")==0) verbose=1; else if (strcmp(argv[argc],"-V")==0) verbose=2; else if (strcmp(argv[argc],"-g")==0) greedy=1; else { fprintf(stderr,"Usage: %s [-nN][-rN][-sN][-tN][-g][-v][-V]\n",argv[0]); return -2; } } @ The optimum permutation is a function only of the $\Delta$ matrix, because we can subtract any constant from both $M_{jk}$ and $M_{kj}$ without changing the basic problem. @= {@+register Vertex *v; register Arc *a; n=g->n; for (v=g->vertices;vvertices+n;v++) for (a=v->arcs;a;a=a->next) mat[v-g->vertices][a->tip-g->vertices]=a->flow; for (j=0;j @^J\"unger, Michael@> @^Reinelt, Gerhard@> [{\sl Operations Research \bf32} (1984), 1195--1220]. The basic idea is to formulate the problem as the task of minimizing $\sum M_{jk}x_{jk}$ for integer variables $x_{jk}\ge0$, subject to the conditions $x_{jk}+x_{kj}=1$ and $x_{ik}\le x_{ij}+x_{jk}$ for all triples $(i,j,k)$ of distinct subscripts; these conditions are necessary and sufficient. Relaxing the integrality constraints gives a lower bound, and we can also add additional inequalities such as $x_{14}+x_{25}+x_{36}+x_{42}+x_{43}+x_{51}+x_{53}+x_{61}+x_{62}\le7$. The interesting story of inequalities like this has been surveyed by P. C. Fishburn [{\sl Mathematical Social Sciences\/ \bf23} (1992), 67--80]. @^Fishburn, Peter Clingerman@> However, our goal is more modest---we just want to study two of the simplest heuristics. So we will be happy with a trivial bound based only on the constraints $x_{jk}+x_{kj}=1$. @= {@+register long sum=0; for (j=1;jvertices+mapping[k]|. The current below-diagonal sum will be the value of |score|. We will not actually have to permute anything inside of |mat|. @d sec_name(k) (g->vertices+mapping[k])->name @= long mapping[79]; /* current permutation */ long score; /* current sum of elements above main diagonal */ long steps; /* the number of iterations so far */ @ @= { @; while(1) { @