E4004 2021 Final
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
E4004 2021 Final
Problem 1: (14 points) Given c → Rn , show that the following mathe- matical program
xe(m)Rn(in) cT x subject to 1 ≤ lxlo ≤ 2 (1)
can be cast as a mixed-integer linear program, where lxlo := maxe}x1 }, . . . , }xm }(.
Problem 2: (14 points) We would like to install temporary healthcare facilities in counties in New Mexico so that each county is within at most 10km of a facility. The distances between counties can be found in Table 1. Suppose we would like to build as few facilities as possible. Formulate this problem as an integer program and solve it using python. Take a screenshot of your code. Where should one install the facilities?
|
County |
Catron |
Eddy |
Luna |
Mora |
Taos |
Lea |
|
Catron |
0 |
10 |
40 |
25 |
20 |
10 |
|
Eddy |
10 |
0 |
25 |
20 |
35 |
20 |
|
Luna |
40 |
25 |
0 |
10 |
25 |
5 |
|
Mora |
25 |
20 |
10 |
0 |
35 |
15 |
|
Taos |
20 |
35 |
25 |
35 |
0 |
10 |
|
Lea |
10 |
20 |
5 |
15 |
10 |
0 |
Table 1: Distance between counties in km
Problem 3: (14 points) Imagine that you are helping a friend to move into their new place. Your friend only has one box of 28kg to move their belongings, so you propose to lend your box of 22kg to help your friend. The weight and the value of your friend’s belongings are given in Table 2. Provide an integer programming formulation that maximizes the value of the items packed. Without solving the integer program, is it the case that one of the items will definitely be packed no matter what? Justify your answer.
Item #1 #2 #3 #4 #5 #6 #7 #8
Weight (kg) 10 9 15 3 3 6 11 4
Value ($) 5 2 7 6 8 6 1 6
Table 2: Belongings
Problem 4: (14 points) A gala is being organized for the students of a masters program. To promote exchanges, it is desired that no more than three students from one country sit at the same table, and no more than six from the same continent. Use a maximum flow formulation to determine whether one can find a seating arrangement. There are eight countries with respectively s1 , . . . , s8 students. The first three countries are in Asia, the next three countries are in Europe, and the remaining two are in North America. There are n tables with respectively t1 , . . . , tn seats.
Problem 5: (14 points) Given a list of relative integers such as in Table 3, we would like to the find the greatest consecutive sum of numbers. For example, the second, third and fourth numbers in Table 3 add up to eleven, while the last four numbers add up to ten. Propose a dynamic program- ming approach to solve this problem. How does the computational burden compare with simply computing every possible sum?
10 -15 6 20 -13 9 -16 10 7
Table 3: List of relative numbers
Problem 6: (30 points) Consider the following optimization problem:
inf f (x1 , x2 ) (2)
x 1 ,x2 eR
where f : R2 -● R.
1. Assume that f (x1 , x2 ) := x1(2) + (1 - x1 x2 )2 . Write the first and second order necessary optimality conditions at a point (x1 , x2 ). What can you deduce about the set of minimizers? Is the infimum reached?
2. Assume that f (x1 , x2 ) := x1(4) + x2(4) + x1 x2 - x1(2) + x2 . Write the first and second order necessary optimality conditions at a point (x1 , x2 ). Prove that }x1 } >^6/6.
3. Assume that f (x1 , x2 ) := 2x1(3) + x1(2) + 1/4x1 x2 + x2(2) - x2 /2 + 1/16 and that we would like to find the infimum on the ball x1(2) + x2(2) ≤ 1. Write the first order necessary optimality conditions (i.e., KKT) at a point (x1 , x2 ).
2022-12-07