Hello all. I am attaching the files to run the pricing problem. The necessary files are the following: price.cpp All of the necessary functions and code used to test them price.h The main header file, function declarations, etc. pdata.h A second header file, which contains data to run different cases Since I have four cases to run initially, I am sending each case along as a different file. To use them, copy the file and name it pdata.h, then run the program. Here are the four files and the corresponding cases: pdata1.h K = 5, neighborhood is stepwise pdata2.h K = 5, neighborhood is random pdata3.h K = 1, neighborhood is stepwise pdata4.h K = 1, neighborhood is random Again, you *must* copy and rename these files as pdata.h to use them. The bounds on my indexes corresponding to the cases are: K = 1 bound = 11 K = 5 bound = 11^5 The estimated bound on my objective function is as follows: K = 1 -300 <= objective <= 200 K = 5 -300 <= objective <= 50 Let me know if you have any questions :-) Julie --=====================_896480711==_ Content-Type: text/plain; charset="us-ascii" Content-Disposition: attachment; filename="Pdata.h" /* pdata.h */ #ifndef pdata.h #define pdata.h #define K 5 /* Number of periods */ #define disttype 4 /* Demand distribution */ /* 1 = Uniform (random) demand with max and min 2 = Uniform (random) demand, sorted inverse to prices 3 = Poisson demand w/ mean (~Normal, sorted inverse to prices) 4 = Poisson demand, mean inversely related to prices */ // Use integers for both demands and prices #define mindemand 0 /* Minimum demand */ #define maxdemand 20 /* Maximum demand */ #define meandemand 50 /* Mean demand */ #define minprice 0 #define maxprice 10 #define pincrement 1 #define neightype 2 /* Type of neighborhood */ /* 1 = random (sorted in descending order) 2 = stepwise (up or down by increment, sort) */ #define HCost 1 /* Holding cost per unit */ #define purchase 2 /* Cost to purchase one unit */ #define SValue .5 /* Salvage cost */ #define AInv 25 /* Available inventory */ #endif --=====================_896480711==_ Content-Type: text/plain; charset="us-ascii" Content-Disposition: attachment; filename="Pdata1.h" /* pdata1.h */ #ifndef pdata.h #define pdata.h #define K 5 /* Number of periods */ #define disttype 4 /* Demand distribution */ /* 1 = Uniform (random) demand with max and min 2 = Uniform (random) demand, sorted inverse to prices 3 = Poisson demand w/ mean (~Normal, sorted inverse to prices) 4 = Poisson demand, mean inversely related to prices */ // Use integers for both demands and prices #define mindemand 0 /* Minimum demand */ #define maxdemand 20 /* Maximum demand */ #define meandemand 50 /* Mean demand */ #define minprice 0 #define maxprice 10 #define pincrement 1 #define neightype 2 /* Type of neighborhood */ /* 1 = random (sorted in descending order) 2 = stepwise (up or down by increment, sort) */ #define HCost 1 /* Holding cost per unit */ #define purchase 2 /* Cost to purchase one unit */ #define SValue .5 /* Salvage cost */ #define AInv 25 /* Available inventory */ #endif --=====================_896480711==_ Content-Type: text/plain; charset="us-ascii" Content-Disposition: attachment; filename="Pdata2.h" /* pdata2.h */ #ifndef pdata.h #define pdata.h #define K 5 /* Number of periods */ #define disttype 4 /* Demand distribution */ /* 1 = Uniform (random) demand with max and min 2 = Uniform (random) demand, sorted inverse to prices 3 = Poisson demand w/ mean (~Normal, sorted inverse to prices) 4 = Poisson demand, mean inversely related to prices */ // Use integers for both demands and prices #define mindemand 0 /* Minimum demand */ #define maxdemand 20 /* Maximum demand */ #define meandemand 50 /* Mean demand */ #define minprice 0 #define maxprice 10 #define pincrement 1 #define neightype 1 /* Type of neighborhood */ /* 1 = random (sorted in descending order) 2 = stepwise (up or down by increment, sort) */ #define HCost 1 /* Holding cost per unit */ #define purchase 2 /* Cost to purchase one unit */ #define SValue .5 /* Salvage cost */ #define AInv 25 /* Available inventory */ #endif --=====================_896480711==_ Content-Type: text/plain; charset="us-ascii" Content-Disposition: attachment; filename="Pdata3.h" /* pdata3.h */ #ifndef pdata.h #define pdata.h #define K 1 /* Number of periods */ #define disttype 4 /* Demand distribution */ /* 1 = Uniform (random) demand with max and min 2 = Uniform (random) demand, sorted inverse to prices 3 = Poisson demand w/ mean (~Normal, sorted inverse to prices) 4 = Poisson demand, mean inversely related to prices */ // Use integers for both demands and prices #define mindemand 0 /* Minimum demand */ #define maxdemand 20 /* Maximum demand */ #define meandemand 50 /* Mean demand */ #define minprice 0 #define maxprice 10 #define pincrement 1 #define neightype 2 /* Type of neighborhood */ /* 1 = random (sorted in descending order) 2 = stepwise (up or down by increment, sort) */ #define HCost 1 /* Holding cost per unit */ #define purchase 2 /* Cost to purchase one unit */ #define SValue .5 /* Salvage cost */ #define AInv 25 /* Available inventory */ #endif --=====================_896480711==_ Content-Type: text/plain; charset="us-ascii" Content-Disposition: attachment; filename="Pdata4.h" /* pdata4.h */ #ifndef pdata.h #define pdata.h #define K 1 /* Number of periods */ #define disttype 4 /* Demand distribution */ /* 1 = Uniform (random) demand with max and min 2 = Uniform (random) demand, sorted inverse to prices 3 = Poisson demand w/ mean (~Normal, sorted inverse to prices) 4 = Poisson demand, mean inversely related to prices */ // Use integers for both demands and prices #define mindemand 0 /* Minimum demand */ #define maxdemand 20 /* Maximum demand */ #define meandemand 50 /* Mean demand */ #define minprice 0 #define maxprice 10 #define pincrement 1 #define neightype 1 /* Type of neighborhood */ /* 1 = random (sorted in descending order) 2 = stepwise (up or down by increment, sort) */ #define HCost 1 /* Holding cost per unit */ #define purchase 2 /* Cost to purchase one unit */ #define SValue .5 /* Salvage cost */ #define AInv 25 /* Available inventory */ #endif --=====================_896480711==_ Content-Type: text/plain; charset="us-ascii" Content-Disposition: attachment; filename="Price.cpp" // the following program (price2.cpp) includes the test functions // f and neighbor, plus the random-variate generation routines // and necessary supporting functions #include "pdata.h" #include "price.h" //**************************************************************************** main() { int i,j; long PriceID = 0; double Objective; PriceID = initTheta(); for (i = 1; i < 10; i++) { printf("\n"); for (j = 1; j < K + 1; j++) // print price ID here { printf("%d ", prices[j]); } printf("\t\t"); Objective = f(PriceID); // get objective. for (j = 1; j < K + 1; j++) // print demands here { printf("%d ", demand[j]); } printf("\tObj: %.2f\n", Objective); // print objective PriceID = neighbor(PriceID); // get new price array } } //**************************************************************************** double f(long theta) // This function returns the objective value from // evaluating according to the value of theta provided // which is the ID of the price vector. It calls // GenDemand to generate demand according to the prices // according to the demand distribution (using random // variate generation). { double objective = 0, revenue = 0, salvage = 0, holdcost = 0, sumdem = 0, EndPeriodInv = 0,tempsum = 0; int i, j; MapIDtoPrice(theta); // Map ID to price array GenDemand(); // Call routine to generate demand // Current prices are available, function creates // demands (in global array) according to prices for (i = 1; i < K + 1; i++) // For each period, { revenue += prices[i]*demand[i]; // Sum revenue sumdem += demand[i]; // Sum total demand if (i>=2) { for (j = 1; j < i + 1; j++) // For all the previous periods, tempsum += demand[j]; // sum demand EndPeriodInv += AInv - tempsum; } } salvage = SValue*(AInv - sumdem); // Salvage value * Amount unsold holdcost = HCost*EndPeriodInv; // Holding cost * sum end period inv objective = -1*(revenue + salvage - holdcost); // CHECK TO SEE IF 0's OKAY!! return objective; }// end fn f long neighbor(long theta) // This function generates a candidate solution from the neighborhood // of theta (either stepwise increments from current theta or randomly). // Theta is wrapped on ends if price is chosen outside of minprice or maxprice. // Theta is ID of price vector, prices are mapped using this. //If a bad value is entered, the function returns -9999 { double U, IntStart = 0, IntFinish = 0, NumPrices; long neighborhood, PriceID = 0; int i, j; MapIDtoPrice(theta); // Map ID to price array neighborhood = neightype; // Assign type of neighborhood // input error check for (i = 1; i < K + 1; i++) { if (prices[i] > maxprice || prices[i] < minprice) {return -9999;} } if (neighborhood == 1) // Random (constrained) neighborhood, sorted { // Number of prices NumPrices = floor((maxprice - minprice)/pincrement) + 1; for (i = 1; i < K + 1; i++) // For all k periods, { U = rand(6); // generate a uniform random variable for (j = 1; j < NumPrices + 1; j++) { IntStart = (j - 1)/NumPrices; // Calculate beginning and IntFinish = j/NumPrices; // end of intervals if (U >= IntStart && U < IntFinish) // Determine which interval { // Match interval to a price prices[i] = (j-1)*pincrement + minprice; // Assign to array } } } } else { if (neighborhood == 2) // Stepwise neighborhood, sorted { for (i = 1; i < K + 1; i++) // For all k periods, { U = rand(6); // choose to go up or down randomly, if (U < 0.5) // (< 0.5 indicates down) { // Assign price up or down by increment prices[i] += 0 - pincrement; } else { prices[i] += 0 + pincrement; } // Wrap if necessary if (prices[i] == maxprice + pincrement) { prices[i] = minprice; } if (prices[i] == minprice - pincrement) { prices[i] = maxprice; } } } } revbubblesort(); // Sort array of prices in decreasing order PriceID = MapPricetoID(); // Map price array to ID return PriceID; }//end fn neighbor ///////////////////////////////////////////////////////////////// long initTheta (void) // Function initializes all arrays. // function also determines first price vector randomly { int i,j; long PriceID; double U, IntStart, IntFinish, NumPrices; for (i = 0; i < K + 2; i++) { prices[i] = 0; demand[i] = 0; } // Code is same as in neighbor function // Number of prices NumPrices = floor((maxprice - minprice)/pincrement) + 1; for (i = 1; i < K + 1; i++) // For all k periods, { U = rand(6); // generate a uniform random variable for (j = 1; j < NumPrices + 1; j++) { IntStart = (j - 1)/NumPrices; // Calculate beginning and IntFinish = j/NumPrices; // end of intervals if (U >= IntStart && U < IntFinish) // Determine which interval { // Match interval to a price prices[i] = (j-1)*pincrement + minprice; // Assign to array } } } revbubblesort(); PriceID = MapPricetoID(); return PriceID; } ///////////////////////////////////////////////////////////////// void MapIDtoPrice(long ID) // Function maps ID of solution (in vector) to price array // Output is price in global array { int i; long IDleft = 0; double NumPrices = 0, PriceNum = 0; NumPrices = floor((maxprice - minprice)/pincrement) + 1; IDleft = ID; for (i = 1; i < K + 1; i++) { // For each period, PriceNum = floor(IDleft/(pow(NumPrices, K - i))) + 1; // Find the price ID prices[i] = minprice + (PriceNum - 1)*pincrement;// Translate ID to value IDleft = fmod(IDleft, pow(NumPrices, K-i)); // Determine ID left } return; } ///////////////////////////////////////////////////////////////// long MapPricetoID(void) // Function maps price array to ID (in vector) // Input is global price array, output is integer ID { int i; long ID = 0; double NumPrices = 0, PriceNum = 0; NumPrices = floor((maxprice - minprice)/pincrement) + 1; for (i = 1; i < K + 1; i++) { // For each period, PriceNum = (prices[i] - minprice)/pincrement + 1; // Give the price an ID ID += (PriceNum - 1)*(pow(NumPrices,K - i)); // Translate the ID to space } // Sum(j): (PriceID - 1)*(Num slots before it) return ID; } ///////////////////////////////////////////////////////////////// void GenDemand (void) { // this routine generates demand for each price according to the // distribution specified. Prices are contained in a global array int i,j, demandtype, InvMean = 0, sumdemand = 0, temp = 0; double U, IntStart, IntFinish, NumDemands = 0; demandtype = disttype; // Records distribution of demand if (demandtype == 1 || demandtype == 2)// Demand is uniform with max and min { NumDemands = floor(maxdemand - mindemand) + 1 ; // Number of demands for (i = 1; i < K + 1; i++) // CHECK DOUBLE LOOP!! { for (j = 1; j < NumDemands + 1; j++) { IntStart = (j - 1)/NumDemands; // Determine start of interval IntFinish = j/NumDemands; // and end of interval U = rand(2); // Generate random number if (U >= IntStart && U < IntFinish) // Determine which interval { demand[i] = j - 1 + mindemand; // Assign appropriate demand } } } } else { if (demandtype == 3) // Demand is poisson with mean demand { for (i = 1; i < K + 1; i++) { // Generate Poisson random number demand[i] = Poisson(meandemand,2); } } else { if (demandtype == 4) // Demand is poisson according to prices { for (i = 1; i < K + 1; i++) { if (prices[i] == maxprice) { demand[i] = 0; } else { InvMean = maxprice - prices[i]; demand[i] = Poisson(InvMean, 2); } } } } } if (demandtype == 2 || demandtype == 3)// sorted uniform or sorted Poisson { bubblesort(); // Now prices are decreasing, } // and demands are increasing. for (i = 1; i < K + 1; i++) // Check for 0's, means salvage. { if (prices[i] == 0) { demand[i] = 0; } temp = sumdemand + demand[i]; if (temp > AInv) { demand[i] = AInv - sumdemand; } } return; } ///////////////////////////////////////////////////////////////// void revbubblesort(void) // this function sorts the array of prices (in decreasing order) { int i, j, p; for (i = 1; i < K + 1; i++) { for (j = 1; j < K + 1 - i; j++) { if (prices[j] < prices[j+1]) // This line changed from usual sort { p = prices[j]; prices[j] = prices[j+1]; prices[j+1] = p; } } } return; } ///////////////////////////////////////////////////////////////// void bubblesort(void) /* Function bubble sorts the array in increasing order */ { int i, j, d; for (i = 1; i < K + 1; i++) { for (j = 1; j < K + 1 - i; j++) { if (demand[j] > demand[j+1]) { d = demand[j]; demand[j] = demand[j+1]; demand[j+1] = d; } } } return; } ///////////////////////////////////////////////////////////////// int Poisson(double lambda, int stream) // Poisson distribution generated based on mean lamda // Generates, sums, and counts exponentials w/ mean 1/lambda { int n = 0; double sumexp = 0, mean; mean = 1/lambda; do { n += 1; sumexp += expon(mean,stream); } while (sumexp < 1); n = n-1; return n; } ////////////////////////////////////////////////////////////////////////// //Random-Number Generator form Law and Kelton, p454 //Prime modulus multiplicative linear congruential generator //Z[i]=(630360013 *Z[i-1]) (mod(pow2,31)-1), based on Marse and //Roberts portable Fortran random-number generator UINRAN. Multiple //(100) streams are supported, with seeds spaced 100,000 apart. //throughout, input argument "stream" must be an int giving the //desired stream number. The header file rand.h must be included // in the calling program (#include "rand.h") before using these // functions //Usage: (Three functions) //1. To obtain the next U(0,1) random number from stream "stream," // execute // u = rand(stream); // where rand is a float function. The float variable u will // contain the next random number. // //2. To set the seed for stream "stream" to a desired value zset, // execute // randst(zset, stream); // where randst is a void function and szet must be a long set to // the desired seed, a number between 1 and 2147483646 (inclusive). // Default seeds for all 100 streams are given in the code. // //3. To get the current (most recently used)integer in the sequence // being generated for stream "stream" into the long variable zget, // execute // zget = randgt(stream) // where randgt is a long function /* Generate the next random number. */ double rand(int stream) { long zi, lowprd, hi31; zi = zrng[stream]; lowprd = (zi & 65535) * MULT1; hi31 = (zi >> 16) * MULT1 + (lowprd >> 16); zi = ((lowprd & 65535) - MODLUS) + ((hi31 & 32767) << 16) + (hi31 >> 15); if (zi < 0) zi += MODLUS; lowprd = (zi & 65535) * MULT2; hi31 = (zi >> 16) * MULT2 + (lowprd >> 16); zi = ((lowprd & 65535) - MODLUS) + ((hi31 & 32767) << 16) + (hi31 >> 15); if (zi < 0) zi += MODLUS; zrng[stream] = zi; return (( (double) (zi >> 7 | 1) + 1 )/ 16777216.0); } ////////////////////////////////////////////////////////////////////////////// //Set the current zrng for stream "stream" to zset void randst (long zset, int stream) { zrng[stream] = zset; } ////////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////////// //Return the current zrng for stream "stream". long randgt (int stream) { return zrng[stream]; } ////////////////////////////////////////////////////////////////////////////// double expon(double rmean,int istream) /* return exponential random variable with mean rmean. */ { return -1.00 * rmean * log( (double)simrand(istream) ); } ////////////////////////////////////////////////////////////////////////////// /* Generate the next random number. */ float simrand(int stream) { long zi, lowprd, hi31; zi = zrng[stream]; lowprd = (zi & 65535) * MULT1; hi31 = (zi >> 16) * MULT1 + (lowprd >> 16); zi = ((lowprd & 65535) - MODLUS) + ((hi31 & 32767) << 16) + (hi31 >> 15); if (zi < 0) zi += MODLUS; lowprd = (zi & 65535) * MULT2; hi31 = (zi >> 16) * MULT2 + (lowprd >> 16); zi = ((lowprd & 65535) - MODLUS) + ((hi31 & 32767) << 16) + (hi31 >> 15); if (zi < 0) zi += MODLUS; zrng[stream] = zi; /* the next line has been corrected by GDG 7/22/93 */ return (zi >> 7 | 1)/ 16777216.0; } ////////////////////////////////////////////////////////////////////////////// --=====================_896480711==_ Content-Type: text/plain; charset="us-ascii" Content-Disposition: attachment; filename="Price.h" /* Created 5/14/98 */ /* Last Updated 5/14/98 */ // following is the header file for price2.cpp #ifndef PRICE_H #define PRICE_H #include #include #include #include #include #include // Function Declarations double f(long theta); // this function returns a single random value from the // quadratic test function of Nelson at point theta. // it calls CalcNorm, a function to generate N(0,1) // random variates via the inverse cdf method, by // passing a U(0,1) generated by rand(); long neighbor(long theta); // this routine generates a candidate solution from the neighborhood // of theta for the feasible region THETA = [-100, -99, ..., 99, 100] // by wrapping the feasible region. // If a bad value is entered, the function returns -9999 long initTheta (void); // Function initializes all arrays. // function also determines first price vector randomly void MapIDtoPrice(long ID); // Function maps ID of solution (in vector) to price array // Output is price in global array long MapPricetoID(void); // Function maps price array to ID (in vector) // Input is global price array, output is integer ID void GenDemand (void); // this routine generates demand for each price according to the // distribution specified. void revbubblesort (void); // this function sorts the array of prices (which is an external array) // in decreasing order void bubblesort(void); // this function sorts the array of demands (in increasing order) int Poisson(double lambda, int stream); // Poisson distribution generated based on mean lamda // Generates, sums, and counts exponentials w/ mean 1/lambda //Law & Kelton generator p.454-6 double expon(double rmean,int istream); float simrand(int stream); double rand(int stream); void randst(long zset, int stream); long randgt(int stream); //Definitions for L&K // Define the constants #define MODLUS 2147483647 #define MULT1 24112 #define MULT2 26143 // External (global) declarations of variables and arrays int prices[K + 1]; // Holds the prices for each period int demand[K + 1]; // Holds the demands based on prices /* Set the default seeds for all 100 streams. */ static long zrng[] = { 0, 1973272912, 281629770, 20006270,1280689831,2096730329,1933576050, 913566091, 246780520,1363774876, 604901985,1511192140,1259851944, 824064364, 150493284, 242708531, 75253171,1964472944,1202299975, 233217322,1911216000, 726370533, 403498145, 993232223,1103205531, 762430696,1922803170,1385516923, 76271663, 413682397, 726466604, 336157058,1432650381,1120463904, 595778810, 877722890,1046574445, 68911991,2088367019, 748545416, 622401386,2122378830, 640690903, 1774806513,2132545692,2079249579, 78130110, 852776735,1187867272, 1351423507,1645973084,1997049139, 922510944,2045512870, 898585771, 243649545,1004818771, 773686062, 403188473, 372279877,1901633463, 498067494,2087759558, 493157915, 597104727,1530940798,1814496276, 536444882,1663153658, 855503735, 67784357,1432404475, 619691088, 119025595, 880802310, 176192644,1116780070, 277854671,1366580350, 1142483975,2026948561,1053920743, 786262391,1792203830,1494667770, 1923011392,1433700034,1244184613,1147297105, 539712780,1545929719, 190641742,1645390429, 264907697, 620389253,1502074852, 927711160, 364849192,2049576050, 638580085, 547070247 }; #endif --=====================_896480711==_--