Assignment:
Q. A company has $200,000 available for funding new initiatives. Six proposals 1-6 are received from various departments. The costs and values of the projects in 1000s of dollars are given in the table.
|
Project
|
1
|
2
|
3
|
4
|
5
|
6
|
|
Cost
|
60
|
56
|
90
|
50
|
40
|
20
|
|
Value
|
330
|
280
|
405
|
405
|
140
|
60
|
|
Value/Cost
|
5.5
|
5
|
4.5
|
3.6
|
3.5
|
3
|
a. Formulate this as an integer programming problem, clearly identifying the meanings of any variables you introduce.
b. Compute an initial LP bound for the problem, including the initial values of the variables involved.
c. What are the next two nodes for which LP bounds should be computed. [You do not need to compute bounds for these next nodes.]
d. State clearly how you would determine which of the two nodes in c should be branched on next. You need not determine which one to use.]
e. Suppose that later in the application of the algorithm, a terminal node gives an integer solution (10.1.0.1) with z 875, and this is the best integer solution determined to that point. State clearly the criterion by which the next non-terminal node will be selected for branching. What can you conclude if no non-terminal node meets your criterion?