Formulation of real-world optimization problems using techniques such as linear programming, network flows, integer programming, dynamic programming. Solution by appropriate software.

This course is eligible for Credit/D/Fail grading. To determine whether you can take this course for Credit/D/Fail grading, visit the Credit/D/Fail website. You must register in the course before you can select the Credit/D/Fail grading option.

Credits: 3

Pre-reqs: MATH 340.

Instructor:

Jozsef Solymosi

email: solymosi@math.ubc.ca

office: MATH Building 220

In this course you will work in teams of 4-5(-6) students. (Note: 6 is not allowed when you start a group) Most of your grade is based on a project, to be done in groups. Students not in a self-selected group will be assigned randomly into new groups.

I need all teams to submit the list of students in their group by the end of this week, by Sunday, Sept 15.

If you don't have a (complete) group then send me an email saying what type of optimization problems are you interested about. (You can also say that you don't have preference, you are open to any type of problems .)

HW 1 (Due Sept 26, Thursday, in class or by email before class)

Grading:

- HW assignments 20%.

- Team work evaluation (Presentation, essay (written summary of your project), and individual Q/A during presentation) 80%.

In the exceptional case, if you are unhappy your team's performance, and you think it does not reflect your knowledge of the subject, then you can choose to write a final exam.

In this case, the previous 20%+80% (HW included) will count as your term work with weight 50%. Your final counts for 50%. This decision should be made at least 2 weeks before the end of the term, Nov. 15, and submitted to me in writing.

You will learn the basics of combinatorial optimization.

Then, you (your team) will choose an NP-complete problem.

NP-complete problems (List from Wikipedia)

You will present the selected problem and will try to come up with a solution plan.

You are expected to use an optimization software in order to find the solution of a given problem.

List of optimization software (List from Wikipedia)

I don't expect prior knowledge of programming, however it is not a bad thing if one of the team members has some affinity to coding.

There will be regular homework assignments. Late homework will not be accepted. Your two lowest scores will be dropped in the overall homework computation.

Office hours are by appointment for now -- email me and let me know when you are free over the next few days. When things get too busy (e.g., near project deadlines), appointments will be scheduled more rigidly.

Each member of your group must present some material/slides, and must be prepared to answer questions on this material. Your group needs to email a PDF file of your slides by 7am on the day of your presentation (it's OK to make small corrections to the slides and to send me a revised set of slides later in the day, after your talk).

Suggested readings:

The Golden Ticket

P, NP, and the Search for the Impossible (UBC Library link)

Millennium Problems (How to earn one million dollars?)

P, NP, and NP-Completeness: The Basics of Complexity Theory (UBC Library link)

Sept 12.

- After the previous two introductory classes we started a more systematic way to talk about classification of complexity classes.

- When are two problems algorithmically similar? Problems solvable in polynomial time are complexity theoretically similar.

- A useful tool to prove that two problems are in the same complexity class is the use of REDUCTIONS.

- We introduced the basics of the Network Flow problem.

- Then we reduced the Maximum Matching problem to the Network Flow problem using a few steps (linear in time) only.

- We gave a brief informal intro to the 3-SAT problem which will serve us as one of the most important problem among the NP-complete problems.

Academic Misconduct:

1. UBC takes cheating incidents very seriously. After due investigation, students found guilty of cheating on tests and examinations are usually given a final grade of 0 in the course and suspended from UBC for one year.

2. While students are encouraged to study together, they should be aware that blatant copying of another student's work is a serious breach of academic integrity. Please discuss with your instructors their expectations for acceptable collaboration on any assigned coursework. Cases of suspected cheating will be investigated thoroughly.

3. Note that academic misconduct includes misrepresenting a medical excuse or other personal situation for the purposes of postponing an examination or quiz or otherwise obtaining an academic concession.

Statement on UBC's Policies and Resources to Support Student Success:

UBC provides resources to support student learning and to maintain healthy lifestyles but

recognizes that sometimes crises arise and so there are additional resources to access including those for survivors of sexual violence. UBC values respect for the person and ideas of all members of the academic community. Harassment and discrimination are not tolerated nor

is suppression of academic freedom. UBC provides appropriate accommodation for students

with disabilities and for religious and cultural observances. UBC values academic honesty

and students are expected to acknowledge the ideas generated by others and to uphold the

highest academic standards in all of their actions. Details of the policies and how to access

support are available at

https://senate.ubc.ca/policies-resources-support-student-success