Integer Programming: Discrete Optimization Solutions

Integer Programming (IP) extends linear programming to handle problems where decision variables must take integer or binary values. It's essential for optimization problems involving discrete choices like yes/no decisions, selecting items, or allocating indivisible resources.

What is Integer Programming?

Integer Programming is a mathematical optimization technique where some or all decision variables are restricted to integer values. When all variables must be integers, it's called Pure Integer Programming. When some variables are continuous, it's Mixed Integer Programming (MIP).

Types of Integer Programming

Pure Integer Programming

All decision variables must be integers:

xᵢ ∈ ℤ (integers)

Mixed Integer Programming (MIP)

Some variables are integers, others are continuous:

xᵢ ∈ ℤ, yⱼ ∈ ℝ

Binary Integer Programming (0-1 IP)

All variables are binary (0 or 1):

xᵢ ∈ {0, 1}

Also called Binary Programming or Zero-One Programming.

Mathematical Formulation

A general integer programming problem:

📐 Formula

Maximize (or Minimize): Z = c₁x₁ + c₂x₂ + ... + cₙxₙ Subject to: a₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ ≤ b₁ a₂₁x₁ + a₂₂x₂ + ... + a₂ₙxₙ ≤ b₂ ... aₘ₁x₁ + aₘ₂x₂ + ... + aₘₙxₙ ≤ bₘ x₁, x₂, ..., xₖ ∈ ℤ (integer variables) xₖ₊₁, ..., xₙ ∈ {0, 1} (binary variables) xₙ₊₁, ..., xₚ ∈ ℝ (continuous variables)

Why Integer Programming?

Many real-world problems require discrete decisions:

Yes/No Decisions: Build a facility or not
Item Selection: Choose from available options
Counting: Number of units must be whole
Logical Constraints: If-then relationships
Fixed Costs: Step functions in costs

Applications

Facility Location

Decide which facilities to open:

Warehouse location
Distribution centers
Manufacturing plants
Service facilities

Production Planning

Lot sizing problems
Production scheduling
Setup decisions
Capacity allocation

Capital Budgeting

Select investment projects:

Project selection
Resource allocation
Budget constraints

Assignment Problems

Job assignment
Vehicle routing
Team formation
Resource matching

Network Design

Network topology
Communication networks
Transportation networks

Solution Methods

Branch and Bound

Most common exact method:

Relaxation: Solve LP relaxation (ignore integer constraints)
Branching: If solution has fractional values, branch on a variable
Bounding: Use LP relaxation to get bounds
Pruning: Eliminate subproblems that can't improve solution
Iteration: Repeat until optimal solution found

Cutting Plane Methods

Add constraints (cuts) to eliminate fractional solutions:

Gomory cuts
Mixed integer rounding cuts
Cover cuts

Branch and Cut

Combines branch and bound with cutting planes.

Heuristic Methods

Approximate solutions for large problems:

Greedy algorithms
Local search
Genetic algorithms
Simulated annealing

Binary Decision Variables

Binary variables (0-1) are particularly useful for modeling logical conditions.

Fixed Cost Problem

Model setup costs:

📐 Formula

If x > 0, then y = 1, else y = 0 x ≤ My Where M is a large constant (big-M constraint)

Logical Constraints

At least one: Σᵢ xᵢ ≥ 1

At most one: Σᵢ xᵢ ≤ 1

Exactly one: Σᵢ xᵢ = 1

If-then: If x₁ = 1, then x₂ = 1

x₂ ≥ x₁

Either-or: x₁ + x₂ ≥ 1

Example: Facility Location

📐 Formula

Minimize: Σⱼ fⱼyⱼ + Σᵢ Σⱼ cᵢⱼxᵢⱼ Subject to: Σⱼ xᵢⱼ = 1 for all i (demand points) xᵢⱼ ≤ yⱼ for all i, j (can't assign to closed facility) yⱼ ∈ {0, 1} (open facility j?) xᵢⱼ ≥ 0 (assignment amount) Where: fⱼ = Fixed cost to open facility j cᵢⱼ = Cost to serve demand i from facility j yⱼ = 1 if facility j is open, 0 otherwise

Computational Complexity

Integer programming is NP-hard in general
Solution time can grow exponentially with problem size
Modern solvers use sophisticated techniques
Many practical problems can be solved efficiently
Approximation methods for very large problems

Linear Programming Relaxation

Solving IP by ignoring integer constraints gives LP relaxation:

Provides upper bound (maximization) or lower bound (minimization)
Solution may be infeasible (fractional values)
Gap between LP and IP solution indicates difficulty

Integrality Gap

Difference between LP relaxation and IP optimal solution.

Strengthening Formulations

Better formulations lead to faster solutions:

Tighter Bounds

Reducing feasible region of LP relaxation without removing integer solutions.

Fewer Variables

Eliminating unnecessary variables simplifies problem.

Better Constraints

Adding valid inequalities can improve bounds.

Software and Solvers

Modern solvers can handle large integer programs:

Commercial: CPLEX, Gurobi, XPRESS
Open Source: GLPK, CBC, OR-Tools
Modeling Languages: AMPL, GAMS, PuLP, Julia

Tips for Modeling

Use Binary Variables: Often easier than general integers
Avoid Big-M: Use smallest possible M values
Strengthen Formulations: Tighter constraints help
Symmetry Breaking: Reduce equivalent solutions
Reformulation: Alternative models may solve faster

When to Use Integer Programming

Appropriate When:

Discrete decisions required
Fixed costs present
Logical relationships needed
Exact solutions needed
Problem size manageable

Alternatives When:

Large-scale problems (heuristics)
Approximations acceptable
Can relax to continuous
Special structure allows other methods

Limitations

Computational complexity increases with size
Solution time can be unpredictable
May require approximation for large problems
Requires careful modeling
Big-M constraints can cause numerical issues

Conclusion

Integer programming is a powerful tool for optimization problems requiring discrete decisions. While computationally challenging, modern solvers and modeling techniques enable solutions to many practical problems. Understanding integer programming expands your ability to model and solve complex real-world optimization challenges.