Discrete Optimization

Undergraduate

Problems and methods in discrete optimization. Linear programming: problem formulation, the simplex method, software, and applications. Network models: assignment problems, max-flow problem. Directed graphs: topological sorting, dynamic programming and path problems, and the travelling salesman’s problem. General graphs: Eulerian and Hamiltonian paths and circuits, and matchings. Course Format: Lectures, 3 hours per week; lab, 1 hour per week. Prerequisite(s): MATH 1P11 or MATH 1P12 Course Notes: This course may be offered in multiple modes of delivery. The method of delivery will be listed on the academic timetable, in the applicable term. Software Fee Required. Exclusions: Completion of this course will replace previous assigned grade and credit obtained in MATH 2P72.