June 5, 2003 DESIGN PRINCIPLES AND NEW DEVELOPMENTS IN THE AMPL MODELING LANGUAGE RobertFourer DepartmentofIndustrialEngineeringandManagementSciences NorthwesternUniversity Evanston,IL,USA [email protected] DavidM.Gay AMPLOptimizationLLC NewProvidence,NJ,USA [email protected] BrianW.Kernighan DepartmentofComputerScience PrincetonUniversity Princeton,NJ,USA [email protected] Abstract ThedesignoftheAMPLmodelinglanguagestressesnaturalnessofexpressions, generalityofiteratingoversets,separationofmodelanddata,easeofdatama- nipulation,andautomaticupdatingofderivedvalueswhenfundamentalvalues change. We show how such principles have guided the addition of database access,complementaritymodeling,andotherlanguagefeatures. Thispaperwillappearaschapter7ofModelingLanguagesinMathematical Optimization,editedbyJosefKallrath,KluwerAcademicPublishers,2003. Keywords: AMPL,modelinglanguages,optimization,mathematicalprogramming,model- data separation, sets, iteration, set manipulation, automatic updates, database access,complementarity,sparsity,nonlinearity 1 2 Introduction AMPL is a little language that grew. Originally designed to express linear programming problems, it gradually expanded to encompass nonlinear pro- gramming problems — possibly with complementarity constraints and some integervariables—anditacquiredacommandenvironmentformanipulating suchproblems. AlthoughAMPL’spresolvephaseoccasionallydeterminesthe solutiontoaproblem,AMPLwasnevermeanttosolveproblemsitself;rather, itworkswithseparatesolversthatmayevenrunondifferentmachines. TherestofthischapterprovidesmoredetailonAMPL’sdesignandcapabil- ities. AMPL’shistoricalbackgroundhasstronglyaffecteditsdesign,sosection 1givesmoredetailaboutAMPL’shistory. Section2presentsasimpleexample, a variant of the venerable diet problem, to illustrate some aspects of AMPL’s design. OneofAMPL’sstrengthsliesinthegeneralityofitsindexingandset expressions; section3demonstratessomeofthisbydiscussinganexampleof airlinefleetassignmentthatusessetsofquadruplesandslices. Inthedecadebetweentheappearancesofthefirstandsecondeditionsofthe AMPLbook[12],weextendedAMPLinvariousways. Threefurthersections summarize these extensions, including some that are still underway. Section 4dealswithiterativeschemesandotherflow-of-controlissues;section5con- sidersnewkindsofmodels—complementarity,combinatorial,andstochastic; and section 6 discusses communications with other systems — databases, In- ternetservices,andsolvers. Section7summarizesdifferencesbetweenthefirst andsecondAMPLbookeditions,andabriefconclusionappearsinsection8. 1 Background and Early History SeveralthreadsconvergedintheinitialdesignofAMPL.Intheearly1980s little languages were a topic of interest in the Computing Science Research CenterofBellLaboratories. Thesearespecial-purposelanguagesdesignedto simplify and facilitate computing in well focused applicationareas. Two nice examples are grap [3], a troff preprocessor that makes it easy to typeset various kinds of graphs, and chem [2], a troff preprocessor for typesetting chemicalformulae. AnotheraspectofAMPL’sbackgroundwasthehooplasurroundingNarendra Karmarkar’sannouncementofanefficientpolynomial-timelinearprogramming algorithm [20]. It was clear to us in the Computing Science Research Center thatoneneedsmorethanjustapowerfulalgorithm;onealsoneedsaproblem- formulationlanguagethatisnaturalforusebypeopleyetsuitableforprocessing byacomputer,andoneneedsaconvenientwaytoprovidetherelevantdataand datastructurestosolvers. Webelievedthatamathematicallynaturallanguage would help to make the audience for optimization technology much broader thanitwouldotherwisebe. AMPLDesignPrinciples&NewDevelopments 3 BobFourerandDavidGayhadfirstmetwhenbothworkedattheNationalBu- reauofEconomicResearch’sComputerResearchCenterinCambridge,Mas- sachusetts, where Fourer worked on documentation for sesame, an LP solver that William Orchard-Hayes was developing for NBER. Fourer subsequently attended graduate school at Stanford, then joined the faculty at Northwestern University. Among other things, he wrote about the advantages of modeling languagesovermatrixgenerators[8]. MeanwhileGayhadmovedtoBellLabs. WhenGayandFourerhappenedtomeetataconference,Fourermentionedhe wouldbecomingupforsabbatical. Inthatwayitdevelopedthathewasinvited tovisitBellLabsforthe1985-86academicyear,withtheexpectationthatthe three of us (Fourer, Gay, Kernighan) would work on a modeling language for linearprogramming. Ourinitialworkledtoareport[10]aboutthefirstversionofAMPL.Models acceptable to that version would still work today, but commands would not: the first implementation did not recognize any commands, not even “solve”. Itsimplyreadamodelandsubsequentdataandwroteoutatranslatedproblem in a simple text format (that we no longer use). Much of the current data- specificationsyntaxwasprovidedbyaseparatepreprocessor. TheinitialAMPL reporteventuallybecameour1990AMPLpaper[11]inManagementScience. Manyimprovementsensued,asthefollowingsectionswillshow. 2 The McDonald’s Diet Problem Asanintroduction,imagineastudentwhomustdecidewhatfoodstobuyat acertainpopularfast-foodestablishmentsoastominimizecostwhilemeeting some nutritional requirements. For concreteness, suppose the 9 foods and 7 nutrientsshowninTable1.1arerelevant. Supposefurtherthatthefoodcosts, nutrients,andnutrientrequirementsareasgiveninTable1.2(derivedfromthe establishment’sliterature). Table1.1. McDonald’sDietProblemfoodsandnutrients. Foods: Nutrients: QP QuarterPounder Prot Protein FR Fries,small Iron Iron MD McLeanDeluxe VitA VitaminA SM SausageMcMuffin Cals Calories BM BigMac VitC VitaminC 1M 1%LowfatMilk Carb Carbohydrates FF Filet-O-Fish Calc Calcium OJ OrangeJuice MC McGrilledChicken 4 Table1.2. McDonald’sDietProblemdata. QP MD BM FF MC FR SM 1M OJ Cost 1.84 2.19 1.84 1.44 2.29 0.77 1.29 0.60 0.72 Need: Protein 28 24 25 14 31 3 15 9 1 55 VitaminA 15 15 6 2 8 0 4 10 2 100 VitaminC 6 10 2 0 15 15 0 4 120 100 Calcium 30 20 25 15 15 0 20 30 2 100 Iron 20 20 20 10 8 2 15 0 2 100 Calories 510 370 500 370 400 220 345 110 80 2000 Carbo 34 35 42 28 42 26 27 12 20 350 Table1.3. ConcreteMcDonald’sDietProblem. Minimize 1.84x +2.19x +1.84x + 1.44x QP MD BM FF +2.29x + 0.77x +1.29x +0.60x +0.72x MC FR SM 1M OJ Subjectto 28x + 24x + 25x + 14x QP MD BM FF + 31x + 3x + 15x + 9x + x ≥ 55 MC FR SM 1M OJ 15x + 15x + 6x + 2x QP MD BM FF + 8x + 4x + 10x + 2x ≥ 100 MC SM 1M OJ 6x + 10x + 2x QP MD BM + 15x + 15x + 4x + 120x ≥ 100 MC FR 1M OJ 30x + 20x + 25x + 15x QP MD BM FF + 15x + 20x + 30x + 2x ≥ 100 MC SM 1M OJ 20x + 20x + 20x + 10x QP MD BM FF + 8x + 2x + 15x + 2x ≥ 100 MC FR SM OJ 510x + 370x + 500x + 370x QP MD BM FF + 400x + 220x + 345x + 110x + 80x ≥2000 MC FR SM 1M OJ 34x + 35x + 42x + 38x QP MD BM FF + 42x + 26x + 27x + 12x + 20x ≥ 350 MC FR SM 1M OJ Since the expressions for total food cost and resulting nutrients are linear, thisproblemhastheformofagenerallinearprogrammingproblem, Minimize cTx Subjectto Ax = b x ≥ 0 butsuchaformulationistoogeneralforconvenientmanipulation. Theproblem alsohastheconcreteformshowninTable1.3,butthisformistoospecific— AMPLDesignPrinciples&NewDevelopments 5 Table1.4. AbstractmodelfortheMcDonald’sDietProblem. Given F,asetoffoods, N,asetofnutrients, a ≥0,theunitsofnutrientiinoneservingoffoodj, ij foreachi∈N andj ∈F, b ≥0,theunitsofnutrientirequiredinthediet,foreachi∈N, i c ≥0,thecostperservingoffoodj,foreachj ∈F, j Definex ≥0tobethenumberofservingsoffoodjtobepurchased, j foreachj ∈F. P Minimize c x , j j j∈F P Subjectto a x ≥b foreachi∈N. ij j i j∈F Table1.5. DietModelinAMPL(mcdiet.mod). set NUTR; # nutrients set FOOD; # foods param amt {NUTR,FOOD} >= 0; # amount of nutrient in each food param nutrLow {NUTR} >= 0; # lower bound on nutrients in diet param cost {FOOD} >= 0; # cost of foods var Buy {FOOD} >= 0 integer; # amounts of foods to be purchased minimize TotalCost: sum {j in FOOD} cost[j] * Buy[j]; subject to Need {i in NUTR}: sum {j in FOOD} amt[i,j] * Buy[j] >= nutrLow[i]; toohardtosetupandmaintain. Between these extremes lies the general mathematical model for the diet problemshowninTable1.4. AMPLwasdesignedtopermiteasytranscription ofmathematicalmodelsinsuchaform. AnAMPLmodelforthedietproblem is shown in Table 1.5. This model represents a whole class of diet problems; toobtaintheparticularinstancecorrespondingtoTables1.2and1.3,wemust supply the relevant data. There are various ways to do this, but the simplest for small examples is to provide a file of AMPL data statements, such as the oneinTable1.6. Withfilesmcdiet.modandmcdiet1.datcontainingthetext shown in Tables 1.5 and 1.6, we obtain a continuous-variable solution to the problem if we use AMPL’s default solver, MINOS, which ignores integrality restrictionsonvariables. ThisisshowninTable1.7. 6 Table1.6. AMPLdatastatementsforMcDonald’sDietProblem(mcdiet1.dat). data; param: FOOD: cost := "Quarter Pounder" 1.84 "Fries, small" .77 "McLean Deluxe" 2.19 "Sausage McMuffin" 1.29 "Big Mac" 1.84 "1% Lowfat Milk" .60 "Filet-o-Fish" 1.44 "Orange Juice" .72 "McGrilled Chicken" 2.29 ; param: NUTR: nutrLow := Prot 55 VitA 100 VitC 100 Calc 100 Iron 100 Cals 2000 Carb 350 ; param amt (tr): Cals Carb Prot VitA VitC Calc Iron := "Quarter Pounder" 510 34 28 15 6 30 20 "McLean Deluxe" 370 35 24 15 10 20 20 "Big Mac" 500 42 25 6 2 25 20 "Filet-o-Fish" 370 38 14 2 0 15 10 "McGrilled Chicken" 400 42 31 8 15 15 8 "Fries, small" 220 26 3 0 15 0 2 "Sausage McMuffin" 345 27 15 4 0 20 15 "1% Lowfat Milk" 110 12 9 10 4 30 0 "Orange Juice" 80 20 1 2 120 2 2; Table1.7. Continuous-variablesolutionofMcDonald’sDietProblem. ampl: model mcdiet.mod; ampl: data mcdiet1.dat; ampl: solve; MINOS 5.5: ignoring integrality of 9 variables MINOS 5.5: optimal solution found. 7 iterations, objective 14.8557377 ampl: option omit_zero_rows 1; ampl: display Buy; Buy [*] := ’1% Lowfat Milk’ 3.42213 ’Fries, small’ 6.14754 ’Quarter Pounder’ 4.38525 ; AMPLDesignPrinciples&NewDevelopments 7 Table1.8. IntegersolutionofMcDonald’sDietProblem. ampl: option solver cplex; solve; CPLEX 8.0.0: optimal integer solution; objective 15.05 27 MIP simplex iterations 15 branch-and-bound nodes ampl: display Buy; Buy [*] := ’1% Lowfat Milk’ 4 Filet-o-Fish 1 ’Fries, small’ 5 ’Quarter Pounder’ 4 ; Table1.9. McDonald’sDietfor63foods,12nutrients. ampl: reset data; ampl: data mcdiet2.dat; ampl: solve; CPLEX 8.0.0: optimal integer solution; objective 0 0 MIP simplex iterations 0 branch-and-bound nodes ampl: display Buy; Buy [*] := ’Barbeque Sauce’ 50 Croutons 55 ’Hot Mustard Sauce’ 50 ; Inreality,onecannotorderfractionalservings,soitisbettertouseasolver thatrespectsintegrality. ThisisshowninTable1.8. Solvingwithalargerdatasetiseasy. Table1.9illustratesthisandrevealsa weakness in the model: one can satisfy all the nutritional requirements in the bigger data set by using free condiments. A more palatable solution requires additionalconstraintslinkingcondimentamountstopurchasesofrelatedfoods. 3 The Airline Fleet Assignment Problem TheMcDonald’sDietProblemprovidesanintroductiontomanyfundamental aspectsofAMPL,butitillustratesonlyafewofthesetindexingfeaturesthat areessentialinagoodmodelinglanguage. AMPL’sfacilitiesforconstructing and manipulating sets and for iterating over sets make it a powerful language that can readily express complex models. Whereas the diet example involves 8 onlysimpleone-dimensionalsets(FOODandNUTR),ourexampleinthissection —theAirlineFleetAssignmentProblem—alsoreliesonhigher-dimensional sets and on slices through these sets, as well as indexed collection of sets. Multi-dimensionalsetscanbeviewedashavingmembersthatarepairs,triples, orhigher-order“tuples”ofelements,inwhichcaseslicesaresubsetsinwhich certaincomponentsofthetupleshaveprescribedvalues. AmodelfortheFleet AssignmentProblemappearsinTables1.10and1.11. Themodelbeginswithdeclarationsofthreesimplesets: FLEETSofairplanes, CITIESservedbytheairplanes,anddiscreteTIMESatwhichtheairplanestake off or land. The TIMES set is circular, meaning that its members are ordered, withthefirstmemberconsideredtofollowthelastwhencomputingthe“next” member. SetFLEGSdescribesthescheduletobeflown; itconsistsof5-tuples (f,c1,t1,c2,t2)withfinFLEETS,c1,c2inCITIES,andt1,t2inTIMES, suchthatfleetfcanprovideanairplanethatdepartscityc1attimet1andarrives incityc2attimet2. Parametersleg_costandfleet_sizeareindexedover thesesets. The model’s first four sets are fundamental: their values must be provided before AMPL can generate a problem instance. The next three sets to be de- clared — LEGS, SERV_CITIES, and OP_TIMES — are all derived from the fundamentalsets. LEGSisthesetofallquadruples(c1,t1,c2,t2)suchthat (f,c1,t1,c2,t2) appears in set FLEGS for at least one f. SERV_CITIES is an indexed collection of sets, that is, a collection of similar sets that are dis- tinguished from one another by subscripts (in square brackets): for each f in FLEETS,SERV_CITIES[f]isthesetofcitiesservedbyfleetf. OP_TIMESisan- otherindexedcollectionofsets: foreachfinFLEETSandcinSERV_CITIES[f], OP_TIMES[f,c] is the ordered set of times at which an airplane from fleet f may take off or land at city c. The phrase circular by TIMES defines each set OP_TIMES[f,c] to be ordered in the same way as the fundamental set TIMES. Both setof expressions in the declaration for OP_TIMES iterate over slicesofsetFLEGS,thefirstslicebeingthesetofalltriples(t1,c2,t2)such that for a given pair (f,c), (f,c,t1,c2,t2) is in FLEGS, and the second similarlybeingthesetofalltriples(c1,t1,t2)suchthatforagiven(f,c), (f,c1,t1,c,t2)isinFLEGS. AMPLallowsonetospecifyamodelineitheroftwoways: “row-wise”—declaringeachobjectiveorconstraintallatonce,through analgebraicexpression;or “column-wise” — using each variable’s declaration to indicate its con- tributionstovariousconstraintsandobjectives. AMPL’snodeandarcdeclarationsarethemostoftenusedcolumn-wisenota- tion: anodedeclarationsetsupanetworkbalance-of-flowconstrainttowhich variablesdeclaredwitharccancontribute. Sinceairlinefleetassignmenthas AMPLDesignPrinciples&NewDevelopments 9 Table1.10. AirlineFleetAssignmentModel,part1—column-wisespecificationofnetwork flowcostsandbalanceconstraints. set FLEETS; set CITIES; set TIMES circular; set FLEGS within {f in FLEETS, c1 in CITIES, t1 in TIMES, c2 in CITIES, t2 in TIMES: c1 <> c2 and t1 <> t2}; # (f,c1,t1,c2,t2) represents the availability of fleet f # to cover the leg that leaves c1 at t1 and # whose arrival time plus turnaround time at c2 is t2 param leg_cost {FLEGS} >= 0; param fleet_size {FLEETS} >= 0; # leg costs and sizes for each fleet set LEGS = setof {(f,c1,t1,c2,t2) in FLEGS} (c1,t1,c2,t2); # the set of all legs that can be covered by some flight set SERV_CITIES {f in FLEETS} = union {(f,c1,t1,c2,t2) in FLEGS} {c1,c2}; set OP_TIMES {f in FLEETS, c in SERV_CITIES[f]} circular by TIMES = setof {(f,c,t1,c2,t2) in FLEGS} t1 union setof {(f,c1,t1,c,t2) in FLEGS} t2; # for each fleet and city served by that fleet, # the set of active arrival & departure times at that city minimize Total_Cost; node Balance {f in FLEETS, c in SERV_CITIES[f], OP_TIMES[f,c]}; # for each fleet and city served by that fleet, # a node for each possible time arc Fly {(f,c1,t1,c2,t2) in FLEGS} >= 0 <= 1 from Balance[f,c1,t1] to Balance[f,c2,t2] obj Total_Cost leg_cost[f,c1,t1,c2,t2]; # arcs for fleet/flight assignments arc Sit {f in FLEETS, c in SERV_CITIES[f], t in OP_TIMES[f,c]} >= 0 from Balance[f,c,t] to Balance[f,c,next(t)]; # arcs for planes on the ground 10 Table1.11. AirlineFleetAssignmentModel,part2—row-wisespecificationofflightcoverage andfleetsizelimitations. subject to Service {(c1,t1,c2,t2) in LEGS}: sum {(f,c1,t1,c2,t2) in FLEGS} Fly[f,c1,t1,c2,t2] = 1; # each leg must be served by some fleet subject to Capacity {f in FLEETS}: sum {(f,c1,t1,c2,t2) in FLEGS: ord(t2,TIMES) < ord(t1,TIMES)} Fly[f,c1,t1,c2,t2] + sum {c in SERV_CITIES[f]} Sit[f,c,last(OP_TIMES[f,c])] <= fleet_size[f]; # number of planes used is the number in the air # at day’s end (arriving "earlier" than they leave) # plus the number on the ground in each city at day’s end theformofanetworkflowproblemplus“side”constraints,itisconvenientto useamixtureofrow-wiseandcolumn-wisespecifications. Table1.10showsthe objective,Total_Cost,andtheBalanceconstraintsexpressedcolumn-wise; this part of the model sets up a separate network flow problem for each fleet. Table1.11showsthesideconstraintsexpressedrow-wise. TheCapacitycon- straintsrestrictthenumberofairplanesineachfleetnetwork,andtheService constraintsinsurethatexactlyonefleetisassignedtoeachflightintheschedule. Slicenotationsagainappear,thistimeinsummationsintheseconstraints. 4 Iterative Schemes Many applications require solving sequences of problems. AMPL has var- ious facilities that are useful in such applications. The following subsections discuss flow of control expressions and commands, named subproblems, and debuggingfacilities. 4.1 Flow of Control AMPL offers two sorts of conditional computations: if-then-else expres- sions and flow-of-control commands. The former are occasionally useful in declarations, such as the following from a model in our first paper on AMPL [11]: param minv ’minimum inventory’ {p in prd, t in time} = dem[p,t+1] * (if pro[p,t+1] then pir else rir);