CS 521: Linear Programming -- Fall 2022

Instructor Sepehr Assadi
Credits 3 units
Schedule Fridays 10:20 AM - 1:20 PM in PH-111 (Busch campus)
Prerequisites Undergraduate courses on algorithms, complexity theory, discrete mathematics, linear algebra, and probability; mathematical maturity. An advanced graduate course on algorithms (like CS 513 or 514) is strongly encouraged.
Syllabus The full course syllabus is available here. This webpage contains the highlights of course syllabus that are potentially updated as the semester progresses.

Overview

Linear programming (LP) is an extremely general and popular method of optimization in various domains including computer science, operations research, engineering, and economics. This course primarily focuses on the theoretical foundations of LPs including modeling concepts, theory, algorithms, and theoretical applications.

The course is intended for computer science graduate students, as well as advanced graduate students from other disciplines, with the main purpose of equipping the students with required background to use linear programming as part of their own research toolkit.

Logistics

This course has no recitation sections.

COVID-19 Protocols: In accordance with Rutgers' policy, masks must be worn during class meetings. (According to Rutgers' updated policy, masks are no longer required in classes).

List of Topics

The following is a tentative list of topics (not necessarily in order) that will be covered in this course. Along the way, we will learn about various algorithmic, analytic, and structural results in the context of linear programming that are widely applicable to other areas of theoretical computer science as well.

Grading

The final grade for the course will be based on the following weights: More details on the grading is posted in the course syllabus.

Course Calendar

The schedule below the red line is tentative and subject to change.

# Date Topics Lecture notes and Remarks
1 Fri 09/09 Introduction, Course Policy, Simple Examples of LPs Lecture Notes 1
2 Fri 09/16 Basics of LPs: Standard Forms and Basic Feasible Solutions Lecture Notes 2
3 Fri 09/23 The Simplex Algorithm Lecture Notes 3
4 Fri 09/30 Duality in Linear Programming, Farkas Lemma Lecture Notes 4
5 Fri 10/07 Low Dimensional LPs and Clarkson's Algorithm Lecture Notes 5
6 Fri 10/14 Multiplicative Weight Update Method and Applications to Max-Flow Lecture Notes 6
7 Fri 10/21 Convexity in Linear Programming Lecture Notes 7
8 Fri 10/28 Introduction to Cutting Plane Methods: Center of Gravity Lecture Notes 8
9 Fri 11/04 Ellipsoid Algorithm Lecture Notes 9
10 Fri 11/11 More on Ellipsoid Algorithm and Applications
11 Fri 11/18 Gradient Descent and Applications Lecture Notes 11
12 Wed 11/23 Newton Method and Intro to Interior Point Methods Lecture Notes 12
13 Fri 12/02 Interior Point Methods
14 Fri 12/09 More on Interior Point Methods and Applications

Resources

There is no official textbook for this course and all required materials will be posted on this webpage. The following is a list of some helpful supplementary materials (this list is by no means comprehensive):

LaTeX

You can download LaTeX for free here. For the purpose of this course, you do not even need to install LaTeX and can instead use an online LaTeX editor such as Overleaf.

Two great introductory resources for LaTeX are A Short Introduction to LaTeX by Allin Cottrell (for general purpose LaTeX) and LaTeX for Undergraduates by Jim Hefferson (for undergraduates mathematics) accompanied by the following cheatsheet (note that this document use "\( MATH \)" notation compared to the perhaps more widely used "$ MATH $" -- both are completely fine in LaTeX). You can also use this wonderful tool Detexify by Daniel Kirsch for finding the LaTeX commands of a symbol (just draw the symbol!).

If you are interested in learning more about LaTeX (beyond what is needed for this course), check the Wikibook on LaTeX and the Wikibook on LaTeX for Mathematics.

Rutgers CS Diversity and Inclusion Statement

Rutgers Computer Science Department is committed to creating a consciously anti-racist, inclusive community that welcomes diversity in various dimensions (e.g., race, national origin, gender, sexuality, disability status, class, or religious beliefs). We will not tolerate micro-aggressions and discrimination that creates a hostile atmosphere in the class and/or threatens the well-being of our students. We will continuously strive to create a safe learning environment that allows for the open exchange of ideas and cherished freedom of speech, while also ensuring equitable opportunities and respect for all of us. Our goal is to maintain an environment where students, staff, and faculty can contribute without the fear of ridicule or intolerant or offensive language.

If you witness or experience racism, discrimination micro-aggressions, or other offensive behavior, you are encouraged to bring it to the attention to the undergraduate program director and/or the department chair. You can also report it to the Bias Incident Reporting System

COVID-19 Protocols

In order to protect the health and well-being of all members of the University community, masks must be worn by all persons on campus when in the presence of others (within six feet) and in buildings in non-private enclosed settings (e.g., common workspaces, workstations, meeting rooms, classrooms, etc.). Masks must be worn during class meetings; any student not wearing a mask will be asked to leave.

Masks should conform to CDC guidelines and should completely cover the nose and mouth.

If you are feeling sick, or suspect you may have been exposed to COVID-19, do not come to the class. Arrangements will be made for students who are not able to attend class because of an illness or quarantine.