Introduction To Optimization MS&E 111/MS&E 211/ENGR 62 HW2 Course Instructor: Ashish Goel

MS&E 111/MS&E 211/ENGR 62
Introduction to Optimization
MS&E 111/MS&E 211/ENGR 62 HW2
Course Instructor: Ashish Goel
Midterm Practice Problems

True or False
No explanations needed. You get 2 points for each correct answer, -1 for each incorrect answer, 0 points
for each part you do not attempt.
1. If a contingent claims market has an arbitrage opportunity, then there must be two portfolios with
the same payoff but different prices.
2. In the pattern classification problem, there always exists a feasible solution for the problem of
minimizing the total violation.
3. The set of all points x ∈ ℜ satisfying |x| ≥ 1 is convex.
Short Questions
You will receive 5 points if you state whether the statement is true or false correctly, 5 points if you
provide correct explanation, and -5 points if you answer it incorrectly (with or without explanation). If
the net score on this question is negative, we will make it up to zero.
1. Is it possible for a linear program to have exactly two basic feasible solutions?
2. Consider the linear program
maximize cx
subject to Ax = b
x ≥ 0.
where A ∈ ℜM ×N . Is it possible for there to be more than M non-zero variables at an optimum?

If not, why not, and if so, provide an example.
For questions 3) and 4) below, suppose that two constraints in a system are cT x ≤ 1 and dT x ≤ 1,
where c and d are linearly dependent. A constraint is called reduntant if removing it does not
change the feasible region.
3. (Extra Credit*) Does cT d ≥ 0 imply that one of cT x ≤ 1 or dT x ≤ 1 is redundant? If so, explain
why. If not, give an example.
4. (Extra Credit*) Does c ≤ d imply that one of cT x ≤ 1 or dT x ≤ 1 is redundant? If so, explain
why. If not, give an example.
1
Long Questions
1. Alice and Bob have $200, 000 in their Investment Retirement Account(IRA) which they need to
withdraw over three years. Funds in their IRA earn an annual 10% rate of return and do not get
taxed while they are in the IRA. Unfortunately, (for Alice and Bob), withdrawls from their IRA
get taxed as income. Alice and Bob would like to maximize the total after tax income over three
years. Assume they have an additional fixed income of $30, 000 each year from social security (this
$30, 000 is not deposited into the IRA. Instead it is treated as an income which will
taxed). Also assume that their tax rate is 0% for the first $40, 000, 10% for the next $40, 000, and
25% thereafter e.g. for $90, 000 the amount of tax is .1 × 40, 000 + .25 × 10, 000. Assume that IRA
withdrawals are made at the beginning and social security is also received in the beginning. Note
that all the money will be withdrawn at the beginning of the third year.
Formulate this problem as an LP.
2. You plan to buy stocks (no shorting is allowed). There are two stocks you are interested in
purchasing: stock A and B. They both cost $10 per unit. You have $1000 which you wish to
completely invest. You believe that there are three possible prices for the shares in one year as
given in the table below.
scenario stock A stock B

1 20 6
2 12 12
3 8 15
Table 1: Price of stocks in different scenarios in one year.
Formulate this problem as a linear program to maximize the worst case value of your portfolio in
a year.
3. Given points x, y, z, suppose a is a convex combination of x, y and b is a convex combination of

a, z. Show that b is also a convex combination of x, y, z.
4. There are 12 possible food items that can be part of an emergency food package for dropping
from an airplane to areas affected by California wildfires. Each package must provide 200% of the
daily recommended value of carbs and fat each. The maximum allowed cost for a package is $20.
Let si represent the cost in dollars of 1 lb of food i. Let ri , fi denote the percentage of the daily
recommended value of carbs and fats, respectively, in 1 lb of food i. The goal is to minimize the
total weight of the food in a package.
(a) You need to formulate this problem as a linear program of the form
minimize bT · y
subject to:
Ay ≥ c
y ≥ 0.
More specifically, write down the dimensions of b, A, y, and c, and clearly explain what the
components of these matrices/vectors correspond to in this problem.
(b) How many different food items could be present in the optimal package obtained by solving
this linear program using a typical commercial linear programming solver (eg. Excel)? Explain
briefly. Assume that the LP has a basic feasible solution as well as an optimum solution.
5. Consider a directed graph with the set of nodes V and the set of edges E where c(v, w) is the cost
of edge (v, w). Suppose that a graph has one source node s and two possible destination nodes t1
and t2 . Your goal is to find the shortest path starting at s and going to either t1 or t2 .
2
(a) How will you rewrite this as a standard shortest path problem with a single source and a
single destination? Note that we are not looking for an LP formulation.
(b) Consider the following network. Let the numbers on the edges represent the cost of traversing
that edge. Your goal is to find the shortest path starting at s and ending at either p or w.
Formulate this as a standard shortest path problem by drawing the new graph, specifying the
source and the destination, and the edge costs. Do not solve the problem.
6. (Extra Credit*) Suppose that we have N different currencies (e.g., US Dollars, Euros, etc.). For
each pair of currencies, (i, j), one unit of currency i can be exchanged into rij units of currency j.
We wish to find an arbitrage opportunity if it exists, i.e. a sequential series of currency trades that
allows us to make a profit with no risk. Formulate this as a min-cost flow problem and provide an
LP with a bounded feasible polytope which solves it. Assume no transaction costs.

Introduction To Optimization MS&E 111/MS&E 211/ENGR 62 HW2 Course Instructor: Ashish Goel

Uploaded by

Copyright:

Available Formats

Introduction To Optimization MS&E 111/MS&E 211/ENGR 62 HW2 Course Instructor: Ashish Goel

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Introduction To Optimization MS&E 111/MS&E 211/ENGR 62 HW2 Course Instructor: Ashish Goel

Uploaded by

Copyright:

Available Formats

MS&E 111/MS&E 211/ENGR 62

Midterm Practice Problems

3. The set of all points x ∈ ℜ satisfying |x| ≥ 1 is convex.

where A ∈ ℜM ×N . Is it possible for there to be more than M non-zero variables at an optimum?

scenario stock A stock B

Table 1: Price of stocks in different scenarios in one year.

3. Given points x, y, z, suppose a is a convex combination of x, y and b is a convex combination of

You might also like