CS498: Algorithmic Engineering: Solving Real-World Problems with Theoretical Tools
Elfarouk Harb
Spring 2026
E-mail: eyfmharb@gmail.com
Instructors Homepage: Elfarouk Harb (aka Farouk) will lead the course, with Professor Chandra Chekuri participating in an advisory and helping role throughout the course.
Office Hours: TBD
Class Hours: TR 2 p.m - 3:15 p.m at 2200 Sidney Lu Mech Engr Bldg.
Links:
Gradescope: Entry Code PK5XK2
EdStem: https://edstem.org/us/join/gjX2Kw
This is a preliminary list of topics planned for the course. I might add, remove, or revise topics throughout the semester This is a new course, so expect some changes to content and schedule over the next several weeks. However, no major changes should happen.
Course Description
This course explores the powerful intersection of theory and practice in algorithmic problem-solving, teaching students to apply advanced computational tools like LP solvers, SAT/SMT solvers, metaheuristics, and other theoretical tools to real-world engineering, optimization, and decision-making challenges.
We explain the theory behind these tools to build intuition, but the emphasis is on application: modeling, using solvers effectively, and engineering robust, efficient solutions. Students will gain hands-on experience working on problems in logistics, verification, scheduling, fair division, auctions, online algorithms, and LLM driven program-synthesis.
Topics include:
- Linear, Integer, and Mixed-Integer Programming: Modeling and solving real-world problems using Gurobi, Pyomo, and SCIP. Topics include LP duality, sensitivity analysis, integer formulations, branch-and-bound, cutting planes, disjunctive constraints, and mixed-integer nonlinear programming (MINLP). Applications span logistics, scheduling, verification, and network design.
- Global Optimization & Differentiable Algorithms: Extending classical optimization to non-convex and differentiable settings. Implementing gradient descent, stochastic methods, and Newton’s method; exploring metaheuristics such as simulated annealing and genetic algorithms; and introducing automatic differentiation and neural network optimization with PyTorch.
- SAT and SMT Solving: Automating reasoning and verification with Z3 and PySAT, including encodings of combinatorial, scheduling, and verification problems. Topics include DPLL, CDCL, theory combination, and symbolic execution.
- Learning-Augmented Algorithms & Data-Driven Optimization: Integrating predictive models into algorithmic decision-making. Online regression, incremental learning, and hybrid optimization pipelines that use predictions to improve classical algorithms and solver performance under uncertainty.
- Large-Scale Differentiable and Symbolic Systems: Exploring applications in LLM-driven optimization and program synthesis. Using large language models, constraint solvers, and synthesis techniques together for algorithmic reasoning, automated code generation, and human-AI collaborative problem solving.
By the end of the course, students will not only understand the basic underlying theoretical principles, but more importantly, be equipped to integrate these powerful tools into complex, real-world systems.
Grading
Overview
Your final grade in CS498: Algorithmic Engineering is composed of three components:
| Component | Weight | Description |
|---|---|---|
| Weekly Homeworks | 60 % | Weekly, collaborative, high-volume assignments done in groups of 2–4. Working alone is a competitive disadvantage. Collaboration is encouraged. |
| Pulse Checks | 10 % | Three short, in-class individual quizzes given after Parts I, II, III of the course. Their goal is simply to check if you’re “alive”, understanding the bare minimum earns 100 %. |
| Final Project | 30 % | An individual Algorithmic Engineering project, build a system, implement a paper, or optimize a complex pipeline, comparing performance (speed/quality). |
Schedule and Lectures Table (Preliminary)
| # | Date | Lecture Slides (Pauses) | Lecture Handouts (For printing) | Topics Covered | Todos Before | Todos After | Notes | Additional Readings (For those Interested) |
|---|---|---|---|---|---|---|---|---|
| 1 | 01/20/2026 | Lecture 1 Slides (Pauses) | Lecture 1 Handout | Course overview, comparison to CS374/473, tooling stack, history of LP, Engineer’s Diet problem, Gurobi output interpretation. | Read syllabus; install Gurobi + Python env. | Review LP basics; try “Engineer’s Diet” Problem in HW1 | Homework 1 Released and the Jupyter Notebook. Due Feb 01/2026 midnight 11:59 p.m. | Reminiscences about the origins of linear programming. Also, the structure of polyhedra as intersections of halfspaces and their equivalence with convex hulls of finitely many points Minkowski–Weyl theorem. See for example Ziegler, Lectures on Polytopes (Theorem 1.1). |
| 2 | 01/22/2026 | Lecture 2 Slides (Pauses) | Lecture 2 Handout | Simplex algorithm, geometric intuition, basic feasible solutions, pivoting. | Refresh your memory with Matplotlib/pandas. | Finish HW 1. | ||
| 3 | 01/27/2026 | Lecture 3 Slides (Pauses) | Lecture 3 Handout | Continue Simplex, LP duality, accessing duals in Gurobi, Sensitivity analysis, shadow prices, complementary slackness, discussed duals as “what-if” tools for constraints, network flow models, interpreting Gurobi duals, and shadow price limitations. | ||||
| 4 | 01/29/2026 | Lecture 4 Slides (Pauses) | Lecture 4 Handout | LP relaxations, vertex cover modeling, LP rounding (0.5-threshold), assignment problem (total unimodularity), independent set and integrality gaps. | Review graph basics and Gurobi modeling syntax. | Homework 2 Released and the Jupyter Notebook. Due Feb 08, 2026 midnight 11:59 p.m. | ||
| 5 | 02/03/2026 | Lecture 5 Slides (Pauses) | Lecture 5 Handout | Integer programs vs LP relaxations, 0–1 knapsack, LP bounds, branch-and-bound (bounds, incumbents, pruning) | Review LP relaxations from Lecture 4. | |||
| 6 | 02/05/2026 | Lecture 6 Slides (Pauses) | Lecture 6 Handout | formulation strength and cover inequalities, Binary modeling patterns, fixed-charge and logical constraints, Big-M (tight vs loose), SOS1/SOS2. | Review binary variable modeling in Gurobi. | Homework 3 Released and the Jupyter Notebook. Due Feb 17, 2026 midnight 11:59 p.m. | ||
| 7 | 02/10/2026 | Lecture 7 Slides (Pauses) | Lecture 7 Handout | TSP modeling and subtour elimination, Mixed Integer Non Linear Optimization, Non-Convex optimization in Gurobi, Spatial Branch and Bound. | ||||
| 8 | 02/12/2026 | Lecture 8 Slides (Pauses) | Lecture 8 Handout | Minimum s-t cut. Row Generation in linear programming, Separation oracles, and The Ellipsoid Method | ||||
| 9 | 02/17/2026 | Lecture 9 Slides (Pauses) | Lecture 9 Handout | Large scale integer linear programs, lazy cuts, user cuts (aka strengthening cuts), and case study on TSP | Homework 4 Released and the Jupyter Notebook. Due Feb 24, 2026 midnight 11:59 p.m. | |||
| 10 | 02/19/2026 | Lecture 10 Slides (Pauses) | Lecture 10 Handout | Convex Optimization Lingo (definitions, examples ,etc), Gradient Descent, and just introduced Pytorch | ||||
| 11 | 02/24/2026 | Lecture 11 Slides (Pauses) | Lecture 11 Handout | Continuing Pytorch and its internals, Ridge Regression, Teaser on Constrained Optimization (Projected gradient descent) | Homework 5 Released and the Jupyter Notebook. Due March 3, 2026 midnight 11:59 p.m. | |||
| 12 | 02/26/2026 | Lecture 12 Slides (Pauses) | – | Penalty Methods, Lagrangian Duality (with Primal-dual descent) & Constrained Optimization | ||||
| 13 | 03/03/2026 | Guest Lecture 1 by Chandra | – | Semidefinite Programming and its convex programming formulation, Max-Cut | ||||
| 14 | 03/05/2026 | Guest Lecture by Saurav – Fleetline | Homework 6 Released and the Package. Due March 23, 2026 midnight 11:59 p.m. | |||||
| 15 | 03/10/2026 | Guest Lecture 2 by Chandra | – | More applications of SDP like Metric Space embeddings, Balanced Graph Partition, Sum of squares Polynomials, and Artin Polynomials. | ||||
| 16 | 03/12/2026 | Lecture 16 Slides (Pauses) | – | Non-Convex Landscapes, Simulated Annealing & Genetic Algorithms | ||||
| 17 | 03/24/2026 | Lecture 17 Slides (Pauses) | – | Introduction to SAT and SMT solvers, Z3, Sudoku and N-Queens in Z3. | ||||
| 18 | 03/26/2026 | Lecture 18 Slides (Pauses) | – | Internals of SAT Solvers: DPLL, Unit Propagation, Literal Elimination, CDCL, VSIDS Heuristic, and random restarts. | ||||
| 19 | 03/31/2026 | Lecture 19 Slides (Pauses) | – | SMT: What is a theory, a solver, common theories in Z3, combining theories | ||||
| 20 | 04/02/2026 | Lecture 20 Slides (Pauses) | – | SMT Applications: Puzzles, Verification, and Proof verification | Homework 7 Released and the Package. Due April 14, 2026 midnight 11:59 p.m. | |||
| 21 | 04/07/2026 | Lecture 21 Slides (Pauses) | Lecture 21 Slides (Handout) | The Learning Problem, Stochastic Gradient Descent, Adam, AdamW, and learning rate schedules. | ||||
| 22 | 04/09/2026 | Lecture 22 Slides (Pauses) | Lecture 22 Slides (Handout) | Neural Networks and PyTorch, MLPs, key building blocks (residual connections, normalization, dropout), and training on MNIST/GPUs. | A nice paper on double descent and related topics, shared by your classmate Jake Mayer. | |||
| 23 | 04/14/2026 | Lecture 23 Slides (Pauses) | PyTorch in Practice, training on MNIST/GPU, Convolutional Neural Networks. | Homework 8 Released and accompanying required Package. Due April 21, 2026 midnight 11:59 p.m. |
Late Homework Policy
Intuition and Motivation
To balance flexibility and fairness, each student is allocated 168 total late hours (7 days) across all homework assignments. This policy encourages consistent progress while allowing for unforeseen circumstances (illness, travel, project deadlines, etc.).
- Each assignment has an official due date (e.g., 11:59 p.m. on the listed due day).
- You may submit any assignment late, and your late time for that submission will be the number of hours past the deadline.
- The total sum of your late hours across all assignments (say, HW₁, HW₂, …, HWₙ) is tracked.
- If
then there is no penalty whatsoever.
If your total lateness exceeds the 168-hour allowance, we will automatically determine the set of homework submissions to count toward your grade using an optimization procedure (yes, a real algorithmic selection process!) designed to maximize your total homework score under the late-hour constraint.
Formal Definition (Optimization Model)
Let:
- $n$ : total number of homework assignments
- $s_i$: your score on homework $i$ (a number between 0 and 100)
- $l_i$: number of late hours for homework $i$. This can be fractional (example 3.35 hours).
- $x_i \in {0, 1}$: binary decision variable indicating whether HW $i$ is counted toward your grade (1) or discarded (0)
We solve the following 0–1 Knapsack Integer Linear Program (ILP):
\[\begin{aligned} \text{maximize}\quad & \sum_{i=1}^{n} s_i x_i \\ \text{subject to}\quad & \sum_{i=1}^{n} l_i x_i \le 168, \\ & x_i \in \{0, 1\}, \quad i = 1, \dots, n. \end{aligned}\]This ensures we select the subset of assignments (within your late-hour budget) that maximizes your total homework score.
- If you exceed 168 late hours, some of your late submissions may be ignored (i.e., (x_i = 0)) when computing your final grade. This means you get $0$ on them.
- This procedure is deterministic, fair, and, of course, algorithmically optimal.
Examples
Example 1 — Within Limit
| HW | Score ($s_i$) | Late (hours $l_i$) |
|---|---|---|
| 1 | 95 | 12 |
| 2 | 100 | 36 |
| 3 | 85 | 48 |
| 4 | 90 | 60 |
| Total | – | 156 ≤ 168 |
You’re fine! No penalty. All homeworks count toward your grade.
Example 2 — Over Limit (Knapsack Activated)
| HW | Score ($s_i$) | Late (hours $l_i$) |
|---|---|---|
| 1 | 100 | 72 |
| 2 | 95 | 84 |
| 3 | 90 | 72 |
| 4 | 70 | 36 |
| Total | – | 264 > 168 |
Here we solve the ILP:
\[\max 100x_1 + 95x_2 + 90x_3 + 70x_4\] \[\text{s.t. } 72x_1 + 84x_2 + 72x_3 + 36x_4 \le 168,\quad x_i \in \{0, 1\}.\]The optimal solution (e.g., found by any ILP solver) might be:
- $x_1 = 1$, $x_2 = 1$, $x_3 = 0$, $x_4 = 0$
- Total hours = 156 (≤ 168), Total score = 195
The ILP chooses HW1 and HW2 (scores 100 and 95, total 195 points) with 156 late hours, and drops HW3 and HW4.
Notes
- You are encouraged to use your solver skills (Gurobi, etc.) to simulate your own late-policy outcomes. Yes, this is an open invitation to run your own Knapsack solver on your homework history!
- Think of it as a meta-homework problem—the course’s late policy is itself a real-world application of the very optimization techniques we study.
Required Materials and References
No required materials, and references will be used when needed. Course notes and slides will be provided as needed, and book references will be made.
Prerequisites
The equivalent of CS374, and proficiency in programming in Python (All assignments can be solved in Python only). Experience with a compiled language like C++ or rust is also beneficial.
In terms of Python experience, if you have some experience with numpy, Python programming, etc, you should be good for the course.
Course Objectives
By the end of this course, successful students will be able to:
- Model real-world problems using tools from linear programming, integer programming, satisfiability solving, and game theory.
- Select and apply appropriate algorithmic tools (e.g., LP solvers, SAT/SMT solvers, global optimization methods) to solve complex engineering and decision-making problems.
- Understand the core theoretical foundations of the tools used (e.g., duality in LP, CDCL in SAT solvers, basic auction theory) to better guide their practical application.
- Use modern optimization software (e.g., Gurobi, Pyomo, SCIP, Z3, PySAT) to formulate and solve problems efficiently.
- Compare and integrate multiple solving strategies, including exact, heuristic, and hybrid approaches, depending on the structure and scale of the problem.
- Translate abstract problems into formal models, including constraints, objectives, and variables suitable for solver-based techniques.
- Develop practical implementations of algorithms for scheduling, verification, planning, and fair resource allocation.
- Explore emerging applications, such as LLM-assisted program synthesis and solver-driven automation in AI pipelines.