Question 1

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.

Accepted Answer

In an all-integer linear program, the only requirement is that all variables must be integer. The objective function coefficients and right-hand side values can be any real number.

Question 2

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.

Accepted Answer

Most practical applications of integer linear programming involve primarily 0-1 integer variables, which are used to model decision-making situations where choices are binary (e.g., yes/no, true/false). This allows for a wide range of applications, including scheduling, resource allocation, and logistics, where decisions are often binary in nature. Ordinary integer variables are less common in practical applications due to the complexity they add and the efficiency of solving problems with binary variables.

Question 3

Assuming W₁,W₂ 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.

Accepted Answer

The constraint W₁ + W₂ + W₃ < 1 is often called a mutually exclusive constraint because it means that only one of the three variables can take the value 1 while the other two are forced to be 0. This is equivalent to saying that the three variables are mutually exclusive in the sense that if one takes the value 1, the other two must take the value 0.

Question 4

Rounded solutions to linear programs must be evaluated for
A)feasibility and optimality.
B)sensitivity and duality.
C)relaxation and boundedness.
D)each of these choices are true.

Accepted Answer

Rounded solutions to linear programs must be evaluated for both feasibility and optimality to ensure that the solution is both valid and optimal. Sensitivity and duality are important concepts, but not directly related to rounded solutions. Relaxation and boundedness are also important, but relate more to the linear programming problem as a whole rather than just rounded solutions.

Question 5

Rounding the solution of an LP Relaxation to the nearest integer values provides
A)a feasible but not necessarily optimal integer solution.
B)an integer solution that is optimal.
C)an integer solution that might be neither feasible nor optimal.
D)an infeasible solution.

Accepted Answer

Rounding the solution of an LP Relaxation to the nearest integer values might result in an integer solution that is neither feasible (it might violate some of the integer problem's constraints) nor optimal (it might not be the best possible solution within the feasible region of the integer problem).

Question 6

To perform sensitivity analysis involving an integer linear program,it is recommended 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.

Accepted Answer

Sensitivity analysis for an integer linear program requires making multiple computer runs, because it is often difficult to determine the impact of changes to the objective function or constraints on the optimal solution. The use of dual prices is not recommended, as they may not provide accurate information for an integer program. Using the same approach as for a linear program or LP relaxation may also not be appropriate, as the integer constraints can significantly impact the solution.

Question 7

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.

Accepted Answer

In fixed cost models, the 0-1 variables correspond to a process for which a fixed cost occurs. These variables are used to represent whether or not a particular process or activity is chosen, which in turn determines whether or not the fixed cost associated with that process is incurred. The other options do not accurately describe the role of 0-1 variables in fixed cost models.

Question 8

Which of the following applications modeled in the textbook is an example of a fixed cost problem?​
A)​supply chain design
B)​bank location
C)​capital budgeting
D)​product design and market share optimization

Accepted Answer

Supply chain design often involves determining the number and location of facilities, such as warehouses or factories, which are typically associated with fixed costs. Fixed costs are expenses that do not change with the level of output or sales, such as rent, salaries, or the cost of purchasing and maintaining equipment. In supply chain design, these costs are crucial for deciding where to place new facilities and how to structure the supply chain network efficiently.

Question 9

​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

Accepted Answer

The answer of ​Which of the following applications modeled in...

Question 10

The solution to the LP Relaxation of a maximization integer linear program provides
A)an upper bound for the value of the objective function.
B)a lower bound for the value of the objective function.
C)an upper bound for the value of the decision variables
D)a lower bound for the value of the decision variables

Accepted Answer

The LP Relaxation of an integer linear program relaxes the integrality constraints on the decision variables, resulting in a linear program that can be solved using standard techniques such as the simplex method. The solution to this relaxed linear program provides an upper bound for the optimal value of the original integer linear program. Therefore, choice A is correct – the solution to the LP relaxation provides an upper bound for the value of the objective function.

Question 11

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

Accepted Answer

The answer of Which of the following is the most...

Question 12

In a model,x₁ ≥ 0 and integer,x₂ ≥ 0,and x₃ = 0,1.Which solution would not be feasible? A)x₁ = 5,x₂ = 3,x₃ = 0 B)x₁ = 4,x₂ = .389,x₃ = 1 C)x₁ = 2,x₂ = 3,x₃ = .578 D)x₁ = 0,x₂ = 8,x₃ = 0

Accepted Answer

In the given model, x₁ and x₂ are both non-negative integers, while x₃ can only take the values of 0 or 1. Therefore, option A and D are feasible, as they satisfy the given constraints. Option B is not feasible, as x₂ is not an integer. Option C is not feasible, as x₂ is a non-integer value. Hence, the answer is C.

Question 13

Let x₁ ,x₂ ,and x₃ be 0 - 1 variables whose values indicate whether the projects are not done (0)or are done (1).Which answer below 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

Accepted Answer

The correct answer is A because it ensures that the sum of the variables is at least 2, meaning at least two projects must be done.

Question 14

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 and should be disregarded.
D)is most useful for 0 - 1 models.

Accepted Answer

The answer of Sensitivity analysis for integer linear programming
A)can be...

Question 15

​Integer linear programs are harder to solve than linear programs.

Accepted Answer

Integer linear programs involve additional constraints on the integer values of the decision variables, causing the problem to become more complex and harder to solve than regular linear programs.

Question 16

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.

Accepted Answer

A corequisite constraint is appropriate when the acceptance of one project is dependent on the acceptance of another project. This is the case when the acceptance of project A is conditional on the acceptance of project B, and vice versa.

Question 17

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.

Accepted Answer

Modeling a fixed cost problem as an integer linear program requires the use of 0-1 variables, also known as binary variables. These variables can take on only two values, 0 or 1, which helps to enforce the fixed cost constraint in the objective function. By multiplying each binary variable by the fixed cost amount, the fixed cost is effectively added to the objective function when the variable is equal to 1, and is not added when the variable is equal to 0.

Question 18

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

Accepted Answer

While many applications of integer linear programming may involve only 0-1 integer variables, this is not always the case. Integer linear programming allows for the use of any integer variables, including those with values other than 0 and 1.

Question 19

Let x₁ and x₂ be 0 - 1 variables whose values indicate whether projects 1 and 2 are not done or are done.Which answer below 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

Accepted Answer

The expression x₁ - x₂ represents the condition that project 2 can be done only if project 1 is done. If project 1 is not done (x₁ = 0), then the entire expression evaluates to a negative value, indicating that project 2 cannot be done. If project 1 is done (x₁ = 1), then the expression evaluates to either 0 or a positive value, indicating that project 2 can potentially be done. Therefore, the condition x₁ - x₂ ≥ 0 ensures that project 2 can only be done if project 1 is done.

Question 20

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)of dots. C)of horizontal stripes. D)of vertical stripes.

Accepted Answer

The constraints x₁ and x₂ being integers mean that the solution points must be discrete, represented as dots on the graph, rather than continuous lines or areas.

Quiz 11: Integer Linear Programming

In an all-integer linear program,

Most practical applications of integer linear programming involve

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

Rounded solutions to linear programs must be evaluated for

Rounding the solution of an LP Relaxation to the nearest integer values provides

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

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

Which of the following applications modeled in the textbook is an example of a fixed cost problem?

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

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

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

In a model,x₁ ≥ 0 and integer,x₂ ≥ 0,and x₃ = 0,1.Which solution would not be feasible?

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

Sensitivity analysis for integer linear programming

Integer linear programs are harder to solve than linear programs.

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

Modeling a fixed cost problem as an integer linear program requires

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

Let x₁ and x₂ be 0 - 1 variables whose values indicate whether projects 1 and 2 are not done or are done.Which answer below indicates that project 2 can be done only if project 1 is done?

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