Integer Linear Programming: A Comprehensive Guide for Advanced Mathematics Students

Question 1

Which of the following is NOT a defining characteristic of integer linear programming?

Accepted Answer

Can accurately model problems with nonlinear constraints.

Answer

Decision variables can only take integer values.

Answer

Can be solved using methods designed for linear programming.

Answer

Has wide applications in areas such as logistics and finance.

Question 2

Which of the following techniques is primarily used to solve integer linear programming problems?

Accepted Answer

Branch and price method

Answer

Graphical method

Answer

Interior point method

Answer

Dynamic programming

Question 3

During the branching step in the branch and bound method for integer linear programming, the primary goal is to:

Accepted Answer

Eliminate infeasible regions of the solution space.

Answer

Identify a feasible solution to the problem.

Answer

Determine the optimal solution to the problem.

Answer

Reduce the number of decision variables in the problem.

Question 4

In the context of integer linear programming applied to logistics, which of the following is NOT an example of a real-world application?

Accepted Answer

Forecasting future demand patterns

Answer

Optimizing inventory management systems

Answer

Designing efficient vehicle routing plans

Answer

Planning warehouse layouts

Question 5

What is the primary purpose of applying presolve techniques to integer linear programming problems?

Accepted Answer

Reduce the size and complexity of the problem, making it easier to solve.

Answer

Improve the accuracy and precision of the solution obtained.

Answer

Find a feasible solution to the problem quickly and easily.

Answer

Avoid getting trapped in local optima during the solution process.

Question 6

What is a key characteristic that sets integer linear programming (ILP) models apart?

Accepted Answer

Variables can only take integer values

Answer

Objective function is linear

Answer

Constraints are nonlinear

Question 7

Which of the following is NOT a fundamental concept of integer linear programming?

Accepted Answer

Continuous Optimization

Answer

Modeling Techniques

Answer

Applications

Answer

Solution Methods

Question 8

In integer linear programming, which modeling technique is primarily used to represent logical constraints?

Accepted Answer

Binary Variables

Answer

Linear Equations

Answer

Objective Functions

Answer

Inequalities

Question 9

Which solution method guarantees an optimal solution for an integer linear programming problem?

Accepted Answer

Branch and Bound

Answer

Lagrangian Relaxation

Answer

Cutting Plane Method

Answer

Heuristic Methods

Question 10

What is the main purpose of adding a cutting plane to an integer linear programming problem?

Accepted Answer

To refine the feasible region and strengthen the linear programming relaxation

Answer

To solve the problem directly

Answer

To eliminate infeasible solutions

Answer

To simplify the objective function

Question 11

Which software package is widely used for solving integer linear programming problems?

Accepted Answer

Gurobi

Answer

Microsoft Excel Solver

Answer

MATLAB

Answer

R

Question 12

Which of the following is NOT an assumption of the integer linear programming model?

Accepted Answer

Continuous variables are permitted

Answer

Integrality of variables

Answer

Feasibility region is bounded

Answer

Linearity of objective function

Question 13

Which of the following approaches guarantees finding the optimal solution to an integer linear programming problem?

Accepted Answer

Branch-and-bound method

Answer

Lagrangian relaxation

Answer

Simplex method

Answer

Cutting plane method

Question 14

A defining characteristic of a mixed integer linear programming problem is that:

Accepted Answer

Some variables are continuous while others are constrained to integer values

Answer

All variables are binary (0 or 1)

Answer

All variables are continuous

Answer

All variables must be integers

Question 15

The cutting plane method for integer linear programming involves:

Accepted Answer

Adding valid inequalities to refine the problem formulation

Answer

Introducing new variables

Answer

Modifying the objective function

Answer

Eliminating constraints from the problem formulation

Question 16

Lagrangian relaxation is a technique commonly used to:

Accepted Answer

Temporarily relax the integer constraints

Answer

Strengthen the integer constraints

Answer

Eliminate the integer constraints entirely

Answer

Add new integer constraints

Question 17

Which of the following software packages is widely used to solve integer linear programming problems?

Accepted Answer

CPLEX

Answer

Python (without specific libraries for ILP)

Answer

MATLAB (without specific libraries for ILP)

Question 18

What is the primary purpose of using a binary variable in integer linear programming?

Accepted Answer

To represent the presence or absence of an item.

Answer

To enforce integer values for a continuous variable.

Answer

To represent the number of occurrences of an item.

Question 19

Which of the following algorithms is commonly employed to solve integer linear programming problems?

Accepted Answer

Branch and bound

Answer

Lagrange multipliers

Answer

Simplex method

Answer

Gradient descent

Question 20

What is the key distinction between an integer programming problem and a mixed-integer programming problem?

Accepted Answer

In the former, all decision variables are integers, while in the latter, some decision variables can be continuous.

Answer

Integer programming problems are linear, while mixed-integer programming problems are non-linear.

Answer

Integer programming problems have continuous objective functions, while mixed-integer programming problems have integer objective functions.

Question 21

What is the definition of a facet-defining inequality in the context of integer linear programming?

Accepted Answer

An inequality that cannot be derived from any other constraints in the problem and defines a facet of the feasible region.

Answer

An inequality that is always satisfied by any feasible solution.

Answer

An inequality that is only satisfied by the optimal solution.

Question 22

What is the primary role of a cutting plane in integer linear programming?

Accepted Answer

To eliminate infeasible solutions from the feasible region by adding valid inequalities.

Answer

To find the optimal solution to the problem.

Answer

To generate new integer solutions.

Question 23

Which of the following is a primary advantage of using integer linear programming over other optimization techniques?

Accepted Answer

It guarantees that the solution to the problem will be an integer.

Answer

It is easier to implement than other techniques.

Answer

It can handle non-linear problems.

Answer

It is always more efficient than other techniques.

Question 24

What is the time complexity of solving an integer linear programming problem?

Accepted Answer

NP-hard

Answer

Linear

Answer

Logarithmic

Answer

Polynomial

Question 25

Which of the following is NOT a fundamental characteristic of integer linear programming (ILP) problems?

Accepted Answer

Continuous variables can be present in ILP problems

Answer

Variables must take on integer values

Answer

Constraints are linear

Answer

Objective function is linear

Question 26

A complete formulation of an ILP problem should include all of the following EXCEPT:

Accepted Answer

Penalty terms for violating the integrality constraints

Answer

Constraints

Answer

Objective function

Question 27

Which of the following methods is commonly used to solve ILP problems?

Accepted Answer

Branch and bound

Answer

Simplex method

Answer

Gradient descent

Answer

Dynamic programming

Question 28

In a branch and bound algorithm for ILP, the lower bound is typically obtained from:

Accepted Answer

The optimal solution value of the linear programming relaxation

Answer

The maximum possible value of the objective function

Answer

The current best integer solution found

Question 29

Which of the following is a potential real-world application of ILP?

Accepted Answer

Scheduling workforce shifts

Answer

Solving differential equations

Answer

Predicting stock market behavior

Answer

Rendering 3D graphics

Question 30

What is the key purpose of relaxation in the context of ILP?

Accepted Answer

To obtain a lower bound on the optimal integer solution

Answer

To ensure that the ILP problem is feasible

Answer

To find an exact integer solution faster

Question 31

Which of the following is a frequently used modeling technique in ILP?

Accepted Answer

Binary variables

Answer

Calculus of variations

Answer

Lagrange multipliers

Answer

Dynamic programming equations

Question 32

What is a major computational challenge associated with integer linear programming?

Accepted Answer

Computational complexity increases rapidly with problem size

Answer

Only suitable for small-scale problems

Answer

Requires specialized software to solve

Question 33

What is the primary distinction between mixed integer linear programming (MILP) and ILP?

Accepted Answer

MILP allows both continuous and integer variables, while ILP only allows integer variables

Answer

MILP is more complex to solve than ILP

Answer

MILP is used for larger-scale problems than ILP

Question 34

A company produces two types of products, A and B. Product A requires 2 hours of labor and 1 unit of raw material per unit, while product B requires 3 hours of labor and 2 units of raw material per unit. The company has 100 hours of labor and 50 units of raw material available. If the profit per unit of product A is $10 and the profit per unit of product B is $15, how many units of each product should the company produce to maximize profit? This problem can be formulated as an integer linear program. Which of the following represents the objective function?

Accepted Answer

Maximize Profit = 10A + 15B

Answer

Minimize Profit = 10A + 15B

Answer

Minimize Profit = 2A + 3B

Answer

Maximize Profit = 2A + 3B

Question 35

Which of the following is NOT a characteristic of an integer linear programming problem?

Accepted Answer

The decision variables can take on any real value.

Answer

The objective function is linear.

Answer

The constraints are linear.

Answer

The decision variables must be integers.

Question 36

A company wants to schedule production of three products (A, B, and C) over the next three months. The production capacity for each product varies monthly. The company wants to minimize the total production cost while meeting demand for each product in each month. This problem can be modeled as an integer linear program. Which of the following is likely to be a constraint in this model?

Accepted Answer

The total production of product A in month 1 cannot exceed the production capacity for product A in month 1.

Answer

The production cost of product A is always less than the production cost of product B.

Question 37

Which of the following is a common method used to solve integer linear programming problems?

Accepted Answer

Branch and Bound

Answer

Simplex Method

Answer

Newton-Raphson Method

Answer

Gradient Descent

Question 38

A transportation problem involves minimizing the cost of transporting goods from multiple sources to multiple destinations. This problem can be formulated as an integer linear program. What type of integer variable would typically be used to represent the amount of goods transported from a specific source to a specific destination?

Accepted Answer

Non-negative integer

Answer

Binary integer

Answer

Continuous variable

Answer

Negative integer

Question 39

What is the primary advantage of using integer linear programming over linear programming?

Accepted Answer

The ability to model and solve problems with decision variables that must be integers.

Answer

Integer linear programming is computationally faster than linear programming.

Answer

Integer linear programming can handle non-linear objective functions.

Question 40

A company is deciding which of three new products to introduce. Each product requires a different amount of resources (labor, materials, etc.). The company wants to maximize its profit while staying within its resource constraints. This problem can be modeled as an integer linear program. What type of integer variable would typically be used to represent whether or not a specific product is introduced?

Accepted Answer

Binary integer

Answer

Negative integer

Answer

Non-negative integer

Answer

Continuous variable

Question 41

A project manager is assigning tasks to team members. Each task has a different duration and requires specific skills. The project manager wants to minimize the total project duration while ensuring that each task is assigned to a team member with the necessary skills. This problem can be modeled as an integer linear program. Which of the following is a potential limitation of using integer linear programming to solve this problem?

Accepted Answer

Integer linear programming can be computationally expensive for large-scale problems.

Answer

Integer linear programming cannot handle constraints involving time.

Answer

Integer linear programming can only be used for problems with a single objective function.

Question 42

A company is planning to open new stores in different locations. The company wants to maximize its total revenue while considering the cost of opening each store and the potential market demand in each location. This problem can be formulated as an integer linear program. Which of the following is likely to be a decision variable in this model?

Accepted Answer

Number of stores to open in each location

Answer

Cost of opening a store in each location

Answer

Total revenue generated by the company

Answer

Market demand in each location

Question 43

Which of the following is an example of a real-world application of integer linear programming?

Accepted Answer

Optimizing production schedules in a manufacturing plant

Answer

Predicting the price of a stock

Answer

Classifying images in a computer vision system