Home About
Courses Concepts Tools
GitHub

ORIE 4390

Course description (from class roster):

Hands-on experience with integer linear programming and dynamic programming: creating ILPs and DPs, implementing them, critiquing them, understanding solver output, and improving ILPs using better variables, constraints, symmetry breaking, etc. Examples of problems that we will study in this course are logistical problems like sequencing in production, scheduling problems with conflicts (vertex coloring), matching problems for markets and clustering problems in networks, but are not limited to these domains. In addition, a variety of general linear programming techniques such as Fourier-Motzkin elimination, Dantzig-Wolfe decomposition, Benders decomposition and extended formulations may be covered, as well as rounding techniques of LP solutions.

Offered: Fall or Spring.

Prerequisites: ORIE 3300 and ORIE 3310, or permission of instructor.

Outcomes:

  • Demonstrate ability to formulate strong ILPs.
  • Recognize, identify and improve problematic formulations.
  • Understand information from solver, and use this to improve formulations.
  • Ability to use Dynamic Programming in a variety of settings.

Is Python used?

Yes, although there is an option to use AMPL instead.

If Python is used, where is it used?

Python is used in homeworks, although students have the option to use AMPL instead. (Most students will probably want to use Python.)

What is Python used for?

Python is used as a frontend to an ILP solving package (Gurobi). It's recommended to either use GurobiPy or OR-Tools, and slightly preferred to use GurobiPy as it allows you to interface more directly with Gurobi (which is the only ILP solver used in the course).

What do I need to know?

You should have a minimal understanding of Python; specifically, you should be set if you've used GurobiPy or OR-Tools (or even CVXPY) before.

Relevant pages