﻿ 高级优化exam代考 IEOR 3609代写 – 天才代写

# 高级优化exam代考 IEOR 3609代写

2022-07-12 11:34 星期二 所属： 优化代写 浏览：291

## Midterm 1 IEOR 3609

### Notes

• The exam contains Three questions. (Total = 50 points).
• Answer all questions in the space provided.
• Time Allowed: 1 Hour 10 minutes. Budget your time. If a problem is taking too long, you may want to consider going to the next one.
• The exam is closed book (NO cheat sheets or other references allowed).

### Problem 1. (20 points)  高级优化exam代考

You are planning family trips for the year. You have a list of 10 domestic destinations and 10 international destinations. You ask each of your 12 family members to pick one domestic destination and one international destination from this list. Find the smallest set of destinations such that for each family member, at least one of his/her picks is included in this subset.

(a) Formulate this problem as an integer program.

(b) Argue that your formulation in (a) satisfies total unimodularity. (if needed, reformulate the IP to make sure it does satisfy total unimodularity)

### Problem 2. (20 points)  高级优化exam代考

A salesman needs to visit n cities in a given order: C1, C2, . . . , Cn, starting from city C0. The salesman can travel for at most 20 hours in one day. It takes hi hours go from Ci1 to Ci, where hi is an integer and hi 20, for all i = 1, . . . , n. Break this tour into multiple days, so that each day, the salesman travels for 20 hours or less. (You cannot end a day’s travel at some point between two cities. That is, for any i, if you start the leg Ci1 Ci on a day, you must completely finish it on the same day.)

Consider the following greedy heuristic for breaking the tour: travel as much as possible on the first day, then as much as possible on second day, and so on. For each of the three criteria (a), (b), and (c) below, either prove that this greedy heuristic is optimal or give a counter example.

#### (a)  高级优化exam代考

Minimize the number of travel days

#### (b)

After finishing a day’s travel, the salesman spends the remaining hours of the day at a hotel, which charges per hour. Minimize the total number of hours spent in a hotel on all but the last day.

#### (c)

Minimize the maximum of the number of hours spent in a hotel on all but the last day.

Below is an example. Here, a tour of 4 cities has been broken into 3 days in two possible ways. The shaded part shows the hours of the day spent traveling, and the white part shows the hours spent in a hotel. So, in the first case, the salesman covers the first two legs C0 C1 C2 on the first day, third leg C2 C3 on the second day, and the fourth leg C3 C4 on the last day. The total number of hours spent in the hotel are same for both cases. However, on the third criteria, i.e., the maximum of the number of hours spent, the second way of breaking the tour is better than the first.

### Problem 3. (10 points)  高级优化exam代考

Provide a dynamic programming formulation for part (c) of Problem 2.

HINT: Define fi(j) as the objective value (maximum of remaining hours in all but last day) for breaking tour {C0, C1, . . . , Ci}, in a way that there are j hours remaining on the last day. For a new city, you have choice between either fitting it in the last day of this tour without changing the objective, or adding an additional day. What will be the new objective value in the latter case?