MthSc 440, H440, 640 – Linear Programminginstructor: Pietro BelottiMartin Hall, O-321phone: (864) 656 6765office hrs: Tue/Thu, 3pm – 5pm (or by appt.)email: [email protected] page:http://myweb.clemson.edu/˜pbelottExcerpt from the syllabusHomework: 35% (one every two weeks?)Midterm: 25% (beginning of October)Final exam: 40%Learning and exercising material:◮Textbook: Vaˇsek Chv´atal, Linear Programming, Wiley.◮Modeling languages: they are great for modeling any typeof optimization problem◮they are similar, and each has its own pros/cons. All havelimited version available to students.AMPL: preferred. No Graphical User Interface (GUI), but I know itbetter (read: I can help) – www.ampl.comMosel: very nice GUI – google “xpress mosel”GAMS: Has version with even nicer GUI (Aimms) –www.gams.com, www.aimms.comLecture plan◮Formulations, relaxations, lower/upper bounds◮Linear Programming models◮The simplex method◮Duality theory◮Sensitivity analysis◮The revised simplex method◮Network flow modelsOptimization models◮are used to find the best configuration of processes,systems, products, etc.◮rely on a theory developed mostly in the past 50 years◮applied in an industrial, financial, military context, yield abetter use of budget/resources or a higher revenueSuccess storiesSource: http://www.informs.com(see also http://www.ScienceOfBetter.org)yr company result86 Eletrobras (hydroelectric energy) 43M$ saved90 Taco Bell (human resources) 7.6M$ saved92 Harris semicond. prod. planning 50% → 95% orders “on time”95 GM – Car Rental +50M$96 HP printers — re-designed prod. 2x production99 IBM — supply chain 750M$ saved00 Syngenta — corn production 5M$ savedAn example◮You work at a company that sells food in tin cans, and arecharged with designing the next generation can, which is acylinder made of tin◮The can must contain V = 20 cu.in. (11 fl.oz., 33 cl)◮Cut and solder tin foil to produce cans◮Tin (foil) is expensive, use as little as possible⇒ Design a cylinder with volume V using as little tin (i.e.,total area) as possible.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πr2Rewrite the quantity of tin as Q(r) = 2πr2+ 2πrVπr2, orQ(r) = 2πr2+2Vr⇒ Find the minimum of Q(r)!Minimize the quantity of tin0 1 2 3 4 5 6050100150200250Q(r)[in2]r [in]minimumr = 1.471 in h =Vπ(1.471)2= 2.942 inYour first Optimization modelVariables r: radius o f the can’s baseh: height of the canObjective 2πrh + 2πr2(minimize)Constraints πr2h = Vh > 0r > 0Optimization Models, in general, have:Variables: Height and radius, number of trucks, . . . Theunknown (and desired) part of the problem (one thing yourboss cares about).Constraints: Physical, explicit (V = 20in3), imposed by law,budget limits . . . They define all and only values of thevariables that give possible solutions.Objective function: what the boss really cares about.Quantity of tin, total cost of trucks, total estimatedrevenue, . . . a function of thevariablesThe general optimization problemConsider a vector x ∈ Rnof variables.An optimization problem can be expressed as:P : minimize f0(x)subject to f1(x) ≤ b1f2(x) ≤ b2...fm(x) ≤ bmFeasible solutions, local and global optimaDefine F = {x ∈ Rn: f1(x) ≤ b1, f2(x) ≤ b2, . . . , fm(x) ≤ bm}, thatis, F is thefeasible set of an optimization problem.All points x ∈ F are calledfeasible solutions.A vector xl∈ Rnis alocal optimum if◮xl∈ F◮there is a neighbourhood1N of xlwith no better point than xl:f0(x) ≥ f0(xl) ∀x ∈ N ∩ FA vector xg∈ Rnis a global optimum if◮xg∈ F◮there is no x ∈ F better than xg, i.e.,f0(x) ≥ f0(xg) ∀x ∈ F1A neighbourhood of xlcan be defined as N = {x : ||x − xl||2≤ ǫ} for some ǫ.Local optima, global optimaLocal OptimaGlobal OptimumRelaxation of an Optimization problemConsider an optimization problemP : min f0(x)s.t. f1(x) ≤ b1f2(x) ≤ b2...fm(x) ≤ bm,Let us denote F the set of points x that satisfy all constraints:F = {x ∈ Rn: f1(x) ≤ b1,f2(x) ≤ b2,...fm(x) ≤ bm}So we can denote P : min{f0(x) : x ∈ F} for short.Relaxation of an Optimization problemConsider a problem P : min{f0(x) : x ∈ F}.A problem P′: min{f′0(x) : x ∈ F′} is arelaxation of P if:◮F′⊇ F◮f′0(x) ≤ f0(x) for all x ∈ F.2If P′is a relaxation of a problem P, then the global optimum ofP′is≤ the global optimum of P:min{f0(x) : x ∈ F′} ≤ min{f0(x) : x ∈ F}2We don’t care what f′0(x) is outside of F.Examples◮min{f (x) : −1 ≤ x ≤ 1} is a relaxation of min{f(x) : x = 0}◮min{f (x) : −1 ≤ x ≤ 1} is a r. of min{f (x) : 0 ≤ x ≤ 1}◮min{f (x) : −1 ≤ x ≤ 1} is not a r. of min{f (x) : −2 ≤ x ≤ 1}◮min{f (x) : g(x) ≤ b} is a r. of min{f (x) : g(x) ≤ b − 1}◮min{f (x) − 1 : g(x) ≤ b} is a r. of min{f (x) : g(x) ≤ b}Restriction of an optimization problemConsider again a problemP : min{f0(x) : f1(x) ≤ b1, f2(x) ≤ b1, . . . , fm(x) ≤ bm}, orP : min{f0(x) : x ∈ F} for short.◮deleting a constraint from P provides a relaxation of P.◮adding a constraint fm+1(x) ≤ bm+1to a problem Pprovides arestriction of P, i.e., the opposite:F′′= {x ∈ Rn: f1(x) ≤ b1,f2(x) ≤ b2,. . . ,fm(x) ≤ bm,fm+1(x) ≤ bm+1} ⊆ Fand thereforemin{f0(x) : x ∈ F′′} ≥ min{f0(x) : x ∈ F}Lower and upper boundsConsider an optimization problem P : min{f0(x) : x ∈ F}:◮for any feasible solution x ∈ F, the corresponding objectivefunction value f0(x) is anupper bound.◮the most interesting upper bounds are local optima.◮a lower bound of P is instead a value z such thatz ≤ min{f0(x) : x ∈ F}.Upper vs. Lower boundsSituation #1:You: “We found a solution that will only cost 372,000 $.”Boss: “Ok, that sounds good.”Situation #2:You: “We found a solution that will only cost 372,000 $.”Boss: “That’s too much, find something better.”. . .You:“We found another solution that costs 354,000 $.”Boss: “Can’t you do better than that?”You: “I can try again, but here’s the proof that we can’t gobelow351,500.”Boss: “Ok then, that’s a good solution.”What relaxations are for◮If P′is a relaxation of a problem P, then the globaloptimum of P′is≤ the global optimum of P.◮Hence, any relaxation P′of P provides a lower bound on P.⇒ If a problem P is difficult but a relaxation P′of P is easier tosolve than P