Page 1Page 2Page 3Page 4Page 5Page 6Page 7Page 8Page 9Page 10Page 11Page 12Page 13Page 14Page 15Page 16Page 17Page 18Page 19Page 20Page 211985-06 Spring 1985 OKA: Multi-goal NetworkOptimization Buddy Rhoads SOUTHERN METHODIST UNIVI-4 OKA: Multi-goal Network Optimization Buddy Rhoads OREM 4390 May 13, 1985...... S. .... ,. . •... • •. .. DEPARTMENT OF OPERATIONS RESEARCH AND ENGINEERING MANAGEMENTSCHOOL OF ENGINEERING AND APPLIED SCIENCE DALLAS, TEXAS 75275OKA: Multi-goal Network Optimization Buddy Rhoads OREM 4390 May 13, 1985OKA is an interactive network optimization program that solves multi-goal network problems. After given a set of arcs with multiple costs and limits for those arcs, OKA solves the network for both goals, giving the best and worst possible situations for each goal. OKA then allows for weights to be set on each of the goals and will then re-evaluate the model and present a graphical analysis of each cost in relation to its best and worst possible cost. In order to test OKA, a network problem based on school integration was modeled to have multiple goals. The first goal was to minimize the distance traveled by students, while the second goal was to minimize penalty costs. These penalty costs are assessed when a school exceeds or does not meet its minority requirements.OKA was initially coded in the 'C' programming language by Dr. Richard Barr of the Operations Research Department at Southern Methodist University. Dr. Barr took existing FORTRAN code using the Out of Kilter algorithm and converted it to 'C'. Originally, the code only solved single goal network problems and included no user interaction. In order to make the program multi-goal, additional input data needed to be supplied in the input file. Each arc now needed to have multiple costs; one for each goal. These costs are then multiplied by given weights to compute a single weighted cost for each arc in the model. The model is then processed by the Out of Kilter algorithm, which returns a minimum cost for the model and the foiws for each arc. These flows are then used to compute costs for each criterion by multiplying the flows by the original costs from the input data. Before this process is done, best and worst possible costs are computed for each goal by assigning weights of 0 and 1 to each goal and solving the network twice, alternating weights. This gives a maximum cost and a minimum cost for both criter. Using these best and worst costs, a graphic analysis of the new given weights is presented. The new costs are presented in relation to the worst and best possible costs foreach goal. A bar graph representing each goal shows this relationship. The larger the bar, the better your problem is to being at the best possible solution for that goal. The model used to test tIlP'application was created from a problem based on the New Haven School Board's proposal to improve racial balances in the city's public school system. A map of the district is shown in Exhibit 2. Students from nine neighborhoods needed to be assigned to four junior high schools within the district. Racial breakdowns for each neighborhood are shown in Exhibit 4 and road distances from those neighborhoods to the schools are given in Exhibit 5. Current enrollment statistics are shown in Exhibit 3. Notice the high imbalance in the minority distributions. Bassett has a minority enrollment of 91 percent while Fair Haven and Sheridan both show very low minority enrollments, 13 and 17 percent respectively. For the new desegregation plan, New Haven set a goal of a 41.5 percent balance of minorities at each of the four schools while also attempting to minimize the total distance traveled by the students. Exhibit 3 also shows optimal enrollments for the four schools in the district. Attempts in the past have been to remain within 20 percent of these optimal enrollments. Therefore, the maximum enrollment at Troup cannot exceed 1200 and the minimum must not go below 800.iTechnical Description OKA: See flow chart Exhibit 6. OKA reads the definition to the model for the input file MINDTA. This file contains all arcs with costs and upper and lower bounds for that arc. Also included is the total number of nodes and arcs in the model. This data is the are the first two numbers in the file. After the number of nodes and arcs is the model definition, one line per arc, in the following order: from node, to node, cost for goal A, cost for goal B, upper limit, and lower limit on that arc. All information must be entered. There are no defaults for limits or costs. Also, currently all nodes must be numbers. Future enhancements will allow literals for node definitions. After all data has been read in, OKA calculates tha maximum and minimum costs for both goal A and goal B. This is done by assigning a weight of 1 to weight A and a weight of 0 to weight B and then solving the network model with the weighted costs. This function will give the minimum, or best, possible cost for goal A and the maximum, or worst, possible cost for goal B. This step is duplicated with the weights reversed to give the minimum for B and the maximum for A; These four values are stored for use in later computations. IAt this point, a prompt is given to enter weights for both goal A andgoal B. New weighted costs are then calculated by: cost[m] = costa[m*wejghta + costb[m]*weightb where cost is the total weighted cost for that arc, costa is the cost associated with goal A, costb is the cost associated with goal B, weighta and weightb are the given weights, and m is the arc number. This calculation is made for each arc in the model. Now the new model with the weighted costs is passed to the network optimization code, which returns an optimal solution with a total cost and flows for all arcs. After the flows have been returned, total costs for goal A and goal B must be computed. totcosta += flow[m]*costa[m] totcostb += flow[m]*costb[m] where totcosta is the total cost for goal A, totcostb is total cost for goal B, and flow is the amount of flow through arc m. Costa and costb are the original costs for each arc from the input data. A graphic analysis of the model is now calculated for each goal using: = (maxcost - totcost)/(maxcost - mincost)N This calculation will give the integer i, which represents how good the new weighted cost (totcost) is in relation to the maximum and minimum costs for each goal that were stored in a previous step. Also available is the option of