Homework 2 Integer Programming Solution

Please submit the following problem at the beginning of class Monday, September 24. Ad-ditionally, 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...).




User Solver (or a program of your choice) to answer the above question as a LP prob-lem. 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 deci-sion 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 di erence 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).



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



State the modi ed Linear Programming problem (what we have after introducing slack, surplus, and arti cial variables, etc.);



graph the feasible region;



provide the initial simplex tableau;



begin iteratively introducing Gomory cuts until an integer solution is attained where for each iteration:



clearly show work supporting why you have introduced a particular cut-plane (i.e. the new constraint),



write down the new LP problem (the one from the previous iteration plus the new constraint) and the new initial Simplex Tableau,



provide a diagram showing the feasible region for the decision variables and



use any computer resource to nd the nal simplex tableau for this iteration’s LP and provide the nal Simplex tableau (a screen shot is acceptable).



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.




State the modi ed Linear Programming problem (what we have after introducing slack, surplus, and arti cial variables, etc.);



provide the initial simplex tableau;



begin iteratively introducing Gomory cuts until an integer solution is attained where for each iteration:



clearly show work supporting why you have introduced a particular cut-plane (i.e. the new constraint),



write down the new LP problem (the one from the previous iteration plus the new constraint) and the new initial Simplex Tableau, and



use any computer resource to nd the nal simplex tableau for this iteration’s LP and provide the nal Simplex tableau (a screen shot is acceptable).



























Page 2



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 identi ed 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 bud-geted $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