Integer Programming

Optimization · Axiom Academy

Optimization with discrete decision variables and combinatorial structure 1. Integer Programming Formulation An integer program has the same structure as a linear program, but with integrality constraints on the variables. The general form consists of a linear objective function subject to linear constraints, with variables restricted to integer values. 2. Pure IP vs Mixed-Integer Programming The distinction between pure IP and MIP is important for both modeling and solution approaches. Pure IPs have only integer variables, while MIPs combine continuous and integer variables, offering more modeling flexibility but different algorithmic challenges. Pure IP Example: Facility location - decide which locations to open (binary variables). MIP Example: Production planning - how much to produce (continuous) and which machines to use (binary). The LP relaxation is formed by removing integrality constraints, allowing variables to take any real values within their bounds. This provides a bound on the optimal IP value and is fundamental to solution algorithms like branch-and-bound. The LP relaxation is easier to solve and always gives an optimistic bound: for maximization problems, the LP optimal value is an upper bound on the IP optimal value. For minimization, it's a lower bound.

This is the written version of the interactive lesson above. See the full Optimization course.