Integer linear programming: Meaning, Criticisms & Real-World Uses

Integer linear programming (ILP) is a mathematical optimization technique used within the broader field of operations research to find the best possible outcome in a mathematical model whose requirements are represented by linear relationships and where some or all of the decision variables are restricted to be whole numbers, known as integers. This approach falls under the category of mathematical optimization, a core component of quantitative analysis and decision science. Unlike standard linear programming, which allows variables to take on any real value, integer linear programming imposes the additional constraint that certain variables must be integers. This distinction is crucial for problems where fractional solutions are not sensible or feasible, such as allocating discrete units of resources or making "yes/no" decisions.

History and Origin

The foundation of integer linear programming lies within the development of linear programming and the broader field of operations research, which emerged significantly during World War II for strategic and logistical planning. Operations research, often shortened to O.R., applies scientific methods to complex systems to aid in decision-making, drawing on disciplines such as mathematics, statistics, and computer science.⁶, ⁷ Early pioneers like George Dantzig are credited with significant advancements in linear programming during the mid-20th century. As problems became more complex and involved indivisible items or binary choices, the necessity for integer constraints became apparent. The formalization of integer linear programming as a distinct area of study evolved from these needs, extending the capabilities of continuous optimization to address discrete problems. The Institute for Operations Research and the Management Sciences (INFORMS) is a prominent international society for practitioners in operations research, management science, and analytics, formed from the merger of earlier organizations in 1995. The International Federation of Operational Research Societies (IFORS) provides a more detailed history of the field of Operations Research, noting its origins in scientific management and queuing theory.⁵

Key Takeaways

Integer linear programming (ILP) is a mathematical method for optimizing an objective function subject to linear constraints, with the added requirement that some or all variables must be integers.
It is a specialized form of linear programming, essential for real-world problems where fractional solutions are impractical or meaningless.
ILP problems are often more computationally challenging to solve than continuous linear programming problems.
Applications span various fields, including finance, logistics, manufacturing, and resource allocation.
The complexity of ILP problems increases significantly with the number of variables and constraints, often requiring sophisticated algorithms and computational power.

Formula and Calculation

An integer linear programming problem aims to maximize or minimize an objective function subject to a set of constraints, with the critical addition that specific decision variables must be integers.

The general form of an integer linear programming problem can be expressed as:

Maximize or Minimize:

Z = c_1x_1 + c_2x_2 + \dots + c_nx_n

Subject to:

a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n \le b_1 \\ a_{21}x_1 + a_{22}x_2 + \dots + a_{2n}x_n \le b_2 \\ \vdots \\ a_{m1}x_1 + a_{m2}x_2 + \dots + a_{mn}x_n \le b_m

And:

x_j \ge 0 \quad \text{for all } j=1, \dots, n \\ x_j \text{ is an integer for some or all } j \in I

Where:

(Z) = The objective function value to be optimized (maximized or minimized).
(x_j) = The decision variables, representing the quantities or choices to be determined.
(c_j) = The coefficients of the objective function, representing the contribution or cost per unit of (x_j).
(a_{ij}) = The coefficients of the constraints, representing the resource consumption or impact of (x_j) on constraint (i).
(b_i) = The right-hand side values of the constraints, representing the available resources or limits for constraint (i).
(m) = The number of constraints.
(n) = The number of decision variables.
(I) = The set of indices for which (x_j) must be an integer.

Solving integer linear programming problems often involves advanced techniques such as branch-and-bound, cutting planes, or specialized heuristic methods, as directly enumerating all integer possibilities is usually impractical.

Interpreting the Integer Linear Programming Solution

Interpreting the solution of an integer linear programming problem involves understanding the optimal values of the decision variables and the corresponding value of the objective function. Unlike continuous linear programming, where solutions might include fractions, the integer constraint ensures that the output variables provide practical, whole-number answers. For example, if a variable represents the number of facilities to build, an integer solution of "3" is directly interpretable, whereas "3.7" from a continuous model would require further rounding or a re-evaluation, potentially leading to a suboptimal or infeasible plan.

The optimal solution indicates the specific integer values for the decision variables that achieve the best possible outcome for the objective (e.g., maximum profit, minimum cost) while adhering to all defined constraints. Analysts evaluate whether the solution aligns with real-world practicality and organizational goals. A sensitivity analysis might also be performed, though more complex than for continuous models, to understand how robust the optimal solution is to changes in input parameters. This interpretation is critical for translating the mathematical modeling into actionable business strategies.

Hypothetical Example

Consider a small investment firm aiming to maximize its expected return by investing in two types of projects: Project A and Project B. Due to regulatory requirements and the nature of the projects, the firm can only invest in a whole number of projects.

Objective: Maximize total expected return.
Decision Variables:
- (x_A): Number of Project A investments (must be an integer)
- (x_B): Number of Project B investments (must be an integer)
Expected Return per Project:
- Project A: $100,000
- Project B:¹ ² ³ ⁴