Chapter 3: Mixed Integer Linear Programming Problems

In this article, we will delve into the application of linear programming by examining the furniture problem as an example. We will explore the key components of linear programming and introduce the concept of mixed integer programming. Additionally, we will discuss the general formulation of linear and mixed integer programming problems, highlighting their various representations and solving methods.

The Furniture Factory Problem

To illustrate the concepts of linear and mixed integer programming, let’s consider the furniture problem. In this scenario, we are tasked with determining the optimal production plan for chairs and tables. We define two decision variables: x1 represents the number of chairs to produce, and x2 represents the number of tables to produce. These decision variables are associated with respective indices, 1 for chairs and 2 for tables.

To facilitate problem formulation, we create sets to map each product to its corresponding decision variable index. In this case, the set of products includes “chair” with the index 1 and “table” with the index 2. Similarly, we establish a set of resources, which comprises two elements: mahogany (index 1) and labor (index 2).

LP Model Parameters

Linear programming models rely on various parameters that define known quantities or data related to the problem. In the furniture problem, we encounter three types of parameters: prices, resource capacity, and technology coefficients.

• For instance, prices are defined for each product. We assign parameter b1 = \$45 to represent the price of a chair, which can be adjusted to accommodate price fluctuations. Similarly, we set b2 = \$80 as the price of a table.
• The availability of resources is captured by parameters K1 and K2. K1 represents the capacity of mahogany, with a value of 400 units, while K2 signifies the amount of available labor, set at 450 hours.
• Technology coefficients, denoted by a1 and a2, describe the resource consumption during production. In this problem, a1 = 5 indicates that building one chair consumes 5 units of mahogany, while a2 = 20 denotes that one table requires 20 units of mahogany. Additionally, a1 = 10 implies that producing a chair consumes 10 units of labor, and a2 = 15 indicates that manufacturing a table consumes 15 units of labor.

To visualize the relationship between resources and products, we can represent the technology coefficients in a matrix form. This two-dimensional array maps resources (rows) to products (columns) and encapsulates the resource consumption by the production plan.

Components of a Linear Programming Model

Linear programming problems typically consist of five key components: sets of indices, parameters, decision variables, constraints, and objectives.

• In the case of the furniture problem, we have two sets: the set of resources and the set of products. The set of resources includes mahogany (index 1) and labor (index 2), while the set of products comprises chairs (index 1) and tables (index 2).
• Parameters define the known quantities in the problem, such as prices, resource capacities, and technology coefficients, as discussed above.
• Decision variables, represented by x1 and x2, determine the number of chairs and tables to be produced.
• Constraints impose limitations on resource availability, specifying the maximum consumption allowed. The furniture problem involves two types of constraints, which limit the production quantities of chairs and tables. These constraints are defined in terms of the available resources: mahogany and labor. The consumption of resources, as dictated by the production plan, must not exceed the available resource amounts.
• The objective function seeks to maximize the total revenue generated by the production plan. The objective function of the furniture problem aims to maximize the total revenue generated by the production plan. This function is determined by the decision variables x1 and x2, representing the number of chairs and tables produced, respectively.
  

Abstraction and Generalization of the Furniture Problem

By parameterizing the furniture problem, we can separate the data from the model, allowing for more flexibility. Parameters like b1, b2, K1, K2, and a1, a2 represent the specific values of the problem. By using general parameters, we can adapt the model to different scenarios without altering the underlying structure.

To generalize the furniture problem, we can extend the formulation to accommodate multiple products and resources. In this more comprehensive formulation, the objective function consists of revenue associated with each product, determined by the product’s objective function coefficient bj. The constraints account for resource consumption, ensuring that it does not exceed the available resource capacities Ki.

Linear, Integer, Binary, and Mixed Programming Models

Linear programming problems can be formulated with different types of constraints and decision variable requirements. In addition to non-negativity constraints, which ensure non-negative values for decision variables, we can have less than or equal to constraints, greater than or equal to constraints, equality constraints, integer constraints, and binary constraints. For example, a job position can only be filled with only one resource and you have a set of possible qualified resources to assign on the job. This particular constraint will be defined as an equality constraint.

Mixed integer programming combines linear programming with additional requirements on decision variables, such as integrality and binary restrictions. This approach allows for addressing more complex optimization problems, including combinatorial optimization.

Solving MIP Problems

When solving mixed integer programming problems, the formulation and representation of the problem play a crucial role in the performance of the solver. Efficient formulations are essential for achieving optimal solutions. Understanding the behavior of mixed integer programming algorithms can significantly impact the effectiveness of problem-solving.

Conclusion

Linear and mixed integer programming offer powerful techniques for solving optimization problems. By applying these methodologies to real-world scenarios like the furniture problem, we can make informed decisions and optimize various aspects of production and resource allocation. Understanding the components and formulations of linear and mixed integer programming models equips us with valuable tools for tackling a wide range of optimization challenges.

Resources

Download the complete Linear Programming Tutorial Series slide deck.

View the entire series:

• Welcome: Linear Programming Tutorial
• Chapter 1: Mathematical Programming
• Chapter 2: Introduction to Linear Programming
• Chapter 3: Mixed Integer Linear Programming Problems
• Chapter 4: Furniture Factory Problem
• Chapter 5: Simplex Method
• Chapter 6: Modeling and Solving Linear Programming Problems
• Chapter 7: Sensitivity Analysis of Linear Programming Problems
• Chapter 8: Multiple Optimal Solutions
• Chapter 9: Unbounded Linear Programming Problems
• Chapter 10: Infeasible Linear Programming Problems
• Chapter 11: Linear Programming Overview – Further Considerations
• Chapter 12: Duality in Linear Programming
• Chapter 13: Optimality Conditions
• Chapter 14: Dual Simplex Method