Deck 12: Integer Programming

Question 1

Consider the following activity-on-arc project network,where the 12 arcs (arrows)represent the 12 activities (tasks)that must be performed to complete the project and the network displays the order in which the activities need to be performed.The number next to each arc (arrow)is the time required for the corresponding activity.Consider the problem of finding the longest path (the largest total time)through this network from start (node 1)to finish (node 9),since the longest path is the critical path.Formulate a BIP model for this problem.

Answer 1

Let The time required for activity (i,j)will become the coefficient of x_ij in the objective function being maximized in the BIP model.The model also will need some functional constraints to ensure that a feasible solution defines one continuous path from node 1 to node 9.In particular,the critical path needs to include exactly one activity leading out of node 1 and exactly one activity leading into node 9.Similarly,for each of the other nodes,the critical path needs to include either zero or one activity leading into that node and the same number of activities leading out of that node.These observations lead to the following BIP model.Maximize Z = 5 x₁₂ + 3 x₁₃ + 4 x₂₄ + 2 x₂₅ + 3 x₃₅ + x₄₆ + 4 x₄₇ + 6 x₅₇ + 2 x₅₈ + 5 x₆₉ + 4 x₇₉ + 7 x₈₉,subject to x₁₂ + x₁₃ = 1 x₁₂ -x₂₄- x₂₅ = 0 x₁₃ - x₃₅ = 0 x₂₄ - x₄₆ - x₄₇ = 0 x₂₅ + x₃₅ - x₅₇ - x₅₈ = 0 x₄₆ - x₆₉ = 0 x₄₇ + x₅₇ - x₇₉ = 0 x₅₈ - x₈₉ = 0 x₆₉ + x₇₉ + x₈₉ = 1 and x_ij is binary,for each activity (i,j).

Question 2

The Washington State legislature is trying to decide on locations at which to base search-and-rescue teams.The teams are expensive,so the legislature would like as few as possible while still providing the desired level of service.In particular,since response time is critical,the legislature would like every county to either have a team located in that county or in an adjacent county.Formulate and solve a BIP model in a spreadsheet to determine where the teams should be located.

Answer 2

This is a set covering problem.The decisions to be made are whether to locate a team in each county.The requirement for each county is that there be a team nearby,where nearby is defined as in that county or an adjacent county.The data for this problem are the coverage data.In particular,in the row representing each county,there is a 1 in every column that would satisfy the coverage of the row's county if there were a team there.For example,Clallum county would be covered if there is a team in either Clallum or Jefferson county. The decisions to be made in this problem are whether or not to place a team in each county.Thus,a binary variable is defined for each county in the changing cells Team? (D44:AN44).The values in Team? (D44:AN44)will eventually be determined by Solver.For now,arbitrary values are entered.The goal is to minimize the total number of teams.Thus,the objective cell should calculate this total: Total Teams = SUM(Teams?).This formula is entered into TotalTeams (AQ44). The functional constraints in this problem are that each county must have at least one team nearby.Given Teams? (D44:AN44),we calculate the number of teams nearby in TeamsNearby(AO5:AO41).For Clallum county,this will be =SUMPRODUCT(D5:AN5,Team?).Using a range name or an absolute reference for Team?,this formula can be copied into cells AO6:AO41 to calculate the number of teams nearby for the other counties.The TeamsNearby (AO5:AO41)must be >= 1,as indicated by the >= in AP5:AP41. The Solver information and solved spreadsheet are shown below. Thus,they should locate a team in Jefferson,King,Lewis,Clark,Okanagan,Blanton,Spokane,and Whitman counties,for a total of 8 teams.(There are multiple optimal solutions for this problem.)

Question 3

Consider the following discrete nonlinear programming problem.Maximize Z = ,subject to x₁ + x₂ ≤ 0.75 and each variable is restricted to the values: .
(a)Reformulate this problem as a pure binary integer linear programming problem.
(b)Use the following outline in designing the main features of a branch-and-bound algorithm for solving this problem (and similar problems)directly without reformulation.(1)Specify the tightest possible nonlinear programming relaxation that has only continuous variables,and so can be solved efficiently by nonlinear programming techniques.(2)Specify the fathoming tests.(3)Specify a branching procedure that involves specifying two ranges of values for a single variable.

Answer 3

(a)We define the binary variable y_ij as follows.Let for i = 1,2 and j = 1,2,3,4.For each i and j,calculate the contribution to the objective function associated with having y_ij = 1 because x_i = 1/(j+1),as shown in the following table. These numbers in the second and third columns then become the coefficients of the respective y_ij in the objective function of the reformulated problem.The reformulated problem also requires some functional constraints on the y_ij.In particular,for each i = 1,2,exactly one of the y_i1,y_i2,y_i3,and y_i4 variables must be 1.Furthermore,because of the x₁ + x₂ ≤ 0.75 constraint,certain pairs of y_ij variables (y₁₁ and y₂₁,y₁₁ and y₂₂,y₁₂ and y₂₁)cannot both be 1.These observations lead to the following pure binary integer linear programming formulation.Maximize Z = (3/4)y₁₁ + (5/9)y₁₂ + (7/16)y₁₂ + (9/25)y₁₄ + (3/4)y₁₁ + (2/3)y₂₂ + (9/16)y₂₃ + (12/25)y₂₄,subject to y₁₁ + y₁₂ + y₁₂ + y₁₄ $\le$ 1 y₂₁ + y₂₂ + y₂₃ + y₂₄ $\le$ 1 y₁₁ + y₂₁ $\le$ 1 y₁₁ + y₂₂ $\le$ 1 y₁₂ + y₂₁ $\le$ 1 and y_ij is binary,for i = 1,2 and j = 1,2,3,4.
(b)(i)Use the following relaxation: Maximize Z = 2x₁ - 3 + 3x₂ - 3 ,subject to x₁ + x₂ $\le$ 3/4 and 1/5 $\le$ x₁ $\le$ 1/2 ,1/5 $\le$ x₂ $\le$ 1/2.
(ii)The fathoming tests are the same as those stated in Sec.12.6 of the textbook.A subproblem is fathomed if Test 1: The upper bound on Z for the subproblem is ≤ Z for the incumbent,or Test 2: Its relaxation has no feasible solutions,or Test 3: The optimal solution for its relaxation satisfies the original constraint that each variable is restricted to the values: .
(iii)To branch from a value for x_j^* where 1/(m+1)< x_j^* < 1/m for some m = 2,3,4,we use the following two alternative constraints for the two new subproblems: x_j $\le$ 1/(m+1)or x_j $\ge$ 1/m.

Question 4

Consider a small company that produces a single product in two plants and serves customers in five different regions.The company has been using a make-to-order policy of producing the product only in the quantities needed to fill the orders that have come in from the various regions.However,because of the problems caused by the sporadic production schedule,management has decided to smooth out the production rate and ship the product to one or more storage warehouses,which then will use inventory to fill the incoming regional orders.Management now needs to decide where to locate the company's new warehouse(s).There are three locations under consideration.For each location,there is a fixed monthly cost associated with leasing and operating the warehouse there.Furthermore,each potential warehouse location has a maximum capacity for monthly shipments restricted primarily by the number of trucking docks at the site.The product costs $400 to produce at plant 1 and $300 to produce at plant 2.The shipping cost from each plant to each potential warehouse location is shown in the first table below.The fixed leasing and operating cost (if open),the shipping costs,and the capacity (maximum monthly shipments)of each potential warehouse location are shown in the second table below.The monthly demand in each of the customer regions is expected to be 200,225,100,150,and 175 units,respectively.Formulate and solve a BIP model in a spreadsheet to determine which warehouse(s)should be used and how the product should be distributed from plant to warehouse(s)to customer. Shipping Costs and Capacity of the Plants Fixed Cost,Shipping Costs,and Capacity of the Warehouses

Question 5

Decora Accessories manufactures a variety of bathroom accessories,including decorative towel rods and shower curtain rods.Each of the accessories includes a rod made out of stainless steel.However,many different lengths are needed: 12",18",24",40",and 60".Decora purchases 60" rods from an outside supplier and then cuts the rods as needed for their products.Each 60" rod can be used to make a number of smaller rods.For example,a 60" rod could be used to make a 40" and an 18" rod (with 2" of waste),or 5 12" rods (with no waste).For the next production period,Decora needs 25 12" rods,52 18" rods,45 24" rods,30 40" rods,and 12 60" rods.What is the fewest number of 60" rods that can be purchased to meet their production needs? (a)Formulate an integer programming model in algebraic form for this problem.(b)Formulate and solve an integer programming model in a spreadsheet for this problem.

Question 6

A company is planning its capital budget over the next several years.There are eight potential projects under consideration.A calculation has been made of the expected net present value of each project,along with the cash outflow that would be required over the next four years.These data,along with the cash that is available each year,are shown in the table below.(If any of the cash available in a given year is not fully used for these projects,it will be used in other ways and so will not be available in later years.)There also are the following special constraints: (a)at least one of project 1,2,or 3 must be done,(b)project 6 and 7 cannot both be done,and (c)project 5 can only be done if project 6 is done.The objective is to determine which projects should be pursued to maximize the total expected net present value. (a)Formulate a BIP model in algebraic form for this problem.(b)Formulate and solve a BIP model in a spreadsheet for this problem.