Exercise 1 PDF

Preview

Summary

exercise 1...

Description

Integer Programming: Formative Set 1 1. Suppose that x ∈ {0, 1}3 . Which conditions are expressed by the following constraints? (a) x1 + x2 ≤ 1 and x1 ≤ x2 ; (b) x1 + x2 ≤ 1 and x1 + x2 ≥ 1; (c) x1 ≤ x2 and x2 + x3 ≤ 1; (d) x1 ≤ 5000x2 . (Hint: The right side can be simplified.) 2. Suppose that you are interested in choosing a set of investments from {1, ..., 7} using binary variables. Model the following constraints: (a) you cannot invest in all of them; (b) you must choose at least one of them; (c) investment 1 cannot be chosen if investment 3 is chosen; (d) investment 4 can be chosen only if investment 2 is also chosen; (e) you must choose either both investments 1 and 5 or neither; (f) you must choose at least one of the investments 1,2,3, or at least two from the investments 2,4,5,6. 3. You must determine the best selection of 5 out of 10 possible sites for oil drilling. Label the sites s1 , s2 , . . . , s10 and let the expected profits be p1 , p2 , . . . , p10 . Regional development restrictions are as follows: (a) if s2 is selected, then so also must be s3 ; (b) selecting s1 or s7 excludes s8 ; (c) if s3 or s4 are chosen then s5 shouldn’t be selected. Formulate an integer program for this task. 4. Five projects are being evaluated for a possible investment over a 3-year planning horizon. The expected returns and the associated yearly expenditures are given below. The government requires that project 5 be selected if either project 1 or project 3 is selected. Formulate this as a binary integer program. Project 1 2 3 4 5 Availale funds (million £)

Expenditures (million £)/yr year 1 year 2 year 3 5 1 8 4 7 10 3 9 2 7 4 1 8 6 10 25 25 25

1

Returns (million £) 20 40 20 15 30

5. Solve the following 0-1 knapsack problem by dynamic programming: max 7x1 + 9x2 + 3x3 s.t. x1 + 3x2 + 2x3 ≤ 5 x1 , x2 , x3 ∈ {0, 1}

6. Solve the 0-1 knapsack problem by dynamic programming for each λ ∈ {3, 4, 5}: max 5x1 + 3x2 + 7x3 s.t. 2x1 + x2 + 4x3 ≤ λ x1 , x2 , x3 ∈ {0, 1}

7. Let r ≥ 1 and λ ≥ 0 be integer. Consider the following problem: Pr cj xj (Pr (λ)) fr (λ) = max Pj=1 r s.t. j=1 aj xj ≤ λ x ∈ {0, 1}r where all the aj are nonnegative. If λ < ar , show that fr (λ) = fr−1 (λ). 8. Consider the following 0-1 knapsack problem: max 10x1 + 7x2 + 25x3 + 24x4 s.t. 2x1 + x2 + 6x3 + 5x4 ≤ 7 x ∈ {0, 1}4 Solving this 0-1 knapsack problem by dynamic programming yields the table λ 0 1 2 3 4 5 6 7

f1 0 0 10 10 10 10 10 10

f2 0 7 10 17 17 17 17 17

f3 0 7 10 17 17 17 25 32

f4 p1 0 0 7 0 10 1 17 1 17 1 24 1 31 1 34 1

p2 0 1 0 1 1 1 1 1

p3 0 0 0 0 0 0 1 1

p4 0 0 0 0 0 1 1 1

By using the value of the indicators pr (λ) given above, find (a) the optimal solution of the integer program with (r, λ) = (4, 6); (b) the optimal solution of the integer program with (r, λ) = (3, 6); (c) the optimal solution of the integer program with (r, λ) = (2, 5).

2

9. Solve the following problem by dynamic programming max 11x1 + 6x2 + 12x3 s.t. 2x1 + x2 + 2x3 ≤ 4 x1 , x2 , x3 ∈ Z+ Is the optimal solution to this integer program unique? 10. Consider the quadratic 0-1 knapsack problem ( n ) j−1 n X n X X X cj xj + cij xi xj | min aj xj ≥ b, x ∈ {0, 1}n . j=1

j=2 i=1

j=1

By introducing binary variables yij equal to xi xj , reformulate the problem as a linear integer program. 11*. Show that any integer program of the form min{cT x | Ax = b, x ≤ u, x ∈ Zn+ } where u ∈ Rn+ is a given vector, can be converted into a 0-1 knapsack problem. 12*. Suppose that you have 7 full wine bottles, 7 half-full, and 7 empty. You would like to divide the 21 bottles among three individuals so that each receives exactly 7. Additionally, each must receive the same quantity of wine. How can the above conditions be expressed as integer programming constraints?

3...