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.
- 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.
- [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 :=
param h :=
param a :=
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.
- [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
- [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.
- Write down an
integer programming formulation for the problem of finding a maximum
assignment. Reduce this problem to a max-flow problem.
- 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.
- [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?
- [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
- [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.