Winter Session

2016/17 Term 2

Section 201:

Tue Thu 9:30-11:00 CSCI-200

Section 202:

Mon Wed Fri 12:00-13:00 BUCH-A103

News (updated 19/01/17):

Instructor: Ricardo G??mez, Mathematics Building 218, (604) 822 3262, rgomez at math dot ubc dot ca

Office hours: Mon & Fri 14:00-15:00 LSK-300B, Wed 13:30-14:30 LSK-300C, and by appointment.

Calendar:

calendar

Overview

Linear programming is the branch of mathematical optimization that focuses on linear constraints and linear objective functions. It is known under other aliases like linear optimization, operations research, etc. The course covers the basic theory, divided in four main topics, in approximately the first 8 weeks:

   

Chapters (main textbook)

Weeks
1. Simplex method
1-4, 8
2
2. Duality
5,9
2
3. Simplex method revised
6-7
2
4. Sensitivity
10
2

Optional topics will be coverd, they will be chosen among the following:

   
Chapters (main textbook)
Weeks
6. Applications and modelling
11-14
2
7. Branch and bound
1
8. Game theory
15
2
9. Non-linear programming and the Karush-Kuhn-Tucker conditions
2
10. Conections with geometry
17
1
11. Network flow problems
19-23
2
12. General upper bounding
25
1

Textbooks

Main

  • Linear Programming, Va??ek Chv??tal.
Additional
  • Linear Programming. Foundations and Extensions, Robert J. Vanderbei.
  • Understanding and Using Linear Programming, Matousek and Gartner.
  • Elementary Linear Programming with Applications, Kolman and Beck.

Grading

grading

Exams. There will be two exams (no books nor calculators):

  • Midterm. A 50min long exam in classroom, containing the main topics of the course.
  • Final. A 3hrs long exam (date and place to be announced), containing all the material covered in the course.

Making up exams policy strictly limmited to very serious reasons, previous notification (72 hrs in advance) and prooving documentation required. In the case of the final, contact Faculty of Science Office.

Homeworks. There will be 5 assignments. Their emphasis will be on theory. Some will give computational questions and you will be able to use the available resoursers. Students may work together on assignments but must write up their solutions independently. They will be due at the beginning of class. No late homeworks will be accepted.

Quizes. There will be 5 quizes of 25 minutes in length maximum. Practice questions will be given in advance. These will be mostly computational problems. There will be no make up quizes.

Quizes

Samples
Date* (Section 1)
Date* (Section 2)
Thursday 12/01/17
Friday 13/01/17
Thursday 26/01/17
Friday 27/01/17
Thursday 09/02/17
Friday 10/02/17
Thursday 02/03/17
Friday 03/03/17
Thursday 23/03/17
Friday 24/03/17
* Dates may vary, please follow updates and announcements.

Homeworks

Homeworks
Solutions
Due date* (Section 1)
Due date* (Section 2)
Solutions A1
Tuesday 24/01/17
Wednesday 25/01/17
Assignment 2
Solutions A2
Thursday 16/02/17
Friday 17/02/17
Assignment 3
Solutions A3
Thursday 16/03/17
Friday 17/03/17
Assignment 4
Solutions A4
Tuesday 28/03/17
Wednesday 29/03/17
Assignment 5
Solutions A5
Tuesday 04/04/17
Wednesday 05/04/17
* Dates may vary, please follow updates and announcements.

Exams

Exam
Solutions

Date* and location (Section 1)

Date* and location (Section 2)
Midterm

Solutions ME1

Solutions ME2

Classroom, Tuesday 07/03/17
Classroom, Wednesday 08/03/17
Final

Solutions FE1

Solutions FE2

To be announced
To be announced
* Dates may vary, please follow updates and announcements.

Notes

We adapt the most recent scheme of the course in charge of Prof. Richard Anstee, in particular we will rely on Omar Antol??n Camarena's Notes on Linear Programming. Additional slide notes and class material that complement the references will be posted:

Slides

  1. Slide notes 1. Introduction, LP problems, software, LP problems in standard form.
  2. Slide notes 2. Slack variables, dictionaries, pivoting.
  3. Slide notes 3. Simplex algorithm in a nutshell, example of phase 1.

Resources

Programs

Websites

Platforms

Other resources