ulysses8791.github.io

Penn State, University Park, Spring 2024

MATH 484 — LINEAR OPTIMIZATION

The instructor reserves the right to make changes to this syllabus during the semester.

Space-Time Coordinates

Section Days Time Room
MATH 484.001 Mon Wed Fri 09:05 — 09:55 Agricultural Science & Industries 107
MATH 484.002 Mon Wed Fri 10:10 — 11:00 Business Building 004

Classes begin on Monday January 8, 2024 and end on Friday April 26, 2024.

Spring break: March 4-8, 2024.

Instructor

Professor Mathieu Stiénon

Information and Communications Technology

All electronic devices must be silenced during lectures. Disrupting class in any way will not be tolerated.

We will use Canvas to share course materials, Gradescope to administer assignments, Teams for instant messaging, and Zoom for virtual office hours.

IT support is available 24/7.

     
Canvas iOS android
Gradescope iOS android
Teams iOS android
Zoom iOS android

Gradescope

Your Gradescope account will be created automatically the first time you click on the “Gradescope” tab in Canvas.

Using Gradescope as a Student

Once an assignment is marked, grades are available in Gradescope instead of Canvas.

Instant Messaging

We will use Microsoft Teams for text-based communication outside the classroom.

Depending on the issue at hand, we will use either the team channel or the private chat features of Teams. Watch this video to learn how team channels (i.e. public conversations) work. Watch this other video to learn how chats (i.e. private one-on-one or group conversations) work.

Login to Office 365 with your PSU email address and password.

You will be added automatically to the team channel for the course.

For your convenience, I encourage you to install the Teams app on your phone and/or tablet.

Please take a moment now to download the app and join the team as I will share important information with the class through Teams rather than through Canvas announcements and your Canvas inbox. Do it now!

Virtual Office Hours

Tentatively scheduled on Wednesdays from 17:00 to 18:00.

Check the ‘course administration module’ in Canvas for the day and time of virtual office hours.

We will use Zoom in conjunction with a shared online whiteboard. You will find instructions and links for joining the Zoom meeting and the shared online whiteboard in the ‘Course Administration’ module in Canvas. You must be logged into the Zoom app with your PSU credentials to be allowed into the meeting.

Disrupting virtual office hours in any way will not be tolerated. Refusal to comply with University policies is a violation of the Code of Conduct. Students may face disciplinary action for Code of Conduct violations.

Required Textbook

Dimitris Bertsimas and John N. Tsitsiklis, Introduction to Linear Optimization, Athena Scientific / Dynamic Ideas, ISBN 978-1-886529-19-9

Why Learn Linear Programming?

Linear programming is widely used by Fortune 100 companies, including tech giants like Apple and Google, retail behemoth Walmart, and leading airlines like Air France and Lufthansa. These companies use linear and mixed-integer linear programming to optimize their operational efficiency. For example, airlines use mathematical programming for flight routing, staffing, and maintenance, while professional sports leagues like the NFL use it for game scheduling. Manufacturing companies also use it for procurement, production, and distribution planning.

Prerequisites

MATH 220 (or any equivalent introductory Linear Algebra course) is an absolute prerequisite for MATH 484. Section 1.5 of our textbook briefly reviews the Linear Algebra material that you should be familiar with and explains the notational conventions adopted in the textbook. Read that section on your own as soon as you get hold of your copy of the textbook.

Course Outline

We will aim to cover the first four chapters of the book. We will learn how to solve linear optimization problems, aka linear programs. First, we will learn what they are and how to interpret them geometrically. From the geometry, we will then derive the simplex algorithm, which is probably the most well known and widely used algorithm for solving linear optimization problems — other algorithms have emerged more recently. Finally, we will learn about duality.

Chapter 1 — Linear optimization problems

Chapter 2 — Geometry of polyhedra

Chapter 3 — Simplex algorithm

Chapter 4 — Duality theory

Class Attendance

Regular class attendance is one of the most important ways that students learn and understand course materials. It is a critical element of student success. Accordingly, it is the policy of the University that class attendance is expected. Students should attend every scheduled class and should be held responsible for all work covered in the course. Class attendance is expected regardless of the format of the course and this expectation applies equally to students in face-to-face, online, and hybrid courses.

Weekly Problem Sets

Problem sets will be assigned weekly on Friday and are due one week later. All problem sets will have equal weight.

Discussion of problem sets with others is allowed, but each student should write his or her own solutions independently. You should definitely never share work you are submitting for credit with other students.

Once you have completed the assignment for the week, you will scan your work and submit the resulting PDF file through Gradescope.

Submit your work well ahead of the deadline. Assignments submitted late will automatically be marked as such in Gradescope and the Canvas grade-book. If you submit too many assignments late, I reserve the right to apply a penalty to your grade.

Problem Sets will lock 48 hours after their respective due dates and late submission will be disabled at that time.

Students who have a valid and documented reason for not submitting problem solutions on time may request to be excused for that assignment. However, there will be no makeup assignments.

Scanning Apps for Your Phones and Tablets

The easiest way to scan and submit your work is to use the Gradescope app for your phone.

The mobile apps for Microsoft OneDrive and Google Drive allow you to scan your completed assignments, convert them into PDF files, and store them in the cloud. As a PSU student, you have virtually unlimited cloud storage on OneDrive and Google Drive — you must be logged into the app with your PSU credentials.

     
Gradescope iOS android
OneDrive iOS android
Google Drive iOS android

Instructions for Assignment Submission

  1. Download the PDF of the assignment from Gradescope.
  2. Solve the problems using a black pen either on the printout or on blank sheets of white letter-size printer paper. Show all your work and explain your work briefly in full sentences. Final answers without supporting work and explanations will not receive credit. Write cleanly! If your work is not easily readable and intelligible, you will loose points!
  3. Scan your work, and submit it as one single PDF file in Gradescope. If you’d rather work directly on your pen-enabled tablet, make sure to submit all layers of the PDF document.
  4. In Gradescope, once you have uploaded your PDF file, you must match the pages of your document to the questions of the assignment. Otherwise, your submission will be considered incomplete and will receive a zero score.
  5. Check that your submission is complete and that you have submitted all pages. Unreadable work will result in a zero score.
  6. Assignments dropped in the instructor’s mailbox, sent to his email address, slipped under his office door, or submitted in Teams chat are not acceptable, will not be acknowledged, will be ignored, and will not be graded. You must submit your work through Gradescope.

Examinations

Students in this class are expected to complete the examinations on their own, and to write their answers in their own words. Students are not to obtain exam answers from any other person and present them as their own. Students who present other people’s work as their own may receive a zero score on the examination and an F or XF grade for the course.

Should I have any reason to believe that you may have submitted work which is not your own, I will request that you meet with me through videoconferencing, I will have you explain your work to me and I will ask you follow-up questions to test your understanding of the material. If you are not able to answer satisfactorily, I reserve the right to reduce your score on the examination, possibly down to zero. Academic integrity matters!

Warning: All University and College policies regarding academic integrity/academic dishonesty apply to this course and to the students enrolled in this course. Academic dishonesty could result in a transcript notation indicating failure due to academic misconduct.

Midterm Examinations

Two 45-minutes midterm examinations will be given in class on Wednesday February 14, 2024 and Wednesday April 3, 2024.

No books, notes, or calculators may be used on mid-term examinations.

If there is a valid and documented reason for not being available during the regular mid-term examination time-window, such as classes or other official university activities or illness, a student may arrange with the instructor to take a makeup exam.

You need to IM (Teams) your instructor 48 hours prior to the exam regarding conflicts, and within 24 hours of missing the exam due to illness. If you miss the mid-term exam without an official excuse (such as illness or official university business), you may be allowed to take a makeup exam, but with an automatic 15% deduction from the grade. To avoid this deduction, you must notify your instructor via IM (Teams) with your official excuse, within 24 hours of the missed exam.

Forgetting the date or time of an examination is not a valid excuse.

Final Project

Information about the final project will appear in Gradescope on Week 13.

The deadline for submission of your final project is Monday April 29, 2024 at 09:00.

Grades

Assignments will be weighted as follows:

Type of Assignment Weight
Weekly Problem Sets 40%
First Midterm Examination 20%
Second Midterm Examination 20%
Final Project 20%

Course letter grades will be assigned as follows:

100% ⩾ A ⩾ 93% > A- ⩾ 90% > B+ ⩾ 87% > B ⩾ 83% > B- ⩾ 80% > C+ ⩾ 77% > C ⩾ 70% > D ⩾ 60% > F ⩾ 0%

The unavoidable consequence is that some students will be ‘just a point’ away from the next higher or lower grade. For reasons of fairness, the policy in this course is to NOT adjust individual grades in such circumstances.

Your grade will be based exclusively on the problem sets, the midterm examination, the final examination, and the final project. There is no ‘extra-credit’ work.

Deferred Grades

Students who are currently passing a course but are unable to complete the course because of illness or emergency may be granted a deferred grade which will allow the student to complete the course within the first several weeks of the following semester. Note that deferred grades are limited to those students who can verify and document a valid reason for not being able to take the final examination. A deferred grade which is not changed to a letter grade by the instructor by 10 weeks after the course ends will automatically become an F. For more information see Deferred Grades.

Late-Drop

Students may add/drop a course without academic penalty within the first six calendar days of the semester. A student may late drop a course within the first twelve weeks of the semester but accrues late drop credits equal to the number of credits in the dropped course. A baccalaureate student is limited to 16 late drop credits. The late drop deadline is Friday April 5, 2024 at 23:59 (Eastern Time).

Tutoring

Free mathematics tutoring is available at Penn State Learning. They offer both online and in-person options.

For more help, the Department of Mathematics maintains a list of private tutors.

Counseling and Psychological Services

Many students at Penn State face personal challenges or have psychological needs that may interfere with their academic progress, social development, or emotional well-being. The university offers a variety of confidential services to help you through difficult times, including individual and group counseling, crisis intervention, consultations, online chats, and mental health screenings. These services are provided by staff who welcome all students and embrace a philosophy respectful of students’ cultural and religious backgrounds, and sensitive to differences in race, ability, gender identity and sexual orientation.

988 Suicide & Crisis Lifeline

The 988 Lifeline is a national network of local crisis centers that provides free and confidential emotional support to people in suicidal crisis or emotional distress 24 hours a day, 7 days a week in the United States.

There is hope. Providing 24/7, free and confidential support to people in suicidal crisis or emotional distress works. The Lifeline helps thousands of people overcome crisis situations every day.

Need Support Now? If you or someone you know is struggling or in crisis, help is available. Call or text 988 or chat 988lifeline.org.

Academic Integrity

According to Penn State policy G-9: Academic Integrity, an academic integrity violation is “an intentional, unintentional, or attempted violation of course or assessment policies to gain an academic advantage or to advantage or disadvantage another student academically.” Unless your instructor tells you otherwise, you must complete all course work entirely on your own, using only sources that have been permitted by your instructor, and you may not assist other students with exams or other assessments.

Using ideas, images, or word phrases created by another person (e.g., from Course Hero or Chegg) or by generative technology, such as ChatGPT, is prohibited in this course. You may not submit false or fabricated information, use the same academic work for credit in multiple courses, or share instructional content. Students with questions about academic integrity should ask their instructor before submitting work.

Students facing allegations of academic misconduct may not drop/withdraw from the affected course unless they are cleared of wrongdoing (see G-9: Academic Integrity). Attempted drops will be prevented or reversed, and students will be expected to complete course work and meet course deadlines. Students who are found responsible for academic integrity violations face academic outcomes, which can be severe, and put themselves at jeopardy for other outcomes which may include ineligibility for Dean’s List, pass/fail elections, and grade forgiveness. Students may also face consequences from their home/major program and/or The Schreyer Honors College.

Academic integrity is the pursuit of scholarly activity in an open, honest and responsible manner. Academic integrity is a basic guiding principle for all academic activity at The Pennsylvania State University, and all members of the University community are expected to act in accordance with this principle. Consistent with this expectation, the University’s Code of Conduct states that all students should act with personal integrity, respect other students’ dignity, rights and property, and help create and maintain an environment in which all can succeed through the fruits of their efforts. Academic integrity includes a commitment not to engage in or tolerate acts of falsification, misrepresentation or deception. Such acts of dishonesty violate the fundamental ethical principles of the University community and compromise the worth of work completed by others. In order to ensure all students have a fair and equal opportunity to succeed in this course, the Mathematics Department is committed to enforcing the University’s academic integrity policy. Below is a description of academic misconduct and the department’s responsibilities when misconduct is suspected.

Academic Misconduct

In this course, academic misconduct includes, but is not limited to:

When Academic Misconduct is Suspected

If a student is suspected of academic misconduct, the instructor’s duties are to:

Note that a student’s refusal to meet with the instructor or respond to the charges within a reasonable period of time is construed as acceptance of the allegation and proposed sanctions.

Once the Academic Integrity form has been accepted or contested by the student, it is sent to the College’s Academic Integrity Committee for adjudication. A student cannot drop or withdraw from the course during the adjudication process.

Sanctions

If a student accepts an academic misconduct allegation, or if (s)he is found guilty during adjudication, probable sanctions include:

Additional sanctions might include:

In addition, the student will be unable to drop or withdraw from the course.

Please see the Eberly College of Science Academic Integrity homepage for additional information and procedures. Also see the Code of Ethics for Engineers published by the National Society of Professional Engineers.

Students with Disabilities

Penn State welcomes students with disabilities into the University’s educational programs. If you have a disability-related need for reasonable academic adjustments in this course, contact Student Disability Resources at 814-863-1807 (V/TTY). For further information, please visit the Student Disability Resources web site. In order to receive consideration for accommodations, you must contact SDR and provide documentation (see the documentation guidelines at the Student Disability Resources web site). If the documentation supports your request for reasonable accommodations, SDR will provide you with an accommodation letter identifying appropriate academic adjustments. Please share this letter with your instructors and discuss the accommodations with them as early in your courses as possible. You must follow this process for every semester that you request accommodations.

Educational Equity

The Office of the Vice Provost for Educational Equity serves as a catalyst and advocate for Penn State’s diversity and inclusion initiatives. Educational Equity’s vision is a Penn State community that is an inclusive and welcoming environment for all. If you wish to learn more or if you wish to report bias, please visit the Educational Equity website.

All course materials students receive or to which students have online access are protected by copyright laws. Students may use course materials and make copies for their own use as needed, but unauthorized distribution and/or uploading of materials without the instructor’s express permission is strictly prohibited. University Policy AD 40: Recording of Classroom Activities and Note-Taking Services addresses this issue. Students who engage in the unauthorized distribution of copyrighted materials may be held in violation of the University’s Code of Conduct and/or liable under Federal and State laws.

A rising trend across the University is the posting and/or retrieval of material from course-share sites. Generally speaking, the uploading of materials to a course-share site is viewed as an Intellectual Property violation, and the downloading and use of materials from a course-share site could be a violation of academic integrity. If you have questions regarding the specific use of such a site, seek clarification directly from your instructor.

Student Class Recordings

Students are not allowed to record class sessions without permission.

According to University Policy, students must get express permission from their instructor to record class sessions. Screenshots showing instructors and students are considered recordings. Even if permission is granted, student-initiated recordings must be used only for educational purposes for the students enrolled in the initiating student’s class. Recordings may be used only during the period in which the student is enrolled in the class. Authorized student-initiated recordings may not be posted or shared in any fashion outside of the class, including online or through other media, without the express written consent of the course instructor or appropriate University administrator. Students who engage in the unauthorized distribution of class recordings may be held in violation of the University’s Code of Conduct, and/or liable under Federal and State laws.

Calendar

Week Mon Wed Fri
1 Jan 8 Jan 10 Jan 12
2   Jan 17 Jan 19
3 Jan 22 Jan 24 Jan 26
4 Jan 29 Jan 31 Feb 2
5 Feb 5 Feb 7 Feb 9
6 Feb 12 Feb 14 Feb 16
7 Feb 19 Feb 21 Feb 23
8 Feb 26 Feb 28 Mar 1
9 Mar 11 Mar 13 Mar 15
10 Mar 18 Mar 20 Mar 22
11 Mar 25 Mar 27 Mar 29
12 Apr 1 Apr 3 Apr 5
13 Apr 8 Apr 10 Apr 12
14 Apr 15 Apr 17 Apr 19
15 Apr 22 Apr 24 Apr 26