Deck 5: Integer Programming

Question 1

The management scientist's fiance informed him that if they were to be married, he would also have to welcome her mother into their home. The management scientist should model this decision as a contingency constraint.

Answer 1

False

Question 2

In a problem involving capital budgeting applications, the 0-1 variables designate the acceptance or rejection of the different projects.

Answer 2

True

Question 3

In a 0-1 integer model, the solution values of the decision variables are 0 or 1.

Answer 3

True

Question 4

One type of constraint in an integer program is a multiple-choice constraint.

Question 5

The branch and bound solution method cannot be applied to 0-1 integer programming problems.

Question 6

In a mixed integer model, some solution values for decision variables are integer and others can be non-integer.

Question 7

The production planner for Airbus showed his boss the latest product mix suggestion from their slick new linear programming model: 12.5 model 320s and 17.4 model 340s. The boss looked over his glasses at the production planner and reminded him that they had several half airplanes from last year's production rusting in the parking lot. No one, it seems, is interested in half of an airplane. The production planner whipped out his red pen and crossed out the .5 and .4, turning the new plan into 12 model 320s and 17 model 340s. This production plan is definitely feasible.

Question 8

A conditional constraint specifies the conditions under which variables are integers or real variables.

Question 9

The divisibility assumption is violated by integer programming.

Question 10

In a total integer model, all decision variables have integer solution values.

Question 11

The three types of integer programming models are total, 0-1, and mixed.

Question 12

The branch and bound method can only be used for maximization integer programming problems.

Question 13

In a mixed integer model, the solution values of the decision variables are 0 or 1.

Question 14

In the classic game show Password, the suave, silver-haired host informed the contestants, "you can choose to pass or to play." This expression suggests a mixed integer model is most appropriate.

Question 15

Rounding non-integer solution values up to the nearest integer value can result in an infeasible solution to an integer programming problem.

Question 16

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 cannot be selected.

Question 17

If exactly three projects are to be selected from a set of five projects, this would be written as three separate constraints in an integer program.

Question 18

A feasible solution to an integer programming problem is ensured by rounding down non-integer solution values.

Question 19

The college dean is deciding among three equally qualified (in their eyes, at least) candidates for his associate dean position. If this situation could be modeled as an integer program, the decision variables would be cast as 0-1 integer variables.

Question 20

In a mixed integer model, all decision variables have integer solution values.

Question 21

A rounded-down integer solution can result in a less than optimal solution to an integer programming problem.

Question 22

Rounding non-integer solution values up to the nearest integer value will still result in a feasible solution.

Question 23

The ________ method is based on the principle that the total set of fesible solutions can be partitioned into smaller subsets of solutions.

Question 24

"It's me or the cat!" the exasperated husband bellowed to his well-educated wife. "Hmmmm," she thought, "I could model this decision with a ________ constraint."

Question 25

If we are solving a 0-1 integer programming problem, the constraint x1 + x2 + x3 ≤ 3 is a mutually exclusive constraint.

Question 26

If we are solving a 0-1 integer programming problem, the constraint x1 ≤ x2 is a conditional constraint.

Question 27

In a ________ integer programming model, a solution of x2 = 7 is not possible.

Question 28

In a ________ linear programming model, the solution values of the decision variables are zero or one.

Question 29

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

Question 30

In a ________ linear programming model, some of the solution values for the decision variables are required to assume integer values and others can be integer or noninteger.

Question 31

Rounding non-integer solution values up to the nearest integer value will result in an infeasible solution to an integer linear programming problem.

Question 32

If we are solving a 0-1 integer programming problem, the constraint x1 + x2 ≤ 1 is a mutually exclusive constraint.

Question 33

Rounding down integer solution values ensures an infeasible solution to an integer linear programming problem.

Question 34

If exactly one investment is to be selected from a set of five investment options, then the constraint is often called a ________ constraint.

Question 35

If we are solving a 0-1 integer programming problem, the constraint x1 + x2 = 1 is a mutually exclusive constraint.

Question 36

If we are solving a 0-1 integer programming problem, the constraint x1 ≤ x2 is a mutually exclusive constraint.

Question 37

An optimal solution to an integer programming problem is ensured by rounding down non-integer solution values.

Question 38

In choosing four electives from the dazzling array offered by the Decision Sciences Department next semester, the students that had already taken the management science class were able to craft a model using a ________ constraint.

Question 39

A ________ integer model allows for the possibility that some decision variables are not integers.

Question 40

If we graph the problem that requires x1 and x2 to be an integer, it has a feasible region consisting of ________.

Question 41

Consider a capital budgeting example with five projects from which to select. Let x1 = 1 if project a is selected, 0 if not, for a = 1, 2, 3, 4, 5. Projects cost $100, $200, $150, $75, and $300, respectively. The budget is $450.
Write the appropriate constraint for the following condition: If project 3 is chosen, project 4 must be chosen.

Question 42

Consider a capital budgeting example with five projects from which to select. Let x1 = 1 if project a is selected, 0 if not, for a = 1, 2, 3, 4, 5. 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.

Question 43

Consider the following integer linear programming problem:
Max Z =   3x1 + 2x2
Subject to:  3x1 + 5x2 ? 30
      5x1 + 2x2 ? 28
        x1 ? 8
       x1, x2 ? 0 and integer
The solution to the linear programming formulation 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.

Question 44

The Wiethoff Company has a contract to produce 10,000 garden hoses for a customer. Wiethoff has four 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.

Write the objective function.

Question 45

________ variables are best suited to be the decision variables when dealing with yes-or-no decisions.

Question 46

The Exorbitant Course Fees. The $75 per credit hour course fee tacked on to all the MBA classes has generated a windfall of $56,250 in its first semester. "Now we just need to make sure we spend it all," the Assistant Dean cackled. She charged the Graduate Curriculum Committee with generating a shopping list before their next meeting. Four months later, the chairman of the committee distributed the following. As the professor for the quantitative modeling course, he tended to think in terms of decision variables, so he added the left-most column for ease of use.

What is a full set of constraints for this problem if there are 30 MBA students enrolled this semester?

Question 47

Consider a capital budgeting example with five projects from which to select. Let x1 = 1 if project a is selected, 0 if not, for a = 1, 2, 3, 4, 5. Projects cost $100, $200, $150, $75, and $300, respectively. The budget is $450.

-Write the appropriate constraint for the following condition: Choose no fewer than 3 projects.

Question 48

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

Question 49

If we are solving a 0-1 integer programming problem, the constraint x1 + x2 ≤ 1 is a ________ constraint.

Question 50

In an integer program, if building one facility required the construction of another type of facility, this would be written as: ________.

Question 51

In an integer program, if we were choosing between two locations to build a facility, this would be written as: ________.

Question 52

Saba conducts regular tours of his favorite city in the world, Paris. Each semester he selects among the finest students in the university and escorts them to the City of Lights. In addition to a world-class education on conducting business in Europe, he arranges a number of cultural outings for them to help them immerse themselves in all that France has to offer. He collects an extra $100 from each student for this purpose and limits his tour group to ten lucky individuals. Some of the events (and their prices) he proposes to the students include:
Eiffel Tower visit, $40 per student, E
Paris Sewer spelunking, $20 per student, S
Half day passes to the Louvre, $60 per student, L
Bon Beret tour, $50 per student, B
So much to do and so little time!
What is the full set of constraints if the following situations occur? The Eiffel Tower visit needed to take place at the same time has the half day at the Louvre. Students taking the Paris Sewer tour had to wear the special sanitary beret available only from the Bon Beret tour. Saba applies for university tarvel funds and supplements the students' accounts with an extra $30 each.

Question 53

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

Question 54

If one location for a warehouse can be selected only if a specific location for a manufacturing facility is also selected, this decision can be represented by a ________ constraint.

Question 55

The Wiethoff Company has a contract to produce 10,000 garden hoses for a customer. Wiethoff has four 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.

This problem requires two different kinds of decision variables. Clearly define each kind.

Question 56

Saba conducts regular tours of his favorite city in the world, Paris. Each semester he selects among the finest students in the university and escorts them to the City of Lights. In addition to a world-class education on conducting business in Europe, he arranges a number of cultural outings for them to help them immerse themselves in all that France has to offer. He collects an extra $100 from each student for this purpose and limits his tour group to ten lucky individuals. Some of the events (and their prices) he proposes to the students include:
Eiffel Tower visit, $40 per student, E
Paris Sewer spelunking, $20 per student, S
Half day passes to the Louvre, $60 per student, L
Bon Beret tour, $50 per student, B
So much to do and so little time!
The tour group has three days remaining in Paris and the opportunity to do three cultural events. It is important to soak up as much culture as possible, so Saba decides to model this as a 0-1 integer program mandating that the group does three events. A couple of students object, not to the integer program, but to the set of cultural events that they have to choose from. They would rather have the option to do up to three events but perhaps only one or two and spend the rest of their time doing some "retail benchmarking." What was Saba's original constraint and how does that constraint change to cater to the whims of the students?

Question 57

Saba conducts regular tours of his favorite city in the world, Paris. Each semester he selects among the finest students in the university and escorts them to the City of Lights. In addition to a world-class education on conducting business in Europe, he arranges a number of cultural outings for them to help them immerse themselves in all that France has to offer. He collects an extra $100 from each student for this purpose and limits his tour group to ten lucky individuals. Some of the events (and their prices) he proposes to the students include:
Eiffel Tower visit, $40 per student, E
Paris Sewer spelunking, $20 per student, S
Half day passes to the Louvre, $60 per student, L
Bon Beret tour, $50 per student, B
So much to do and so little time!
What would the constraints be if the Eiffel Tower visit needed to take place at the same time as the half day at the Louvre and if students taking the Paris Sewer tour had to wear the special sanitary beret available only from the Bon Beret tour?

Question 58

The Wiethoff Company has a contract to produce 10,000 garden hoses for a customer. Wiethoff has four 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.

Write a constraint to ensure that if machine 4 is used and machine 1 will not be used.

Question 59

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

Question 60

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

Question 61

In a ________ integer model, the solution values of the decision variables are 0 or 1.

A) total
B) 0-1
C) mixed
D) all of the above

Question 62

You have been asked to select at least 3 out of 7 possible sites for oil exploration. Designate each site as S1, S2, S3, S4, S5, S6, and S7. The restrictions are:
Restriction 1. Evaluating sites S1 and S3 will prevent you from exploring site S7.
Restriction 2. Evaluating sites S2 or S4 will prevent you from assessing site S5.
Restriction 3. Of all the sites, at least 3 should be assessed.
Assuming that Si is a binary variable, write the constraint for the first restriction.

Question 63

Which of the following is not an integer linear programming problem?

A) pure integer
B) mixed integer
C) 0-1 integer
D) continuous

Question 64

Due to increased sales, a company is considering building three new distribution centers (DCs) to serve four regional sales areas. The annual cost to operate DC 1 is $500 (in thousands of dollars). The cost to operate DC 2 is $600 (in thousands of dollars.). The cost to operate DC 3 is $525 (in thousands of dollars). Assume that the variable cost of operating at each location is the same, and therefore not a consideration in making the location decision.
The table below shows the cost ($ per item) for shipping from each DC to each region.
Region
The demand for region A is 70,000 units; for region B, 100,000 units; for region C, 50,000 units; and for region D, 80,000 units. Assume that the minimum capacity for the distribution center will be 500,000 units.
Write the constraints for the three distribution centers.

Question 65

Due to increased sales, a company is considering building three new distribution centers (DCs) to serve four regional sales areas. The annual cost to operate DC 1 is $500 (in thousands of dollars). The cost to operate DC 2 is $600 (in thousands of dollars.). The cost to operate DC 3 is $525 (in thousands of dollars). Assume that the variable cost of operating at each location is the same, and therefore not a consideration in making the location decision.
The table below shows the cost ($ per item) for shipping from each DC to each region.
Region
The demand for region A is 70,000 units; for region B, 100,000 units; for region C, 50,000 units; and for region D, 80,000 units. Assume that the minimum capacity for the distribution center will be 500,000 units.
Write the objective function for this problem.

Question 66

Types of integer programming models are ________.

A) total
B) 0-1
C) mixed
D) all of the above

Question 67

Binary variables are

A) 0 or 1 only.
B) any integer value.
C) any continuous value.
D) any negative integer value.

Question 68

You have been asked to select at least 3 out of 7 possible sites for oil exploration. Designate each site as S1, S2, S3, S4, S5, S6, and S7. The restrictions are:
Restriction 1. Evaluating sites S1 and S3 will prevent you from exploring site S7.
Restriction 2. Evaluating sites S2 or S4 will prevent you from assessing site S5.
Restriction 3. Of all the sites, at least 3 should be assessed.
Assuming that Si is a binary variable, write the constraint(s) for the second restriction.

Question 69

If the solution values of a linear program are rounded in order to obtain an integer solution, the solution is

A) always optimal and feasible.
B) sometimes optimal and feasible.
C) always feasible.
D) never optimal and feasible.

Question 70

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(n) ________ solution to the integer linear programming problem.

A) always, optimal
B) always, non-optimal
C) never, non-optimal
D) sometimes, optimal

Question 71

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.

Question 72

Due to increased sales, a company is considering building three new distribution centers (DCs) to serve four regional sales areas. The annual cost to operate DC 1 is $500 (in thousands of dollars). The cost to operate DC 2 is $600 (in thousands of dollars.). The cost to operate DC 3 is $525 (in thousands of dollars). Assume that the variable cost of operating at each location is the same, and therefore not a consideration in making the location decision.
The table below shows the cost ($ per item) for shipping from each DC to each region.
Region
The demand for region A is 70,000 units; for region B, 100,000 units; for region C, 50,000 units; and for region D, 80,000 units. Assume that the minimum capacity for the distribution center will be 500,000 units.
Define the decision variables for this situation.

Question 73

The Wiethoff Company has a contract to produce 10,000 garden hoses for a customer. Wiethoff has four 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.

Write a constraint that will ensure that Weithoff purchases exactly two machines.

Question 74

In a ________ integer model, all decision variables have integer solution values.

A) total
B) 0-1
C) mixed
D) all of the above

Question 75

In a ________ integer model, some solution values for decision variables are integers and others can be non-integer.

A) total
B) 0-1
C) mixed
D) all of the above

Question 76

Max Z =   x1 + 6x2
Subject to: 17x1 + 8x2 ? 136
     3x1 + 4x2 ? 36
    x1, x2 ? 0 and integer

Find the optimal solution.

Question 77

You have been asked to select at least 3 out of 7 possible sites for oil exploration. Designate each site as S1, S2, S3, S4, S5, S6, and S7. The restrictions are:
Restriction 1. Evaluating sites S1 and S3 will prevent you from exploring site S7.
Restriction 2. Evaluating sites S2 or S4 will prevent you from assessing site S5.
Restriction 3. Of all the sites, at least 3 should be assessed.
Assuming that Si is a binary variable, write the constraint for the third restriction.

Question 78

Max Z = 3x1 + 5x2
Subject to: 7x1 + 12x2 ? 136
       3x1 + 5x2 ? 36
       x1, x2 ? 0 and integer

Find the optimal solution.

Question 79

Solve the following integer linear program graphically.
MAX Z = 5x1 + 8x2
s.t. x1 + x2 ? 6
   5x1 + 9x2 ? 45
   x1, x2 ? 0 and integer

Question 80

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) always
B) sometimes
C) optimally
D) never