An Evaluation And Comparison Of Three Non-linear .
Calhoun: The NPS Institutional ArchiveDSpace RepositoryTheses and DissertationsThesis and Dissertation Collection1976An evaluation and comparison of threenon-linear programming codes.Waterman, Ralph JohnMonterey, California. Naval Postgraduate Schoolhttp://hdl.handle.net/10945/17750Downloaded from NPS Archive: Calhoun
AN EVALUATION AND COMPARISON OFTHREE NONLINEAR PROGRAMMING CODESRalph John Waterman
—u\vs\IIaC ilonierey, uaiiforniaSi « j***a——.''it——"-"-AN EVALUATION AND COMPARISON OFTHREE NONLINEAR PROGRAMMING CODESbyRalph John WatermanThesis AdvisorApprovedfor public release; distribution unlimited.March 1976T173114
Uadassif i dSECURITY CLASSIFICATION OF THIS PAGE (Vhen DetaEnter. d)READ INSTRUCTIONSBEFORE COMPLETING FORMREPORT LXjCUMENTATIGN PAGE1.4.REPORT NUM3ERTITLE2.GOVT ACCESSION NO(arid Subtltl*)TYPE OF REPORT5.4PERIOD COVEREDMaster's ThesisMarch 1976An Evaluation and Comparison of ThreeNonlinear Programming CodesAUTHOR* *;-7.RECIPIENT'S CATALOG NUMBERJ.«.PERFORMING ORG. REPORT NUMBER8.CONTRACT OR GRANT NOMSERC»JRalph John Waterman9.PERFORMING ORGANIZATION NAUE AND ADDRESS10.PROGRAM ELEMENT. PROJECT TASKAREA & WORK UNIT NUMBERS12.REPORT DATENaval Postgraduate SchoolMonterey, CA 93940II.CONTROLLING OFFICE NAME AND ADDRESSPostgraduate SchoolMonterey, CA 93940March 1976Naval'14.MONITORING AGENCY NAME4AODRESSf //ditterent /resi ControlttneOIHco)13.NUMBER OF PAGES94IS.SECURITY CLASS,(oi thla riftort)Unclassified15".16.DISTRIBUTION ST ATEMtH TO ECL AS5IFI CATION/SCHEDULEDOWN GRADING(ol thit ,i?pcrt)Approved for public release; distribution unlimited17.DISTRIBUTION STATEMENT16.SUPPLEMENTARY NOTES19.KEY WORDSfof the abetrecl(Continue on r»r*rto fid*tutored In Block 30,It dlifererittr m Report)neceeeery and identity by block number)linonlinear programmingcomputational testingoptimization20.ABSTRACT(Continue on revere* aideIInacaeeasy end l&entlty by block muxm-a*)This study evaluates and compares the production use of three nonlinearSUMT by W. C.programming codes.The three codes and their developers are:Mylander, R. L. Holmes and G. P. McCormick, GRG by L. S. Lasdon, A. D. Waren,M. W. Ratner and A. Jain, and GRAVES by G. W. Graves.This is the firstcomputer comparison of these three particular codes.Each code was evaluatedwith respect to the time and sophistication required of the user and thedegree of mandatory or potential interaction between the code and theTDD /JA(Page731)1473EDITION OF«MOV65S/N 0103-014-6601IISOBSOLETESECURITY CLASSIFICATION OF THIS PAOE(VThen Date SntaroJ)
UnclassifiedJt UWlTV CLASSIFICATION OFTM '.o»OF » .n(Orlm Fnl.20.analyst.The comparison criteria were accuracy, robustness, efficiencyand ease of utilization.Eight current and realistic test problems employing from 9-100 variablesand 2-20 constraints were used.The results revealed that no single code was superior or inferior in allThe choice of an optimal code among these three would be dependentaspects.upon the problems to be solved, the ability of the analyst and the desire ofthe analyst to alter the code for his own purposes.DDForm1473Jan 73S/N 0102-014-G601,1UnclassifiedSECURITY CLASSIFICAT,ON OF THIS P»CEfW.n DmtmEnlmrmd,
An Evaluation and Comparison ofThree Nonlinear Programming CodesbyRalph John WatermanLieutenant, United States NavyB.A., Columbia University,1969Submitted in partial fulfillment of therequirements for tne degree ofMASTER 0? SCIENCE IN OPERATIONS RESEARCHfrom theNAVAL POSTGRADUATE SCHOOLMarch 1976
DUDLEYABSTRACTThis study evaluates and compares the production use ofprogrammingnonlinearthreecodes.Thethree codes andtheir developers are: SUMT by W.C. Mylander, R.L. Holmes andG.P.McCormick, GRG by L.S. Lasdon, A.D.and A. Jain, and GRAVES by G.W. cationWaren, M.W.This isRatnerthefirstof these three particular andthedegree ofmandatory or potential interaction between the code andtheThe comparison criteria were accuracy, robustness,analyst.efficiency and ease of utilization.realistic test problems employingfrom 9-100 variables and 2-20 constraints were used.EightThecurrentresultsandrevealed that no single code was superioror inferior in all aspects.optimalThe choice of ancodeamong these three would be dependent upon the problems to besolved,the ability of the analyst andthedesireanalyst to alter the code for his own purposes.ofthe
TABLE OF CONTENTSI.II.INTRODUCTIONA.COMPARISON CRITERIA12B.TEST PROBLEMS16DESCRIPTION OF ation3.Printout234.Debugging plementation283.Printout294.Debugging .Printout374.Debugging Aids38METHOD AND RESULTS OF STUDYA.21ALGORITHMS'PERFORMANCE FOR EACH PROBLEM3949
B.APPENDIXCONCLUSIONS AND SUMMARYA:Test Problems and Results5356LIS! OF REFERENCES92INITIAL DISTRIBUTION LIST94
INTRODUCTIONI.This study compares and evaluates the production use ofThe analyst was not anthree nonlinear programming codes.author of any ofexperienceincodes,theclassroomstandardaprevious exposure tosomehadpriorprogrammingcontextbuthad noproduction nonlinear programming codeaor numerical solution of nonlinear programming problems.Obtainingthansolution y problem will requirefree,preciselyboth the analystandproblemand the code-amanbetweeneachdifferent degree ofacodetheanditisthis variation between problems that prevents theseparation of the analyst's responsibilities fromnonlinearthetwosolution isnonlinearacomplex interaction with subtle relationshipscomponent.ofcomputer and an analystawith an understanding of the problem for whichdesired.moreofutilizationthecomponents: an algorithm coded es,butavenue selected.thecode.codestheisamultitudeofone controlling theproduction type code has to The code must be able to respond to the variation in orhighlymanyorobjectivefew,nonlinear, constraints, many,few, linear, nonlinear, equality or inequality.An adequateis able to handle all of these possibilitiescodedegree of success.with someIn many instances however, the degree ofsuccess is dependent upon the ability of the analyst and hisfamiliarity with the internal actions and reactionsofthecode and its mathematical approach.Auser of a nonlinear programming code must be ableto
communicatecode withwithcode, he must be able to provide thetheuseable interpretation ofaandhebe able to interpret the results provided by the code.mustprogramThis requires the ability tocomputeremployedlanguagecompute ectan understanding of the printout to determineminimumbeenhasobtainedremedy the problem.boxrequiringAcodeaifnonlinear programming code isinputqualityglobalaablackorder to provide qualityincodelittleofisvaluecapable user.practical the analyst-code interaction, anAllcodesrequireby the user to evaluate the objectiveprovidedfunction and constraint eraction loaded withfirstenough ofif not what changes mightandThe most sophisticatedoutput.withoutAparameterseven more important,for the code and,thethe ability tocode,knowledge of theincodesHostalsoneedand some require second derivatives, inorder to determine directions for improvedsolutions.Theknowledqe of the functions other than what isgeneral evaluationavailable frcm these subroutines.Acriterion is the relative ease with which the user cancodehasncformulate these subroutines, especially the first time user.The code cannot operate without these function and gradientroutines; the accuracy and correctness of these functionevaluationsdeterminesthe code's ability to interact withthe user.Therealwaysexiststheelementcoding these subroutines, errors whichresultininaccuratesolutions.Aofifhuman error inundetectedwillcode which leaves theuser with no clue as to the type and location of such errorswillacause delays in debugging.solution is not solelyaThe total cost of reachingfunctionofthecomputertime
useddependent on the time of the man andThis author's experience indicates that, while anbutmachine.analystjointlyisoverdoesefficiency in usingcosttheproblemssignificant partcode,aof time develop anperiodanonlinearthe analyst's time will always gestasinglecomponent of the total cost.This study is alsoaguideapotentialtocomparison of the codes,usersaswhichtothe threeofnonlinear prcgramming codes might best satisfy aNumerous nonlinear programming vesimilarahopefullybeendegreeofinterest being shown in testing and comparing their specificconvergence ion towasDefense Program Analysis and Evaluation.L.S.Lasdon, A.D.SUMTcodeMylander, R.I. Holmes and aren, ucedmembersDepartment ofandthejcintlyand A. Jain asbeforGeneralizedGEG code, location nonlinearDepartmentProfessorbychosenThe GRAVES code wasand GRAVES.as GRG, SUMT,formulated incodesthreeTheW.CharlesMccormick as members oftheResearch Analysis Corporation, McLean, Virginia.This is the first computer and their closeFor easier evaluation of the resultsNIPthreeThe GRAVES and GRG codes do not, at thistime, have widespread usage andbeenoftheSUMTcode was chosen as the third and final codebecause of its more widely known qualities andlimitations.
This study was to compare the codes from the standpointof a s of each.Although studies and tests performed bysomeone thoroughly familar with the vagarities and intrinsicbehaviorofcode do reveal the upper bounds ofaacode'scapabilities, it was desired to test the accuracy and easeutilization when each code was used by an analyst in aofnormal production atmosphere.tolerances were originated bytuningroutinesinputtheIfanduser other than eachacode's author would they continue to perform satisfactorily?codes were compared on the ease of preparation forThethe first tiire user and on their responsetoanalyst'saneffort to interact with the internal operations of the code.After developingcodeafeel for the weaker characteristics timprovementsandproductionareaoneincodescomplete disruption elsewhere.ofpossible?suchisneeds.suitcodesperiod ofhisspecificThese three codes have very different approaches tocomparingtalentseachofuserandcommunication for each of theuser-codethethree codes one must keep in mind the factandanathe need for interaction between the code and theinthatall-purposeare not really desirable for an analyst who overyears may wish to alter an algorithm toThecode may causethePerhapsaanalystvarythethatneedsas will the code bestsuited to these needs.Theseroutineslanguage (FORTfiAN)360/67.Thisarecodedand run gmachine,theof attempting tocompare run times from two or more different machines.IBM360/67isaIBMThemultiprogramming machine; there may beavariation in run times of identical jobs of as much as 25%depending on the loading of other work on the macnine at the10
There is no effective way totime of underwiththe sameconditions.Thestudyknownbesttopaper [Kef.apresented by Colville in 1967, comparing 28 ]codesgeneralclassifications:1.Direct search methods2.Small step gradient methods3.Large step gradient methods4.Second derivative methodsColvillechoseeightproblemsselection made available to him by olvetothisset of eightproblems using his own NLP code and the computer facility ofhischoice.The results of Colville's study revealed manydifficulties, inaccuracies and discrepancies inherent in anycooperativeeffortofthis size.Of course, the time andeffort required for one person to program andcodeswouldbecanbegreatlyaffected28NLPColville concluded that theprohibitive.efficiency and performance oftestabynonlinearprogrammingcodethe method and efficiency ofinplementaticn on a computer.Several codes utilizingidentical mathematical approaches had a large variance inaccuracy and time.Algorithms which were identical from iability, accuracy and efficiency because of considerabledifferences in the method of programming these algorithmsforacomputer.11
standardize the solution times fromdifferent computers Colville developed a FORTRAN ramtimes.However, the comparison of standardized times is notaprecisediscrepancy betweenstandardizedtheusingwhen40 x 40 matrix tenand the Colville study revealed quitemeasurecomputersadifferentofprogramming code to solvesamethetimesaidentical problems.developforanalysis it is first necessary tomeasure of effectiveness.The ear programming code are complex andathere exists no instance, the number of function evaluationsnumberand constraint lthough somefunctionoptimal solution asisadditioninevaluations,solution of the problem.thetowilleach code.Foristhetotalanyfirstandreaching the finalstudieshaveusedevaluations required to reach themeasure of the code's efficiency, thisuseful criterion for constrained problems.The time required to determine the next pointevaluationtheit is necessary to evaluate the objectivetimesofweighsaccuratelygreatly among codes.varyforfunctionThus,the timeallotted for function evaluations may be quite insignificantrelativetothe total solution time and the scalar used todenote the number of function evaluations iscomparingthenonlinear programming alHowever,thecan be as important as their cost interms of computation time.A.ofnotbe the soundest andsimplest measure of efficiency of the codes.qualityreallyComparison Criteria12
The comparison of the three codes will be based onthefollowing criteria.Accuracy of the final solutions1.evaluating general purpose codes a primarycriterion must be whether or nor the algorithm can solve theproblems presented to an acceptable degree of precision.InRobustness of2.Althoughaanycodesolutionlccateswhichminimum must be considered somewhat e whichboth feasible andfromncnfeasible initial points is certainly more desirable.Speed of solution3.Total solution time is a function of the degree ofprecision desired in the values of the objective functions,the independent variables and the mptmadewasfunctions.procedure was not always successful for each differenttest problem because of the variety of minimum absolutefunctionbetweenrelatively flat minimum canprecisiondifferent level ofsteep slope orcause each code to attainthoughcomponentsnumericalchange may be required initerations.criteriaThe stopping criterion may be acodes.functioneveninto vary the termination parameters so that eachcode attained similar degrees of accuracy in allThisthetermination criteriatheemployed to stop the computation, anBecauseuseridentical.13asuppliedtolerances may be
Not all codes are designed to obtain the same degree ofprecision.solutiongoodfast,Asolutionmayextreme accuracy may be desired.withdesign determines the ability to differentprecisionbeyondcomparisonstimein order to achieve comparable timesfor each code in terms of accuracy, parameters werealteredsolutions had been attained until similarsuccessfulafterorThe code'sthesetoreasonable limits will completely distortbetweenneededbebut not identical degrees of accuracy were attained.Perhaps the most accurate timing comparison between thecodes quiredincludenotprocessing read and write statements andother unrelated machine activity.times do affect the actualfactorfortime forthedelayseachforcausedbyHowever, these additionalturnaroundtime,animportantany analyst working against a deadline.study progressed it was discovered that theAs thesolutiontimeswere typically significantly different for most problems andtherefore total CPU time was chosen as an adequate criterionfor the comparison data.Ease of setting up the user supplied subroutinesevaluation of the objective function and the4.fortheconstraint equationsIn order to utilize any nonlinear programming codeitisnecessarysubroutines.forEveryuserthecode requiressupplytoaoneormoreroutine for evaluatingobjective and constraint functions and many require thesecondfirstfew evenderivatives,whileaneed the.theThe physical size and degree of reparedbeutilization are two very important Difficultandhuman error.The
ondandproblemswithoutanalyticalvery sparce, orrecurring special structure in the constraints such as blockdiagonal, angular, staircase, or other form) can be a tryingprocedure.Asignificant factor is the value of theuser'sInsome circumstances a less efficientpreparation time.algorithm that can be easily coded for use is more practicalthan an efficient code requiring many man hours for setup.comparison along these lines is highly subjective and willvary from situation to situation but the relative degree ofAdifficulty involved in using eachcodecertainlymustbeconsidered.Output available to aid in debugging new programs5.Improperlyfunctionscodedbound to occur for almost every problem.foraderivatives areandItisimportantcode to provide appropriate output to aid in locatingthe particular mis-coded equations which are preventingattainmentcfsolution.theMostcodes do have the capability offorcheckingforconsistencythenonlinear onandgradient evaluations.Computer memory region required6.At most computer centers main memorylargelydeterminerequirementsthe priority of job requests and as suchcodes requiring large amounts of core will have muchturnaroundtimes.for computerlongerAlso many commercial data centers chargeserviceonakilobyte-secondbasismakingregion equally important with time of computation.7.Failure modeAllcodesfailat some time or another, usually15
either they are not suited forfor one of two reasons:particulartypebe reached,crtheof problem involved and a solution can notonesuppliedusertheofparametersorperhaps even the initial starting point needs to be altered.Some codes fail "hard" and thefromcausewith pinpointdetailsfunctiongradient values and, in the case thatpoint,bindinganeedsbetoand accurate determination of the cause ofQuickfailure can save an analyst many trialruns.availablelastthetoparticularthetheoutput while others fail mputererrorthe case of longinturnaround times.8.orpossibilitiesGrowthvariablesContemporary nonlinear problems of 100less are really small or moderate sized and the prospect
Calhoun: The NPS Institutional Archive DSpace Repository Theses and Dissertations Thesis and Dissertation Collection 19
Comparison table descriptions 8 Water bill comparison summary (table 3) 10 Wastewater bill comparison summary (table 4) 11 Combined bill comparison summary (table 5) 12 Water bill comparison – Phoenix Metro chart 13 Water bill comparison – Southwest Region chart 14
chart no. title page no. 1 age distribution 55 2 sex distribution 56 3 weight distribution 57 4 comparison of asa 58 5 comparison of mpc 59 6 comparison of trends of heart rate 61 7 comparison of trends of systolic blood pressure 64 8 comparison of trends of diastolic blood pressure 68 9 comparison of trends of mean arterial pressure
Water bill comparison summary (table 3) 10 Wastewater bill comparison summary (table 4) 11 Combined bill comparison summary (table 5) 12 Water bill comparison - Phoenix Metro chart 13 Water bill comparison - Southwest Region chart 14 Water bill comparison - 20 largest US cities chart 15
figure 8.29 sqt comparison map: superior bay (top of sediment, 0-0.5 ft) figure 8.30 sqt comparison map: 21st avenue bay figure 8.31 sqt comparison map: agp slip figure 8.32 sqt comparison map: azcon slip figure 8.33 sqt comparison map: boat landing figure 8.34 sqt comparison map: cargill slip figure
Comparison of Teacher Evaluation Models New Jersey schools use a multitude of different teacher evaluation models, including major . Comparison Table of Evaluation Models with Each Other and With the New Jersey Professional Teaching Standards . 1.e Designing Coherent Instruction: i Learning activities 4.4 The teacher aligns student .
Section 2 Evaluation Essentials covers the nuts and bolts of 'how to do' evaluation including evaluation stages, evaluation questions, and a range of evaluation methods. Section 3 Evaluation Frameworks and Logic Models introduces logic models and how these form an integral part of the approach to planning and evaluation. It also
POINT METHOD OF JOB EVALUATION -- 2 6 3 Bergmann, T. J., and Scarpello, V. G. (2001). Point schedule to method of job evaluation. In Compensation decision '. This is one making. New York, NY: Harcourt. f dollar . ' POINT METHOD OF JOB EVALUATION In the point method (also called point factor) of job evaluation, the organizationFile Size: 575KBPage Count: 12Explore further4 Different Types of Job Evaluation Methods - Workologyworkology.comPoint Method Job Evaluation Example Work - Chron.comwork.chron.comSAMPLE APPLICATION SCORING MATRIXwww.talent.wisc.eduSix Steps to Conducting a Job Analysis - OPM.govwww.opm.govJob Evaluation: Point Method - HR-Guidewww.hr-guide.comRecommended to you b
2.1 A comparison of the existing bus ticketing systems 14 2.2 Comparison between Linux, Window and Mac 18 2.3 Comparison between Chrome , Mozilla and IE 20 2.4 Comparison between PHP,ASP.NET and JSP 22 2.5 Comparison between MySQL and Oracle 24 3.1 Data dictionary for AgentBasicInfotable 44 3.2 Data dictionary for feedbacktable 45
