Homework 2 - Integer Programming

Homework 2 - Integer Programming
via Branch and Bound Method and Cut-Planes
Math 3060 - An Introduction to Optimization

Please submit the following problem at the beginning of class Monday, September 24. Additionally, please staple these sheets to the front of your solutions.
1. Solve the following problem by incrementally using Dakin’s Branch and Bound Method:
Maximize: 4x1 + 3x2 + 3x3
Subject to:
4x1 + 2x2 + x3 ≤ 10 (1)
3x1 + 4x2 + 2x3 ≤ 14 (2)
2x1 + x2 + 3x3 ≤ 7 (3)
where x1, x2, x3 are nonnegative integers.
Please draw a decision tree similar to what we did in class for your answers. As well,
for each iteration of the particular path you are following, please clearly state the LP
problem you are answering. You may use Solver (or a program of your choice) to answer
each of these individual LP problems (you do not have to show row operations...).
2. User Solver (or a program of your choice) to answer the above question as a LP problem. Observe the computation time (should be incredibly fast). Return to the original
problem, solve it a second time but choose“integer” as a constraint for each of the decision variables. Do this a third time but change the tolerance under ”Options” to 1% or
less. Observe the computation time for the IP problem. This should be a little longer,
but for this small of a problem the difference in computation time is probably not very
noticeable. Submit the Answer Report for the third run of the problem (if you are using
software or a program other than Solver, submit a screenshot of the program’s output).
3. Solve the following problem by hand incrementally using Cut-Planes:
Minimize: x − y
Subject to:
3x + 4y ≤ 6 (4)
x − y ≤ 1 (5)
where x and y are nonnegative integers.
1
1. State the modified Linear Programming problem (what we have after introducing
slack, surplus, and artificial variables, etc.);
2. graph the feasible region;
3. provide the initial simplex tableau;
4. begin iteratively introducing Gomory cuts until an integer solution is attained where
for each iteration:
(a) clearly show work supporting why you have introduced a particular cut-plane
(i.e. the new constraint),
(b) write down the new LP problem (the one from the previous iteration plus the
new constraint) and the new initial Simplex Tableau,
(c) provide a diagram showing the feasible region for the decision variables and
(d) use any computer resource to find the final simplex tableau for this iteration’s
LP and provide the final Simplex tableau (a screen shot is acceptable).
4. Solve the following problem by hand incrementally using Cut-Planes:
Maximize: 4x1 + 3x2 + 3x3
Subject to:
4x1 + 2x2 + x3 ≤ 10 (6)
3x1 + 4x2 + 2x3 ≤ 14 (7)
2x1 + x2 + 3x3 ≤ 7 (8)
where x1, x2, x3 are nonnegative integers.
1. State the modified Linear Programming problem (what we have after introducing
slack, surplus, and artificial variables, etc.);
2. provide the initial simplex tableau;
3. begin iteratively introducing Gomory cuts until an integer solution is attained where
for each iteration:
(a) clearly show work supporting why you have introduced a particular cut-plane
(i.e. the new constraint),
(b) write down the new LP problem (the one from the previous iteration plus the
new constraint) and the new initial Simplex Tableau, and
(c) use any computer resource to find the final simplex tableau for this iteration’s
LP and provide the final Simplex tableau (a screen shot is acceptable).
Page 2
5. User Solver (or a program of your choice) to answer the following IP question (you are
not to answer this one by hand!). Do note that solving the problem requires making
certain decision variables binary (i.e. 0-1) variables. If you are running Solver, there is
an option in the drop-down list box for the binary constraint (this is the box with “<=”,
etc.).
(From Ragsdale) In his position as vice president of research and development (R&D)
for CRT Technologies, Mark Schwartz is responsible for evaluating and choosing which
R&D projects to support. The company received 18 R&D proposals from its scientists
and engineers and identified six projects as being consistent with the company’s mission.
However, the company does not have the funds available to undertake all six projects,
so Mark must determine which projects to select. The funding requirements for each
project are summarized in the following table along with the NPV (Net Present Value;
let’s not worry about what that means) the company expects each project to generate.
Project Expected NPV Year 1 CR Year 2 CR Year 3 CR Year 4 CR Year 5 CR
1 $141 $75 $25 $20 $15 $10
2 $187 $90 $35 $0 $0 $30
3 $121 $60 $15 $15 $15 $15
4 $83 $30 $20 $10 $5 $5
5 $262 $100 $25 $20 $20 $20
6 $127 $50 $20 $10 $30 $40
KEY: NPV = Net Present Value; CR = Capital Required.
NOTE: all dollar values are in $1,000’s
(So think of NPV as revenue and CR as costs.)
The company currently has $250,000 available to invest in new projects. It has budgeted $75,000 for continued support for these projects in year 2 and $50,000/year for
years 3,4,and 5. Surplus funds in any year are reappropriated for other uses within the
company and may not be carried over to future years (note: this actually makes the
problem easier).
So, what projects should the company select in order to maximize NPV? (Note to all
future analysts; please begin your solution by clearly stating what your decision variables
are and what they represent and clearly state the model.) Submit your model and the
answer report.
Page 3