Question 1

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

Accepted Answer

Sensitivity analysis in integer linear programming often requires multiple computer runs because changes in parameters can lead to different integer solutions, unlike linear programming where dual prices can be used more directly.

Question 2

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

Accepted Answer

A mutually exclusive constraint restricts the variables so that only one of them can take value 1. This is exactly what the constraint W₁ + W₂ + W₃ < 1 does, since it ensures that the sum of these variables is less than 1, meaning that at most one of them can take the value 1. Multiple-choice, k out of n alternatives, and corequisite constraints have different definitions and are not applicable in this case.

Question 3

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

Accepted Answer

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

Question 4

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

Accepted Answer

x₃ must be either 0 or 1, but in option C, x₃ is 0.578, which is not allowed.

Question 5

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

Accepted Answer

The appropriate constraint to use is a corequisite constraint, which indicates that two or more activities must be performed together or in a specific order. In this case, the acceptance of project A is a prerequisite for the acceptance of project B, and vice versa. Therefore, these two projects are corequisite and must be considered together.

Question 6

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

Accepted Answer

The feasible region for an integer programming problem consists of discrete points (dots) where both x₁ and x₂ are integers, unlike the continuous region of its LP relaxation.

Question 7

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

Accepted Answer

The 0-1 variables in the fixed cost models correspond to a process for which a fixed cost occurs. These variables help determine whether or not a fixed cost is incurred for a particular process or activity.

Question 8

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

Accepted Answer

This is true, as many real-world problems can be formulated as binary integer linear programs, where the variables are restricted to taking on only binary (0 or 1) values. This simplifies the problem, making it easier to solve using specialized algorithms. However, there are also cases where integer linear programming involves variables that can take on values other than 0 or 1.

Question 9

Most practical applications of integer linear programming involve

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 10

Solve the following problem graphically.
Max
5X + 6Y
s.t.
17X + 8Y ≤ 136
3X + 4Y ≤ 36
X, Y ≥ 0 and integer
​
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.

Accepted Answer

The answer of Solve the following problem graphically.
Max
5X + 6Y
s.t.
17X...

Question 11

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

Accepted Answer

The LP relaxation of an integer linear program removes the integer constraints, potentially increasing the objective function value, thus providing an upper bound for the integer program's objective function.

Question 12

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

Accepted Answer

Rounding the solution of an LP Relaxation to the nearest integer values can result in a solution that violates the integer constraints or other constraints of the original integer programming problem, making it potentially neither feasible nor optimal.

Question 13

Sensitivity analysis for integer linear programming

Accepted Answer

The answer of Sensitivity analysis for integer linear programming
...

Question 14

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?

Accepted Answer

The inequality x₁ + x₂ + x₃ ≥ 2 ensures that the sum of the variables is at least 2, meaning at least two projects must be done.

Question 15

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

Accepted Answer

Integer linear programs are NP-hard, meaning they are computationally more complex to solve than linear programs, which can be solved in polynomial time.

Question 16

Rounded solutions to linear programs must be evaluated for

Accepted Answer

Rounded solutions to linear programs must be checked for feasibility to ensure they satisfy all constraints, and for optimality to ensure they provide the best possible value for the objective function.

Question 17

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?

Accepted Answer

The condition "project 2 can be done only if project 1 is done" translates to x₂ ≤ x₁, which is equivalent to x₁ − x₂ ≥ 0.

Question 18

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

Accepted Answer

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

Question 19

Modeling a fixed cost problem as an integer linear program requires

Accepted Answer

Using 0-1 variables allows for the modeling of fixed costs in an integer linear program, as the fixed cost is incurred if and only if the corresponding variable is positive.

Question 20

In an all-integer linear program,

Accepted Answer

In an all-integer linear program, the integer constraint applies only to the decision variables. The objective function coefficients and right-hand side values may take on any real value. Therefore, choice C is the only correct option.

Quiz 7: Integer Linear Programming

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

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

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

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

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

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

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

Most practical applications of integer linear programming involve

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

Sensitivity analysis for integer linear 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?

Integer linear programs are harder to solve than linear programs.

Rounded solutions to linear programs must be evaluated for

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?

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

Modeling a fixed cost problem as an integer linear program requires

In an all-integer linear program,

Quiz 7: Integer Linear Programming

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

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

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

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

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

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

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

Most practical applications of integer linear programming involve

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

Sensitivity analysis for integer linear 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?

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

Rounded solutions to linear programs must be evaluated for

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?

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

Modeling a fixed cost problem as an integer linear program requires

In an all-integer linear program,

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

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

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

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

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

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?

Integer linear programs are harder to solve than linear programs.

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?