Discrete Optimization Summary

Optimization · Axiom Academy

Let's review the key concepts from integer programming, classic problems, and solution techniques. What Makes It Hard: Variables must take integer or discrete values, not continuous real numbers Computational Complexity: Most discrete optimization problems are NP-hard, meaning no polynomial-time algorithm exists Practical Impact: Even small problems can have exponentially large solution spaces Why It Matters: Models real-world decisions where fractional solutions make no sense (schedules, assignments, routing) Formulation: Objective function and constraints with integer variable requirements LP Relaxation: Remove integer constraints to get a continuous problem with a lower/upper bound Integrality Gap: Difference between LP relaxation solution and true integer optimum Binary Variables: Special case where variables are 0 or 1, enabling logical constraints Example: Branch and Bound Algorithm Step 1 - Relax: Solve LP relaxation to get fractional solution and a bound on optimal value Step 2 - Branch: Select a fractional variable x i and create two subproblems: x i ≤ ⌊value⌋ and x i ≥ ⌈value⌉ Step 3 - Bound: Use LP relaxation values to prune subproblems that cannot improve the best known solution Step 4 - Iterate: Continue branching until all nodes are pruned or solved, guaranteeing optimality Classic Discrete Optimization Problems Traveling Salesman Problem (TSP): Find shortest tour visiting all cities exactly once

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