Deck 13: Integer Linear Optimization Models

Question 1

In order to choose the best solution for implementation, practitioners usually recommend re-solving the integer linear program several times with variations in the

A)objective function.
B)decision variables.
C)constraint coefficients.
D)integer constraints.

Answer 1

constraint coefficients.

Question 2

The objective function for a linear optimization problem is: Max 3x + 5y, with constraints x ≥ 0, y ≥ 0 and x and y are both integers and they are also the only decisions variables. This is an example of a(n)

A)all-integer linear program.
B)mixed-integer linear program.
C)nonlinear program.
D)binary integer linear program.

Answer 2

all-integer linear program.

Question 3

In a binary integer linear program, the integer variables take only the values

A)0 or 1.
B)0 or 8.
C)1 or 8.
D)1 or -1.

Answer 3

0 or 1.

Question 4

The imposition of an integer restriction is necessary for models where

A)nonnegativity constraints are needed.
B)variables can take negative values.
C)the decision variables cannot take fractional values.
D)possible values of variables are restricted to particular intervals.

Question 5

The __________ approach to solving integer linear optimization problems breaks the feasible region of the LP Relaxation into subregions until the subregions have integer solutions or it is determined that the solution cannot be in the subregion.

A)cutting plane
B)trial-and-error
C)breaking region
D)branch-and-bound

Question 6

The optimal solution to the integer linear program will be an extreme point of the

A)convex hull.
B)objective contour.
C)cutting plane.
D)slope.

Question 7

Which of the following approaches to solving integer linear optimization problems tries to identify the convex hull by adding a series of new constraints that do not exclude any feasible integer points?

A)Branch-and bound approach
B)Cutting plane approach
C)Trial-and-error approach
D)Convex hull approach

Question 8

The objective function for an optimization problem is: Max 5x - 3y, with constraints x ≥ 0, y ≥ 0 and y must be an integer. x and y are the only decisions variables. This is an example of a(n)

A)all-integer linear program.
B)mixed-integer linear program.
C)LP relaxation of the integer linear program.
D)binary integer linear program.

Question 9

The worksheet formulation for integer linear programs and linear programming problems is exactly the same except that the __________ for integer linear programs.

A)objective function using Set Objective in the Solver Parameters dialog box is set to Value Of option
B)decision variables need not be added in By Changing Variable Cells in the Solver Parameters dialog box
C)decision variables must be added in By Changing Variable Cells in the Solver Parameters dialog box along with selecting the Ignore Integer Constraints in the Integer Options dialog box
D)constraints must be added in the Solver Parameters dialog box to identify the integer variables and the value for Tolerance in the Integer Options dialog box may need to be adjusted

Question 10

The linear program that results from dropping the integer requirements for the variables in an integer linear program is known as

A)convex hull.
B)a mixed-integer linear program.
C)LP relaxation.
D)a binary integer linear program.

Question 11

The objective function for an optimization problem is: Min 3x - 2y, with constraints x ≥ 0, y ≥ 0. x and y must be integers. Suppose that the integer restriction on the variables is removed. If so, this would be a familiar two-variable linear program; however, it would also be an example of

A)the convex hull of the linear program.
B)a mixed-integer linear program.
C)an LP relaxation of the integer linear program.
D)a binary integer linear program.

Question 12

A __________ problem is a binary integer programming problem that involves choosing which possible projects or activities provide the best investment return.

A)capital budgeting
B)fixed-cost
C)market share optimization
D)location

Question 13

Which of the following is true of rounding the optimized solution of a linear program to an integer?

A)It always produces the most optimal integer solution.
B)It always produces a feasible solution.
C)It does not affect the value of the objective function.
D)It may or may not be feasible.

Question 14

The __________ of a set of points is the smallest intersection of linear inequalities that contain the set of points.

A)concave hull
B)slope
C)convex hull
D)geometry

Question 15

Which of the following is true about the sensitivity analysis for integer optimization problems?

A)Sensitivity reports are readily available for integer optimization problems similar to the linear programming problems.
B)Because of the discrete nature of the integer optimization, Excel Solver takes much more time to calculate objective function coefficient ranges, shadow prices, and right-hand-side ranges.
C)The sensitivity analysis is not important for integer problems.
D)To determine the sensitivity of the solution to changes in model inputs for integer optimization problems, the data must be changed and the problem must be re-solved.

Question 16

The importance of _________ for integer linear programming problems is often intensified by the fact that a small change in one of the coefficients in the constraints can cause a relatively large change in the value of the optimal solution.

A)objective function
B)decision variables
C)sensitivity analysis
D)optimization analysis

Question 17

The objective function for a linear optimization problem is: Max 3x + 2y, with one of the constraints being x and y both only take the values 0, 1. Also x and y are the only decision variables. This is an example of a

A)nonlinear program.
B)mixed-integer linear program.
C)LP relaxation of the integer linear program.
D)binary integer linear program.

Question 18

Binary variables are identified with the __________ designation in the Solver Parameters dialog box.

A)bin
B)0 and 1
C)int
D)dif

Question 19

In cases where Excel Solver experiences excessive run times when solving integer linear problems, the Integer Optimality is set to

A)5%.
B)0%.
C)infinity.
D)a value equal to the number of integer constraints.

Question 20

Which of the following is true of the relationship between the value of the optimal integer solution and the value of the optimal solution to the LP Relaxation?

A)For integer linear programs involving minimization, the value of the optimal solution to the LP Relaxation provides an upper bound on the value of the optimal integer solution.
B)For integer linear programs involving maximization, the value of the optimal solution to the LP Relaxation provides a lower bound on the value of the optimal integer solution.
C)For integer linear programs involving minimization, the value of the optimal solution to the LP Relaxation provides a lower bound on the value of the optimal integer solution.
D)For any linear program involving either minimization or maximization, the value of the optimal solution to the LP Relaxation provides an infeasible value for the optimal integer solution.

Question 21

In a fixed-cost problem, choosing excessively large values for the maximum production quantity will result in

A)all reasonable levels of production.
B)no production.
C)no solution at all.
D)possibly a slow solution procedure.

Question 22

Which of the following is true about generating alternatives in binary optimization?

A)If the second-best solution is very close to optimal, it is always preferred over the true optimal solution because of factors outside the model.
B)If alternative solutions exist, it would not help management because some factors that make one alternative are not preferred over the factors that make another alternative.
C)If the solution is a unique optimal solution, it would be good for management to know how much worse the second-best solution is than the unique optimal solution.
D)If any alternative solution exists, it would only be a second-best next to the optimal solution because there is no third-best or an alternative second-best solution to any binary integer programming problem.

Question 23

In a production application involving a fixed setup cost and a variable cost, the use of __________ makes including the setup cost possible in a production model.

A)location variables
B)noninteger constraints
C)objective function coefficients
D)binary variables

Question 24

A binary mixed-integer programming problem in which the binary variables represent whether an activity, such as a production run, is undertaken or not is known as the

A)capital budgeting problem.
B)share of choice problem.
C)fixed-cost problem.
D)covering problem.

Question 25

An apparel designing company is planning to enter the women's trousers market. They are in the process of developing a product that will appeal most to customers. What category does the above objective fall under?

A)Capital budgeting problem
B)Covering problem
C)Fixed-cost problem
D)Product design and market share optimization problem

Question 26

__________ analysis is a market research technique that can be used to learn how prospective buyers of a product value the product's attributes.

A)Part-worth
B)Conjoint
C)Regression
D)Sensitivity

Question 27

The results of _____________ can be used in an integer programming model of a product design and market share optimization problem.

A)conjoint analysis
B)product design
C)part-worth
D)variations analysis

Question 28

An apparel designing company is planning to enter the women's trousers market. They are in the process of developing a product that will appeal most to customers. Pink, green, and black will be __________ of the color attribute.

A)levels
B)constraints
C)regression constants
D)utility values

Question 29

In a fixed-cost model, each fixed cost is associated with a binary variable and a specification of the

A)upper bound for the corresponding production variable.
B)upper bound for each of the binary variable.
C)integer constraints involving the corresponding production variables.
D)objective function involving these binary variables only.

Question 30

__________ constraint is a constraint requiring that two binary variables be equal and that thus are both either in or out of the solution together.

A)Conditional
B)Corequisite
C)k out of n alternatives
D)Mutually exclusive

Question 31

Which of the following is a likely constraint on the production quantity x associated with a maximum value and a setup variable y in a fixed-cost problem?

A)x ≥ My
B)x ≤ My
C)Mx ≤ y
D)xy ≥ M

Question 32

The sum of two or more binary variables must be less than or equal to one in a __________ constraint.

A)corequisite
B)conditional
C)multiple-choice
D)mutually exclusive

Question 33

For a location problem, if the variables are defined as x_i = 1 if an outlet store is established in region i and 0 otherwise, the objective function is best defined by __________ for i = 1, 2, …, n number of outlet stores included in the problem.

A)Min(Sx_i)
B)Max(Sx_i)
C)Min(px_i)
D)Max(px_i)

Question 34

The part-worth for each of the attribute levels in a conjoint analysis is determined by

A)regression analysis.
B)sensitivity analysis.
C)online surveys.
D)word-of-mouth.

Question 35

A constraint involving binary variables that does not allow certain variables to equal one unless certain other variables are equal to one is known as a

A)conditional constraint.
B)corequisite constraint.
C)k out of n alternatives constraint.
D)mutually exclusive constraint.

Question 36

Coming up with a product design that will have the highest utility for a sufficient number of people to ensure sufficient sales to justify making the product is known as the ___________ problem in marketing literature.

A)capital budgeting
B)share of choice
C)fixed-cost
D)traveling-salesman

Question 37

An apparel designing company is planning to enter the women's trousers market. They are in the process of developing a product that will appeal most to customers. In an integer programming model for this problem, the available sizes of the trousers will be represented as

A)binary variables.
B)constraints.
C)attributes.
D)regression constants.

Question 38

An apparel designing company is planning to enter the women's trousers market. They are in the process of developing a product that will appeal most to customers. The part-worth for each of the attribute levels obtained from an initial customer survey and the subsequent regression analysis can be used to determine the

A)customer utility value.
B)optimal solution for the regression analysis.
C)overall profit for the company.
D)overall sales achieved by the company.

Question 39

An apparel designing company is planning to enter the women's trousers market. They are in the process of developing a product that will appeal most to customers. The levels - small, medium, and large of the size attribute are modeled using

A)objective function coefficients.
B)slack variables.
C)binary variables.
D)nonlinear coefficients.

Question 40

The __________ is the utility value that a consumer attaches to each level of each attribute in a conjoint analysis model.

A)weightage
B)share of choice
C)part-worth
D)share of market

Question 41

Based upon the optimal solution and slack variables, what recommendations could you make to management?
​
Where
S = 1 if the store expansion project is accepted; 0 if rejected
F = 1 if the fleet expansion project is accepted; 0 if rejected
M = 1 if the equipment upgrade project is accepted; 0 if rejected
R = 1 if the market research project is accepted; 0 if rejected
and currency is in $1,000s.
Maximize
75S + 50F + 16E + 12R
s.t.
30S + 30F + 10E + 20R ≤ 85
30S + 35F + 20E + 10R ≤ 60
40S + 50F + 20E + 10R ≤ 100
65S + 55F + 20E + 10R ≤ 125
S, F, E, R = 0, 1 (binary)
​

Question 42

What is a binary variable?