Deck 7: Integer Linear Programming

Question 1

For the classic assignment problem,the optimal linear programming solution will consist of 0s and 1s.

Answer 1

True

Question 2

Integer linear programs provide substantial modeling flexibility and thus are harder to solve than linear programs.​

Answer 2

True

Question 3

If the LP Relaxation of an integer program has a feasible solution,then the integer program has a feasible solution.

Answer 3

False

Question 4

If x₁ + x₂ ≤ 500y₁ and y₁ is 0-1,then if y₁ is 0,x₁ and x₂ will be 0.

Question 5

Most practical applications of integer linear programming involve only 0-1 integer variables.

Question 6

The LP Relaxation contains the objective function and constraints of the IP problem,but drops all integer restrictions.

Question 7

In a model involving fixed costs,the 0-1 variable guarantees that the capacity is not available unless the cost has been incurred.

Question 8

A multiple-choice constraint involves selecting k out of n alternatives,where k ≥ 2.

Question 9

In general,rounding large values of decision variables to the nearest integer value causes fewer problems than rounding small values.

Question 10

Slack and surplus variables are not useful in integer linear programs.

Question 11

The computer output for integer programs in the textbook does not include reduced costs,dual values,or sensitivity ranges because these variables are not meaningful for integer programs.​

Question 12

A product design and market share optimization problem involves choosing a product design that maximizes the number of consumers preferring it.

Question 13

Some linear programming problems have a special structure that guarantees the variables will have integer values.

Question 14

If the optimal solution to the LP Relaxation problem is an integer,it is the optimal solution to the integer linear program.

Question 15

Generally,the optimal solution to an integer linear program is less sensitive to the constraint coefficients than is a linear program.

Question 16

If project 5 must be completed before project 6,the constraint would be x₅ − x₆ ≤ 0.

Question 17

Binary variables can be used to model multiple-choice and mutually exclusive constraints.

Question 18

If a problem has only less-than-or-equal-to constraints with positive coefficients for the variables,rounding down will always provide a feasible integer solution.

Question 19

The constraint x₁ − x₂ = 0 implies that if project 1 is selected,project 2 cannot be.

Question 20

The constraint x₁ + x₂ + x₃ + x₄ ≤ 2 means that two out of the first four projects must be selected.

Question 21

In a model,x₁ ≥ 0 and integer,x₂ ≥ 0,and x₃ = 0,1.Which of the following solutions would NOT be feasible?

A)x₁ = 5,x₂ = 3,x₃ = 0
B)x₁ = 4,x₂ = 0.389,x₃ = 1
C)x₁ = 2,x₂ = 3,x₃ = 0.578
D)x₁ = 0,x₂ = 8,x₃ = 0

Question 22

The graph of a problem that requires x₁ and x₂ to be integer has a feasible region

A)the same as its LP Relaxation.
B)consisting of dots.
C)consisting of horizontal stripes.
D)consisting of vertical stripes.

Question 23

Solve the following problem graphically. ​
a.Graph the constraints for this problem.Indicate all feasible solutions.
b.Find the optimal solution to the LP Relaxation.Round down to find a feasible integer solution.Is this solution optimal?
c.Find the optimal solution.

Question 24

Let x₁,x₂,and x₃ be 0-1 variables whose values indicate whether the projects are not done (0)or are done (1).Which of the following answers indicates that at least two of the projects must be done?

A)x₁ + x₂ + x₃ ≥ 2
B)x₁ + x₂ + x₃ ≤ 2
C)x₁ + x₂ + x₃ = 2
D)x₁ − x₂ = 0

Question 25

The solution to the LP Relaxation of a maximization integer linear program provides a(n)

A)upper bound for the value of the objective function.
B)lower bound for the value of the objective function.
C)upper bound for the value of the decision variables.
D)lower bound for the value of the decision variables.

Question 26

In an all-integer linear program,

A)all objective function coefficients must be integer.
B)all right-hand-side values must be integer.
C)all variables must be integer.
D)all objective function coefficients and right-hand-side values must be integer.

Question 27

If the acceptance of project A is conditional on the acceptance of project B,and vice versa,the appropriate constraint to use is a

A)multiple-choice constraint.
B)k out of n alternatives constraint.
C)mutually exclusive constraint.
D)corequisite constraint.

Question 28

Most practical applications of integer linear programming involve

A)only 0-1 integer variables and not ordinary integer variables.
B)mostly ordinary integer variables and a small number of 0-1 integer variables.
C)only ordinary integer variables.
D)a near equal number of ordinary integer variables and 0-1 integer variables.

Question 29

Which of the following applications modeled in the textbook does NOT involve only 0-1 integer variables?

A)supply chain design
B)bank location
C)capital budgeting
D)product design and market share optimization

Question 30

To perform sensitivity analysis involving an integer linear program,it is best to

A)use the dual prices very cautiously.
B)make multiple computer runs.
C)use the same approach as you would for a linear program.
D)use LP Relaxation.

Question 31

In general,whenever rounding has a minimal impact on the objective function and constraints,most managers find it acceptable.

Question 32

The 0-1 variables in the fixed cost models correspond to

A)a process for which a fixed cost occurs.
B)the number of products produced.
C)the number of units produced.
D)the actual value of the fixed cost.

Question 33

Let x1 and x2 be 0-1 variables whose values indicate whether projects 1 and 2 are/are not done.Which of the following answers indicates that project 2 can be done only if project 1 is done?

A)x₁ + x₂ = 1
B)x₁ + x₂ = 2
C)x₁ − x₂ ≤ 0
D)x₁ − x₂ ≥ 0

Question 34

Rounded solutions to linear programs must be evaluated for

A)feasibility and optimality.
B)sensitivity and duality.
C)relaxation and boundedness.
D)All of these are correct.

Question 35

Sensitivity analysis for integer linear programming

A)can be provided only by computer.
B)has precisely the same interpretation as that from linear programming.
C)does not have the same interpretation as that from linear programming and should be disregarded.
D)is most useful for 0-1 models.

Question 36

Assuming W₁,W_2,and W₃ are 0-1 integer variables,the constraint W₁ + W₂ + W₃ < 1 is often called a

A)multiple-choice constraint.
B)mutually exclusive constraint.
C)k out of n alternatives constraint.
D)corequisite constraint.

Question 37

Rounding the solution of an LP Relaxation to the nearest integer values provides a(n)

A)feasible but not necessarily optimal integer solution.
B)integer solution that is optimal.
C)integer solution that might be neither feasible nor optimal.
D)infeasible solution.

Question 38

Solve the following problem graphically. ​
a.Graph the constraints for this problem.Indicate all feasible solutions.
b.Find the optimal solution to the LP Relaxation.Round down to find a feasible integer solution.Is this solution optimal?
c.Find the optimal solution.
​

Question 39

Modeling a fixed cost problem as an integer linear program requires

A)adding the fixed costs to the corresponding variable costs in the objective function.
B)using 0-1 variables.
C)using multiple-choice constraints.
D)using LP Relaxation.

Question 40

Which of the following is the most useful contribution of integer programming?

A)finding whole number solutions where fractional solutions would not be appropriate
B)using 0-1 variables for modeling flexibility
C)increased ease of solution
D)provision for solution procedures for transportation and assignment problems

Question 41

Westfall Company has a contract to produce 10,000 garden hoses for a large discount chain.Westfall 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. ​
a.This problem requires two different kinds of decision variables.Clearly define each kind.
b.The company wants to minimize total cost.Give the objective function.
c.Give the constraints for the problem.
d.Write a constraint to ensure that if machine 4 is used,machine 1 cannot be.

Question 42

Given the following all-integer linear program:
​
Max 15x₁ + 2x₂
s.t. 7x₁ + x₂ < 23
3x₁ - x₂ < 5
x₁,x₂ > 0 and integer
​
a.Solve the problem as an LP,ignoring the integer constraints.
b.What solution is obtained by rounding up fractions greater than or equal to 1/2? Is this the optimal integer solution?
c.What solution is obtained by rounding down all fractions? Is this the optimal integer solution? Explain.
d.Show that the optimal objective function value for the ILP (integer linear programming)is lower than that for the optimal LP.
e.Why is the optimal objective function value for the ILP problem always less than or equal to the corresponding LP's optimal objective function value? When would they be equal? Comment on the optimal objective function of the MILP (mixed-integer linear programming)compared to the corresponding LP and ILP.

Question 43

Your express package courier company is drawing up new zones for the location of drop boxes for customers.The city has been divided into seven zones.You have targeted six possible locations for drop boxes.The list of the seven zones and which drop boxes could be reached easily from each zone is listed below. ​
Let x_i = 1 if drop box location i is used,0 otherwise.Develop a model to provide the smallest number of locations,but make sure that each zone is covered by at least two boxes.​

Question 44

Market Pulse Research has conducted a study for Lucas Furniture on some designs for a new commercial office desk.Three attributes were found to be most influential in determining which desk is most desirable: number of file drawers,the presence or absence of pullout writing boards,and simulated wood or solid color finish.Listed below are the part-worths for each level of each attribute provided by a sample of seven potential Lucas customers.​ ​
Suppose the overall utility (sum of part-worths)of the current favorite commercial office desk is 50 for each customer.What product design will maximize the share of choices for the seven sample participants? Using Excel,formulate and solve this 0-1 integer programming problem.

Question 45

Solve the following problem graphically. ​
a.Graph the constraints for this problem.Indicate all feasible solutions.
b.Find the optimal solution to the LP Relaxation.Round up to find a feasible integer solution.Is this solution optimal?
c.Find the optimal solution.

Question 46

Hansen Controls has been awarded a contract for a large number of control panels.To meet this demand,it will use its existing plants in San Diego and Houston and consider new plants in Tulsa,St.Louis,and Portland.Finished control panels are to be shipped to Seattle,Denver,and Kansas City.Pertinent information is given in the table below.​ ​
Develop a model whose solution would reveal which plants to build and the optimal shipping schedule.

Question 47

Grush Consulting has five projects to consider.Each will require time in the next two quarters according to the table below. ​
Revenue from each project is also shown.Develop a model whose solution would maximize revenue,meet the time budget of 25 in the first quarter and 20 in the second quarter,and not do both projects C and D.

Question 48

Given the following all-integer linear program: ​
a.​
Solve the problem as a linear program ignoring the integer constraints.Show that the optimal solution to the linear program gives fractional values for both x₁ and x₂.
b.​
What solution is obtained by rounding fractions greater than or equal to 1/2 to the next larger number? Show that this solution is not a feasible solution.
c.What is the solution obtained by rounding down all fractions? Is it feasible?
d.​
​
Enumerate all points in the linear programming feasible region in which both x₁ and x₂ are integers,and show that the feasible solution obtained in part (c)is not optimal and that in fact the optimal integer is not obtained by any form of rounding.

Question 49

Consider a capital budgeting example with five projects from which to select.Let x_i = 1 if project i is selected,0 if not,for i = 1,… ,5.Write the appropriate constraint(s)for each condition.Conditions are independent.
a.Choose no fewer than three projects.
b.If project 3 is chosen,project 4 must be chosen.
c.If project 1 is chosen,project 5 must not be chosen.
d.Projects cost 100,200,150,75,and 300,respectively.The budget is 450.
e.No more than two of projects 1,2,and 3 can be chosen.

Question 50

Kloos Industries has projected the availability of capital over each of the next three years to be $850,000,$1,000,000,and $1,200,000,respectively.It is considering four options for the disposition of the capital:
a.Research and development of a promising new product
b.Plant expansion
c.Modernization of its current facilities
d.Investment in a valuable piece of nearby real estate
​
Monies not invested in these projects in a given year will NOT be available for the following year's investment in the projects.The expected benefits three years hence from each of the four projects and the yearly capital outlays of the four options are summarized in the table below in millions of dollars.
In addition,Kloos has decided to undertake exactly two of the projects.If plant expansion is selected,it will also modernize its current facilities.
​
Formulate and solve this problem as a binary programming problem.

Question 51

A business manager for a grain distributor is asked to decide how many containers of each of two grains to purchase to fill its 1,600-pound capacity warehouse.The table below summarizes the container size,availability,and expected profit per container upon distribution.​ ​
a.Formulate as a linear program with the decision variables representing the number of containers purchased of each grain.Solve for the optimal solution.
b.What would be the optimal solution if you were not allowed to purchase fractional containers?
c.There are three possible results from rounding an LP solution to obtain an integer solution:
(1)The rounded optimal LP solution will be the optimal IP solution.
(2)The rounded optimal LP solution gives a feasible,but not optimal IP solution.
(3)The rounded optimal LP solution is an infeasible IP solution.
​
For this problem,(i)round down all fractions; (ii)round up all fractions; and (iii)round off (to the nearest integer)all fractions (Note: Two of these are equivalent.)Which result above (1,2,or 3)occurred under each rounding method?

Question 52

Given the following all-integer linear programming problem:
​
Max 3x₁ + 10x₂
​
s.t.2x₁ + x₂ < 5
x₁ + 6x₂ < 9
x₁ - x₂ > 2
x₁,x₂ > 0 and integer
​
a.Solve the problem graphically as a linear program.
b.Show that there is only one integer point and that it is optimal.
c.Suppose the third constraint was changed to x₁ - x₂ > 2.1.What is the new optimal solution to the LP? To the ILP?