Problems:
Integer Programming
TRUE/FALSE
1. In a mixed integer model, some solution values for decision variables are integer and others can be non-integer.
2. In a total integer model, some solution values for decision variables are integer and others can be non-integer.
3. The branch and bound method can only be used for maximization integer programming problems.
4. The solution value (Z) to the linear programming relaxation of a maximization problem will always be less than or equal to the optimal solution value (Z) of the integer programming maximization problem
5. In a 0-1 integer programming problem involving a capital budgeting application where xj = 1, if project j is selected, xj = 0, otherwise, the constraint x1 - x2 = 0 implies that if project 2 is selected, project 1 can not be selected
6. Rounding non-integer solution values up to the nearest integer value will still result in a feasible solution to an integer programming problem.
7. Rounding non-integer solution values up to the nearest integer value will still result in a feasible solution.
8. The solution to the LP relaxation of a minimization integer linear program provides an upper bound for the value of the objective function.
9. If we are solving a 0-1 integer programming problem, the constraint x1 = x2 is a conditional constraint.
10. In a problem involving capital budgeting applications, the 0-1 variables designate the ____________ or _____________ of the different projects.
11.If exactly one investment is to be selected from a set of five investment options, then the constraint is often called a ____________ constraint.
12. If we are solving a 0-1 integer programming problem, the constraint x1 + x2 ≤ 1 is a ________________constraint.
13. If we are solving a 0-1 integer programming problem, the constraint x1 ≤ x2 is a ________________constraint.
14. If we are solving a 0-1 integer programming problem, the constraint x1 = x2 is a ________________constraint.
15. Consider the following integer linear programming problem
Max Z = 3x1 + 2x2
Subject to: 3x1 + 5x2≤30
4x1 + 2x2≤28
x1≤8
x1 ,x2≤0 and integer
The solution to the Linear programming relaxation is: x1 = 5.714, x2= 2.571.
What is the upper bound for the value of the objective function?
What is the value of the objective function for the rounded down solution?
Is the rounded down solution feasible?
16. Consider the following integer linear programming problem
Max Z = 3x1 + 2x2
Subject to: 3x1 + 5x2≤30
4x1 + 2x2≤28
x1 ≤8
x1 ,x2≥0 and integer
The solution to the Linear programming relaxation is: x1 = 5.714, x2= 2.571.
What is the optimal solution to the integer linear programming problem? State the optimal values of decision variables and the value of the objective function.
17. Consider a capital budgeting example with 5 projects from which to select. Let x1 = 1 if project a is selected, 0 if not, for a = 1, 2, 3, 4, 5. Conditions are independent. Projects cost $100, $200, $150, $75, and $300 respectively. The budget is $450. Write the appropriate constraint for the following condition. If project 1 is chosen, project 5 must not be chosen.
18. The Wiethoff Company has a contract to produce 10000 garden hoses for a customer. Wiethoff has 4 different machines that can produce this kind of hose. Because these machines are from different manufacturers and use differing technologies, their specifications are not the same.
Machine Fixed cost to set up production run Variable cost per hose Capacity
1 750 1.25 6000
2 500 1.50 7500
3 1000 1.00 4000
4 300 2.00 5000
The company wants to minimize total cost. Give the objective function.
MULTIPLE CHOICE
19. The branch and bound method of solving linear integer programming problems is ________________.
a. an integer method
b. a relaxation method
c. a graphical solution
d. an enumeration method
20. If a maximization linear programming problem consist of all less-than-or-equal-to constraints with all positive coefficients and the objective function consists of all positive objective function coefficients, then rounding down the linear programming optimal solution values of the decision variables will ______ result in a(n) _____ solution to the integer linear programming problem.
a. always, optimal
b. always, non-optimal
c. never, non-optimal
d. sometimes, optimal
e. never, optimal
21. How is the assignment linear program different from the transportation model?