Integer vs Linear Programming

Integer vs Linear Programming

Submit Homework

Integer programming (IP) and linear programming (LP) are core topics in business analytics tutoring and optimization. They look similar on paper, but integer constraints fundamentally change the geometry of the feasible region and the algorithms used to solve the problem. This page explains the key differences and why IP problems are much harder than LP problems.

LP → continuous, convex, solved efficiently. IP → discrete, non‑convex, often NP‑hard.

Why does adding integer constraints change everything? Because the feasible region becomes a set of isolated points instead of a continuous polyhedron. This destroys convexity, meaning the simplex method and interior‑point methods no longer apply. Instead, IP requires combinatorial search methods like branch‑and‑bound, branch‑and‑cut, or dynamic programming.

1. Start with a linear programming model. Objective: maximize or minimize a linear function. Constraints: linear equalities or inequalities.
2. Identify which variables must be integers. Examples: number of trucks, workers, machines, shipments, or binary decisions.
3. Observe the geometric change. LP feasible region = convex polyhedron. IP feasible region = discrete lattice points.
4. Relax the integer constraints. Solve the LP relaxation to get a bound on the optimal value.
5. Use branch‑and‑bound. Split the problem into subproblems by forcing integer choices.
6. Prune subproblems. Use bounds to eliminate branches that cannot contain the optimal integer solution.

Consider the LP relaxation:

Maximize 3x + 2y subject to x + y ≤ 4, x ≥ 0, y ≥ 0.

LP solution: (x, y) = (4, 0) with value 12.

Now add integer constraints: x, y ∈ ℤ.

Feasible integer points include (0,0), (1,3), (2,2), (3,1), (4,0). The best integer solution is (2,2) with value 10.

This gap between 12 (LP) and 10 (IP) is the **integrality gap**.

• Assuming the LP solution is valid for an IP problem.
• Forgetting that integer constraints destroy convexity.
• Thinking IP can be solved with simplex alone.
• Ignoring integrality gaps when interpreting results.

Integer programming is essential for scheduling, routing, facility location, supply chain design, and capital budgeting. Understanding the difference between LP and IP is crucial for selecting the right model and interpreting solutions correctly.

This idea connects directly to:

• Business Analytics (parent)
• Linear Programming & Optimization (spoke)
• Quantitative Post Hub
• Question Hub
• Tutoring Services