Question 1

A fixed charge problem models shops that incur a fixed cost for producing any positive quantity of a product and incur 0 cost if nothing is produced.

Accepted Answer

A fixed charge problem indeed models situations where there is a fixed cost associated with producing any positive quantity of a product, and no cost if production is zero. This reflects scenarios where initiating production incurs certain expenses regardless of the production volume, but no costs are incurred if there is no production.

Question 2

In general, we consider more feasible solutions in solving integer linear programming problems. as compared to solving linear programming problems by simplex method.
1.

Accepted Answer

Integer linear programming problems have additional constraints that the variables must be integers, which makes them more difficult to solve than linear programming problems. As a result, we typically consider more feasible solutions in solving integer linear programming problems to find a solution that satisfies all the constraints.

Question 3

For a typical integer programming problem, the number of feasible solutions
A) increases linearly
B) increases exponentially
C) decreases exponentially
D) decreases linearly

Accepted Answer

For a typical integer programming problem, the number of feasible solutions increases exponentially as the size of the problem (number of variables and constraints) increases. This is because each additional variable, assuming it's binary for simplicity, can essentially double the number of possible solutions, leading to an exponential growth in the solution space.

Question 4

For a pure 0-1 integer programming problem with 3 variables, the maximum number of potential solutions is
A) 9
B) 27
C) 16
D) 8

Accepted Answer

Each variable in a 0-1 integer programming problem can take on two values (0 or 1). With 3 variables, the number of potential solutions is $2^3 = 8$.

Question 5

Branching in the branch and bound method refers to
A) adding a constraint
B) removing a constraint
C) either adding or removing a constraint
D) removing a constraint and extending the feasible set

Accepted Answer

Branching in the branch and bound method refers to adding a constraint to divide the problem into smaller subproblems, which can then be solved more easily or determined to be infeasible or not optimal.

Question 6

In modeling a shopping mall construction problem, there are four potential locations giving rise to four 0-1 decision variables, denoted as $X_{1}, X_{2}, X_{3}, X_{4}$, which take a value of 1 if a mall is constructed and 0 otherwise. Identify the correct set of constraint/s to satisfy the following condition/s: at most only one mall may be constructed among locations 1 and 3
A) $\mathrm{X}_{1}+\mathrm{X}_{3} \leq$ 1
B) $\mathrm{X}_{1}+\mathrm{X}_{3} \geq$1
C) $X_{1}+X_{3}<$1
D) $X_{1}+X_{3}=$ 1

Accepted Answer

The constraint $X_{1} + X_{3} \leq 1$ ensures that the sum of the decision variables for locations 1 and 3 does not exceed 1, meaning at most one of these locations can have a mall constructed, which satisfies the given condition.

Question 7

In modeling a shopping mall construction problem, there are four potential locations giving rise to four 0-1 decision variables, denoted as $\mathrm{X}_{1}, \mathrm{X}_{2}, \mathrm{X}_{3}, \mathrm{X}_{4}$, which take a value of 1 if a mall is constructed and 0 otherwise. Identify the correct set of constraint/s to satisfy the following condition/s: at least one mall may be constructed among locations 1 and 3
A) $\mathrm{X}_{1}+\mathrm{X}_{3} \leq$1
B) $\mathrm{X}_{1}+\mathrm{X}_{3} \geq$1
C) $X_{1}+X_{3}>$1
D) $X_{1}+X_{3}=$

Accepted Answer

The constraint $\mathrm{X}_{1}+\mathrm{X}_{3} \geq 1$ ensures that at least one mall is constructed between locations 1 and 3, either one or both.

Question 8

In modeling a shopping mall construction problem, there are four potential locations giving rise to four 0-1 decision variables, denoted as $X_{1}, X_{2}, X_{3}, X_{4}$,which take a value of 1 if a mall is constructed and 0 otherwise. Identify the correct set of constraint/s to satisfy the following condition/s: exactly one mall should be constructed among locations 1 and 3
A) $\mathrm{X}_{1}+\mathrm{X}_{3} \leq$ 1
B) $\mathrm{X}_{1}+\mathrm{X}_{3} \geq$1
C) $X_{1}+X_{3}>$1
D) $X_{1}+X_{3}=$ 1

Accepted Answer

To ensure exactly one mall is constructed either at location 1 or 3, the sum of $X_{1}$ and $X_{3}$ must equal 1. This means one variable is 1 and the other is 0, satisfying the condition.

Question 9

In modeling a shopping mall construction problem, there are four potential locations giving rise to four 0-1 decision variables denoted as $X_{1}, X_{2}, X_{3}, X_{4}$, which take a value of 1 if a mall is constructed and 0 otherwise. Identify the correct set of constraint/s to satisfy the following condition/s: if a mall is constructed in location 2, then a mall should be constructed in location 4
A) $\mathrm{X}_{2}-\mathrm{X}_{4} \leq$ 0.
B) $-X_{2}+X_{4} \geq$0.
C) $\mathrm{X}_{2}-\mathrm{X}_{4} \leq$ 0
D) $-\mathrm{X}_{2}+\mathrm{X}_{4} \leq$0

Accepted Answer

If a mall is constructed in location 2, then $X_2 = 1$. To ensure that a mall is also constructed in location 4, we need to enforce the constraint $-X_2 + X_4 \geq 0$. This constraint ensures that if $X_2$ is 1 (i.e., a mall is constructed in location 2), then $X_4$ must also be 1 (i.e., a mall is constructed in location 4).

Question 10

In modeling a traveling salesman problem, let $X_{\mathrm{ijk}}$ be a 0-1 decision variable, which takes a value of 0 if in the kth leg the tour corresponding to the solution does not go from node $\mathrm{i}$ to node $\mathrm{j}$. $\mathrm{X}_{\mathrm{ijk}}$ is set to be equal to 1 if the tour goes from node $\mathrm{i}$ to node $\mathrm{j}$ in the kth leg. In a problem with just 4 nodes and without loss of generality, assume that the tour starts and ends in node 1. Mark the correct constraint to make sure that the tour starts in node 1
A) $\mathrm{X}_{121}+\mathrm{X}_{131}+\mathrm{X}_{141} \leq 1$
B) $X_{121}+X_{131}+X_{141} \geq 1$
C) $X_{121}+X_{131}+X_{141}=1$
D) $X_{214}+X_{314}+X_{414}=1$

Accepted Answer

The constraint $X_{121}+X_{131}+X_{141}=1$ ensures that the tour starts in node 1 and goes to exactly one of the other nodes (2, 3, or 4) in the first leg. This is necessary to ensure a valid start of the tour from node 1.

Question 11

In modeling a traveling salesman problem, let $X_{\mathrm{ijk}}$ be a 0-1 decision variable, which takes a value of 0 if in the kth leg the tour corresponding to the solution does not go from node $\mathrm{i}$ to node $\mathrm{j}$. $\mathrm{X}_{\mathrm{ijk}}$ is set to be equal to 1 if the tour goes from node $i$ to node $\mathrm{j}$ in the kth leg. In a problem with just 4 nodes and without loss of generality, assume that the tour starts and ends in node 1. Mark the correct constraint to make sure that the tour ends in node 1
A) $\mathrm{X}_{214}+\mathrm{X}_{314}+\mathrm{X}_{414} \leq 1$
B) $X_{214}+X_{314}+X_{414} \geq 1$
C) $X_{214}+X_{314}+X_{414}=1$
D) $\mathrm{X}_{121}+\mathrm{X}_{131}+\mathrm{X}_{141}=1$

Accepted Answer

The constraint $X_{214}+X_{314}+X_{414}=1$ ensures that exactly one of the nodes 2, 3, or 4 connects to node 1 in the final (4th) leg of the tour, thus ensuring the tour ends at node 1.

Question 12

In modeling a traveling salesman problem, let $X_{i j k}$ be a 0-1 decision variable, which takes a value of 0 if in the kth leg the tour corresponding to the solution does not go from node $\mathrm{i}$ to node $\mathrm{j}$. $\mathrm{X}_{\mathrm{ijk}}$ is set to be equal to 1 if the tour goes from node $\mathrm{i}$ to node $\mathrm{j}$ in the kth leg. In a problem with just 4 nodes and without loss of generality, assume that the tour starts and ends in node 1 . If, in a particular solution, $X_{213}=1$, it means that the tour corresponding to the solution
A) goes from node 3 to 1 in the 2nd leg
B) goes from node 2 to 1 in the 3rd leg
C) goes from node 1 to 2 in the 3rd leg
D) goes from node 1 to 3 in the 2 nd leg

Accepted Answer

Given $X_{213}=1$, it indicates that the tour goes from node 2 to node 1 in the 3rd leg, as the first index represents the starting node, the second index represents the ending node, and the third index represents the leg of the tour.

Question 13

An airport limousine service which parks all its limos at the airport can minimize its cost by using a proper order to pick up passengers from their houses and return to the airport using a
A) set covering problem
B) traveling salesman problem
C) knapsack problem
D) fixed charge problem

Accepted Answer

The traveling salesman problem (TSP) is the most suitable for this scenario. It involves finding the shortest possible route that visits each location exactly once and returns to the origin point, which aligns with the goal of minimizing costs for picking up passengers from their houses and returning to the airport.

Question 14

An Avon lady carrying her tote containing makeup materials can maximize her profit from one trip to the rural Mississippi hinterland if she models the process of loading her bag (with the "right" materials having maximum profitability per unit volume) by using a
A) set covering problem
B) traveling salesman problem
C) knapsack problem
D) fixed charge problem

Accepted Answer

The knapsack problem is the most suitable model for maximizing profit by selecting the "right" materials (with maximum profitability per unit volume) to fit into a limited space, like a tote bag. This problem involves choosing items with the highest value while staying within a weight or volume limit, which aligns with the scenario of maximizing profit from a selection of makeup materials.

Question 15

A problem that has fixed cost as well as variable cost per unit, depending on the level of that activity, is usually formulated as a
A) set covering problem
B) knapsack problem
C) fixed charge problem
D) traveling salesman problem

Accepted Answer

Fixed charge problems involve scenarios where there is a fixed cost that does not change with the level of activity, as well as a variable cost that does change with the level of activity. This is characteristic of the fixed charge problem.

Question 16

Problems with variables that are yes-no types are called
A) pure integer programming problems
B) linear programming problems
C) yes-no type problems
D) $0-1$ problems
E) binary linear problems

Accepted Answer

Yes-no type problems are often referred to as $0-1$ problems because the variables can only take on the values 0 or 1, representing the two possible states.

Question 17

Problems in which some variables are required to be integers are called
A) pure integer programming problems
B) mixed integer programming problems
C) linear and integer programming problems
D) $0-1$ problems
E) yes-no type problems

Accepted Answer

Mixed integer programming problems are those in which some variables are required to be integers.

Question 18

Problem $\mathrm{A}$ is a two-variable linear programming problem with a maximization objective function. Problem B is a two-variable pure integer programming problem obtained from Problem A by requiring the variables to be integers and leaving all other things unchanged. Assuming that both problems have optimal solutions, the objective function value of problem A will always be the objective function value of Problem B.
A) greater than
B) less than
C) equal to
D) greater than or equal to
E) less than or equal to

Accepted Answer

In linear programming problems, allowing variables to take any real values (including fractions) can lead to an optimal solution that is not possible when variables are restricted to integer values, as in integer programming problems. Therefore, the optimal solution of a linear programming problem (Problem A) can be equal to or better (higher in the case of maximization) than that of the corresponding integer programming problem (Problem B) because the latter has more restrictive conditions.

Question 19

Problem A is a two-variable linear programming problem with a minimization objective function. Problem B is a two-variable pure integer programming problem obtained from Problem A by requiring the variables to be integers and leaving all other things unchanged. Assuming that both problems have optimal solutions, the objective function value of problem A will always be the objective function value of Problem B.
A) greater than
B) less than
C) equal to
D) greater than or equal to
E) less than or equal to

Accepted Answer

The answer of Problem A is a two-variable linear programming...

Question 20

Problem $\mathrm{A}$ is a two-variable linear programming problem with a minimization objective function. Problem B is a two-variable mixed integer programming problem obtained from Problem A by requiring one of the variables to be integer and leaving all other things unchanged. Assuming that both problems have optimal solutions and that Problem A has a unique non-integer optimal solution, the objective function value of problem A will always be the objective function value of Problem B.
A) greater than
B) less than
C) equal to
D) greater than or equal to
E) less than or equal to

Accepted Answer

The answer of Problem $\mathrm{A}$ is a two-variable linear programming...

Quiz 7: Integer Programming

A fixed charge problem models shops that incur a fixed cost for producing any positive quantity of a product and incur 0 cost if nothing is produced.

In general, we consider more feasible solutions in solving integer linear programming problems. as compared to solving linear programming problems by simplex method. 1.

For a typical integer programming problem, the number of feasible solutions

For a pure 0-1 integer programming problem with 3 variables, the maximum number of potential solutions is

Branching in the branch and bound method refers to

An airport limousine service which parks all its limos at the airport can minimize its cost by using a proper order to pick up passengers from their houses and return to the airport using a

An Avon lady carrying her tote containing makeup materials can maximize her profit from one trip to the rural Mississippi hinterland if she models the process of loading her bag (with the "right" materials having maximum profitability per unit volume) by using a

A problem that has fixed cost as well as variable cost per unit, depending on the level of that activity, is usually formulated as a

Problems with variables that are yes-no types are called

Problems in which some variables are required to be integers are called