﻿ 优化Midterm代考 IEOR 3609代写 - 优化代写, 考试助攻

# 优化Midterm代考 IEOR 3609代写

2022-07-13 11:27 星期三 所属： 优化代写 浏览：233 ## Midterm: IEOR 3609

### Submission Instructions.

• The exam contains five problems. (Total = 100 points). Exam duration: 2 hours.
• You do not need to print or copy the questions in your submission. Just submit your solutions, with clearly marked problem numbers.
• Submit on gradescope. Please take a clear photo or scan of your exam and upload it on the gradescope within 15 minutes of exam close time (i.e., by 10:15pm EST). The upload process is similar to homework submission.

### Queries during exam  优化Midterm代考

• All the problems should be self-explanatory. Any student queries asking for further explanation of a problem will not be entertained, as it is not fair to other students who did not receive the additional explanation. If you feel that a problem statement is ambiguous, provide your interpretation of the problem, and answer it according to that interpretation.
• If there are any pressing queries during the exam, go to the zoom meeting for instructor office hours.

• The exam is open book. However, you must take the exam completely on your own. You should not show or discuss your exam with anyone (in-person or online or through chat/email).
• You may use a calculator if needed, although the exam can be solved without using a calculator. No other software (like Gurobi) or online utility should be used during the exam.
• DO NOT post or share the exam or your solutions online during or after the exam. Any violation of the above policies will be considered academic dishonesty and violation of honor code, and can be subject to disciplinary action.

### Problem 1. (20 points)  优化Midterm代考

You are given a dataset with m tuples of form (ai , bi), i = 1, …, m, where vector ai Rn represents feature of candidate i and bi ∈ {−1, 1} is the label for candidate i. Here label bi = 1 means that the candidate i is qualified for the job and bi = 1 means that the candidate i is unqualified. Your task is to find a w Rn such that the scores wT ai , i = 1, ..n provide a ”good”

prediction of candidate qualifications in the sense that the number of candidate pairs i, j where an unqualified candidate i received a score above a qualified candidate j is minimized. More precisely, let B+⊆ {1, . . . , m} denote the set of qualified candidates (those with bi = 1), and B denote the remaining set of unqualified candidates; then the goal is to find w Rn to minimize but this is not a Linear program or Integer Program since the function 1(wT ai < wT aj ) is not linear in w. There will be no credit for writing it in the above form. Your task is to use auxiliary variables, possibly binary or integer, to reformulate this optimization problem as a (mixed) Integer program.

Also note that B+, B are fixed sets input to the program. You can use them to write constraints of form ”for all i B+”, ”for all j B” etc.

### Problem 2. (20 points)   优化Midterm代考

You have received m requests for an appointment for vaccination. Each request j includes a start date sj . Person j can receive the vaccination on any date after (and including) the start date sj . There are 20 appointment slots for vaccination available everyday at the JK hospital. At most one request can be scheduled for one appointment slot. If a request j is scheduled for a date tj > sj , then we say that the request j was delayed by tj sj days. (tj sj is the number of days between date tj and sj ). Your goal is to schedule appointments such that the maximum delay over all requests is minimized.

Consider the following greedy algorithm for scheduling appointments. Order the requests in ascending order of start dates. Then, starting from day 1, on each day schedule as many remaining requests as possible prioritized by start dates. Is this algorithm correct? If correct, give a proof of correctness. If incorrect, give a counter example.

### Problem 3. (20 points)

Consider the following integer program.

maximize      z = 11x1 + 13x2
s.t.
x1 + x2 5
4x1 + 7x2 28
x1 0
x2 0
x1, x2 integer

Following is a partial branch and bound tree for this program.

(a) (15 points) Using the information given in the above tree answer the following.

• What is the current best (highest) lower bound on the optimal solution?
• What is the best (lowest) upper bound available for the value of any integer solutions obtainable from node e or its children?
• Which of the remaining branches can be eliminated to prune the tree and which cannot be? Justify. You can use the letters (a,b,c,d,e) on the top left corner to refer to a node.

(b) (5 points) Finish executing the branch and bound to find the optimal integer solution. You can solve any LPs using graphical method or by inspection (show your work as much as possible). Make sure to prune the tree when possible.

### Problem 4. (20 points)   优化Midterm代考

Consider the following integer program.

maximize         z = 5x1 + 8x2
s.t.                      x1 + x2 6
5x1 + 9x2 45
x1 0
x2 0
x1, x2 integer

The optimal solution to the LP relaxation is (2.25, 3.75). The final simplex tableau (including the slack variables) for this problem is as follows:

z               +1.25s1 +0.75s2 = 41.25
x1                 +2.25s1 0.25s2 = 2.25
x2               1.25s1 +0.25s2 = 3.75

Which of the following are valid inequalities? Justify. To justify that an inequality is valid, you can derive it using Chvatal-Gomory procedure or show graphically that it does not cut any feasible integer points. To show that an inequality is not valid, state an integer feasible point that does not satisfy the inequality.

(a) x1 + 2s1 s2 2

(b) x2 2s1 3

(c) 0.75s1 + 0.25s2 0.75

(d) 2x1 + 3x2 15

### Problem 5. (20 points)  优化Midterm代考

In the shortest path problem with delays, we are given a network G = (V, E), where each edge (i, j) E has a cost cij and a delay dij . The goal is to find a path from source s to terminal t with minimum cost such that the total delay over the path is at most D.

This problem can be formulated as the following integer program: #### (a) (6 points)

Dualize the delay constraint (P(i,j)E dijxij D) to obtain a Lagrangian relaxation. Argue that the Lagrangian relaxation is a standard shortest path problem (with only costs and no delays) and therefore can be easily solved. State the expression for the cost of each edge (i, j) in this shortest path problem.

#### (b) (10 points)

Consider the following example network for the shortest path with delays problem. On each edge, the first number (with dollar sign) indicates cost cij , and the second number (in red) indicates delay dij . Here source s = 1, terminal t = 6, and D = 15.

On this example network, solve the Lagrangian relaxation derived in part (a) for the following two values of the Lagrangian multiplier : µ = 0, µ = 1. You may solve the standard shortest path problem by inspection (by comparing the costs of all possible paths).

Note: If the Lagrangian relaxation you constructed in part (a) provides a lower bound only for negative values of the Lagrange multiplier, solve it for µ = 0, µ = 1.

#### (c) (4 points)

What is the tightest (maximum) lower bound obtained in part (b)? Is there any gap from the optimal value of the original problem? Derive an upper bound in order to bound the gap from the optimal solution. (Note that any feasible solution to the original problem gives an upper bound.) 