MATH3171/5171 Linear and Discrete

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

FACULTY OF SCIENCE

SCHOOL OF MATHEMATICS AND STATISTICS

MATH3171/5171

Linear and Discrete

Optimization Modelling

Term 3, 2021

MATH3171/5171 – Course Outline

Information About the Course

Course Authority and Lecturer:

● Associate Professor Guoyin Li , Red Centre 2082, Email: [email protected]

Consultation:

● Consultation times will be announced in class and posted on the courses moodle site.

Credit and Prerequisites:

● This course counts for 6 Units of Credit (6UOC).

● Prerequisite: For MATH3171, the prerequisites are 12 units of credit in Level 2 Mathe-matics courses including (1) [MATH2011 or MATH2111] and [MATH2501 or MATH2601]; or (2) both MATH2069 (CR) and MATH2099; or (3) both [MATH2018 or MATH2019] (DN) and MATH2089.

The graduate course MATH5171 has no formal prerequisites but students need to have taken courses roughly equivalent to those mentioned required for MATH3171.

Lectures: There will be 4 hours of lectures per week, in week 1-5 and week 7-10, giving a total of 36 hours. Week 6 is a study break (flexible week). The times and format of the lectures are as follows:

The lectures will be common to both MATH3171 and MATH5171 students.

Notes:

● The above time are correct at time of printing, however they may change. Please check your online timetable for the most up–to–date information.

● The lectures/tutorials may be recorded.

Tutorials: There will be one tutorial per week, in week 1-5 and week 7-10, with a total of 9 hours of tutorials. During week 6, there will be no lectures and tutorial.

The times and format of the tutorials are as follows:

The tutorials will be generally looking at problems relevant to material covered in the previous lectures.

Students in the graduate version (MATH5171) are expected to show much more independence, working through the tutorial problems in their own.

Moodle: Further information, skeleton lecture notes, sample tests and exams, and other material will be provided via Moodle

https://moodle.telt.unsw.edu.au/login/index.php

We will also use Moodle for announcements.

Administrative Contacts

Please visit the School of Mathematics and Statistics website for a range of information on School Policies, Forms and Help for Students.

For information on Courses, please go to Current Students and either Undergraduate and/or Postgraduate, Course Homepage for information on all course offerings.

The Student Notice Board can be located by going to the Current Students page; Notices are posted regularly for your information here. Please familiarise yourself with the information found in these locations. The School web page is: https://www.maths.unsw.edu.au

If you cannot find the answer to your queries on the web you are welcome to contact the Student Services Office directly.

● By email

– Undergraduate [email protected]

– Postgraduate [email protected]

● By phone: 9385 7011 or 9385 7053

Should we need to contact you, we will use your official UNSW email address of in the first instance. It is your responsibility to regularly check your university email account. Please state your student number in all emails.

Course Description

Optimization is the mathematical problem of finding a decision to achieve the best possible outcome while satisfying the restriction we faced. Linear programs, conic linear programs and discrete optimization problems arise in a myriad of applications: electricity markets, airlines, logistics, public transport, international shipping, mining, finance, engineering, and data sci-ence. This course will provide an introduction to the basic mathematical theory, modelling techniques, computational methods and selected applications of linear, conic and discrete op-timization.

Student Learning Outcomes

After successfully completing this course, you will

● develop an appreciation of the basic problems of optimization and skills to solve opti-mization problems.

● be able to formulate, solve and analyse solutions to basic linear, conic and discrete opti-mization problems;

● develop analytical and logical thinking in the area of optimization;

● develop modelling skills in the area of optimization.

● develop competency in mathematical presentation, written and verbal skills through regu-larly attending lectures, attempting assessment tasks, and applying themselves in tutorial exercises.

Relation to graduate attributes: The above outcomes are related to the development of the Science Faculty Graduate Attributes, in particular: 1.Research, inquiry and analytical thinking abilities, 4. Communication, 6. Information literacy

Assessment

Assessment in this course will consist of the following:

* Note: Class tests, assignment and final exam will have starred questions indicating harder material. Grades of Pass and Credit can be gained by satisfactory performance on unstarred questions. Grades of Distinction and High Distinction will require satisfactory performance on all questions. Students in the graduate version (MATH5171) are expected to show satisfactory performance on starred questions.

● Class Tests: There will be two class tests counting 30% of the total assessment. Details of the class tests will be announced during lectures. The precise range of material covered by each class test will be announced in lectures and tutorials before each test. The Class Tests are held in place of the Wednesday’s lecture in weeks 5 and 9.

– Rationale: The Tests will give students feedback on their progress and mastery of the material.

– There will be short answer questions in which correct answers are sought and there will be some longer questions requiring clear and logical presentation of correct solutions as well as some simple proofs and verbal explanations.

– Further detailed information on class tests will be announced on Moodle before the class tests.

● Final Exam: The final exam, covering everything in the course, counts for 60% of the total assessment. Further details about the final examination will be available in class closer to the time.

– Rationale: The final examination will assess student mastery of the material covered in lectures, tutorials, problems sheets, and any distributed material.

– Further detailed information on final exam will be announced on Moodle before the final exam.

● Starred Materials: Problem sheets, class tests and the final exam may have starred questions indicating harder material. Grades of Pass and Credit can be gained by satisfactory performance on unstarred questions. Grades of Distinction and High Distinction will require satisfactory performance on all questions.

Students in the graduate version (MATH5171) are expected to show satisfactory performance on starred questions.

● Assignment: It is planned to have an assignment on solution methods of optimization problems. The assignment may involve modelling practical problems and writing a short report. The Matlab software package may also be used for implementing numerical optimization methods to solve practical optimization problems.

– Students in the graduate version (MATH5171) are expected to complete additional work in the assignment.

– Rationale: Assignments will give an opportunity for students to try their hand at more difficult problems requiring more than one line of argument and also introduce them to aspects of the subject which are not explicitly covered in lectures. The assignment will also require a student to draw together several topics in the course

– Late submission for Assignment: A late penalty of 5% of the awarded mark will be applied per day or part day any assignment is submitted more than 1 hour late. (Where “late” in this context means after any extensions granted for Special Consideration or Equitable Learning Provisions.) Any assignment submitted 3 or more days late will be given zero.

● Knowledge and abilities assessed: All assessment tasks will assess the learning outcomes outlined above, specifically, the ability to set up and accurately solve problems involving multiple real variables.

● Assessment criteria: UNSW assesses students under a standards based assessment policy. For how this policy is applied in the School of Mathematics and Statistics see http://www.maths.unsw.edu.au/currentstudents/assessment-policies 

Course Schedule and Delivery

The rough course schedule are as follows:

● Week 1: Introduction to Optimization: linear, conic and discrete modelling.

● Week 1 - Week 2: Mathematical Background.

● Week 2 - Week 4: Linear Programs (LP)

– Part I: Geometry of LP and simplex method;

– Part II: Duality theory and Sensitivity analysis;

– Part III: Further development of LP and applications of LP.

● Week 5: Network Problems

● Study break: Week 6

● week 7- week 9: Conic Linear Programs

– Part I: Motivational examples and introduction to conic linear programming ;

– Part II: Modelling techniques of conic linear programming: second order cone programs and semi-definite programs

– Part III: Conic programming duality, interior point methods and applications of conic programs.

● Week 9-Week 10: Integer Programs

– Part I: Motivational examples and introduction to integer linear programming

– Part II: Modelling with mixed-integer linear programs. Optimality, relaxation, and bounds for integer linear programming.

– Part III: Numerical methods for integer linear programming problems such as Branch and bound methods and Cutting plane techniques.

– Part IV: Semi-definite programming relaxations for integer programming problems (if time permitted).

Additional Resources and Support

● Text and Reference Books: There is NO textbook which covers all aspects of this course. General reference books are listed as below

1. D. Bertsimas and J. N. Tsitsiklis, An introduction to linear optimization, Athena Scientific (Massachusetts Institute of Technology), 1997.

2. S, Boyd and L. Vandenberghe, Convex Optimization, Cambridge, 2002.

3. L. Wosley, Integer Programming, John Wiley & Sons, 1998.

4. D.G. Luenberger and Y. Ye, Linear and Nonlinear Programming (4th edition), Springer, 2016.

5. W. Forst and D. Hoffmann, Optimization - Theory and Practice, Springer, 2010.

● Tutorial Exercises: Problem sheets for tutorials will be provided via UNSW Moodle. These problems are for you to do to enhance mastery of the course. SOME of the problems will be done in tutorials, but you will learn a lot more if you try to do them before the tutorial.

● Lecture Notes: A set of skeleton notes and summary sheets containing only definitions, theorems and proofs will be provided for SOME components of the course on UNSW Moodle.

Course Evaluation and Development

Student feedback is very important to continual course improvement. This is demonstrated within the School of Mathematics and Statistics by the implementation of the UNSW online student survey myExperience, which allows students to evaluate their learning experiences in an anonymous way. myExperience survey reports are produced for each survey. They are released to staff after all student assessment results are finalised and released to students. Course convenor will use the feedback to make ongoing improvements to the course.

Administrative Matters

Additional Assessment

The School of Mathematics and Statistics has a strict policy on additional assessment. It can be found on the school website, which is currently at this web address

http://www.maths.unsw.edu.au/currentstudents/exam-information-and-timetables

School Rules and Regulations

School and UNSW Policies The School of Mathematics and Statistics has adopted a number of policies relating to enrolment, attendance, assessment, plagiarism, cheating, special consideration etc. These are in addition to the Policies of The University of New South Wales. Individual courses may also adopt other policies in addition to or replacing some of the School ones. These will be clearly notified in the Course Handout and on the Course Home Pages on the Maths Stats web site

https://www.maths.unsw.edu.au/currentstudents/courses

Students in courses run by the School of Mathematics and Statistics should be aware of the School and Course policies by reading the appropriate pages on the Maths Stats web site starting at:

https://www.maths.unsw.edu.au/currentstudents/assessment-policies

The School of Mathematics and Statistics will assume that all its students have read and understood the School policies on the above pages and any individual course policies on the Course Initial Handout and Course Home Page. Lack of knowledge about a policy will not be an excuse for failing to follow the procedure in it.

Academic Integrity and Plagiarism

Academic Integrity and Plagiarism UNSW has an ongoing commitment to fostering a culture of learning informed by academic integrity. All UNSW staff and students have a responsibility to adhere to this principle of academic integrity. Plagiarism undermines academic integrity and is not tolerated at UNSW. Plagiarism at UNSW is defined as using the words or ideas of others and passing them off as your own.

The UNSW Student Code provides a framework for the standard of conduct expected of UNSW students with respect to their academic integrity and behaviour. It outlines the primary obligations of students and directs staff and students to the Code and related procedures.

In addition, it is important that students understand that it is not permissible to buy essay/writing services from third parties as the use of such services constitutes plagiarism because it involves using the words or ideas of others and passing them off as your own. Nor is it permissible to sell copies of lecture or tutorial notes as students do not own the rights to this intellectual property.

If a student breaches the Student Code with respect to academic integrity, the University may take disciplinary action under the Student Misconduct Procedure.

The UNSW Student Code and the Student Misconduct Procedure can be found at:

https://student.unsw.edu.au/plagiarism

An online Module Working with Academic Integrity (https://student.unsw.edu.au/aim) is a six-lesson interactive self-paced Moodle module exploring and explaining all of these terms and placing them into your learning context.

Plagiarism

Plagiarism is presenting another person’s work or ideas as your own. Plagiarism is a serious breach of ethics at UNSW and is not taken lightly. So how do you avoid it? A one-minute video for an overview of how you can avoid plagiarism can be found

https://student.unsw.edu.au/plagiarism

Additional Support

ELISE (Enabling Library and Information Skills for Everyone)

ELISE is designed to introduce new students to studying at UNSW.

Completing the ELISE tutorial and quiz will enable you to:

● analyse topics, plan responses and organise research for academic writing and other assessment tasks

● effectively and efficiently find appropriate information sources and evaluate relevance to your needs

● use and manage information effectively to accomplish a specific purpose

● better manage your time

● understand your rights and responsibilities as a student at UNSW

● be aware of plagiarism, copyright, UNSW Student Code of Conduct and Acceptable Use of UNSW ICT Resources Policy

● be aware of the standards of behaviour expected of everyone in the UNSW community

● locate services and information about UNSW and UNSW Library Some of these areas will be familiar to you, others will be new. Gaining a solid understanding of all the related aspects of ELISE will help you make the most of your studies at UNSW.

The ELISE training webpages: https://subjectguides.library.unsw.edu.au/elise/aboutelise

Equitable Learning Services (ELS)

If you suffer from a chronic or ongoing illness that has, or is likely to, put you at a serious disadvantage, then you should contact the Equitable Learning Services (previously known as SEADU) who provide confidential support and advice.

Their web site is:

https://student.unsw.edu.au/els/services

Equitable Learning Services (ELS) may determine that your condition requires special arrangements for assessment tasks. Once the School has been notified of these, we will make every effort to meet the arrangements specified by ELS. Additionally, if you have suffered significant misadventure that affects your ability to complete the course, please contact your Lecturer-in-charge in the first instance.

Academic Skills Support and the Learning Centre

The Learning Centre offers academic support programs to all students at UNSW Australia. We assist students to develop approaches to learning that will enable them to succeed in their academic study. For further information on these programs please go to: http://www.lc.unsw.edu.au/services-programs

Applications for Special Consideration for Missed

Assessment

Please adhere to the Special Consideration Policy and Procedures provided on the web page below when applying for special consideration.

https://student.unsw.edu.au/special-consideration

Please note that the application is not considered by the Course Authority, it is considered by a centralised team of sta↵ at the Nucleus Student Hub.

The School will contact you (via student email account) after special consideration has been granted to reschedule your missed assessment, for a lab test or paper-based test only.

For applications for special consideration for assignment extensions, please note that the new submission date and/or outcome will be communicated through the special consideration web site only, no communication will be received from the School.

For Dates on Final Term Exams and Supplementary Exams please check the Key Dates for Exams ahead of time to avoid booking holidays or work obligations.

https://student.unsw.edu.au/exam-dates