Question 1

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

Accepted Answer

The classic assignment problem involves assigning n jobs to n workers such that the total cost is minimized. The optimal solution will indeed consist of 0s and 1s, where a 0 represents that a worker is not assigned a job and a 1 represents that a worker is assigned a job. This is because each worker can only be assigned one job, so if a worker is assigned a job, the corresponding variable in the LP formulation will be 1, and if not assigned, it will be 0.

Question 2

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

Accepted Answer

Integer linear programs involve discrete variables and can have multiple optimal solutions or infeasible solutions, making them more complex to solve than linear programs with continuous variables.

Question 3

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

Accepted Answer

The LP relaxation of an integer program may have a feasible solution that is not an integer, which means the integer program itself may not have a feasible solution.

Question 4

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

Accepted Answer

If y₁ is 0, then the inequality reduces to 0 ≤ 0, which is always true for any values of x₁ and x₂. Therefore, x₁ and x₂ can be any values, including 0.

Question 5

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

Accepted Answer

Most practical applications of integer linear programming involve variables that are either 0 or 1, making them binary variables. However, it is possible for integer linear programming problems to involve variables with larger ranges of integer values.

Question 6

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

Accepted Answer

The LP relaxation drops the integer restrictions from the IP problem and solves it as a linear programming problem.

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.

Accepted Answer

This statement accurately describes the function of a 0-1 variable in a model involving fixed costs. The 0-1 variable is typically used to indicate whether or not a particular resource or capacity is available, and by setting it to 0 until the associated fixed cost is incurred, the model ensures that the capacity is not included in calculations or decision-making until it is actually feasible to use it.

Question 8

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

Accepted Answer

A multiple-choice constraint typically involves selecting exactly one alternative from a set of options, not multiple.

Question 9

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 10

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

Accepted Answer

Slack and surplus variables are often used in integer linear programming to handle inequalities and constraints with slack or surplus. They help to convert such inequalities into equations that can be solved using integer linear programming. Therefore, slack and surplus variables are useful in integer linear programming.

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.​

Accepted Answer

Reduced costs, dual values, and sensitivity ranges are not applicable in integer programming because the variables can only take on integer values, making the analysis of small changes in the variables irrelevant. Therefore, their values are not included in the computer output 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.

Accepted Answer

A product design and market share optimization problem indeed involves choosing a product design that can attract the maximum number of consumers, which will result in an increased market share. Therefore, the statement is true.

Question 13

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

Accepted Answer

These types of linear programming problems are known as integer programming problems. They have additional constraints that require the variables to take on integer values. Solving integer programming problems is generally more difficult than solving linear programming problems because it involves exploring a discrete set of possible solutions.

Question 14

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

Accepted Answer

If the LP relaxation problem has an optimal solution that is an integer, then that solution satisfies all the constraints of both the LP relaxation problem and the integer linear program. Since the integer linear program is a more restrictive version of the LP relaxation problem, the optimal solution to the integer linear program is either the same as the optimal solution to the LP relaxation problem or a better solution. Therefore, if the LP relaxation problem's optimal solution is an integer, it is also 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.

Accepted Answer

Integer linear programs (ILPs) are generally more sensitive to changes in constraint coefficients than linear programs (LPs) because the feasible region for ILPs is discrete, and small changes can lead to different optimal solutions or make a previously feasible solution infeasible.

Question 16

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

Accepted Answer

The correct constraint to ensure project 5 is completed before project 6 would typically be in the form of x₅ ≤ x₆, indicating that the start or completion time of project 5 is before or equal to the start or completion time of project 6. The given constraint seems to be incorrectly formulated for this purpose.

Question 17

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

Accepted Answer

Binary variables can indeed be used to model multiple-choice and mutually exclusive constraints. For example, if we have the choice between options A, B, and C, we can use binary variables x_A, x_B, and x_C to represent whether or not each option is selected. Since only one option can be selected, we can add the constraint x_A + x_B + x_C = 1 to ensure that the variables are mutually exclusive.

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.

Accepted Answer

If all constraints have less-than-or-equal-to inequalities with positive coefficients, rounding down all variables will never violate any constraints since it will always result in a smaller but still valid solution. Therefore, 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.

Accepted Answer

The given constraint does not imply that if project 1 is selected, project 2 cannot be. It simply states a relationship between two specific conditions or states of projects 1 and 2, without excluding the possibility of both projects being selected under different conditions or configurations.

Question 20

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

Accepted Answer

The constraint actually means that the sum of the selected projects (among the first four mentioned) cannot exceed 2, which implies that at most two of these projects can be selected, not that exactly two must be selected.

Quiz 7: Integer Linear Programming