# Linear Integer Programming: Integer Values

Is integer values a general property of Linear Programming problems? Explain why rounding or truncating non-integer values for the solutions is not an appropriate method for obtaining integer solutions.

© BrainMass Inc. brainmass.com October 25, 2018, 9:22 am ad1c9bdddfhttps://brainmass.com/math/linear-programming/linear-integer-programming-integer-values-571462

#### Solution Summary

In this solution, an example shows why one cannot round or truncate a solution from a linear program to obtain a solution to the corresponding linear integer program. This solution is provided in a Word document.

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.

View Full Posting Details