Question 1

The branch and bound method is a solution technique specifically limited to integer programming problems.

Accepted Answer

The branch and bound method is a general algorithm used for finding optimal solutions to various optimization problems, including but not limited to integer programming. It is also applicable to problems in areas such as combinatorial optimization and mixed-integer programming.

Question 2

In implicit enumeration the feasible integer solutions closest to the optimal non-integer solution are evaluated to see which is best.

Accepted Answer

Implicit enumeration is a technique used in integer programming where all possible solutions are systematically evaluated through a process of branching and bounding, rather than evaluating feasible integer solutions closest to the optimal non-integer solution.

Question 3

The number of nodes considered in a branch and bound tree for maximization integer programming problems is always minimized by going to the node with the largest upper bound.

Accepted Answer

The branch and bound algorithm for maximization integer programming problems always goes to the node with the largest upper bound because this node has the potential to yield the best solution.

Question 4

Rounding non-integer solution values up to the nearest integer value can result in an infeasible solution.

Accepted Answer

Rounding non-integer values up to the nearest integer can result in a value that is too high and violates constraints or makes the solution infeasible. Therefore, it is important to consider the feasibility of the solution before rounding non-integer values.

Question 5

In solving a maximization problem, the optimal profit associated with the relaxed solution (LP-relaxation) is always less than or equal to the value of the optimal profit associated with the integer solution.

Accepted Answer

In a maximization problem, the optimal profit of the LP-relaxation (where the integer constraints are relaxed to allow for fractional values) is always greater than or equal to the optimal profit of the integer solution, because the relaxation allows for a larger feasible region, potentially including solutions with higher profits that are not available in the integer-constrained version.

Question 6

If an integer programming problem has no feasible solution, then its LP relaxation (relaxed solution) must also have no feasible solution.

Accepted Answer

The LP relaxation of an integer programming problem allows for fractional values, which can make feasible solutions available that are not feasible under the integer constraints. This means that even if the original integer programming problem has no feasible solution, its LP relaxation might still have feasible solutions.

Question 7

The branch and bound method of solving linear integer programming problems is an enumeration method.

Accepted Answer

The branch and bound method is a systematic enumeration of all possible integer solutions, with the branching element being the integer constraint. Therefore, it is a type of enumeration method.

Question 8

A linear programming model solution with no integer restrictions is called a relaxed solution.

Accepted Answer

A linear programming model solution with no integer restrictions is called a relaxed solution. It is relaxed because it allows for fractional values for the decision variables. When integer restrictions are added to the model, it becomes an integer linear programming (ILP) model.

Question 9

The branch and bound method is a solution approach that partitions the feasible solution space into smaller subsets of solutions.

Accepted Answer

This is an accurate description of the branch and bound method.

Question 10

A linear programming model solution with integer restrictions is called a relaxed solution.

Accepted Answer

A linear programming model solution with integer restrictions is called an integer solution. A relaxed solution is a solution to a linear programming model without integer restrictions.

Question 11

The branch and bound method is a solution approach that partitions the infeasible solution space into smaller subsets of solutions.

Accepted Answer

The branch and bound method partitions the entire solution space into smaller subsets of solutions, not just the infeasible solution space. It is used to systematically consider various candidate solutions in an optimization problem.

Question 12

A feasible solution is ensured by rounding down non-integer solution values.

Accepted Answer

Rounding down non-integer solution values does not ensure a feasible solution, as it may violate constraints or optimality in integer programming problems.

Question 13

A feasible solution is ensured by rounding down integer solution values.

Accepted Answer

Rounding down integer solution values may result in an infeasible solution because it may violate the constraints of the problem. It is safer to round to the nearest integer and then check if the solution satisfies all the constraints.

Question 14

When the branch and bound approach is applied to an integer programming problem, it is used in conjunction with the normal non-integer solution approach.

Accepted Answer

The branch and bound approach is specifically designed for solving integer programming problems, and it involves splitting the problem into smaller subproblems and solving them recursively. It is not used in conjunction with the normal non-integer solution approach.

Question 15

In using the branch and bound method, if a branch gives an infeasible solution to the associated linear programming problem, then the particular branch is fathomed and is not considered any further.

Accepted Answer

If a branch gives an infeasible solution, then it is known that no feasible solution exists in that branch and it can be fathomed (or pruned) without further consideration.

Question 16

When using branch and bound for a maximization integer programming problem, the lower bound at the initial node can always be determined by rounding down the LP relaxation solution values regardless of the types of constraints in the problem.

Accepted Answer

The lower bound in a branch and bound algorithm for a maximization problem is typically determined by solving the LP relaxation of the problem, not simply by rounding down the solution values. The LP relaxation allows fractional values and provides a bound on the optimal integer solution, but the process involves solving the LP, not just rounding.

Question 17

The branch and bound solution method cannot be applied to 0-1 integer programming problems.

Accepted Answer

The branch and bound method is a commonly used algorithm for solving 0-1 integer programming problems.

Question 18

If an integer linear programming problem has no feasible solution, then its relaxed solution (LP relaxation) must also have no feasible solution

Accepted Answer

The LP relaxation of an integer linear programming problem allows for fractional values, which can result in feasible solutions even when the original integer problem has none. This is because relaxing the integer constraints can expand the feasible region.

Question 19

An infeasible solution is ensured by rounding down non-integer solution values.

Accepted Answer

Rounding down non-integer solution values will result in a feasible solution, but it may not be the optimal solution. An infeasible solution cannot be obtained by rounding down.

Question 20

A rounded-down integer solution can result in a less than optimal solution.

Accepted Answer

When rounding down, we are essentially ignoring the fractional part of a number. This can result in a solution that is lower than the actual optimal solution, which may require using the fractional part. For example, if we are trying to divide a cake into equal parts and we round down the number of slices, it may result in some people getting smaller slices than if we had used a more precise calculation.

Quiz 19: Integer Programming: the Branch and Bound Method