MA 325, Part II HomeworkOptimization February 10, 2017 1. WolfPop Records is releasing a new single. They have a small pool of tracks to choose from, and first they have to figure out which ones should be selected for the album. The songs and their main attributes are summarized in the table below. Song no. Length Rating (1-5 stars) Ballad? Cover song? 1 2 3 4 5 6 7 8 2:38 3:40 3:22 2:50 4:00 3:30 4:05 2:15 5 5 4 4 3 3 2 1 NO YES NO NO YES NO YES NO NO YES YES NO YES NO NO NO For example, song number 7 is four minutes and five seconds long, it's a mediocre song (rated 2 stars), it is a ballad, but it is not a cover song. They want to select three or four songs in such a way that not all of them are ballads, and at most one of the selected songs should be a cover song. The total length of the tracks should be between 9 and 15 minutes. The publisher's policy requires the average rating of the compilation to be at least 3.8. Finally, it is the singer's request that if song 1 is included in the compilation, then song 6 must also be included, too, but song 4 must not. Formulate an integer linear program to find a compilation that satisfies all the constraints. (You need not find a compilation.) 2. The puzzle below was once touted as the \"world's hardest Sudoku\".1 Formulate an integer linear program to solve it. (Hint: use binary variables, not integer-valued variables ranging from 1 through 9. You will need many variables!) 8 3 6 7 5 9 2 7 4 5 7 1 3 6 8 1 1 8 5 9 4 Extra credit: Solve it by hand and report the solution time. (No cheating!) Then solve it with Matlab's intlinprog function. (Don't try this with Excel.) Show the code, report the solution time. 3. It's time to move! You have n items to pack, of sizes a1 , . . . , an ; you bought m boxes, which can accommodate stuff of total size s1 , . . . , sm , respectively, and you rented a truck with capacity C. Formulate an integer linear program (with binary variables) to decide whether the move is possible with these resources. 1 http://www.telegraph.co.uk/news/science/science-news/9359579/Worlds-hardest-sudoku-can-you-crack-it.html Page 1 of 3 MA 325, Part II HomeworkOptimization February 10, 2017 4. An electronics manufacturing company has a contract to deliver 20000 gadgets within the next four weeks. Although the production cost of a gadget is only $6, the client is willing to pay $20 for each gadget delivered by the end of the first week, $18 for those delivered by the end of the second week, $16 by the third week, and $14 by the fourth week. Since each worker can assemble only 60 gadgets per week, the company cannot meet the order with its present labor force of 40 workers; it must hire and train temporary help. Any of the experienced workers can be taken off the assembly line to train a class of up to three temporary workers: after one week of instruction, each of the trainees (as well as the teacher) can either proceed to the assembly line or instruct new classes. The company can hire temporary workers any time, but cannot fire non-temporary workers. All the workers (temporary or not) must be kept on payroll till the end of the fourth week. The weekly wage is $450 per a trained worker, temporary or not, and whether they have anything to do or not. The weekly wage of each trainee is $200. The company wants to find a way to satisfy the demand specified in the contract, and achieve the highest possible profit by the end of the next four weeks. Formulate this problem as a linear program (no integer variables). You can ignore the fact that the number of workers must be integers. You are allowed to skip algebraic simplifications (if any arise). 5. The Green Wolf Co. operates a reclamation center that collects four types of solid waste materials and treats them so that they can be amalgamated into a salable product. (Treating and amalgamating are two separate processes.) Three different grades of this product can be made, depending upon the mix of the ingredients (waste materials) used. Quality standards specify the minimum or maximum amount allowed for the proportion of some of the ingredients in each product. These specifications are given in the first table below, along with the cost of amalgamation and the selling price for each grade. Grade Specification Amalgamation cost ($/lb) Selling price ($/lb) A Material 1: At most 30% of total Material 4: Exactly 20% of total 3.00 8.50 B Material 1: At most 50% of total Material 2: At least 10% of total Material 4: Exactly 10% of total 2.50 7.00 C Material 1: At most 70% of total 2.00 5.50 The reclamation center collects its solid waste materials from regular sources, so it is normally able to maintain a steady rate for treating them. The table below gives the quantities available for collection and treatment each week, as well as the cost of treatment, for each type of material. Green Wolf runs entirely on charitable contributions and grants raised last year, amounting to $30,000 per week, to be used exclusively to cover the entire treatment cost for the solid waste materials. To show how efficient they are, the company wants to spend all of this money, dividing it among the materials in such a way that at least half of the amount available of each material is actually collected and treated. These additional restrictions are also listed in our second table: Material Availability (lb/week) Treatment cost ($/lb) 1 2 3 4 3 000 2 000 4 000 1 000 3.00 6.00 4.00 5.00 Additional restrictions 1. For each material, at least half of the available amount should be treated every week. 2. Available funds must be spent. Within the restrictions specified above, management wants to determine the amount of each product grade to produce and the exact mix of materials to be used for each grade. The objective is to maximize the net weekly profit (total sales income minus total amalgamation cost), exclusive of the fixed treatment cost of $30,000 per week that is being covered by gifts and grants. Formulate this problem as a linear program. Page 2 of 3 MA 325, Part II HomeworkOptimization February 10, 2017 6. Consider the following LP: min s.t. 3x1 7x2 x1 + x2 2 x1 4 x1 + 4x2 12 2x1 + x2 12 x1 , x2 0. (a) Sketch the feasible region. (Watch out for signs and subscripts.) (b) There is exactly one redundant constraint in the above problem. Which one? (c) Demonstrate that the redundant constraint can be written as a linear combination of the remaining constraints (and possibly the trivial inequality 0 1) using only nonnegative coefficients. (Hint: This will be difficult to guess from the algebraic form alone, but your picture should be of great help.) (d) Name the theorem that guarantees that redundant constraints are always linear combinations of the others. (e) Use the Excel solver or Matlab's linprog function to compute the optimal solution. (f) Convert the problem to standard form. Write down its dual. (g) Use the graphical approach we have seen in class to read off the optimal (primal) solution. 7. A certain minimization integer program has two integer variables x and y (among other decision variables that are not required to be integers). Suppose that at a certain point during the solution of the problem by the branch-and-bound method, the branch-and-bound tree has exactly 6 leaves (A through F ), and that the LP relaxations they represent have the following optimal solutions (\"val\" denotes the optimal objective function value, the values of the non-integer variables are not shown): (A) val = 26, x = 2, y = 0 (D) val = 20, x = 2, y = 3.4 (B) val = 10, x = 3, y = 4.5 (E) val = 30, x = 6, y = 3 (C) val = 26, x = 0.5, y = 3 (F) infeasible (a) Which leaves can be pruned? Is any further branching needed? Have we found the optimal solution already? Explain. (b) Answer the same questions assuming that leaf (A) is not in the tree. (c) Answer the same questions assuming that leaves (B) and (D) are not in the tree (but the other four are). 8. Extra credit. (Reverse-engineering a linear program from its solution.) An absent-minded professor has solved a linear program in standard form, and obtained the optimal solution x . However, she completely forgot what the cost vector c was! Fortunately, she still remembers A and b in the constraints Ax = b, x 0. Formulate a linear program to find a cost vector c for which the vector x is indeed optimal. (This problem has more serious applications than shown in this exercise, for example, in quantifying decision makers' unknown utilities and preferences based on their perception of what appears to be an optimal solution to the problem that is being modeled. It is often called inverse optimization.) Due on February 21, before 4pm. Turn in the physical copy of your work. You may find me in my office (SAS 3222) any time to turn it in, or slide your (stapled!) paper under the door if I am not there. No email submissions, and absolutely no late submission or extensions, please. Page 3 of 3 \f\f\f\f