Introduction to Optimization Problem Set 8

Introduction to Optimization 1. Integer Programming and Scheduling (5 points) Greyhound needs to assign drivers to all of its upcoming trips. Currently, there are three drivers based in Boston, and twelve different trips (listed in the first column of the table below). Greyhound assigns each driver to a particular sequence of trips. The table below shows all the different sequences that are possible. (The numbers represent the order of the trips in each sequence; as an example, sequence 6 consists of first going from Boston to Portland, then from Portland to New Haven and finally from New Haven to Boston). possible sequences Trip 1 Boston-New Haven 1 Boston- Pittsburgh 2 4 5 6 1 1 Boston-Portland New-Haven - Niagara Falls New-Haven - Boston 3 1 3 4 4 450 600 650 3 3 4 550 650 2 4 2 350 3 2 2 Portland - New Haven 5 5 2 Portland-Boston 1 2 5 4 3 4 12 1 3 3 Niagara Falls - Portland 2 11 1 3 3 10 1 2 2 250 9 1 1 2 Pittsburgh-Boston Pittsburgh-Niagara Falls 8 1 1 Niagara Falls - Pittsburgh Cost for each sequence 7 700 5 2 4 4 2 900 900 750 950 Each driver can be assigned to one and only one sequence. The cost of assigning a driver to a particular sequence is in the last row of the table. The objective is to assign each driver to a sequence such that all of the possible trips are taken at least once, and the cost is minimized. Formulate the problem as an integer program. (You do not need to solve it.) (HINT: this problem is a set covering problem). Page 1 of 6 2. Integer Programming and Modeling Nonlinear Costs (5 points) A copying service operates a copy machine. The machine has a capacity of 5000 copies of a page per hour. One hour has been reserved for copying a 12-page article and a 25-page article, to be sold to MBA students. The 12-page article sells for $.50 per article, and up to 300 articles can be sold. The 25-page article sells for $1 per article, and up to 100 copies can be sold. Assume that you get no value for copying only part of an article. The costs of copying each article are: $0.08 per page for the first 50 copies of each page (i.e., 1 to 50 copies of the same page), $0.04 per page for the next 50 copies of each pages (i.e., 51 to 100 copies of the same page), $0.02 per page for remaining copies of each page (i.e., 101 copies of the same page and over.) (For example, the first fifty copies of an article made cost $0.08 per page, and the cost of the 51st copy is $0.04 per page.) Formulate as an integer program the problem of determining how many copies of each article should be made. (You do not need to solve it.) 3. Integer Programming and Arranging (8 points) You have been assigned to arrange the songs on the cassette version of Madonna’s latest album. A cassette tape has two sides (1 and 2). The following table shows the type and length of each song that must be included in the cassette. Song 1 2 3 4 5 6 7 8 Type Ballad Hit Ballad Hit Ballad Hit Ballad and Hit Ballad and Hit Minutes 3 5 4 2 4 3 4 5 The following are the requirements of the tape: 1. The songs on each side of the tape must total between 14 and 16 minutes. 2. Each side must have exactly two ballads. 3. Either song 3 or song 6 must be on side 1 (or both). 4. Exactly one of songs 7 and 8 must be on side 2. 5. If song 1 or song 3 is on side 2, then song 4 or song 8 must be on side 1. 6. If songs 2 and 4 are on side 1, then song 5 must be on side 2. Show how integer programming can be used to determine if there is an arrangement of the songs that satisfy the restrictions. (HINT: Model each part as a constraint or set of constraints.) Do not solve the IP. Page 2 of 6 4. Integer Programming and Modeling Fixed Costs (8 points) MIT Press is considering publishing five textbooks. The maximum number of copies of each textbook that can be sold, the sales price of each textbook, the per unit cost of producing each textbook, and the fixed cost of a production run for each book are given in the table below. Maximum Demand Sales Price ($) Per Unit Cost ($) Fixed Cost ($) Book 1 5,000 50 25 80,000 Book 2 4,000 40 20 50,000 Book 3 3,000 38 15 60,000 Book 4 4,000 32 18 30,000 Book 5 3,000 40 22 40,000 The fixed cost is charged if any books of that type are produced. (So, for example, producing 2,000 copies of Book 1 brings in a revenue of 2,000(50) = $100,000, but costs 80,000 + 25(2,000) = $130,000.) MIT Press can produce at most 10,000 books, and it wishes to maximize profit. a) Model this problem as an integer program. b) Using the attached file ps8.xls and Excel Solver (see instructions below), find the optimal solution to the integer program. What are the optimal solution and the optimal profit? Include a printout of your Excel output. Using Excel Solver to Solve Integer Programs Solving integer programs with Excel Solver is a lot like solving linear programs! Just follow these four easy steps: 1. Set up the problem in Excel Solver as you usually would for solving a linear program. 2. For any variable(s) that you would like to be binary valued (i.e., 0 or 1), select “Add Constraint,” input the variable(s) in question into the left hand side, and select “bin” from the drop-down bar in the middle. 3. For any variable(s) that you would like to be integer (not necessarily binary) valued, select “Add Constraint,” input the variable(s) in question into the left hand side, and select “int” from the drop-down bar in the middle. 4. (Optional, but highly recommended) In the main Solver window, select “Options” and change “Tolerance” from the default of 5% to the much stricter bound of .01%. This will mean it takes Solver a little longer to solve, but it will give you much better solutions. Page 3 of 6 5. Branch and Bound Trees (10 points) Solve the following two problems using Branch and Bound. For each problem, you should draw the associated branch and bound tree. On the drawing, for each node that is considered, write the corresponding optimal LP solution and optimal objective value of the subtree. Clearly indicate the branching criteria for each subtree. (You may use Excel to solve the LPs at each node, but you have to draw the entire tree.) a) max 2 x1 + x2 − x3 + 5 6x1 − x2 − x3 ≤ 5 x2 + 5 x3 ≥ 2 s.t. x1 + x2 + x3 = 2 x1 , x2 , x3 ∈ {0,1} b) max 7 x1 + 3 x 2 s.t. 2 x1 + x 2 ≤ 9 3 x1 + 2 x 2 ≤ 13 x1 , x 2 ≥ 0; x1 , x 2 integer 6. Branch and Bound Steps (6 points) Suppose branch and bound is being applied to a 0-1 integer program in which we are maximizing. By node 11 the first three variables have been fixed. An incumbent has already been found (in another part of the tree) and has value 15. Furthermore, x4 has been chosen to be the next variable to branch on. This situation is illustrated in the following fragment of the branch and bound tree: x1, x2, x3 fixed 11 Page 4 of 6 zLP ≥ 16 x4 = 1 x4 = 0 12 13 Incumbent: z = 15 The LP relaxation solved at node 11 (which has x4 and x5 as free variables) was: max 18 x 4 + ax5 + 10 8 x 4 + 10 x5 ≤ 5 0 ≤ x4 ≤ 1 0 ≤ x5 ≤ 1 (HINT: For the following questions, the LP relaxation essentially becomes a one variable problem that can be solved by inspection.) a) Suppose x4 is set to 1. Does node 12 get fathomed? Why or why not? b) Suppose x4 is set to 0 and parameter a = 12. Does node 13 get fathomed? Why or why not? c) Suppose x4 is set to 0 and parameter a = 8. Does node 13 get fathomed? Why or why not? 7. Branch and Bound Analysis (9 points) Consider the following integer program: max 3 x1 + 3 x 2 + ... + 3 x10 s.t. 3 x1 + 3 x 2 + ... + 3 x10 ≤ 16 x1 , x 2 ,..., x10 ∈ {0,1} For parts a) and b), suppose that we consider the subdivision (node) of the branch and bound tree in which x1 = 1, x2 = 1, x3 = 0, x4 = 1, and x5 = 0, and suppose that the incumbent has a value of 15. a) What is the optimum objective value of the LP associated with this subdivision? Does the node get fathomed? b) Give an example of a node of the Branch and Bound Tree that would get fathomed because of the bound. (It should be a descendent of the node x1 = 1, x2 = 1, x3 = 0, x4 = 1, and x5 = 0.) State why it will be fathomed. c) Explain why no subdivision (node) gets fathomed if at most five variables are fixed (with at least one of them being nonzero), and five variables are yet to be determined. d) Show how to use your insight from parts a) to c) to create an integer program for which the Branch and Bound tree would search at least 2100 nodes. Page 5 of 6 Challenge Problem H (6 points) Suppose you are a senior graduating from MIT, and you are leaving Cambridge for your new job. You have n items of size ai, i = 1, 2, …, n, that need to be moved. You have bought m boxes. Box j has size bj, for j = 1, …, m. Boxes typically can hold more than one item. You have rented a truck that has size Q. This means that the sum of the sizes of the boxes in the truck is at most Q, even if the boxes are not fully loaded. Formulate an integer program in order to decide whether you can fit all of your items into boxes and then fit the boxes into the truck, and so as to minimize the number of boxes that are put on the truck. Page 6 of 6