Mathematics / advanced
Linear and integer optimization
Connect polyhedral geometry, combinatorial structure, algorithms, and certificates for discrete optimization.
Your route through mathematics
Follow the path or begin with a question. Every lesson is open.
Your place, at your pace. Progress is optional and saved only in this browser when available.
Read / explore / reason
Inside this module
Module 01 advanced
Linear and integer optimization
Connect polyhedral geometry, combinatorial structure, algorithms, and certificates for discrete optimization.
- 01
Polyhedra, faces, and extreme points
Read linear constraints as geometry and determine when an optimum can be certified at a vertex.
19 min - 02
Standard forms and basic feasible solutions
Translate constraints without changing the optimization problem and connect algebraic bases to vertices.
19 min - 03
Simplex pivots and degeneracy
Derive reduced costs and the ratio test, then distinguish geometric progress from a change of basis.
21 min - 04
Linear programming duality and certificates
Prove global bounds by weighted constraints and distinguish optimality, infeasibility, and unboundedness certificates.
21 min - 05
Complementary slackness and sensitivity
Turn a duality gap into componentwise conditions and identify the range over which shadow prices remain valid.
22 min - 06
Interior-point methods and the central path
Derive barrier optimality conditions and use primal-dual complementarity to measure distance from an LP optimum.
23 min - 07
Total unimodularity and integrality
Use determinant structure to explain when a continuous relaxation already has integral vertices.
22 min - 08
Network-flow linear programs
Formulate conservation and capacity constraints, then connect integral flows, cuts, and min-cost potentials.
22 min - 09
Branch and bound and valid bounds
Build an exhaustive integer search whose relaxed bounds justify pruning and whose incumbent certifies achievable value.
23 min - 10
Cutting planes and integer hulls
Derive valid inequalities that remove fractional relaxations while preserving every intended integer solution.
24 min