An advertising company underwent a thorough reorganization during which the m employees of the department of Creative Designers got laid o.

An advertising company underwent a thorough reorganization during which the m employees of the department of Creative Designers got laid off. However n > m new positions have been created in the company. The human resources manager interviews all m employees regarding their interest in the positions and their qualifications. Then he assigns a score sij to each employee i for each position j (s)he is willing to accept reflecting how qualified employee i is for position j.

The goal of the manager is to assign jobs to employees so that the sum of the scores of the employees who are assigned to jobs is maximized. A single job cannot be assigned to more than one employee and a single employee may not be assigned to more than one job.

i. (4 points) Formulate an integer program (IP) for this problem.

ii. (4 points) Formulate this problem in graph-theoretic terms and explain what the above IP finds.

iii. (4 points) Now suppose that sij = 1 for every employee i that qualifies for a job j. Explain in graph-theoretic terms what the IP finds.

iv. Now consider the specific instance of the above problem where m = 2, n = 3, sij = 1 for all 1 ≤ i ≤ 2,1 ≤ j ≤ 3. i. (12 points) Write out the IP for this instance. Write the LP for its linear programming relaxation and take the dual of the relaxed LP (show all your work). ii. (8 points) Assume that the dual LP has an integral solution. Interpret the dual LP in graph-theoretic terms