Mathematical Programming and Combinatorial Optimization

 

MS&E 212/CME 208; Spring 2005-06

Instructor: Ashish Goel

Handout 4: Homework 1

Given: 4/15/2006. Due: 4/25/2006, in class.

 

Please submit a hardcopy unless otherwise instructed. Limited collaboration is allowed on the homework -- you are allowed to discuss general strategies but you must solve and write the problems by yourself. You are not allowed to share your final solutions with anyone outside the class staff or look at anyone else’s final solutions. Report any collaborations you participate in.

 

  1. You are supposed to plan the ordering of a good for a retail warehouse. At time 0, there is no inventory. For times i = 1… N, you are given demands d(i). The cost of holding inventory over from time i to i+1 is h(i) per unit, which is given to you. The cost of acquiring inventory is a(i) per unit during time i, which is also given to you (assume ordered quantities arrive instantaneously).  Your goal is to decide how much of the good to acquire during each time from 1 to N such that all the demands are satisfied, and the total cost is minimized.
    1. [20 pts.] Assume that the good is infinitely divisible, and that the demands, held inventory, and ordered quantities can all be fractional. Develop an AMPL model to solve this problem. Your model should be able to take the following data file as input:

param N := 6;

param d :=

1 5

2 5

3 5

4 5

5 5

6 6;

param h :=

1 1

2 10

3 1

4 1

5 10

6 10;

param a :=

1 5

2 6

3 18

4 5

5 8

6 16;

The total cost for the above instance should be 286. We will test your model on different data values – the above is given just to make sure that your model is compatible to our data and to give you a test case. The fewer variables and constraints you use, the better your model will be considered. Please submit your model separately using email to the CA and also attach a printout to your hardcopy submission. Make sure that with your model, ampl can quickly solve the data sets at http://www.stanford.edu/~ashishg/msande212/ampl_for_hw1/. Report the time taken by ampl to solve the largest data set and the value of the objective function.

    1. [10 pts.] Explain how this problem can be reduced to a min-cost flow problem. Suppose that the good is indivisible, so only integer quantities can be ordered or held-over, and the demands are also integers. Explain why your AMPL model already solves this integer programming problem.
  1. [20 pts.] Suppose you are given M tasks and N agents. Each agent can perform at most three tasks. There is an edge from agent i to task j if the i-th agent can perform the j-th task. Further, agent i charges wi dollars for each task assigned to her. The tasks are indivisble, so each task must be performed entirely by one agent. The goal is to assign tasks to agents so that the maximum number of tasks can be completed; such an assignment is called a maximum assignment.
    1. Write down an integer programming formulation for the problem of finding a maximum assignment. Reduce this problem to a max-flow problem.
    2. Suppose you are required to find a maximum assignment that has the minimum cost among all maximum assignments. Reduce this problem to a min-cost flow problem.
  1. [10 pts.] Suppose you are given a min-cost problem where the capacities are on the edges, but the cost is on vertices, i.e., it costs w(v) to send one unit of flow through v. No cost is incurred if the flow originates or terminates at v. How would you reduce this problem to a standard min-cost flow problem where both costs and capacities are on the edges?
  2. [10 pts.] Consider the max-flow problem with two commodities. Give an example where the linear program for this problem does not have any integral optimum solution, even if all capacities are integers. Additional question for you to think about but not submit: Which part of the proof that min-cost-flow always has an integral optimum solution (given integer demands and capacities) breaks down?
  3. [10 pts.] There are N NBA teams in a conference, and the j-th team in this conference has won t(j) games so far. The only remaining games are between teams in the same conference. Let k(i,j) denote the number of games remaining between teams i and j in this conference. Our goal is to determine whether team Q can win the conference, assuming ties are not allowed in games. Model this as a max-flow problem.