/* glpnet03.c (Klingman's network problem generator) */ /*********************************************************************** * This code is part of GLPK (GNU Linear Programming Kit). * * This code is the result of translation of the Fortran program NETGEN * developed by Dr. Darwin Klingman, which is publically available from * NETLIB at . * * The translation was made by Andrew Makhorin . * * GLPK is free software: you can redistribute it and/or modify it * under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * GLPK is distributed in the hope that it will be useful, but WITHOUT * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public * License for more details. * * You should have received a copy of the GNU General Public License * along with GLPK. If not, see . ***********************************************************************/ #include "glpenv.h" #include "glpk.h" /*********************************************************************** * NAME * * glp_netgen - Klingman's network problem generator * * SYNOPSIS * * int glp_netgen(glp_graph *G, int v_rhs, int a_cap, int a_cost, * const int parm[1+15]); * * DESCRIPTION * * The routine glp_netgen is a network problem generator developed by * Dr. Darwin Klingman. It can create capacitated and uncapacitated * minimum cost flow (or transshipment), transportation, and assignment * problems. * * The parameter G specifies the graph object, to which the generated * problem data have to be stored. Note that on entry the graph object * is erased with the routine glp_erase_graph. * * The parameter v_rhs specifies an offset of the field of type double * in the vertex data block, to which the routine stores the supply or * demand value. If v_rhs < 0, the value is not stored. * * The parameter a_cap specifies an offset of the field of type double * in the arc data block, to which the routine stores the arc capacity. * If a_cap < 0, the capacity is not stored. * * The parameter a_cost specifies an offset of the field of type double * in the arc data block, to which the routine stores the per-unit cost * if the arc flow. If a_cost < 0, the cost is not stored. * * The array parm contains description of the network to be generated: * * parm[0] not used * parm[1] (iseed) 8-digit positive random number seed * parm[2] (nprob) 8-digit problem id number * parm[3] (nodes) total number of nodes * parm[4] (nsorc) total number of source nodes (including * transshipment nodes) * parm[5] (nsink) total number of sink nodes (including * transshipment nodes) * parm[6] (iarcs) number of arcs * parm[7] (mincst) minimum cost for arcs * parm[8] (maxcst) maximum cost for arcs * parm[9] (itsup) total supply * parm[10] (ntsorc) number of transshipment source nodes * parm[11] (ntsink) number of transshipment sink nodes * parm[12] (iphic) percentage of skeleton arcs to be given * the maximum cost * parm[13] (ipcap) percentage of arcs to be capacitated * parm[14] (mincap) minimum upper bound for capacitated arcs * parm[15] (maxcap) maximum upper bound for capacitated arcs * * The routine generates a transportation problem if: * * nsorc + nsink = nodes, ntsorc = 0, and ntsink = 0. * * The routine generates an assignment problem if the requirements for * a transportation problem are met and: * * nsorc = nsink and itsup = nsorc. * * RETURNS * * If the instance was successfully generated, the routine glp_netgen * returns zero; otherwise, if specified parameters are inconsistent, * the routine returns a non-zero error code. * * REFERENCES * * D.Klingman, A.Napier, and J.Stutz. NETGEN: A program for generating * large scale capacitated assignment, transportation, and minimum cost * flow networks. Management Science 20 (1974), 814-20. */ struct csa { /* common storage area */ glp_graph *G; int v_rhs, a_cap, a_cost; int nodes, iarcs, mincst, maxcst, itsup, nsorc, nsink, nonsor, nfsink, narcs, nsort, nftsor, ipcap, mincap, maxcap, ktl, nodlft, *ipred, *ihead, *itail, *iflag, *isup, *lsinks, mult, modul, i15, i16, jran; }; #define G (csa->G) #define v_rhs (csa->v_rhs) #define a_cap (csa->a_cap) #define a_cost (csa->a_cost) #define nodes (csa->nodes) #define iarcs (csa->iarcs) #define mincst (csa->mincst) #define maxcst (csa->maxcst) #define itsup (csa->itsup) #define nsorc (csa->nsorc) #define nsink (csa->nsink) #define nonsor (csa->nonsor) #define nfsink (csa->nfsink) #define narcs (csa->narcs) #define nsort (csa->nsort) #define nftsor (csa->nftsor) #define ipcap (csa->ipcap) #define mincap (csa->mincap) #define maxcap (csa->maxcap) #define ktl (csa->ktl) #define nodlft (csa->nodlft) #if 0 /* spent a day to find out this bug */ #define ist (csa->ist) #else #define ist (ipred[0]) #endif #define ipred (csa->ipred) #define ihead (csa->ihead) #define itail (csa->itail) #define iflag (csa->iflag) #define isup (csa->isup) #define lsinks (csa->lsinks) #define mult (csa->mult) #define modul (csa->modul) #define i15 (csa->i15) #define i16 (csa->i16) #define jran (csa->jran) static void cresup(struct csa *csa); static void chain(struct csa *csa, int lpick, int lsorc); static void chnarc(struct csa *csa, int lsorc); static void sort(struct csa *csa); static void pickj(struct csa *csa, int it); static void assign(struct csa *csa); static void setran(struct csa *csa, int iseed); static int iran(struct csa *csa, int ilow, int ihigh); int glp_netgen(glp_graph *G_, int _v_rhs, int _a_cap, int _a_cost, const int parm[1+15]) { struct csa _csa, *csa = &_csa; int iseed, nprob, ntsorc, ntsink, iphic, i, nskel, nltr, ltsink, ntrans, npsink, nftr, npsorc, ntravl, ntrrem, lsorc, lpick, nsksr, nsrchn, j, item, l, ks, k, ksp, li, n, ii, it, ih, icap, jcap, icost, jcost, ret; G = G_; v_rhs = _v_rhs; a_cap = _a_cap; a_cost = _a_cost; if (G != NULL) { if (v_rhs >= 0 && v_rhs > G->v_size - (int)sizeof(double)) xerror("glp_netgen: v_rhs = %d; invalid offset\n", v_rhs); if (a_cap >= 0 && a_cap > G->a_size - (int)sizeof(double)) xerror("glp_netgen: a_cap = %d; invalid offset\n", a_cap); if (a_cost >= 0 && a_cost > G->a_size - (int)sizeof(double)) xerror("glp_netgen: a_cost = %d; invalid offset\n", a_cost); } /* Input the user's random number seed and fix it if non-positive. */ iseed = parm[1]; nprob = parm[2]; if (iseed <= 0) iseed = 13502460; setran(csa, iseed); /* Input the user's problem characteristics. */ nodes = parm[3]; nsorc = parm[4]; nsink = parm[5]; iarcs = parm[6]; mincst = parm[7]; maxcst = parm[8]; itsup = parm[9]; ntsorc = parm[10]; ntsink = parm[11]; iphic = parm[12]; ipcap = parm[13]; mincap = parm[14]; maxcap = parm[15]; /* Check the size of the problem. */ if (!(10 <= nodes && nodes <= 100000)) { ret = 1; goto done; } /* Check user supplied parameters for consistency. */ if (!(nsorc >= 0 && nsink >= 0 && nsorc + nsink <= nodes)) { ret = 2; goto done; } if (iarcs < 0) { ret = 3; goto done; } if (mincst > maxcst) { ret = 4; goto done; } if (itsup < 0) { ret = 5; goto done; } if (!(0 <= ntsorc && ntsorc <= nsorc)) { ret = 6; goto done; } if (!(0 <= ntsink && ntsink <= nsink)) { ret = 7; goto done; } if (!(0 <= iphic && iphic <= 100)) { ret = 8; goto done; } if (!(0 <= ipcap && ipcap <= 100)) { ret = 9; goto done; } if (mincap > maxcap) { ret = 10; goto done; } /* Initailize the graph object. */ if (G != NULL) { glp_erase_graph(G, G->v_size, G->a_size); glp_add_vertices(G, nodes); if (v_rhs >= 0) { double zero = 0.0; for (i = 1; i <= nodes; i++) { glp_vertex *v = G->v[i]; memcpy((char *)v->data + v_rhs, &zero, sizeof(double)); } } } /* Allocate working arrays. */ ipred = xcalloc(1+nodes, sizeof(int)); ihead = xcalloc(1+nodes, sizeof(int)); itail = xcalloc(1+nodes, sizeof(int)); iflag = xcalloc(1+nodes, sizeof(int)); isup = xcalloc(1+nodes, sizeof(int)); lsinks = xcalloc(1+nodes, sizeof(int)); /* Print the problem documentation records. */ if (G == NULL) { xprintf("BEGIN\n"); xprintf("NETGEN PROBLEM%8d%10s%10d NODES AND%10d ARCS\n", nprob, "", nodes, iarcs); xprintf("USER:%11d%11d%11d%11d%11d%11d\nDATA:%11d%11d%11d%11d%" "11d%11d\n", iseed, nsorc, nsink, mincst, maxcst, itsup, ntsorc, ntsink, iphic, ipcap, mincap, maxcap); } else glp_set_graph_name(G, "NETGEN"); /* Set various constants used in the program. */ narcs = 0; nskel = 0; nltr = nodes - nsink; ltsink = nltr + ntsink; ntrans = nltr - nsorc; nfsink = nltr + 1; nonsor = nodes - nsorc + ntsorc; npsink = nsink - ntsink; nodlft = nodes - nsink + ntsink; nftr = nsorc + 1; nftsor = nsorc - ntsorc + 1; npsorc = nsorc - ntsorc; /* Randomly distribute the supply among the source nodes. */ if (npsorc + npsink == nodes && npsorc == npsink && itsup == nsorc) { assign(csa); nskel = nsorc; goto L390; } cresup(csa); /* Print the supply records. */ if (G == NULL) { xprintf("SUPPLY\n"); for (i = 1; i <= nsorc; i++) xprintf("%6s%6d%18s%10d\n", "", i, "", isup[i]); xprintf("ARCS\n"); } else { if (v_rhs >= 0) { for (i = 1; i <= nsorc; i++) { double temp = (double)isup[i]; glp_vertex *v = G->v[i]; memcpy((char *)v->data + v_rhs, &temp, sizeof(double)); } } } /* Make the sources point to themselves in ipred array. */ for (i = 1; i <= nsorc; i++) ipred[i] = i; if (ntrans == 0) goto L170; /* Chain the transshipment nodes together in the ipred array. */ ist = nftr; ipred[nltr] = 0; for (i = nftr; i < nltr; i++) ipred[i] = i+1; /* Form even length chains for 60 percent of the transshipments.*/ ntravl = 6 * ntrans / 10; ntrrem = ntrans - ntravl; L140: lsorc = 1; while (ntravl != 0) { lpick = iran(csa, 1, ntravl + ntrrem); ntravl--; chain(csa, lpick, lsorc); if (lsorc == nsorc) goto L140; lsorc++; } /* Add the remaining transshipments to the chains. */ while (ntrrem != 0) { lpick = iran(csa, 1, ntrrem); ntrrem--; lsorc = iran(csa, 1, nsorc); chain(csa, lpick, lsorc); } L170: /* Set all demands equal to zero. */ for (i = nfsink; i <= nodes; i++) ipred[i] = 0; /* The following loop takes one chain at a time (through the use of logic contained in the loop and calls to other routines) and creates the remaining network arcs. */ for (lsorc = 1; lsorc <= nsorc; lsorc++) { chnarc(csa, lsorc); for (i = nfsink; i <= nodes; i++) iflag[i] = 0; /* Choose the number of sinks to be hooked up to the current chain. */ if (ntrans != 0) nsksr = (nsort * 2 * nsink) / ntrans; else nsksr = nsink / nsorc + 1; if (nsksr < 2) nsksr = 2; if (nsksr > nsink) nsksr = nsink; nsrchn = nsort; /* Randomly pick nsksr sinks and put their names in lsinks. */ ktl = nsink; for (j = 1; j <= nsksr; j++) { item = iran(csa, 1, ktl); ktl--; for (l = nfsink; l <= nodes; l++) { if (iflag[l] != 1) { item--; if (item == 0) goto L230; } } break; L230: lsinks[j] = l; iflag[l] = 1; } /* If last source chain, add all sinks with zero demand to lsinks list. */ if (lsorc == nsorc) { for (j = nfsink; j <= nodes; j++) { if (ipred[j] == 0 && iflag[j] != 1) { nsksr++; lsinks[nsksr] = j; iflag[j] = 1; } } } /* Create demands for group of sinks in lsinks. */ ks = isup[lsorc] / nsksr; k = ipred[lsorc]; for (i = 1; i <= nsksr; i++) { nsort++; ksp = iran(csa, 1, ks); j = iran(csa, 1, nsksr); itail[nsort] = k; li = lsinks[i]; ihead[nsort] = li; ipred[li] += ksp; li = lsinks[j]; ipred[li] += ks - ksp; n = iran(csa, 1, nsrchn); k = lsorc; for (ii = 1; ii <= n; ii++) k = ipred[k]; } li = lsinks[1]; ipred[li] += isup[lsorc] - ks * nsksr; nskel += nsort; /* Sort the arcs in the chain from source lsorc using itail as sort key. */ sort(csa); /* Print this part of skeleton and create the arcs for these nodes. */ i = 1; itail[nsort+1] = 0; L300: for (j = nftsor; j <= nodes; j++) iflag[j] = 0; ktl = nonsor - 1; it = itail[i]; iflag[it] = 1; L320: ih = ihead[i]; iflag[ih] = 1; narcs++; ktl--; /* Determine if this skeleton arc should be capacitated. */ icap = itsup; jcap = iran(csa, 1, 100); if (jcap <= ipcap) { icap = isup[lsorc]; if (mincap > icap) icap = mincap; } /* Determine if this skeleton arc should have the maximum cost. */ icost = maxcst; jcost = iran(csa, 1, 100); if (jcost > iphic) icost = iran(csa, mincst, maxcst); if (G == NULL) xprintf("%6s%6d%6d%2s%10d%10d\n", "", it, ih, "", icost, icap); else { glp_arc *a = glp_add_arc(G, it, ih); if (a_cap >= 0) { double temp = (double)icap; memcpy((char *)a->data + a_cap, &temp, sizeof(double)); } if (a_cost >= 0) { double temp = (double)icost; memcpy((char *)a->data + a_cost, &temp, sizeof(double)); } } i++; if (itail[i] == it) goto L320; pickj(csa, it); if (i <= nsort) goto L300; } /* Create arcs from the transshipment sinks. */ if (ntsink != 0) { for (i = nfsink; i <= ltsink; i++) { for (j = nftsor; j <= nodes; j++) iflag[j] = 0; ktl = nonsor - 1; iflag[i] = 1; pickj(csa, i); } } L390: /* Print the demand records and end record. */ if (G == NULL) { xprintf("DEMAND\n"); for (i = nfsink; i <= nodes; i++) xprintf("%6s%6d%18s%10d\n", "", i, "", ipred[i]); xprintf("END\n"); } else { if (v_rhs >= 0) { for (i = nfsink; i <= nodes; i++) { double temp = - (double)ipred[i]; glp_vertex *v = G->v[i]; memcpy((char *)v->data + v_rhs, &temp, sizeof(double)); } } } /* Free working arrays. */ xfree(ipred); xfree(ihead); xfree(itail); xfree(iflag); xfree(isup); xfree(lsinks); /* The instance has been successfully generated. */ ret = 0; done: return ret; } /*********************************************************************** * The routine cresup randomly distributes the total supply among the * source nodes. */ static void cresup(struct csa *csa) { int i, j, ks, ksp; xassert(itsup > nsorc); ks = itsup / nsorc; for (i = 1; i <= nsorc; i++) isup[i] = 0; for (i = 1; i <= nsorc; i++) { ksp = iran(csa, 1, ks); j = iran(csa, 1, nsorc); isup[i] += ksp; isup[j] += ks - ksp; } j = iran(csa, 1, nsorc); isup[j] += itsup - ks * nsorc; return; } /*********************************************************************** * The routine chain adds node lpick to the end of the chain with source * node lsorc. */ static void chain(struct csa *csa, int lpick, int lsorc) { int i, j, k, l, m; k = 0; m = ist; for (i = 1; i <= lpick; i++) { l = k; k = m; m = ipred[k]; } ipred[l] = m; j = ipred[lsorc]; ipred[k] = j; ipred[lsorc] = k; return; } /*********************************************************************** * The routine chnarc puts the arcs in the chain from source lsorc into * the ihead and itail arrays for sorting. */ static void chnarc(struct csa *csa, int lsorc) { int ito, ifrom; nsort = 0; ito = ipred[lsorc]; L10: if (ito == lsorc) return; nsort++; ifrom = ipred[ito]; ihead[nsort] = ito; itail[nsort] = ifrom; ito = ifrom; goto L10; } /*********************************************************************** * The routine sort sorts the nsort arcs in the ihead and itail arrays. * ihead is used as the sort key (i.e. forward star sort order). */ static void sort(struct csa *csa) { int i, j, k, l, m, n, it; n = nsort; m = n; L10: m /= 2; if (m == 0) return; k = n - m; j = 1; L20: i = j; L30: l = i + m; if (itail[i] <= itail[l]) goto L40; it = itail[i]; itail[i] = itail[l]; itail[l] = it; it = ihead[i]; ihead[i] = ihead[l]; ihead[l] = it; i -= m; if (i >= 1) goto L30; L40: j++; if (j <= k) goto L20; goto L10; } /*********************************************************************** * The routine pickj creates a random number of arcs out of node 'it'. * Various parameters are dynamically adjusted in an attempt to ensure * that the generated network has the correct number of arcs. */ static void pickj(struct csa *csa, int it) { int j, k, l, nn, nupbnd, icap, jcap, icost; if ((nodlft - 1) * 2 > iarcs - narcs - 1) { nodlft--; return; } if ((iarcs - narcs + nonsor - ktl - 1) / nodlft - nonsor + 1 >= 0) k = nonsor; else { nupbnd = (iarcs - narcs - nodlft) / nodlft * 2; L40: k = iran(csa, 1, nupbnd); if (nodlft == 1) k = iarcs - narcs; if ((nodlft - 1) * (nonsor - 1) < iarcs - narcs - k) goto L40; } nodlft--; for (j = 1; j <= k; j++) { nn = iran(csa, 1, ktl); ktl--; for (l = nftsor; l <= nodes; l++) { if (iflag[l] != 1) { nn--; if (nn == 0) goto L70; } } return; L70: iflag[l] = 1; icap = itsup; jcap = iran(csa, 1, 100); if (jcap <= ipcap) icap = iran(csa, mincap, maxcap); icost = iran(csa, mincst, maxcst); if (G == NULL) xprintf("%6s%6d%6d%2s%10d%10d\n", "", it, l, "", icost, icap); else { glp_arc *a = glp_add_arc(G, it, l); if (a_cap >= 0) { double temp = (double)icap; memcpy((char *)a->data + a_cap, &temp, sizeof(double)); } if (a_cost >= 0) { double temp = (double)icost; memcpy((char *)a->data + a_cost, &temp, sizeof(double)); } } narcs++; } return; } /*********************************************************************** * The routine assign generate assignment problems. It defines the unit * supplies, builds a skeleton, then calls pickj to create the arcs. */ static void assign(struct csa *csa) { int i, it, nn, l, ll, icost; if (G == NULL) xprintf("SUPPLY\n"); for (i = 1; i <= nsorc; i++) { isup[i] = 1; iflag[i] = 0; if (G == NULL) xprintf("%6s%6d%18s%10d\n", "", i, "", isup[i]); else { if (v_rhs >= 0) { double temp = (double)isup[i]; glp_vertex *v = G->v[i]; memcpy((char *)v->data + v_rhs, &temp, sizeof(double)); } } } if (G == NULL) xprintf("ARCS\n"); for (i = nfsink; i <= nodes; i++) ipred[i] = 1; for (it = 1; it <= nsorc; it++) { for (i = nfsink; i <= nodes; i++) iflag[i] = 0; ktl = nsink - 1; nn = iran(csa, 1, nsink - it + 1); for (l = 1; l <= nsorc; l++) { if (iflag[l] != 1) { nn--; if (nn == 0) break; } } narcs++; ll = nsorc + l; icost = iran(csa, mincst, maxcst); if (G == NULL) xprintf("%6s%6d%6d%2s%10d%10d\n", "", it, ll, "", icost, isup[1]); else { glp_arc *a = glp_add_arc(G, it, ll); if (a_cap >= 0) { double temp = (double)isup[1]; memcpy((char *)a->data + a_cap, &temp, sizeof(double)); } if (a_cost >= 0) { double temp = (double)icost; memcpy((char *)a->data + a_cost, &temp, sizeof(double)); } } iflag[l] = 1; iflag[ll] = 1; pickj(csa, it); } return; } /*********************************************************************** * Portable congruential (uniform) random number generator: * * next_value = ((7**5) * previous_value) modulo ((2**31)-1) * * This generator consists of three routines: * * (1) setran - initializes constants and seed * (2) iran - generates an integer random number * (3) rran - generates a real random number * * The generator requires a machine with at least 32 bits of precision. * The seed (iseed) must be in the range [1,(2**31)-1]. */ static void setran(struct csa *csa, int iseed) { xassert(iseed >= 1); mult = 16807; modul = 2147483647; i15 = 1 << 15; i16 = 1 << 16; jran = iseed; return; } /*********************************************************************** * The routine iran generates an integer random number between ilow and * ihigh. If ilow > ihigh then iran returns ihigh. */ static int iran(struct csa *csa, int ilow, int ihigh) { int ixhi, ixlo, ixalo, leftlo, ixahi, ifulhi, irtlo, iover, irthi, j; ixhi = jran / i16; ixlo = jran - ixhi * i16; ixalo = ixlo * mult; leftlo = ixalo / i16; ixahi = ixhi * mult; ifulhi = ixahi + leftlo; irtlo = ixalo - leftlo * i16; iover = ifulhi / i15; irthi = ifulhi - iover * i15; jran = ((irtlo - modul) + irthi * i16) + iover; if (jran < 0) jran += modul; j = ihigh - ilow + 1; if (j > 0) return jran % j + ilow; else return ihigh; } /*********************************************************************** * NAME * * glp_netgen_prob - Klingman's standard network problem instance * * SYNOPSIS * * void glp_netgen_prob(int nprob, int parm[1+15]); * * DESCRIPTION * * The routine glp_netgen_prob provides the set of parameters for * Klingman's network problem generator (see the routine glp_netgen), * which describe a standard network problem instance. * * The parameter nprob (101 <= nprob <= 150) specifies the problem * instance number. * * The array parm contains description of the network, provided by the * routine. (For detailed description of these parameters see comments * to the routine glp_netgen.) * * PROBLEM CHARACTERISTICS * * The table below shows characteristics of Klingman's standard network * problem instances. * * Problem Nodes Arcs Optimum * ------- ----- ----- ---------- * 101 5000 25336 6191726 * 102 5000 25387 72337144 * 103 5000 25355 218947553 * 104 5000 25344 -19100371 * 105 5000 25332 31192578 * 106 5000 12870 4314276 * 107 5000 37832 7393769 * 108 5000 50309 8405738 * 109 5000 75299 9190300 * 110 5000 12825 8975048 * 111 5000 37828 4747532 * 112 5000 50325 4012671 * 113 5000 75318 2979725 * 114 5000 26514 5821181 * 115 5000 25962 6353310 * 116 5000 25304 5915426 * 117 5000 12816 4420560 * 118 5000 37797 7045842 * 119 5000 50301 7724179 * 120 5000 75330 8455200 * 121 5000 25000 66366360 * 122 5000 25000 30997529 * 123 5000 25000 23388777 * 124 5000 25000 17803443 * 125 5000 25000 14119622 * 126 5000 12500 18802218 * 127 5000 37500 27674647 * 128 5000 50000 30906194 * 129 5000 75000 40905209 * 130 5000 12500 38939608 * 131 5000 37500 16752978 * 132 5000 50000 13302951 * 133 5000 75000 9830268 * 134 1000 25000 3804874 * 135 2500 25000 11729616 * 136 7500 25000 33318101 * 137 10000 25000 46426030 * 138 5000 25000 60710879 * 139 5000 25000 32729682 * 140 5000 25000 27183831 * 141 5000 25000 19963286 * 142 5000 25000 20243457 * 143 5000 25000 18586777 * 144 5000 25000 2504591 * 145 5000 25000 215956138 * 146 5000 25000 2253113811 * 147 5000 25000 -427908373 * 148 5000 25000 -92965318 * 149 5000 25000 86051224 * 150 5000 25000 619314919 */ static const int data[50][1+15] = { { 0, 13502460, 101, 5000, 2500, 2500, 25000, 1, 100, 250000, 0, 0, 0, 100, 1, 1000 }, { 0, 4281922, 102, 5000, 2500, 2500, 25000, 1, 100, 2500000, 0, 0, 0, 100, 1, 1000 }, { 0, 44820113, 103, 5000, 2500, 2500, 25000, 1, 100, 6250000, 0, 0, 0, 100, 1, 1000 }, { 0, 13450451, 104, 5000, 2500, 2500, 25000, -100, -1, 250000, 0, 0, 0, 100, 1, 1000 }, { 0, 14719436, 105, 5000, 2500, 2500, 25000, 101, 200, 250000, 0, 0, 0, 100, 1, 1000 }, { 0, 17365786, 106, 5000, 2500, 2500, 12500, 1, 100, 125000, 0, 0, 0, 100, 1, 1000 }, { 0, 19540113, 107, 5000, 2500, 2500, 37500, 1, 100, 375000, 0, 0, 0, 100, 1, 1000 }, { 0, 19560313, 108, 5000, 2500, 2500, 50000, 1, 100, 500000, 0, 0, 0, 100, 1, 1000 }, { 0, 2403509, 109, 5000, 2500, 2500, 75000, 1, 100, 750000, 0, 0, 0, 100, 1, 1000 }, { 0, 92480414, 110, 5000, 2500, 2500, 12500, 1, 100, 250000, 0, 0, 0, 100, 1, 1000 }, { 0, 4230140, 111, 5000, 2500, 2500, 37500, 1, 100, 250000, 0, 0, 0, 100, 1, 1000 }, { 0, 10032490, 112, 5000, 2500, 2500, 50000, 1, 100, 250000, 0, 0, 0, 100, 1, 1000 }, { 0, 17307474, 113, 5000, 2500, 2500, 75000, 1, 100, 250000, 0, 0, 0, 100, 1, 1000 }, { 0, 4925114, 114, 5000, 500, 4500, 25000, 1, 100, 250000, 0, 0, 0, 100, 1, 1000 }, { 0, 19842704, 115, 5000, 1500, 3500, 25000, 1, 100, 250000, 0, 0, 0, 100, 1, 1000 }, { 0, 88392060, 116, 5000, 2500, 2500, 25000, 1, 100, 250000, 0, 0, 0, 0, 1, 1000 }, { 0, 12904407, 117, 5000, 2500, 2500, 12500, 1, 100, 125000, 0, 0, 0, 0, 1, 1000 }, { 0, 11811811, 118, 5000, 2500, 2500, 37500, 1, 100, 375000, 0, 0, 0, 0, 1, 1000 }, { 0, 90023593, 119, 5000, 2500, 2500, 50000, 1, 100, 500000, 0, 0, 0, 0, 1, 1000 }, { 0, 93028922, 120, 5000, 2500, 2500, 75000, 1, 100, 750000, 0, 0, 0, 0, 1, 1000 }, { 0, 72707401, 121, 5000, 50, 50, 25000, 1, 100, 250000, 50, 50, 0, 100, 1, 1000 }, { 0, 93040771, 122, 5000, 250, 250, 25000, 1, 100, 250000, 250, 250, 0, 100, 1, 1000 }, { 0, 70220611, 123, 5000, 500, 500, 25000, 1, 100, 250000, 500, 500, 0, 100, 1, 1000 }, { 0, 52774811, 124, 5000, 1000, 1000, 25000, 1, 100, 250000, 1000, 1000, 0, 100, 1, 1000 }, { 0, 22492311, 125, 5000, 1500, 1500, 25000, 1, 100, 250000, 1500, 1500, 0, 100, 1, 1000 }, { 0, 35269337, 126, 5000, 500, 500, 12500, 1, 100, 125000, 500, 500, 0, 100, 1, 1000 }, { 0, 30140502, 127, 5000, 500, 500, 37500, 1, 100, 375000, 500, 500, 0, 100, 1, 1000 }, { 0, 49205455, 128, 5000, 500, 500, 50000, 1, 100, 500000, 500, 500, 0, 100, 1, 1000 }, { 0, 42958341, 129, 5000, 500, 500, 75000, 1, 100, 750000, 500, 500, 0, 100, 1, 1000 }, { 0, 25440925, 130, 5000, 500, 500, 12500, 1, 100, 250000, 500, 500, 0, 100, 1, 1000 }, { 0, 75294924, 131, 5000, 500, 500, 37500, 1, 100, 250000, 500, 500, 0, 100, 1, 1000 }, { 0, 4463965, 132, 5000, 500, 500, 50000, 1, 100, 250000, 500, 500, 0, 100, 1, 1000 }, { 0, 13390427, 133, 5000, 500, 500, 75000, 1, 100, 250000, 500, 500, 0, 100, 1, 1000 }, { 0, 95250971, 134, 1000, 500, 500, 25000, 1, 100, 250000, 500, 500, 0, 100, 1, 1000 }, { 0, 54830522, 135, 2500, 500, 500, 25000, 1, 100, 250000, 500, 500, 0, 100, 1, 1000 }, { 0, 520593, 136, 7500, 500, 500, 25000, 1, 100, 250000, 500, 500, 0, 100, 1, 1000 }, { 0, 52900925, 137, 10000, 500, 500, 25000, 1, 100, 250000, 500, 500, 0, 100, 1, 1000 }, { 0, 22603395, 138, 5000, 500, 500, 25000, 1, 100, 250000, 500, 500, 0, 100, 1, 50 }, { 0, 55253099, 139, 5000, 500, 500, 25000, 1, 100, 250000, 500, 500, 0, 100, 1, 250 }, { 0, 75357001, 140, 5000, 500, 500, 25000, 1, 100, 250000, 500, 500, 0, 100, 1, 500 }, { 0, 10072459, 141, 5000, 500, 500, 25000, 1, 100, 250000, 500, 500, 0, 100, 1, 2500 }, { 0, 55728492, 142, 5000, 500, 500, 25000, 1, 100, 250000, 500, 500, 0, 100, 1, 5000 }, { 0, 593043, 143, 5000, 500, 500, 25000, 1, 100, 250000, 500, 500, 0, 0, 1, 1000 }, { 0, 94236572, 144, 5000, 500, 500, 25000, 1, 10, 250000, 500, 500, 0, 100, 1, 1000 }, { 0, 94882955, 145, 5000, 500, 500, 25000, 1, 1000, 250000, 500, 500, 0, 100, 1, 1000 }, { 0, 48489922, 146, 5000, 500, 500, 25000, 1, 10000, 250000, 500, 500, 0, 100, 1, 1000 }, { 0, 75578374, 147, 5000, 500, 500, 25000, -100, -1, 250000, 500, 500, 0, 100, 1, 1000 }, { 0, 44821152, 148, 5000, 500, 500, 25000, -50, 49, 250000, 500, 500, 0, 100, 1, 1000 }, { 0, 45224103, 149, 5000, 500, 500, 25000, 101, 200, 250000, 500, 500, 0, 100, 1, 1000 }, { 0, 63491741, 150, 5000, 500, 500, 25000, 1001, 1100, 250000, 500, 500, 0, 100, 1, 1000 }, }; void glp_netgen_prob(int nprob, int parm[1+15]) { int k; if (!(101 <= nprob && nprob <= 150)) xerror("glp_netgen_prob: nprob = %d; invalid problem instance " "number\n", nprob); for (k = 1; k <= 15; k++) parm[k] = data[nprob-101][k]; return; } /**********************************************************************/ #if 0 static int scan(char card[80+1], int pos, int len) { char buf[10+1]; memcpy(buf, &card[pos-1], len); buf[len] = '\0'; return atoi(buf); } int main(void) { int parm[1+15]; char card[80+1]; xassert(fgets(card, sizeof(card), stdin) == card); parm[1] = scan(card, 1, 8); parm[2] = scan(card, 9, 8); xassert(fgets(card, sizeof(card), stdin) == card); parm[3] = scan(card, 1, 5); parm[4] = scan(card, 6, 5); parm[5] = scan(card, 11, 5); parm[6] = scan(card, 16, 5); parm[7] = scan(card, 21, 5); parm[8] = scan(card, 26, 5); parm[9] = scan(card, 31, 10); parm[10] = scan(card, 41, 5); parm[11] = scan(card, 46, 5); parm[12] = scan(card, 51, 5); parm[13] = scan(card, 56, 5); parm[14] = scan(card, 61, 10); parm[15] = scan(card, 71, 10); glp_netgen(NULL, 0, 0, 0, parm); return 0; } #endif /* eof */