• This assignment is worth 5% of your final grade.
• Due: 2017-02-03 23:00
• To facilitate marking, please hand in both parts electronically. Scans of handwritten notes are OK (of course, so is LaTeX). Microsoft Word is not OK and you're a bad person for asking.

Questions

1. In our discussion of bipartite matching in class, and the proof of Theorem 3.2.1, we assumed that the matching was perfect, i.e. that ever vertex was contained in exactly one edge. Extend the LP to allow (in the notation of the book) |X| ≠ |Y|. Some vertices will necessarily be unmatched. Show that the theorem still holds, that a feasible solution implies an integral optimal solution. This is a small modification to the proof we discussed in class.

2. Use glpsol to solve question 2-6 (paper mill) from AMPL book, chapter 2 You can use integer variables in glpsol to part (d) (i.e. you don't have to find the integer solution by hand).