Integer Programming (IP)

The core feature of an Integer Program is that some or all decision variables are constrained to be integers. This enables the modeling of indivisible quantities and logical conditions that are impossible with continuous variables.

• Binary Variables (0-1): Model yes/no decisions, such as opening a facility or selecting an item.
• General Integer Variables: Represent countable quantities, like the number of trucks to deploy or units to produce.
• Mixed-Integer Programming (MIP): Combines continuous and integer variables, such as blending quantities (continuous) with setup decisions (binary).

Integer Programming is NP-hard in the general case. Finding an optimal solution requires exploring a combinatorial search space that can grow exponentially with the number of integer variables.

• Exponential Worst-Case: The number of potential solutions can be on the order of 2^n for binary variables.
• Optimality Guarantee: Unlike heuristic methods, exact IP solvers provide a mathematical proof of optimality (or infeasibility) upon completion.
• Solution Time: Can vary from milliseconds for easy instances to being computationally intractable for large, complex models, necessitating the use of advanced solving techniques.

Branch and Bound is the fundamental algorithmic framework used by solvers like CPLEX and Gurobi to find proven optimal solutions to IPs.

• Branching: The continuous relaxation of the IP (where integer constraints are ignored) is solved. If the solution has fractional values for integer variables, the solver creates subproblems (branches) by forcing a variable to be ≤ floor(value) or ≥ ceil(value).
• Bounding: Each subproblem's relaxation provides a bound on the best possible integer solution within that branch. Branches with bounds worse than the best-known integer solution are pruned.
• Search Tree: This process creates a tree of subproblems, which is systematically explored to converge on the optimal integer solution.

Cutting planes are linear constraints added to the problem to tighten its continuous relaxation, cutting off fractional solutions without removing any valid integer points.

• Tighter Relaxation: By adding these valid inequalities, the linear programming relaxation provides a better (higher for maximization) bound, accelerating the Branch and Bound process.
• Examples: Gomory cuts are a general class derived from the simplex tableau. Problem-specific cuts, like cover inequalities for knapsack problems, are even more powerful.
• Modern Solvers: Use sophisticated cut generation routines to automatically identify and add thousands of effective cuts, a technique central to modern Branch-and-Cut algorithms.

IP excels at modeling specific types of logical and combinatorial relationships through clever linear constraints.

• Fixed-Charge Costs: Model a setup cost S incurred if any activity x > 0 using a binary variable y: x ≤ M*y, where M is a large constant, and the cost term is S*y.
• Logical Constraints: Enforce If A then B using binary variables a and b: a ≤ b. Enforce At most one of A, B, C: a + b + c ≤ 1.
• Piecewise Linear Functions: Approximate non-linear functions using Special Ordered Sets (SOS).
• Scheduling & Sequencing: Use binary variables x_{i,j} = 1 if job i precedes job j to model disjunctive constraints.

Finding a good initial feasible integer solution quickly is crucial for practical solving, as it provides a lower bound to prune the search tree.

• Feasibility Pump: A popular heuristic that alternates between solving the linear relaxation (to get a fractional point) and rounding to an integer point (which may be infeasible), iteratively projecting between the two to find a feasible integer solution.
• Rounding & Diving: Simple rounding of the LP solution, or diving heuristics that fix variables and re-solve the LP to quickly find an integer leaf node.
• Large Neighborhood Search (LNS): Fixes a large portion of the variables and uses the IP solver to re-optimize the remaining subproblem, often finding significantly improved solutions.

Linear Programming (LP) is the continuous relaxation at the heart of Integer Programming. It is a mathematical method for optimizing a linear objective function, subject to linear equality and inequality constraints, where all variables are permitted to be real numbers.

• Foundation for IP: Most IP algorithms solve a series of LP relaxations, where integer constraints are temporarily ignored.
• Simplex Algorithm: The classic, efficient method for solving LPs by traversing vertices of the feasible polyhedron.
• Polynomial-Time Solvable: Unlike IP, LP problems can be solved in polynomial time (e.g., using interior-point methods), making the relaxation a critical computational step.

Mixed-Integer Programming (MIP) is a direct generalization of Integer Programming where only a subset of the decision variables are required to be integers, while others can be continuous.

• Ubiquitous in Practice: Most real-world IP models are actually MIPs, as they combine discrete yes/no decisions (integer) with continuous quantities like flow, time, or money.
• Modeling Flexibility: Allows for precise representation of problems like fixed-cost logistics (integer for opening a warehouse, continuous for shipment volume).
• Solver Technology: Modern commercial solvers like Gurobi and CPLEX are primarily optimized for large-scale MIP problems.

Branch and Bound is the fundamental, exact algorithmic framework for solving Integer Programs. It systematically explores the solution space by dividing it into smaller subproblems (branching) and eliminating subproblems that cannot contain the optimal solution (bounding).

• Branching: Creates subproblems by fixing a fractional variable to 0 and 1, recursively building a search tree.
• Bounding: Uses the objective value of the LP relaxation to provide a bound on the best possible integer solution in that subtree. If the bound is worse than a known integer solution, the subtree is pruned.
• Core of Modern Solvers: Enhanced with cutting planes, heuristics, and sophisticated node selection rules to achieve practical performance on large problems.

A Constraint Satisfaction Problem (CSP) is a computational problem defined by a set of variables, each with a domain of possible values, and a set of constraints that specify allowable combinations of values. While IP focuses on optimization with linear constraints, CSP is purely about feasibility with often non-linear, declarative constraints.

• Modeling Paradigm: CSPs use a more general constraint language (e.g., alldifferent, logical relations) compared to IP's linear inequalities.
• Solution Techniques: Employs constraint propagation (like arc consistency) and backtracking search rather than linear relaxations.
• Overlap: Many discrete problems can be modeled as either an IP or a CSP. Constraint Programming (CP) solvers for CSPs are often combined with MIP in hybrid optimization approaches.

The Cutting Plane Method is a technique for strengthening the LP relaxation of an IP by adding valid linear inequalities (cuts) that exclude fractional solutions without removing any integer feasible points.

• Tightening the Formulation: Each cut makes the LP relaxation's feasible region closer to the convex hull of integer solutions, yielding a better bound for branch and bound.
• Types of Cuts: Includes Gomory cuts (generated from the LP tableau), cover inequalities for knapsack constraints, and flow covers for network problems.
• Branch-and-Cut: The standard modern approach, which integrates the dynamic generation of cutting planes within the branch and bound tree.

Combinatorial Optimization is the broader field concerned with finding an optimal object from a finite set of discrete possibilities. Integer Programming is its primary mathematical modeling and exact solution framework.

• Canonical Problems: Includes the Traveling Salesperson Problem (TSP), Vehicle Routing Problem (VRP), Scheduling, and Network Design.
• NP-Hardness: Most interesting problems in this field are NP-hard, justifying the use of sophisticated IP techniques and heuristics.
• Interdisciplinary Core: Sits at the intersection of operations research, computer science, and applied mathematics, driving advancements in algorithms and solver technology.