625.736.81 - Combinatorial Optimization

Expanded Course Description

Prerequisites: Probability (EN.625.603 or similar course). Linear algebra and experience with reading and writing proofs as found in EN.625.609 or similar course.

Instructor Contact information:

Christine Nickel

Cell: 703.732.6824
E-mail: cnickel1@jh.edu

Course Structure

The course materials are divided into modules which can be accessed by clicking Modules on the course menu. A module will have several sections including the overview, readings, lectures, discussions, and assignments. You are encouraged to preview all sections of the module before starting. All modules run for a period of seven (7) days. You should regularly check the Calendar and Announcements for assignment due dates.

Course Topics

PART I: Combinatorial algorithms for classic discrete optimization problems

• Quick Overview of flow problems
  • Maximum flow
  • Minimum Cut
  • Minimum cost flow
• Matching theory:
  • Matchings and alternating paths
  • Tutte-Berge formula
  • Maximum cardinality matchings
  • Bipartite matching via flow
  • Edmond’s blossom algorithm

• Basic polyhedral theory
• Linear Programming
  • Quick overview of duality, algorithms for LP
  • Equivalence of optimization and separation
• (3) Integer Programming
  • Totally unimodular matrices (TUM)
  • Total Dual Integrality (TDI)
  • Cutting plane theory
  • Branch and bound, branch and cut algorithms
• Application of linear and integer programming theory to problems discussed in Part I

• Lattice theory and algorithmic geometry of numbers 

Course Goals

To provide a background in the combinatorial optimization problems and the methodologies used to solve them. 

Course Learning Outcomes (CLOs)

• Identify combinatorial optimization problems.
• Describe algorithms for solving maximum flow and cardinality matching problems.
• Formulate combinatorial optimization problems as (integer) linear program.
• Determine the conditions under which the geometry of combinatorial optimization problems results in efficient solution techniques.
• Discuss the basic definitions and important tools from lattice theory as applied to combinatorial optimization.

Textbooks

No required text.

Other Materials & Online Resources

Useful textbooks and resources

• The "4-Bill Book": Combinatorial Optimization by Cook, Cunningham, Pulleyblank, Schrijver; 1st edition; ISBN 978-0-471-55894-1.
• Notes on Combinatorial Optimization by Lex Schrijver
• Integer Programming by Conforti, Cornuejols, Zambelli; ISBN 978-3-319-11007-3. Online access from Springer.
• Theory of Linear and Integer Programming by Lex Schrijver; 1st edition; ISBN 978-0-471-98232-6
• Combinatorial Optimization (3 volumes) by Lex Schrijver; ISBN 3-540-44389-4
• Geometric Algorithms and Combinatorial Optimization by Grotschel, Lovasz, Schrijver; ISBM 978-3-642-78242-8.
  

Student Coursework Requirements

It is expected that each module will take approximately 6–10 hours per week to complete. Here is an approximate breakdown:  listening to the audio annotated slide presentations (approximately 2–3 hours per week), reading the assigned sections of the texts and other readings (approximately 1-2 hours per week), and problem sets (approximately 3–5 hours per week).

Your final grade will be broken down as follows:

• Module Problem Sets: Modules 1-6 and 8-13 will contain a graded problem set that you will complete in groups of size no more than 3. These assignments will be returned weekly, providing frequent feedback. The lowest two grades will be dropped and the remaining 10 grades will have the combined worth of 30% of your final grade. See the Module Problem Sets Guidelines document for more information.

• Discussions: Modules 1-6 and 8-13 will also contain weekly discussion forums posted to the class discussion board. You will be expected to respond to at least 7 of these forums during the semester. You are encouraged to respond to more, but only 7 of the 12 will be required.  Participation in class discussion boards will be worth 15% of your final grade. See the Discussion Rubric for more information.

• Exams: There will be two exams given, one in Module 7 and the other in Module 14. These exams will take home, non-cumulative, and cover the material from the previous 6 modules. These exams will provide you with the opportunity to demonstrate your ability to determine the required techniques and apply them to solve a combinatorial optimization problem outside of the framework of a specific lecture/individual topic. The exams will be completed individually and you are not to speak to anyone about them except for the instructor. Each of these exams will be worth 20% of your final grade.

• Course Project: There will be a course project due by the beginning of Module 14. You may work in individually or in groups. You will choose your own topic, but must have it approved by the instructor during Module 9. A short topic proposal will be due during Module 10 and will be worth 5% of your final grade. You will present your projects to the class. Your presentation will need to be uploaded by the beginning of module 14 so that your classmates may watch it and comment during that week. The projects will be graded by the instructor and will be worth 10% of your final grade.

Grading Policy

Assignments are due according to the dates posted in the Canvas course site. All assignments are released and due on Eastern Time. Each assignment, unless otherwise noted in the course module, should be submitted electronically via the assignment submission link within the module in which it is due.  A comprehensive list of assignments and due dates are provided in the Course Outline. You may also check these due dates in the Calendar or the Assignments in the corresponding modules. I will post grades about a week after assignment due dates.

We generally do not directly grade spelling, grammar, or handwriting. However, egregious violations of the rules of the English language will be noted without comment. Also, if I can't read it, I can’t grade it. So please keep your work neat. 

A grade of A indicates achievement of consistent excellence and distinction throughout the course—that is, conspicuous excellence in all aspects of assignments and discussion in every week.

A grade of B indicates work that meets all course requirements on a level appropriate for graduate academic work. 

A grade of C or F indicates that the student has failed to show a graduate level of understanding of the course material.

The following should be used as a general guideline on assignments to help determine your progress in the course:

100–98 = A+
97–94 = A
93–90 = A−
89–87 = B+
86–83 = B
82–80 = B−
79–70 = C

Final grades will be determined by the following weighting:

Course Policies

Academic Integrity Course

You should have been enrolled in an academic integrity training course shortly after registering for your first class at Johns Hopkins Engineering for Professionals. This course covers the fundamental values of academic integrity, as well as information related to our academic misconduct policy and gives guidance on proper citation, and learn how to avoid mistakes like plagiarism and other violations of academic misconduct.

The academic integrity training course can be accessed through Canvas and will take approximately 30 minutes to complete. This is a pass/fail course and the grade will be posted to your transcript. All students are expected to complete the academic integrity course within their first term. For more information on our academic misconduct policy, please visit: http://ep.jhu.edu/faculty/prepare-to-teach/academic-misconduct.

Plagiarism is defined as taking the words, ideas or thoughts of another and representing them as one's own. If you use the ideas of another, provide a complete citation in the source work and present the words in the correct quotation notation (indentation or enclosed in quotation marks, as appropriate) and include a complete citation to the source. See the course text for examples. 

I take academic integrity very seriously. Copying from any source is considered to be cheating as is searching the internet for solutions to the problems.  If you are caught, you will be reported to the EP Academic Integrity Officer for Academic Misconduct.  

Collaboration Guidelines

While discussion of the homework with your classmates is allowed, the assignments are intended to be done in groups of size no more than 3. Each group must prepare their solutions separately.  Additionally, you should indicate on your assignment the members of the group as well as anyone else with whom you have discussed the assignment by placing their name on the top of the first page in a clear visible location. Copying or sharing of written work and/or computer code is considered to be cheating as is searching the internet for solutions to the problems.  These activities will result in a grade of zero on the assignment and possible an F in the course. 

Exams are to be completed individually. Discussion of exams is strictly prohibited and will result in an F in the course.

Contact me if you have any questions, no matter how slight, about this policy, or if you have questions about a particular assignment.

Academic Policies

Deadlines for Adding, Dropping and Withdrawing from Courses

Students may add a course up to one week after the start of the term for that particular course. Students may drop courses according to the drop deadlines outlined in the EP academic calendar (https://ep.jhu.edu/student-services/academic-calendar/). Between the 6th week of the class and prior to the final withdrawal deadline, a student may withdraw from a course with a W on their academic record. A record of the course will remain on the academic record with a W appearing in the grade column to indicate that the student registered and withdrew from the course.

Academic Misconduct Policy

All students are required to read, know, and comply with the Johns Hopkins University Krieger School of Arts and Sciences (KSAS) / Whiting School of Engineering (WSE) Procedures for Handling Allegations of Misconduct by Full-Time and Part-Time Graduate Students.

This policy prohibits academic misconduct, including but not limited to the following: cheating or facilitating cheating; plagiarism; reuse of assignments; unauthorized collaboration; alteration of graded assignments; and unfair competition. Course materials (old assignments, texts, or examinations, etc.) should not be shared unless authorized by the course instructor. Any questions related to this policy should be directed to EP’s academic integrity officer at ep-academic-integrity@jhu.edu.

Students with Disabilities - Accommodations and Accessibility

Johns Hopkins University values diversity and inclusion. We are committed to providing welcoming, equitable, and accessible educational experiences for all students. Students with disabilities (including those with psychological conditions, medical conditions and temporary disabilities) can request accommodations for this course by providing an Accommodation Letter issued by Student Disability Services (SDS). Please request accommodations for this course as early as possible to provide time for effective communication and arrangements.

For further information or to start the process of requesting accommodations, please contact Student Disability Services at Engineering for Professionals, ep-disability-svcs@jhu.edu.

Student Conduct Code

The fundamental purpose of the JHU regulation of student conduct is to promote and to protect the health, safety, welfare, property, and rights of all members of the University community as well as to promote the orderly operation of the University and to safeguard its property and facilities. As members of the University community, students accept certain responsibilities which support the educational mission and create an environment in which all students are afforded the same opportunity to succeed academically. 

For a full description of the code please visit the following website: https://studentaffairs.jhu.edu/policies-guidelines/student-code/

Classroom Climate

JHU is committed to creating a classroom environment that values the diversity of experiences and perspectives that all students bring. Everyone has the right to be treated with dignity and respect. Fostering an inclusive climate is important. Research and experience show that students who interact with peers who are different from themselves learn new things and experience tangible educational outcomes. At no time in this learning process should someone be singled out or treated unequally on the basis of any seen or unseen part of their identity. 
 
If you have concerns in this course about harassment, discrimination, or any unequal treatment, or if you seek accommodations or resources, please reach out to the course instructor directly. Reporting will never impact your course grade. You may also share concerns with your program chair, the Assistant Dean for Diversity and Inclusion, or the Office of Institutional Equity. In handling reports, people will protect your privacy as much as possible, but faculty and staff are required to officially report information for some cases (e.g. sexual harassment).

Course Auditing

When a student enrolls in an EP course with “audit” status, the student must reach an understanding with the instructor as to what is required to earn the “audit.” If the student does not meet those expectations, the instructor must notify the EP Registration Team [EP-Registration@exchange.johnshopkins.edu] in order for the student to be retroactively dropped or withdrawn from the course (depending on when the "audit" was requested and in accordance with EP registration deadlines). All lecture content will remain accessible to auditing students, but access to all other course material is left to the discretion of the instructor.