625.618.8VL - Discrete Hybrid Optimization
Description
Real-world planning, scheduling, and resource allocation problems are often too large and complex to solve using straightforward applications of classic exact optimization methods. Often a hybrid combination of methods is used to decompose large, unwieldy problems into smaller and computationally-tractable sub-problems. This course introduces the theory, algorithms, and a framework for combining multiple optimization techniques to solve large-scale real-world optimization problems. Techniques include integer optimization, constraint programming, network optimization, heuristics, dynamic programming, and reinforcement learning. The class provides the necessary theoretical underpinnings of the techniques, and focuses on selecting and implementing hybrid methods to solve applied problems. Emphasis is mostly on deterministic methods, but includes some stochastic concepts. Students will gain experience in formulating models of real-world problems, implementing solution techniques using IBM CPLEX and other software, and presenting analytic results clearly and concisely. Some previous experience with a scientific computing language (e.g., Python, MATLAB, Julia, R) is expected.
Instructor
Paul Nicholas
Course Structure
The course materials are divided into modules which can be accessed by clicking Course Modules on the course menu. A module will have several sections including the overview, content, readings, live, recorded lecture via Zoom, examples, and assignments. You are encouraged to preview all sections of the module before starting. Most modules run for a period of seven (7) days. You should regularly check the Announcements page for any updates.
Lectures will be broadcast Wednesday afternoons at 4:30pm; participation in the live (virtual) lecture is highly encouraged, but viewing the recorded lecture afterward is acceptable.Course Topics
The following topics are covered in this course (subject to change):
- Introduction to discrete hybrid optimization
- Integer optimization: Formulation and approach
- Integer optimization: Basic solution methods
- Integer optimization: Advanced solution methods
- Network optimization
- Constraint programming: Modeling and solution methods
- Integer and constraint programming integration
- Heuristics for optimization
- Decision diagrams
- Dynamic programming
- Reinforcement learning
Course Goals
This course covers the fundamental theory and algorithms of integer and combinatorial optimization to solve large-scale resource allocation, planning, and scheduling problems. Emphasis is on formulating optimization problems, understanding the methods available to address them, and solving them using a combination of one or more techniques in a hybrid framework.
Course Learning Outcomes (CLOs)
- Translate real-world resource allocation, planning, and scheduling problems into mathematical models that are tractable using one or more optimization methods.
- Learn and apply integer optimization theory and algorithms, including branch-and-bound and its variants.
- Learn and apply constraint programming theory and algorithms, including various types of search and logical inference.
- Use special formulation techniques (including network flow modeling) and basic heuristic methods (including genetic algorithms) to aid in solving otherwise intractable problems.
- Rigorously decompose large problems and combine multiple optimization techniques to solve otherwise intractable problems.
- Leverage dynamic programming and reinforcement learning to solve multi-stage optimization problems.
Textbooks
All textbooks and other required readings are available online either through the JHU Sheridan Libraries or the Internet; there is no requirement to purchase a textbook. Excerpts are used from the following textbooks:
- Applied Mathematical Programming, by Bradley, Hax, and Magnanti
- Integrated Methods for Optimization, by Hooker
- Logic-based Methods for Optimization, by Hooker
- Integer and Combinatorial Optimization, by Nemhauser and Wolsey
- Meta-heuristics and Evolutionary Algorithms for Engineering Optimization, by Bozorg-Haddad, Solgi, and Loáiciga
- Handbook of Constraint Programming, by Rossi, van Beek, and Walsh
- Network Flows, by Ahuja, Magnanti, and Orlin
- Decision Diagrams for Optimization, by Bergman, Cire, van Hoeve, and Hooker
- Reinforcement Learning, by Sutton and Barto
Required Software
The class is heavily dependent on computation. Students are expected to use a common computational programming language. Python is highly encouraged but not required. Julia, MATLAB, and Java are acceptable. Students will be using the academic version of IBM CPLEX, which is free to download and install.
Student Coursework Requirements
It is expected that each module will take approximately 8–12 hours per week to complete. Here is an approximate breakdown: reading the assigned sections of the texts (approximately 3–4 hours per week) as well as some outside reading, participating in the live lecture on Zoom (or reviewing the recording) (approximately 2–3 hours per week), and homework assignments (approximately 3–5 hours per week).
This course will consist of the following basic student requirements:
Homework Assignments (40% of Final Grade Calculation)
There will be ten homework assignments worth four points each. Assignments will include a mix of writing problem formulations, solving problems using computational software, and developing and explaining problem solution methods.
All homework assignments are due according to the dates on Canvas. Late submissions will not be accepted without prior permission from the instructor.
Mid-Term Exam (30% of Final Grade Calculation)
The midterm exam will be available in Module 9. The format and material covered will be determined at a later date.
The mid-term exam will be due according to the date on Canvas. Late submissions will not be accepted without prior permission from the instructor.
Final Project (30% of Final Grade Calculation)
A course project will be assigned near the end of the course. The format will be determined at a later date.
The final project will be due according to the date on Canvas. Late submissions will not be accepted without prior permission from the instructor.Grading Policy
Assignments are due according to the dates posted in your Canvas course site. You may check these due dates in the Course Calendar or the Assignments in the corresponding modules. Grades will be posted no later than one week after assignment due dates.
The ability to clearly communicate results is an important component of this field of analysis. Egregious violations of the rules of the English language, and/or incomprehensible explanations will result in a reduced grade.
For all graded assignments, the following grading standards apply. A grade of A-/A/A+ indicates achievement of consistent excellence and distinction throughout the course; that is, conspicuous excellence in all aspects of assignments. A grade of B-/B/B+ indicates work that meets all course requirements on a level appropriate for graduate academic work. A grade of less than B- indicates the student is not performing at a level expected of a graduate student. These criteria apply to both undergraduates and graduate students taking the course.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.