IEOR E4004: Optimization Models and Methods
Optimization Models and Methods
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
IEOR E4004: Optimization Models and Methods
Take-home Mini-Midterm2 Examination
YOUMAYCONSULT CLASS LECTURES, THE LITERATUREOR 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
be neatly drawn with flows and arc capacities clearly labeled for you to obtain full credit.
This exam concerns the use ofMax-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
are identified by the 2 players involved in the match; e.g.,
(
3
5
)
refers to a match involving
players P3 and P5. 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.
Table 1.
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
Table 2.
Matches
1
2
1
3
1
4
1
5
1
6
2
3
2
4
2
5
2
6
3
4
3
5
3
6
4
5
4
6
5
6
Games
Played 2 2 1 1 1 1 1 1 1 1 1 1 2 1 1
Games
Remaining 0 0 1 1 1 1 1 1 1 1 1 1 0 1 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 P6 has not won any games, P6 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 Pn, n = 1, . . . , 5 in the tournament
is no more than the maximum number of games that P6 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