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.
This is a preliminary list of topics planned for the course. I might add, remove, or substantially revise topics up until the semester begins. This course is actively being developed, so expect significant changes to content and schedule over the next several weeks.
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 |
|---|---|---|---|---|---|---|---|
| 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. Due Feb 01/2026 midnight 11:59 p.m. |
| 2 | 01/22/2026 | Lecture 2 Slides (Pauses) | Lecture 2 Handout | Simplex algorithm, geometric intuition, basic feasible solutions, pivoting, LP duality, accessing duals in Gurobi. | Refresh your memory with Matplotlib/pandas. | Finish HW 1. | |
| 3 | 01/27/2026 | Lecture 3 Slides (Pauses) | Lecture 3 Handout | 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. Due TBD 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.
Schedule and Weekly Learning Goals
The course is organized into bi-weekly, or tri-weekly modules, each focused on a core topic in algorithmic engineering. Below is a high-level schedule outlining the topics covered each week. This structure is designed to balance theoretical foundations with practical modeling and implementation skills.
Part I: Mathematical Programming
Week 01 – Linear Programming
- Lecture Content: Introduction to linear programming, geometry of linear programming, the simplex algorithm, and LP duality.
- Lab Goal: Install Gurobi, solve simple linear programs, and interpret solver output.
Week 02 – Linear Programming (cont’d)
- Lecture Content: Interpreting and using LP solutions, sensitivity analysis, applications in approximating NP-hard problems (e.g., vertex cover), real-world use cases (manufacturing, supply chain), and network models.
- Lab Goal: Build and solve large-scale linear programs in Gurobi, debug LP models, perform sensitivity analysis, and gain practice with assignment-style problems.
Week 03 – Integer Programming
- Lecture Content: Applications of integer programming, cutting plane methods, branch-and-bound, specially ordered sets (SOS1, SOS2), disjunctive constraints, constraint simplification, bound tightening, and modeling non-convex regions.
- Lab Goal: Build and solve large-scale integer linear programs using Gurobi for applied scenarios.
Week 04 – MILP and MINLP
- Lecture Content: Mixed-integer nonlinear programming (MINLP): basic theory, problem structure, and practical solvability.
- Lab Goal: Use Gurobi to model and solve challenging MINLPs with nonlinear constraints and integer decisions.
Part II: Global Optimization & Differentiable Algorithms
Week 05 – Convex Programming and Gradient-Based Optimization
- Lecture Content: Local vs. global optimization, convexity, optimality conditions, gradient descent and stochastic gradient descent (SGD), Newton’s method, and step-size selection. Introduction to PyTorch tensors and automatic differentiation. Comparison between solver-based (LP/QP) and gradient-based optimization.
- Lab Goal: Implement gradient descent and Newton’s method from scratch for convex functions. Visualize convergence, experiment with learning rates, and verify gradients using PyTorch autograd. Compare with solver-based solutions (e.g., Gurobi).
Week 06 – Metaheuristics and Global Optimization
- Lecture Content: Non-convex optimization and heuristic search. Simulated annealing: temperature schedules and acceptance probabilities. Genetic algorithms: representation, crossover, mutation, and selection. Discussion on gradient-free methods and hybrid optimization strategies combining metaheuristics with gradient descent.
- Lab Goal: Model non-convex optimization problems in Python using Pyomo. Implement simulated annealing for problems like TSP or function minimization. Use the DEAP library to apply genetic algorithms to real problems and evaluate performance.
Week 07 – Neural Networks and Automatic Differentiation
- Lecture Content: Differentiable programming and computational graphs. Chain rule, backpropagation, and reverse-mode automatic differentiation. Neural networks as differentiable programs. Introduction to PyTorch: tensors, autograd, and optimizers. Neural network training as non-convex optimization.
- Lab Goal: Implement a mini automatic differentiation engine (micrograd-style). Train a simple neural network using your custom autodiff, then replicate the same experiment in PyTorch. Compare gradients, performance, and numerical stability.
Part III: Satisfiability & Formal Methods
Week 08 – Introduction to SAT and SMT
- Lecture Content: Introduction to satisfiability (SAT) and satisfiability modulo theories (SMT). Propositional logic and CNF conversion. Overview of theory solvers for equality, integers, arrays, and bitvectors. Applications in verification, planning, and logic puzzles.
- Lab Goal: Install and run SAT/SMT solvers (Z3 and PySAT). Solve introductory SAT and SMT problems such as Sudoku and graph 3-coloring. Familiarize with Z3Py syntax.
Week 09 – Internals of SAT and SMT Solvers
- Lecture Content: How SAT solvers work: DPLL, unit propagation, and CDCL (conflict-driven clause learning). Decision heuristics (e.g., VSIDS). Extensions to MaxSAT and pseudo-Boolean SAT. SMT solver architecture and Nelson–Oppen combination of theories.
- Lab Goal: Write a basic DPLL SAT solver in Python. Modify and experiment with examples using PySAT. Encode SMT formulas with combined theories (e.g., arrays + linear integer arithmetic) in Z3.
Week 10 – Practical SMT Applications and Encoding
- Lecture Content: Applications of SMT solvers in writing proofs, recreational mathematics and puzzles, and NP-Hard problems. Encoding real-world problems in SMT (e.g., puzzles, resource allocation). Techniques for reducing problems to SAT or SMT. SMT-LIB standard and benchmarks.
- Lab Goal: Writing a formal proof for basic theorems in discrete math using Z3. Build an SMT-based symbolic executor for a toy programming language (starter code provided). Formulate scheduling and constraint-based tasks using Z3. Encode graph problems (e.g., coloring, clique) in both SAT and SMT.
Part IV: Learning-Augmented Algorithms and Data-Driven Optimization
Week 11 – Data-Driven Online Algorithms
- Lecture Content: Online algorithms and decision-making under uncertainty. Classical results (secretary problem, prophet inequalities) and competitive analysis. Introduction to learning-augmented algorithms: using predictions to guide online decisions. Applications in scheduling, pricing, and resource allocation.
- Lab Goal: Implement online decision algorithms for sequential selection problems (e.g., secretary problem). Integrate regression-based predictions to improve performance. Compare baseline, prediction-only, and learning-augmented strategies.
Week 12 – Learning-Augmented Optimization and Modeling
- Lecture Content: Integrating predictive models into optimization workflows. Online regression (incremental least squares, SGD) and bilevel formulations. Data-driven optimization using predicted parameters. Applications in pricing, portfolio selection, and project allocation.
- Lab Goal: Train a regression model (e.g., house price or demand prediction) and embed predictions into a linear or integer optimization model. Solve with Gurobi or Pyomo, evaluate how prediction accuracy impacts optimization quality, and explore online model updates.
- Case Studies and Tools: NYC school assignment, organ exchange simulations, MatchingMarkets.jl (Julia), Stanford DA library (Python).
Part V: Large-Scale Differentiable and Symbolic Systems
Week 13 – LLMs as Differentiable Reasoning Engines
- Lecture Content: Introduction to using large language models (LLMs) for code generation and algorithmic reasoning. Overview of in-context learning, few-shot prompting, chain-of-thought reasoning, and self-consistency. Discussion on the capabilities and limitations of LLMs for solving algorithmic problems.
- Lab Goal: Use LLMs (e.g., OpenAI Codex, or Open Source Small LLMs) to solve algorithmic coding problems from a benchmark dataset (e.g., Leetcode). Experiment with different prompt engineering strategies to improve solution quality and reliability.
- Tools and Resources: OpenAI API (or local LLMs if available), Free LLAMA, prompt templates, Leetcode problem set, Python evaluation harness.
Week 14 – Program Synthesis + Verification + Human-in-the-Loop Optimization
- Lecture Content: Program synthesis fundamentals, syntax-guided synthesis (SyGuS), constraint-based synthesis, and inductive programming. How synthesis techniques can complement LLMs for more robust problem solving. Human-in-the-loop approaches for correcting and refining generated code.
- Lab Goal: Build a pipeline that uses an LLM to generate candidate solutions, validates them against test cases, and refines them using synthesis techniques. Use Z3 or PySMT to generate candidate patches or verify logical correctness. Compete to solve as many Leetcode-style problems as possible using automated or semi-automated approaches.
- Project Outcome: End-to-end automated solving and synthesis system for programming tasks; leaderboard or summary comparing approaches across students.
Week 15–16 – Spillover, MLK day, and Spring break.
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.