diff options
Diffstat (limited to 'test/monniaux/glpk-4.65/src/api/netgen.c')
-rw-r--r-- | test/monniaux/glpk-4.65/src/api/netgen.c | 1020 |
1 files changed, 1020 insertions, 0 deletions
diff --git a/test/monniaux/glpk-4.65/src/api/netgen.c b/test/monniaux/glpk-4.65/src/api/netgen.c new file mode 100644 index 00000000..519fd609 --- /dev/null +++ b/test/monniaux/glpk-4.65/src/api/netgen.c @@ -0,0 +1,1020 @@ +/* netgen.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 <http://www.netlib.org/lp/generators>. +* +* The translation was made by Andrew Makhorin <mao@gnu.org>. +* +* 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 <http://www.gnu.org/licenses/>. +***********************************************************************/ + +#include "env.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 */ |