# Quantitative Methods: INTEGER PROGRAMMING

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? ( 10- 12 lines)

See attached file for full problem description.

© BrainMass Inc. brainmass.com October 24, 2018, 8:43 pm ad1c9bdddfhttps://brainmass.com/math/linear-programming/quantitative-methods-integer-programming-105506

#### Solution Summary

Word file contain solutions and explanation of multiple choice questions.

Quantitative Methods - Integer programming

1. In using rounding of a linear programming model to obtain an integer solution, the solution is:

a. always feasible.

b. always optimal.

c. sometimes optimal and feasible.

d. always optimal and feasible.

e. never optimal and feasible.

2. The linear programming relaxation contains the objective function and the original constraints of the integer-programming problem but drops all ________.

a. decision variables

b. different variables

c. slack values

d. integer restrictions

e. nonnegativity constraints

3. If we are solving a 0-1 integer programming problem, the constraint x1 <= x2 is a ________ constraint.

a. Corequisite

b. mutually exclusive

c. conditional

d. multiple-choice

e. none of the above

4. Assume that we are using 0-1 integer programming model to solve a capital budgeting problem and xj = 1 if project j is selected and xj = 0 otherwise.

The constraint (x1 + x2 + x3 + x4 <= 2) means that ________ out of the 4 projects must be selected.

a. exactly 2, 4

b. at least 2, 4

c. exactly 1, 4

d. at most 2, 4

5. The branch and bound method of solving linear integer programming problems is ________.

a. a graphical solution

b. an enumeration method

c. an integer method

d. a relaxation method

6. 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.

Fixed cost to set

Machine 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.

a. Min 750y1+500y2+1000y3+300y4

b. 1.25x1+1.5x2+x3+2x4

c. Min 750y1+500y2+1000y3+300y4+1.25x1+1.5x2+x3+2x4

d. none of the above

7. If a maximization linear programming problem consists 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 feasible solution to the integer linear programming problem.

a. Sometimes

b. Never

c. Always