IEOR E4004: Optimization Models and Methods
Take-home Mini-Midterm2 Examination
Posted: 6pm (EST), Friday, April 1, 2022 Due: 6pm (EST), Friday, April 8, 2022
April 1-8, 2022 Professor D. OU MAY CONSULT CLASS LECTURES, THE LITERATURE OR THE INTERNET FREELY, BUT YOU MAY NOT OBTAIN HELP FROM ANY OTHER PERSON. If you download any codes from the internet or use codes copied from the internet or the literature, you MUST provide citations to your sources. Your answers to the questions must be well documented and clearly presented. For example, any networks corresponding to a max-flow formulation must
Copyright By PowCoder代写 加微信 powcoder
be neatly drawn with flows and arc capacities clearly labeled for you to obtain full credit.
This exam concerns the use of Max-Flow/Min-Cut problem formulations and algorithms to solve such problems to answer some questions about a chess tournament involving 6 players.
The tournament consists of 15 matches (the number of possible pairings of 6 players), in
each of which 2 games are played, where each player plays ”white” in one of the games and
”black” in the other game. Hence, each player plays a total of 10 games, and a total of 30
games are played in the tournament. Referring to the 6 players as P1,…,P6, the matches 3
are identified by the 2 players involved in the match; e.g., 5 refers to a match involving
players P 3 and P 5. In each game, there is either a winner, who is awarded 1 point and a loser, who receives 0 points, or there is a draw in which case both players are awarded a 12 point. The winner(s) of the tournament is that player (those players) who has (have) been awarded the most points after the completion of the 30 games. That is, there may be more than one tournament winner if there is more than one player with the most number of points. Suppose that after 18 games have been played the following results and information about these games is known.
Players Games Played Games Won Games Drawn Games Lost Games Left to Play P1 7 5 0 2 3
P2 6 4 1 1 4
P3 6 4 1 1 4
P4 6 2 0 4 4 P5 6 2 0 4 4 P6 5 0 0 5 5
Played 2 2 1 1 1 1 1 1 1 1 1 1 Games
Remaining 0 0 1 1 1 1 1 1 1 1 1 1 1
2 1 1 0 1 1
All of the following questions refer to the data given in Tables 1 and 2. Where a formulation is asked for, you must give a clearly drawn and labeled diagram of the max-flow network.
1. (20 points) Formulate a Maximum Flow Problem that can be used to verify that the numbers of games won, drawn and lost by each of the players listed in Table 1, after 18 games have been completed, could have resulted from the numbers of the 15 different types of matches that were played given in Table 2 (which adds up to 18 games). Hint: A similar application of the usefulness of max-flow was covered in the lectures.
2. (20 points) Formulate a Maximum Flow Problem that can be used to either verify or contradict the statement that even though player P 6 has not won any games, P 6 can still win or tie for for the tournament leadership by winning all of his/her 5 remaining games. You also must state what must be true about the solution to your formulation that provides a verification that the above statement in bold type is true or a false. Hints: The network for this problem can be significantly smaller than the one in the formulation for Part 1. You should look at this problem as one in which one needs to find out if the outcome of playing the remaining 12 games can result in a solution in which the total number of games won by each player P n, n = 1, . . . , 5 in the tournament is no more than the maximum number of games that P 6 can have won after all 30 games have been played. Recall the application of max-flow to the baseball elimination problem in the course slides Lecture 18 max-flow applications.
3. (20 points) Modify your Maximum Flow Problem Formulation in Part 2 that can be used to either verify or contradict the statement that if there are no draws in the remaining 12 games, then player P6 cannot win the tournament or tie for the leadership. You also must state what must be true about the solution to your formulation that provides a verification that the above statement in bold type is true or a false.
4. (10 points) Write a code for solving maximum flow problems that implements either the Ford-Fulkerson (FF) Augmenting path method or the shortest augmenting path variant of the FF algorithm of Edmonds and Karp. (Shortest here means augmenting paths that have the fewest number of arcs, which are identified by searching for augmenting paths from the source node s using breadth-first search.)
5. (20 points) Use your code to solve the three max-flow formulations in Parts 1, 2, and 3.
6. (10 points) Now that you have verified whether the statements in Parts 2 and 3 are true or false, explain your conclusion in simple terms, referring only to the networks in your Maximum Flow Formulations in Parts 2 and 3, without solving for the maximum flow solution. Note: Even if you can argue why the statements in Parts 2 and 3 are true or false, without formulating a maximum flow problem, you MUST provide such a formulation to receive credit for Parts 2 and 3
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com