Discrete Optimization

Optimization · Axiom Academy

Discover why whole numbers make optimization problems exponentially harder. Step 1: The Shopping Challenge You have 100 to spend on items. Each item costs 15 and gives you 10 points of value. How many should you buy? Compare what happens when we allow fractional solutions versus requiring integers. With just 10 binary decisions (yes/no choices), how many possible solutions exist? Click to reveal! Can we just solve the continuous problem and round to integers? Watch what happens! In discrete optimization, variables must take integer or discrete values (whole items, complete hours, yes/no decisions). This reflects real-world constraints that continuous models can't capture. The solution space grows exponentially with problem size (2 n for n binary variables). Most discrete optimization problems are NP-hard, meaning no known polynomial-time algorithm can solve them optimally. The continuous relaxation is easy to solve but provides only a bound on the optimal value. Rounding doesn't work - we need sophisticated techniques like branch-and-bound and cutting planes. State-of-the-art solvers combine exact methods (branch-and-cut), heuristics, and approximation algorithms to tackle real-world problems with thousands of variables in reasonable time.

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