Question 1

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 of the decision variables. Therefore, the solution to the LP relaxation provides an upper bound for the value of the objective function, but not necessarily for the decision variables.

Question 2

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

C

Question 3

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

Accepted Answer

Rounding large values to the nearest integer is less likely to result in significant changes to the overall solution of a problem compared to rounding small values, which can cause a significant shift in the solution. Additionally, large values tend to have less precision and rounding them may not have a significant impact on the overall objective function.

Question 4

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 5

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 integer linear programming involves making multiple computer runs to test the stability of the solution under different parameter values. This is because changes in the parameter values can lead to different feasible solutions in integer programming. Using the dual prices or LP relaxation may not accurately capture the integer constraints and may not provide accurate sensitivity information. Therefore, B is the best choice.

Question 6

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₁ F1F1F1S1F1F1F10 x₂ F1F1F1S1F1F1F10 0 D)x₁ F1F1F1S1F1F1F10 x₂ F1F1F1S1F1F1F10 0

Accepted Answer

The logical condition for project 2 to be done only if project 1 is done is represented by x₁ F1F1F1S1F1F1F10 x₂ F1F1F1S1F1F1F10 0. This means that if x₁ equals 0 (project 1 is not done), then x₂ must also be 0 (project 2 is not done). However, if x₁ equals 1 (project 1 is done), then x₂ can be either 1 or 0, indicating that project 2 can only be done if project 1 is already done.

Question 7

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 8

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 9

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₃ F1F1F1S1F1F1F10 2 B)x₁ + x₂ + x₃ F1F1F1S1F1F1F10 2 C)x₁ + x₂ + x₃ = 2 D)x₁ F1F1F1S1F1F1F10 x₂ = 0

Accepted Answer

The answer of Let x₁ ,x₂ ,and x₃ be 0...

Question 10

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

Feasibility and optimality are the two main criteria used to evaluate the solutions of a linear program. Feasibility ensures that the solution satisfies all the constraints, while optimality ensures that the solution provides the best possible objective function value. Rounded solutions must meet both of these criteria to be considered valid solutions. Sensitivity and duality are concepts related to the structure and properties of linear programming problems, but are not directly related to the evaluation of solutions. Relaxation and boundedness are also important concepts, but again, not directly related to the evaluation of solutions.

Question 11

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

A mutually exclusive constraint means that only one of the variables can take a value of 1. This is exactly what the given constraint W₁ + W₂ + W₃ < 1 requires. Therefore, the best choice is B, mutually exclusive constraint.

Question 12

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

The correct constraint to use in this situation is a corequisite constraint. This is because the acceptance of project A and project B is dependent on each other, meaning they must both be accepted or neither can be accepted. A corequisite constraint ensures that these two tasks are linked together and cannot be worked on separately.

Question 13

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, only the variables must be integers, the objective function coefficients and right-hand side values can be integers or non-integers.

Question 14

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 answer of The graph of a problem that requires...

Question 15

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

To model a fixed cost problem as an integer linear program, we should use 0-1 variables (also known as binary variables) to represent whether or not each expense is incurred. The fixed cost can then be added to the objective function as a constant.

Question 16

In a model,x₁ F1F1F1S1F1F1F10 0 and integer,x₂ F1F1F1S1F1F1F10 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, all variables are either binary or integer. Therefore, option B is not feasible as the value of x₂ is given as 0.389 which is not an integer or binary value. Option A and D are feasible solutions. Option C is also feasible as all variables have integer values and satisfy the given constraints.

Question 17

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

Accepted Answer

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

Question 18

The solution to the LP Relaxation of a minimization problem will always be less than or equal to the value of the integer program minimization problem.

Accepted Answer

The answer of The solution to the LP Relaxation of...

Question 19

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 because they are used to model decision-making situations where choices are binary (e.g., yes/no, true/false, included/excluded).

Question 20

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

The 0-1 variables in fixed cost models represent whether a certain process or option is chosen or not. They do not correspond to the number of products or units produced, nor do they represent the actual value of the fixed cost.

Quiz 11: Integer Linear Programming

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

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

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

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

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

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?

Sensitivity analysis for integer linear programming

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

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?

Rounded solutions to linear programs must be evaluated for

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

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

In an all-integer linear program,

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

Modeling a fixed cost problem as an integer linear program requires

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

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

The solution to the LP Relaxation of a minimization problem will always be less than or equal to the value of the integer program minimization problem.

Most practical applications of integer linear programming involve

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

Quiz 11: Integer Linear Programming

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

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

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

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

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

Let x1 and x2 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?

Sensitivity analysis for integer linear programming

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

Let x1 ,x2 ,and x3 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?

Rounded solutions to linear programs must be evaluated for

Assuming W1,W2 and W3 are 0 - 1 integer variables,the constraint W1 + W2 + W3 < 1 is often called a

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

In an all-integer linear program,

The graph of a problem that requires x1 and x2 to be integer has a feasible region

Modeling a fixed cost problem as an integer linear program requires

In a model,x1  0 and integer,x2  0,and x3 = 0,1.Which solution would not be feasible?

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

The solution to the LP Relaxation of a minimization problem will always be less than or equal to the value of the integer program minimization problem.

Most practical applications of integer linear programming involve

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

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?

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?

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

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

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