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 ILP is obtained by relaxing the integrality constraints of the decision variables to obtain a linear program. Solving the LP relaxation provides an upper bound for the value of the objective function since this linear program solution may use fractional values for the decision variables. This upper bound provides a benchmark to compare the solutions obtained by solving the ILP with integer values of the decision variables.

Question 2

If the optimal solutionASW8 to the LP relaxation problem is integer,it is the optimal solution to the integer linear program.

Accepted Answer

If the LP relaxation problem provides an optimal integer solution, it means that there are no better fractional solutions that can be rounded up or down to an integer solution. Since the linear program is a relaxation of the integer program, any optimal solution to the integer program must be feasible in the LP relaxation problem. Therefore, the optimal solution to the LP relaxation problem is also the optimal solution to the integer linear program.

Question 3

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

Fixed costs are independent of the level of production or decision variables, and can be represented by 0-1 variables in the ILP formulation. Adding fixed costs to the objective function may result in incorrect solutions, as it would not consider the impact of fixed costs on the decision variables. Multiple-choice constraints and LP relaxation are not necessary for modeling fixed cost problems.

Question 4

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, but maintains the objective function and constraints of the IP problem.

Question 5

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

Since x₃ can only be 0 or 1, option A and D are feasible. Option B has a non-integer value for x₂, which violates the assumption that it must be an integer. Option C has integer values for both x₁ and x₂ and 0 or 1 for x₃, making it the only feasible option.

Question 6

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 ensures that two tasks or projects have to be completed together, or one cannot be completed without the other. In this scenario project A and project B are interdependent and require completion of each other. So, the appropriate constraint to use is a corequisite constraint.

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

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

Accepted Answer

Slack and surplus variables can be useful in integer linear programs for representing constraints with inequalities, and for converting them into equalities to use in the formulation of the ILP.

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

Accepted Answer

In order for at least two projects to be done, we need the sum of the three variables (indicating the completion of each individual project) to be greater than or equal to 2. Therefore, the answer is A.

Question 10

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 11

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

The answer of To perform sensitivity analysis involving an integer...

Question 12

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

The answer of Rounding the solution of an LP Relaxation...

Question 13

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 14

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 15

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

Question 16

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

Accepted Answer

Feasibility and optimality are the two key criteria that rounded solutions to linear programs must be evaluated for. Sensitivity and duality are not relevant to rounded solutions, and relaxation and boundedness are only indirectly related. Therefore, the best choice is A.

Question 17

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 lead to significant changes in the overall solution, whereas rounding small values can result in significant errors.

Question 18

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

If project 2 can only be done if project 1 is done, then the value of x₂ (project 2) should be less than the value of x₁ (project 1). This can be expressed as x₁ - x₂ > 0. Therefore, the correct choice is D.

Question 19

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 are used to represent whether a particular process is used or not. If the variable takes a value of 1, it means that the corresponding fixed cost has been incurred and the process is being used. If the variable takes a value of 0, it means that the corresponding fixed cost has not been incurred and the process is not being used. Therefore, the correct answer is A) a process for which a fixed cost occurs.

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

Quiz 11: Integer Linear Programming

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

If the optimal solutionASW8 to the LP relaxation problem is integer,it is the optimal solution to the integer linear program.

Modeling a fixed cost problem as an integer linear program requires

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

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

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

Sensitivity analysis for integer linear programming

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

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?

Most practical applications of integer linear programming involve

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

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

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.

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

In an all-integer linear program,

Rounded solutions to linear programs must be evaluated for

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

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 0-1 variables in the fixed cost models correspond to

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

Quiz 11: Integer Linear Programming

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

If the optimal solutionASW8 to the LP relaxation problem is integer,it is the optimal solution to the integer linear program.

Modeling a fixed cost problem as an integer linear program requires

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

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

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

Sensitivity analysis for integer linear programming

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

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?

Most practical applications of integer linear programming involve

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

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

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.

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

In an all-integer linear program,

Rounded solutions to linear programs must be evaluated for

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

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?

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

The graph of a problem that requires x1 and x2 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?

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?

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