CIS 1890: Solving Hard Problems in Practice

Spring 2023

๐ŸŽ Course Overview

What does Sudoku have in common with debugging, scheduling exams, and routing shipments? All of these problems are provably hard โ€” no one has a fast algorithm to solve them. But in reality, people are quickly solving these problems on a huge scale with clever systems and heuristics!


In this minicourse, weโ€™ll explore how researchers and organizations like Microsoft, Google, and NASA are solving these hard problems, and weโ€™ll get to use some of the tools theyโ€™ve built!


Topics covered include: routing, scheduling, and packing problems; constraint programming in Python; SAT solving; optimization; operations research.

๐Ÿงญ Logistics

Instructors: Rohan Menezes & Charley Cunningham

Location: Towne 319

Time: Tue 5:15-6:45 PM

Course Sites: Please sign up for Ed and Gradescope through Canvas!

19x Combined Lecture: You must also enroll in the combined lecture, which consists of 3 optional lectures. Please reach out if you want to take CIS 1890 but have a conflict with the combined lecture.

๐ŸŽ“ Enrollment

Please request permission through Path! Permits to register will be granted periodically. Even if you aren't officially enrolled yet, feel free to show up to the first class (on Tuesday, 1/17).

CIS 1210 is a prerequisite for CIS 1890. You are expected to be fairly comfortable with programming and familiar with graphs. Experience with Python is helpful but not necessary. Knowledge of NP-completeness is not necessary but useful to motivate the course.

๐Ÿ“ Grading

Homeworks will consist of 4.5 medium-size programming projects, assigned roughly biweekly.


You will work in pairs on a final project of your choosing — you might choose to solve a practical problem using the tools weโ€™ll learn, implement a solver with modern techniques, or even explore new methods of your own!


Homework: 60%

Final Project: 30%

Attendance: 10%

๐Ÿ‘‹ Teaching Staff

Rohan Menezes

Instructor

rohanmenezes@alumni.upenn.edu

Office hours:

After class

Charley Cunningham

Instructor

ccunning@seas

Office hours:

Mondays 7-9pm in Levine 501 bump space or Zoom

Sahitya Senapathy

Teaching Assistant

sahityas@wharton

Office hours:

Sundays 3-5pm in the MBA Lounge (2nd floor of JMHH) or Zoom

Eric Chen

Teaching Assistant

ebchen@seas

Office hours:

Thursdays 10:30am-12:30pm in Moore 102 (DSL Conference Room) or Zoom

๐Ÿ“… Schedule

Week Date Lecture Additional Code Homework
1 1/17 Intro to Hard Problems Setup and HW0: Finger Exercises (due Tuesday, 1/24 by 4pm)
2 1/24 Solvers & Encoding Graph coloring HW1: Sudoku (due Tuesday, 2/7 by 4pm)
3 1/31 Algorithms for SAT
4 2/7 Modern SAT Techniques HW2: PennSAT (due Tuesday, 2/21 by 4pm)
5 2/14 Linear & Mixed-Integer Programming Basic LP, max flows, CPU assignment
6 2/21 More Mixed-Integer Programming Debugging MIP HW3: Kidney Exchange (due Tuesday, 3/14 by 4pm)
7 2/28 Guest Lecturer: TBA Final projects (partners due 3/16, proposal due 3/23)
8 3/14 Intro to Constraint Programming Cryptarithms, taxis, job shop HW4: Grace Hopper (due Tuesday, 3/28 by 4pm)
9 3/21 More Constraint Programming Magic sequence, ships Project proposal due this Thursday 3/23!
10 3/28 From CP to SAT
11 4/4 TSP Techniques
12 4/11 Local Search Project check-in due next week!
13 4/18 Genetic Algorithms Project presentations next class!