Question 1

The branching part of the branch and bound algorithm that Solver uses to solve integer programming models means that the algorithm:

Accepted Answer

The branching part of the branch and bound algorithm involves creating subsets of solutions, which are systematically explored to find the optimal solution.

Question 2

The default integer optimality setting in Solver is:

Accepted Answer

D

Question 3

Any integer program involving 0 − 1 variables with ____ constraint(s)is called a knapsack problem.

Accepted Answer

A knapsack problem typically involves a single constraint that limits the total weight or value that can be included in the knapsack, making option C correct.

Question 4

Problems with a fixed cost that is incurred only if an activity is undertaken at a positive level are inherently nonlinear.

Accepted Answer

Fixed costs that are incurred only if an activity is undertaken at a positive level introduce a discontinuity or step in the cost function, making the relationship between cost and activity level inherently nonlinear.

Question 5

Many inherently nonlinear problems can be transformed into linear models with the use of:

Accepted Answer

Binary variables can be used to linearize nonlinear constraints, such as the logical OR or logical AND constraints, through the introduction of additional linear constraints. This technique is known as Binary Integer Programming or Mixed Integer Linear Programming. Moreover, binary variables can be used to represent the on-off behavior of decision variables in many applications, such as scheduling, routing, and network flow problems. Therefore, C) is the best choice for transforming nonlinear problems into linear models.

Question 6

Fixed costs imply that the divisibility assumption of linear models no longer holds.

Accepted Answer

Fixed costs do not affect the divisibility assumption of linear models; they simply do not vary with the level of output or activity, unlike variable costs. The divisibility assumption refers to the ability to divide inputs and outputs into any size, which is independent of the nature of the costs involved.

Question 7

Optimization software,including Solver,typically has more difficulty solving an integer programming problem,relative to a linear programming problem.

Accepted Answer

Integer programming problems require the variables to take on only integer values, which makes the problem more complex and difficult to solve than a linear programming problem where variables can take on any real value.

Question 8

During the solution of a maximization problem with the branch and bound algorithm,an incumbent solution represents an upper bound on the solution.

Accepted Answer

In a maximization problem, an incumbent solution represents the current best solution found and acts as a lower bound for the solution, not an upper bound.

Question 9

The LP relaxation of an integer programming (IP)problem is typically easy to solve and provides a bound for the IP model.

Accepted Answer

The LP relaxation of an IP problem involves relaxing the integral constraints to allow real-valued solutions. This relaxed problem can be solved efficiently using linear programming techniques. Moreover, the optimal value of the LP relaxation provides a lower bound for the optimal value of the original IP problem. Thus, the statement is true.

Question 10

In a model with 8 changing cells,all of which are constrained to be binary,the number of potentially feasible solutions is:

Accepted Answer

Each binary cell can have 2 possible values (0 or 1). For 8 binary cells, the number of possible combinations is 2^8 = 256.

Question 11

An algorithm which uses implicit enumeration:

Accepted Answer

Implicit enumeration algorithms work by systematically considering all possible solutions but use various strategies to exclude large subsets of solutions that are guaranteed to be suboptimal, thus making the search process more efficient.

Question 12

The binary variables in the fixed cost models correspond to:

Accepted Answer

Binary variables in fixed cost models correspond to processes or activities for which a fixed cost occurs, such as whether to purchase or not purchase a piece of equipment, whether to outsource or not outsource a process, or whether to perform maintenance or not perform maintenance. They are not related to the number of units or products produced, total profit, or amount of labor hours.

Question 13

In a set-covering model,each member of a given set (set 1)must be "covered" by all members of another set (set 2).

Accepted Answer

In a set-covering model, each member of set 1 must be covered by at least one member of set 2, not necessarily by all members of set 2.

Question 14

The branch and bound algorithm uses:

Accepted Answer

The branch and bound algorithm works by dividing a problem into smaller subproblems or branches, and at each branch, it uses both upper and lower bounds to determine if it is worthwhile to explore further or if the branch can be pruned. The lower bound helps to create an initial estimate of the solution, while the upper bound helps to determine a maximum limit beyond which no solution can be found. By using both bounds, the algorithm can reduce the search space and find the optimal solution efficiently. Therefore, the best choice is to use both upper and lower bounds.

Question 15

Rounding the solution of a linear programming to the nearest integer values provides an:

Accepted Answer

Rounding the solution of a linear programming to the nearest integer values might provide an optimal solution, but it is not guaranteed. It is possible that rounding leads to a suboptimal solution. However, it is known that if the original LP has an optimal solution that is integer-valued, then rounding the solution will give the optimal integer solution. Therefore, rounding can be a useful technique when solving integer programming problems or when an exact solution is not necessary.

Question 16

Solver may be unable to solve some integer programming problems,even when they have an optimal solution.

Accepted Answer

Integer programming problems can be inherently difficult to solve, even for state-of-the-art solvers. There are cases where the solver is not able to determine the optimal solution, even though one exists. Such problems are referred to as infeasible or unbounded.

Question 17

Complete enumeration of all possible solutions in many integer programming problems is impractical.

Accepted Answer

Complete enumeration of all possible solutions in many integer programming problems would involve checking an exponentially large number of solutions, making it impractical.

Question 18

In a linear model,the target cell and constraints are ultimately:

Accepted Answer

In a linear model, the target cell and constraints are ultimately represented as a sum of products of constants and changing cells. This is the standard form of a linear program, where the objective function (target cell) and the constraints are expressed as linear equations in terms of decision variables (changing cells). The coefficients of the decision variables in these equations are constants that reflect the contribution of each variable to the objective or constraint. The optimal solution to the linear program is found by maximizing or minimizing the objective function, subject to the constraints.

Question 19

If Solver fails to find an optimal solution to an integer programming problem,we might be able to find a near optimal solution by specifying a smaller number for the integer optimality setting.

Accepted Answer

The answer of If Solver fails to find an optimal...

Question 20

The higher the upper bound produced for a maximization problem in the branch and bound solution process,the faster the algorithm will be.

Accepted Answer

The statement is incorrect. The opposite is true - the higher the upper bound, the slower the algorithm will likely be because it will have to explore more nodes to find the optimal solution. Lower bounds, on the other hand, can help prune the search tree and speed up the algorithm.

Quiz 6: Optimization Models With Integer Variables