We're still actively developing this site. If you encounter any issues, please report them! - Report an issue

INTRODUCTION TO COMBINATORIAL OPTIMIZATION

COMPSCI/ISYE/MATH 425
Course Description

Focuses on optimization problems over discrete structures, such as shortest paths, spanning trees, flows, matchings, and the traveling salesman problem. We will investigate structural properties of these problems, and we will study both exact methods for their solution, and approximation algorithms.

Prerequisties

(MATH 320 , MATH 340 , MATH 341 , or MATH 375 ) or graduate/professional standing or member of the Pre-Masters Mathematics (Visiting International) Program

Satisfies

This course does not satisfy any prerequisites.

Credits

3

Offered

Spring

Grade Point Average
3

-2.89% from Historical

Completion Rate
93.75%

-1.01% from Historical

A Rate
35.94%

13.17% from Historical

Class Size
64

60.45% from Historical

2025 Fall Grade Distribution

Instructors (2025 Fall)

Sorted by ratings from Rate My Professors

Similar Courses

LINEAR OPTIMIZATION

COMPSCI/ISYE/MATH/STAT 525

Introduces optimization problems whose constraints are expressed by linear inequalities. Develops geometric and algebraic insights into the structure of the problem, with an emphasis on formal proofs. Presents the theory behind the simplex method, the main algorithm used to solve linear optimization problems. Explores duality theory and theorems of the alternatives.

INTRODUCTION TO OPTIMIZATION

COMPSCI/ECE/ISYE 524

Introduction to mathematical optimization from a modeling and solution perspective. Formulation of applications as discrete and continuous optimization problems and equilibrium models. Survey and appropriate usage of basic algorithms, data and software tools, including modeling languages and subroutine libraries.

INTEGER OPTIMIZATION

COMPSCI/ISYE/MATH 728

Introduces optimization problems over integers, and surveys the theory behind the algorithms used in state-of-the-art methods for solving such problems. Special attention is given to the polyhedral formulations of these problems, and to their algebraic and geometric properties. Applicability of Integer Optimization is highlighted with applications in combinatorial optimization. Key topics include: formulations, relaxations, polyhedral theory, cutting planes, decomposition, enumeration. Students are strongly encouraged to have knowledge of Linear Programming (e.g.,MATH/​COMP SCI/​I SY E/​STAT  525), including algorithms, duality and polyhedral theory.

ADVANCED ALGORITHMS

COMPSCI 787

Advanced paradigms for the design and analysis of efficient algorithms, including the use of randomness, linear programming, and semi-definite programming. Applications to data structures, approximating NP-hard optimization problems, learning, on-line and distributed problems. Students are strongly encouraged to have introductory knowledge of algorithms (e.g.,COMP SCI 577)

INTRODUCTION TO COMBINATORICS

COMPSCI/MATH/STAT 475

Problems of enumeration, distribution, and arrangement. Inclusion-exclusion principle. Generating functions and linear recurrence relations. Combinatorial identities. Graph coloring problems. Finite designs. Systems of distinct representatives and matching problems in graphs. Potential applications in the social, biological, and physical sciences. Puzzles. Problem solving.