Integer Programming

Integer Programming (IP) is a mathematical optimization technique where some or all of the decision variables are restricted to take only discrete, integer values. When all variables are integers, it is a Pure Integer Program; when only some are integers while others are continuous, it is a Mixed-Integer Linear Program (MILP). Key engineering and operational concepts in IP include: 1. Binary Variables: A special case of integer variables restricted to {0, 1}. They are crucial for modeling logical decisions (e.g., yes/no, on/off, build/don't build) and fixed costs. 2. LP Relaxation: The process of removing the integer constraints from an IP to solve it as a standard continuous Linear Program (LP). The LP relaxation provides a bound on the optimal IP solution. 3. Big-M Formulation: A modeling technique used to link a continuous variable to a binary logical variable. For example, ensuring a factory can only produce goods if the factory is physically opened. 4. Solution Methods: Unlike continuous LPs, which can be solved easily via the Simplex method, IP problems are generally NP-hard. They are solved using algorithms like Branch-and-Bound, which systematically partitions the solution space into smaller subproblems (branches) and uses LP relaxations to eliminate suboptimal regions (bounds). 5. The Rounding Trap: Simply rounding the continuous results of an LP relaxation to the nearest integer is highly dangerous; it frequently results in solutions that violate constraints (infeasible) or are severely suboptimal.