MthSc-440/640: Linear ProgrammingLecture 13Pietro BelottiDept. of Mathematical SciencesClemson UniversityOctober 7, 2010Additional reading: Chapter 1, sections 1.1 and 1.2:http://www.4er.org/CourseNotes/Book%20A/A-I.pdfAMPL◮a modeling language for optimization problems⇒ an interface between problems and solvers◮easy, intuitive syntax◮it’s interpreted1⇒ that means errors are spotted as soon as they are executed.◮can be used from a command line interface or◮by editing command files and submitting them1As opposed tocompiled.ExamplerhIf we knew radiusr and height h,◮the volume would be πr2h◮qty of tin would be 2πr2+ 2πrhπr2h must be V = 20in3⇒ h =Vπr2Variables r: radius of the can’s baseh: height of the canObjective 2πrh + 2πr2(minimize)Constraints πr2h = Vh > 0r > 0The tin can problemvar r > 0;var h > 0;minimize tin_foil: 2*3.14*rˆ2 + 2*3.14*r*h;vol_fixed: 3.14*rˆ2*h = 20;AMPL: VariablesThe command var specifies a variable of the problem, itsbounds, its type, and (possibly) an initial value.var x1 >= 0 <= 4;var numtrucks >= 3 integer default 5;var buyObj1 binary;AMPL: ConstraintsConstraints are preceded by a name and a “:”myconstr1: x1 + 3*x2 + x3 <= 4;c2: numtrucks >= ntr_AZ + ntr_NY + ntr_PA;at_most_1: buyObj1 + buyObj2 + buyObj3 <= 1;AMPL: Objective func tionPreceded by either minimize or maximize, name of theobjective, and “:”minimize xpense: 10*numtrucks + 3*numcars;minimize myfun: x1*x2 - 2*x3;maximize distance: x1 + 2*cos(x3);Caveats◮the semicolon: all commands must end with one2;◮comments: # this won’t be interpreted◮to solve a problem, choose a solver:◮CPLEX: for linear and integer programming◮MINOS: for nonlinear programmingwith the command option solver cplex;◮guess what the reset; command does?2AMPL gives seemingly unrelated errors when it doesn’t find one.ParametersParameters can be defined with param.They are aninput to the problem.param pi = 3.14159265358979323846;param Vol = 20; # volume of each tin canparam price_per_gallon; # Can set it later!Tin can problemparam pi = 3.14159265358979323846;param Vol = 20; # volume of each tin canvar radius >= 0.0001 default 1;var height >= 0.0001 default 1;minimize tin_foil:2*pi*radiusˆ2 + 2*pi*radius*height;vol_fixed: pi*radiusˆ2*height = Vol;option solver minos; # for nonlinear problemssolve;Sets◮remember the Knapsack problem?var x1 binary;var x2 binary;var x3 binary;var x4 binary;var x5 binary;var x6 binary;var x7 binary;var x8 binary;var x9 binary;param w1 = 3;param w2 = 4;◮Flea markets in Rome have more than 9 objects...Setsset S = 1 2 3 4 5 6 7 8 9;var x {S} binary; # a vector of variablesparam w {S}; # a vector of parametersparam p {S};# even nicer...set S = 1..9;var x {S} binary;param w {S};param p {S};# not happy yet?param n = 9;set S = 1..n;var x {S} binary;param w {S};param p {S};Sets and in dicesSets can be referred to with indices.Useful to specify an element of a vector parameter/variable.Example:param lb {S};param ub {S};var x {i in S} >= lb[i] <= ub[i];set T = 1..100;param firstPar {T};param secondPar {i in T} = firstPar[i] / 2 + 3;Operations with setsIn Linear and Integer Programming, we’ll see very often thenotationnXi=1aixi. How can that be expressed in AMPL?param n;set S = 1..n;param a {S};var x {S};minimize linFun: sum {i in S} a [i]*x[i];Model and dat a◮In AMPL, model and data can be kept separated◮Useful when you have several instances of the sameproblem (e.g. one flea market every day)◮Data section starts with command data;◮In data sections, we assign values to parameters;Example: knapsackparam n;set S = 1..n;var x {S} binary;param C;param w {S};param p {S};minimize tot_weight: sum {i in S} w[i]*x[i];pay_ticket: sum {i in S} p[i]*x[i] >= C;Example: knapsack (cont’d)data;param n := 9;param C := 70;param w {S} :=1 3 2 23 2 4 45 5 6 47 3 8 19 4;param p {S} :=1 30 2 243 11 4 355 29 6 87 31 8 189 12;Example: Transportation problem◮A large manufacturing company produces liquid nytrogeninfive plants spread out in East Pennsylvania◮Each plant has a monthly production capacityPlant i1 2 3 4 5Capacity pi120 95 150 120 140◮It has seven retailers in the same area◮Each retailer has a monthly demand to be satisfiedRetailer j1 2 3 4 5 6 7Demand dj55 72 80 110 85 30 78◮transportation between any plant i and any retailer j has acost of cijdollars per volume unit of nytrogen◮cijis constant and depends on the distance between i and j⇒ find how much nitrogen to be transported from each plantto each retailer◮. . . while minimizing the total transportation costTransportation modelVariables: qty from plant i toretailer j: xij(non-negative)Constraints:1. capacity:P7j=1xij≤ pi∀i2. demand:P5i=1xij≥ dj∀jObjective function: totaltransportation cost,P5i=1P7j=1cijxij123451234567Variables with multiple indices in AMPLVariable and parameter vectors can be defined with sets:set S;param c {S};var x {S} binary;var y {i in S} <= c[i] >= c[i]/2;Variables and parameters can be de fined onmultiple index sets:set Cities;set Months = 1..12;param maxBicycles {Cities};var nBikes {i in Cities} integer <= maxBicycles [i];var y {Cities, Months} >= 0 <= 4;var z {i in Cities, j in Cities: i != j} integer;Defining “classes” of constrai nts in AMPLIndex sets are also useful with constraints!Constraints can also be defined over a set of indices:set S;con1 {i in S}: a[i]*x[i] + b[i]*y >= d;set Cities;set Months;param maxYearlyPollution {Cities};param maxMonthlyPollution {Cities, Months};var pollution {i in Cities, m in Months}>= 0 <= maxMonthlyPollution [i,m];con_YR_Pollution {i in Cities}:sum {m in Months} pollution [i,m]<= maxYearlyPollution [i];Back to our trans portation problemparam np;param nr;set P = 1..np;set R = 1..nr;param maxCap {P};param demand {R};param cost {P,R};var x {P,R} >= 0;minimize tcost:sum {i in P, j in R} cost[i,j]*x[i,j];capCon {i in P}: sum {j in R} x [i,j] <= maxCap [i];demCon {j in R}: sum {i in P} x [i,j] >= demand [j];Problem data ( in a separate .dat file)param np = 5;param nr = 7;param maxCap :=1 34 2 223 41 4 19 5 30;param demand :=1 12 2 213 19 4 155 25 6 9 7 12;param cost:1 2 3 4 5 6 7 :=1 3 7 5 2 8 9 12 5 8 3 6 1 5 43 5 4 9 4 5 6 94 4 5 7 8 2 4 65 5 6 7 2 5 6