Instructor: Swati Gupta
Office: Groseclose Building 437
Contact: swatig@gatech.edu
Lecture: M,W 3:30PM – 4:45PM, Groseclose 402
Office Hours: Tuesday 2:00 – 3:00PM or by appointment.
Course Description: We will study the theoretical foundations of linear and integer programming with focus on algorithmic results. Topics covered will include algorithms for linear programming, polarity, diophantine approximation, lattices, basis reduction, complexity of linear equations, Gaussian Elimination, Euclid’s Algorithm, Lattices, Hermite Normal Form, Integral Farkas Lemma, algorithm for HNF, Minkowski’s Theorem, Gram Schmidt Orthogonalization, LLL algorithm, Applications of LLL, shortest vector problem, Dirichlet’s theorem, Fundamental theorem of Linear Inequalities, Farkas Lemma, totally unimodularity, total dual integrality.
Textbook:
- Theory of Linear and Integer Programming by Alexander Schrijver, Wiley, 1998.
Additional Reading:
- Notes on Lattices by Thomas Rothvoss.
- Lectures on Polytopes, Gunter Ziegler.
Grading:
- Homeworks (40%), Midterm (25%), Final (30%), Class participation (5%)
Course Policies:
- The assignments have to be submitted online, with typed-up solutions in LaTeX.
- Each assignment must include a statement signed by the student:
“I commit to uphold the ideals of honor and integrity by refusing to betray the trust bestowed upon me as a member of the Georgia Tech community.”
20% points will be taken off if this statement is missing.
- You are encouraged to discuss homework/assignments problems with your fellow students. But your final answers should be based on your own understanding unless it is a group assignment, which will be announced on Canvas. Copying others’ work is NOT acceptable and violates the honor code. Write the names of students you have discussed the assignments with. In case answers are found copied from another student, both the students (the one who allowed copying, and the one who copied) will both get a 0 and might also result in obtaining a D or F grade overall.
- Regrade requests will be accepted via email to the instructor within 5 days of the graded assignment/exam being returned. Requests must include (1) a PDF of the original submission and (2) a LaTeX-produced PDF detailing which problems were graded incorrectly and an argument that the submitted solution is indeed correct. Regrades may only be requested if it is believed that a correct answer was marked as incorrect, not because insufficient partial credit was given to an incorrect or partially correct solution. If you request a regrade, you accept that the entire assignment/exam will be regraded, not just the problem(s) believed to be graded incorrectly.
- Late assignments: We will allow a grace period of 1 hourfor every assignment. For every hour that the assignment is submitted late, the grade will be reduced by 10% (linearly interpolated), without exceptions. The only official extensions for late assignments will be granted with a letter from the Dean of Student’s Office to be received before the assignment is due.
- Exams: Exams will be conducted in person. Details of the exams will be announced later. Missing an exam will be accommodated only in case of Institute-approved absences with a letter from the Dean of Students. Alternative arrangements will be made on a case-by-case basis, but the instructor must be informed at least two weeks prior to the exam.
- Academic Honor Code
It is your responsibility to get familiar with the Georgia Tech Honor Code and you are bound by its requirements. For any questions any Academic Honor Code issues, please consult me, my teaching assistants, or honor.gatech.edu.(Links to an external site.)
Mutual Respect and Expectations
ISyE 7661 is an advanced graduate-level course. You are expected to have an attitude to learn, instead of just getting a grade. To produce a positive teaching and learning environment, instructors and students must partner with one another in and out of the classroom. Mutual respect is at the heart of such a partnership and is characterized by respectful language and imagery, punctuality and care for others’ time, clear and thorough communication, access to resources, and an openness to dialogue and debate. As a Georgia Tech faculty member, I am committed to such respect and I invite you to join me in working towards the best possible learning environment, so that all can meet their highest ambitions. Further, we will not tolerate discrimination towards any group of students. For more information about faculty and student expectations, as recognized in Georgia Tech policy, please see the following web page: http://www.catalog.gatech.edu/rules/22.php (Links to an external site.)
Office of Disability Services
If you are a student with learning needs that require special accommodation, please contact the Office of Disability Services (http://disabilityservices.gatech.edu/) at (404)894-2563 as soon as possible to make an appointment to discuss your special needs and to obtain an accommodations letter. Please also e-mail me as soon as possible in order to set up a time to discuss your learning needs.
Tentative Lecture Schedule
Tentative Lecture Schedule:
| Date | Lectures | Content | |
| M | August 22 | Lecture 1 | Review Linear Algebra |
| W | August 24 | Lecture 2 | Gaussian Elimination is PolyTime |
| M | Aug 29 | Lecture 3 | Lattices and Hermite Normal Form |
| W | Aug 31 | Lecture 4 | More on Lattices |
| M | Sep 5 | no class | |
| W | Sep 7 | Lecture 5 | Minkowski Theorem, Shortest Vector in a Lattice, Dirichlet’s Theorem |
| M | Sep 12 | Lecture 6 | LLL Algorithm, Gram Schmidt Orthogonalization, Coefficient Reduction |
| W | Sep 14 | Lecture 7 | LLL Reduction Applications |
| M | Sep 19 | Lecture 8 | Fundamental Theorem of Linear inequalities |
| W | Sep 21 | Lecture 9 | Farkas Lemma |
| M | Sep 26 | Lecture 10 | More Farkas Lemma |
| W | Sep 28 | Lecture 11 | Linear Programming |
| M | Oct 3 | Lecture 12 | Structure of Polyhedra |
| W | Oct 5 | Lecture 13 | Facets and Minimal Faces |
| M | Oct 10 | Lecture 14 | Faces of Dimension t+1 and Applications |
| W | Oct 12 | No Lecture | MIDTERM |
| M | Oct 17 | Fall Break | no class |
| W | Oct 19 | Lecture 15 | Fourier Motzkin Method |
| M | Oct 24 | Lecture 16 | (Dr. Gupta is traveling, and will reschedule class or have a Guest Lecture) |
| W | Oct 26 | Lecture 17 | Complexity of Linear Programming |
| M | Oct 31 | Lecture 18 | Simplex Method |
| W | Nov 2 | Lecture 19 | Ellipsoid Method |
| M | Nov 7 | Lecture 20 | Equivalence b/w Optimization and Separation |
| W | Nov 9 | Lecture 21 | Integer Programming: Hilbert Basis, Irrational Rotation is Dense |
| M | Nov 14 | Lecture 22 | Complexity of Integer Programming |
| W | Nov 16 | Lecture 23 | Lenstra’s Algorithm |
| M | Nov 21 | Lecture 24 | Total Unimodularity |
| W | Nov 23 | student recess, no class | |
| M | Nov 28 | Lecture 26 | More on TU |
| W | Nov 30 | Lecture 27 | Total Dual Integrality |
| M | Dec 5 | Lecture 28 | Cutting Planes and Chvatal Rank |
| W | Dec 7 | no class | |
| Friday | December 9th | 2:40 PM ‐ 5:30 PM | Final Exam |
| December 19th | Grades are due. |
Leave a Reply