COURSE OUTLINE: MH3701

Course Title

Basic Optimization

Course Code

MH3701

Offered Study Year 3, Semester 2
Course Coordinator Yan Zhenzhen (Asst Prof) yanzz@ntu.edu.sg 6513 7466
Pre-requisites {MH1201}OR{MH2800}OR{MH2802}
AU 4
Contact hours Technology-enhanced Learning: 26, Tutorials: 26, Laboratories: 8
Approved for delivery from AY 2019/20 semester 2
Last revised 29 Nov 2019, 16:59

Course Aims

This is a first course in mathematical optimization. It builds the basic knowledge and skills in the theory and techniques of analysing and solving simple optimization models. With these foundations, you will be able to deepen your understanding of more complex optimization models, and their applications to various disciplines in subsequent mathematical optimization and operations research courses.

Intended Learning Outcomes

Upon successfully completing this course, you should be able to:

  1. Solve instances of linear programs with the simplex method.
  2. Explain and relate the geometry, the algebra, and the tabular form of the simplex method.
  3. Solve instances of minimum-cost flow problems with the network simplex method.
  4. Explain the algebra of the network simplex method.
  5. Explain the optimality of a solution to a linear program, and the infeasibility of a linear program, using linear programming duality.
  6. Conduct sensitivity and post-optimality analysis on linear programs.
  7. Solve instances of nonlinear programs via their Karush-Kuhn-Tucker conditions.

Course Content

Geometric simplex method

Algebraic simplex method in tabular form

Implementing the simplex method

Revised simplex method

Fundamental Theorem of the network simplex method

The network simplex method

Linear programming duality

Sensitivity and post-optimality analysis

Lagrange duality and the Karush-Kuhn-Tucker conditions

Assessment

Component Course ILOs tested SPMS-MAS Graduate Attributes tested Weighting Team / Individual Assessment Rubrics
Continuous Assessment
Laboratories
Multiple Choice Questions 1, 2, 6 1. a, c, d
2. a
3 individual See Appendix for rubric
Technology-enhanced Learning
Multiple Choice Questions 1, 2, 5, 6 1. a, c
12 individual See Appendix for rubric
Tutorials
Test 1 1, 2 1. a, b, c
2. b
3. a
4. a
15 individual See Appendix for rubric
Test 2 3, 4 1. a, b, c
2. b
3. a
4. a
20 individual See Appendix for rubric
Examination (2 hours)
Short Answer Questions 1, 2, 3, 4, 5, 6, 7 1. a, b, c
2. b
3. a
4. a
50 individual See Appendix for rubric
Total 100%

These are the relevant SPMS-MAS Graduate Attributes.

1. Competence

a. Independently process and interpret mathematical theories and methodologies, and apply them to solve problems

b. Formulate mathematical statements precisely using rigorous mathematical language

c. Discover patterns by abstraction from examples

d. Use computer technology to solve problems, and to communicate mathematical ideas

2. Creativity

a. Critically assess the applicability of mathematical tools in the workplace

b. Build on the connection between subfields of mathematics to tackle new problems

3. Communication

a. Present mathematics ideas logically and coherently at the appropriate level for the intended audience

4. Civic-mindedness

a. Develop and communicate mathematical ideas and concepts relevant in everyday life for the benefits of society

Formative Feedback

1. Online quizzes:
Your performance in an online quiz will be immediately given upon submission of your answers. The feedback includes your performance on each question, possible misconceptions that may lead you to wrong answers, and how the question can be answered.
2. In-class tests:
Comments on your answers to the questions will be written on your test scripts and returned to you upon grading.

Learning and Teaching Approach

Technology-enhanced Learning
(26 hours)

The basic theories and solution techniques are explained in the videos. After watching each video segment, you can reflect on its content by completing a short online quiz. Prior to the video sequence, and after the short quiz, you are reminded of the learning outcomes for that LAMS sequence.

The online quizzes summarize some of the main learning points into short computational questions. They reinforce your learning as you revisit the online LAMS and classroom activities to formulate solution procedures to these questions.

Tutorials
(26 hours)

You will participate in team-based problem-solving tutorial sessions, where problems are designed based on the theories and solution techniques that you should pick up in the online LAMS sequences prior to the tutorial session. In addition to peer learning through the team-based approach, you will get guidance and one-to-one assistance from the tutor as necessary.

Laboratories
(8 hours)

You will learn how to model real-world optimization problems as linear programs, and solve instances of these models in the lab sessions. The optimization problem will be introduced and the linear programming model explained at the beginning of the lab session. You will then have hands-on experience in extracting the problem data from a randomly selected problem to build a linear programming model, and solve it using a solver of your choice.

Reading and References

1. Frederick S. Hillier and Gerald J. Lieberman, “Introduction to Operations Research”, McGraw-Hill, ISBN 0073376299
2. Robert J. Vanderbei, “Linear Programming: Foundations and Extensions”, Springer, ISBN 1461476291

Course Policies and Student Responsibilities

(1) General
You are expected to complete all assigned pre-class LAMS activities, attend all tutorial and lab classes punctually, and complete all scheduled lab assignments, online quizzes, and in-class tests by due dates. You are expected to take responsibility to follow up with course notes, quizzes, lab assignments, and course related announcements for assessments you have missed. You are expected to participate in all tutorial discussions and activities.
(2) Absenteeism
A missed test will be given a mark of zero, unless prior permission is given by the course coordinator, or a leave of absence is approved by the School. If you miss an in-class test, you must inform the course coordinator via email (cbchua@ntu.edu.sg) within 2 working days of the test.
(3) Online Compulsory Lab Assignments and Quizzes
You are required to complete online compulsory lab assignments and quizzes on due dates. You have unlimited attempts. The highest score will be considered in the course assessment.

Academic Integrity

Good academic work depends on honesty and ethical behaviour. The quality of your work as a student relies on adhering to the principles of academic integrity and to the NTU Honour Code, a set of values shared by the whole university community. Truth, Trust and Justice are at the core of NTU’s shared values.

As a student, it is important that you recognize your responsibilities in understanding and applying the principles of academic integrity in all the work you do at NTU. Not knowing what is involved in maintaining academic integrity does not excuse academic dishonesty. You need to actively equip yourself with strategies to avoid all forms of academic dishonesty, including plagiarism, academic fraud, collusion and cheating. If you are uncertain of the definitions of any of these terms, you should go to the Academic Integrity website for more information. Consult your instructor(s) if you need any clarification about the requirements of academic integrity in the course.

Course Instructors

Instructor Office Location Phone Email
Yan Zhenzhen (Asst Prof) SPMS-MAS-05-19 6513 7466 yanzz@ntu.edu.sg

Planned Weekly Schedule

Week Topic Course ILO Readings/ Activities
1

Geometric simplex method

1

LAMS modules 1–7

2

Geometric simplex method

1

LAMS modules 1–7

3

Algebraic simplex method in tabular form

1, 2

LAMS modules 8–20

4

Algebraic simplex method in tabular form

1, 2

LAMS modules 8–20

5

Implementing the simplex method

1

LAMS modules 21–26

6

Revised simplex method

1

LAMS modules 27–33

7

Fundamental Theorem of the network simplex method

3, 4

LAMS modules 34–39

8

The network simplex method

3

LAMS modules 40–43

9

Linear programming duality

5

LAMS modules 44–52

10

Linear programming duality

5

LAMS modules 44–52

11

Sensitivity and post-optimality analysis

6

LAMS modules 53–58

12

Lagrange duality and the Karush-Kuhn-Tucker conditions

7

LAMS modules 59–67

13

Lagrange duality and the Karush-Kuhn-Tucker conditions

7

LAMS modules 59–67

Appendix 1: Assessment Rubrics

Rubric for Laboratories: Multiple Choice Questions (3%)

As scored by online system

Rubric for Technology-enhanced Learning: Multiple Choice Questions (12%)

As scored by online system

Rubric for Tutorials: Test 1 (15%)

Each question, or each part of a question, in a test or the final examination is graded with the following rubrics.

Grade

Description

Outstanding

The answer demonstrates full understanding of the problem and the solution process. All arguments are logical and presented with the appropriate use of English and mathematical symbols. The answer is completely correct.

Good

The answer demonstrates good understanding of the problem and the solution process. Most arguments are logical and they are mostly presented with the appropriate use of English and of mathematical symbols. The answer is mostly correct.

Average

The answer demonstrates some understanding of the problem and the solution process. Some arguments are logical and they are sometimes presented with the appropriate use of English and of mathematical symbols. The answer is partially correct.

Poor

The answer demonstrates little understanding of the problem or the solution process. Few arguments are logical or they are seldom presented with the appropriate use of English and of mathematical symbols. The answer is mostly incorrect.

Fail

The answer demonstrate no understanding of the problem or the solution process. Arguments are mostly not logical or they are presented with the inappropriate use of English and of mathematical symbols. The answer is completely incorrect.

Rubric for Tutorials: Test 2 (20%)

Each question, or each part of a question, in a test or the final examination is graded with the following rubrics.

Grade

Description

Outstanding

The answer demonstrates full understanding of the problem and the solution process. All arguments are logical and presented with the appropriate use of English and mathematical symbols. The answer is completely correct.

Good

The answer demonstrates good understanding of the problem and the solution process. Most arguments are logical and they are mostly presented with the appropriate use of English and of mathematical symbols. The answer is mostly correct.

Average

The answer demonstrates some understanding of the problem and the solution process. Some arguments are logical and they are sometimes presented with the appropriate use of English and of mathematical symbols. The answer is partially correct.

Poor

The answer demonstrates little understanding of the problem or the solution process. Few arguments are logical or they are seldom presented with the appropriate use of English and of mathematical symbols. The answer is mostly incorrect.

Fail

The answer demonstrate no understanding of the problem or the solution process. Arguments are mostly not logical or they are presented with the inappropriate use of English and of mathematical symbols. The answer is completely incorrect.

Rubric for Examination: Short Answer Questions (50%)

Each question, or each part of a question, in a test or the final examination is graded with the following rubrics.

Grade

Description

Outstanding

The answer demonstrates full understanding of the problem and the solution process. All arguments are logical and presented with the appropriate use of English and mathematical symbols. The answer is completely correct.

Good

The answer demonstrates good understanding of the problem and the solution process. Most arguments are logical and they are mostly presented with the appropriate use of English and of mathematical symbols. The answer is mostly correct.

Average

The answer demonstrates some understanding of the problem and the solution process. Some arguments are logical and they are sometimes presented with the appropriate use of English and of mathematical symbols. The answer is partially correct.

Poor

The answer demonstrates little understanding of the problem or the solution process. Few arguments are logical or they are seldom presented with the appropriate use of English and of mathematical symbols. The answer is mostly incorrect.

Fail

The answer demonstrate no understanding of the problem or the solution process. Arguments are mostly not logical or they are presented with the inappropriate use of English and of mathematical symbols. The answer is completely incorrect.