CPSC 4850B/5850 - Algorithms in Operations Research (Spring 2010)

Project report due Apr 15.
Take home exam pickup: Thu Apr 22, 10AM in D520.
Take home exam due: Fri Apr 23, 10AM in D520.

Lecture times and location

Day Time Room
Tue Th 15:05-16:20 B775

[Office hours]

Outline

[PDF]

Take home exam

Picking up the questions: the questions for the take home exam will be handed out on paper, by your instructor personally on Thursday, April 22 at 10:00 am, in room D520. I will be available to hand out the exam questions between 10:00 am and 11:00 am. After 11:00 am you are not guaranteed to receive the questions and you risk missing the exam.

Handing out the answers: you must deliver your answers written on paper to your instructor, personally, on Friday April 23, at 10:00 am, in D520. Exams delivered 2 hours late will receive a 10% penalty. After 12:00 noon on Friday April 23, no more answers will be accepted and you will receive a mark of zero in the exam.

Emergencies: try to stay out of trouble. Ask your mom for suggestions how to do that. If things do happen and you are unable to hand out your answers, contact me as soon as you can either by e-mail or phone @ 403.329.2298.

If you have questions: I am available on Thursday April 22 between 10 am and 11 am in my office in D520 to answer questions about the exam. After 11 am no questions will be answered by e-mail, phone, or in person, except to settle emergency situations as above. You are strongly advised to stay on campus for the first hour, to read the questions carefully and to think about the solution.

Requests for remarking

If you disagree with your mark in an assignment or test, please fill out this form. Include the form and your marked test/assignment in an envelope and hand them in during the office hours or in class no later than one week after the marked test is returned. Your entire work will then be re-marked and, as a result, your mark may go up or down, or remain unchanged.

Lecture Notes and Readings

Week Topic Document
W1: J7 Admin issues, definition of OR, examples [pdf]
W2: J12, J14 Some Math background [pdf]
Read Chapter 3 in the text.
W3: J19-J21 LP duality. Chapter 4 in text.
W4: J26-J28 Primal-dual algorithms for assignment. Read Chapter 5.
[notes]
W5: F2-4 Primal-simplex method for transportation problem. Read Chapter 6.
[notes]
W6: F9-11 Primal-simplex method. Read Chapter 7.
[notes]
W6 bis: F16-18 Reading week No classes
W7: F23-25 Primal-simplex method (c'ed).
Modelling with integer programming. 		Read Chapter 9.
[notes]
W8: M2-M4 Undergraduate paper presentations.
Topics: Meta-heuristics in solving large optimization problems. 		An introduction to tabu-search, Gendreau (2003): [pdf] ; Presenter: Trevor Gowman
An evolutionary tabu search algorithm and NHL scheduling, Costa (1994): [pdf] ; Presenter: Kevin Kruger
Variable neighborhood decomposition search, Hansen etal (2001): [pdf] ; Presenter: Tom Arjannikov
Ant system: optimization by a colony of cooperating agents, Dorigo etal (2001): [pdf] ; Presenter: Michael Karst
W9: M9-11 Solving integer programs with B& B Read Chapter 10.
[notes]
[example] (by Alexandre Bayen @ Berkeley)
W10: M16-18 Solving integer programs with "branch and cut" and "dual simplex". [notes]
Notes on dual simplex from K. Murty.
W11: M23-25 Non-linear programming Chapter 14 in text
[notes I]
[notes II]
W12: M30-A1 NLP (c'ed)
Graduate student presentations. 		[NLP notes III]
Raqibur: TSP [Dantzig etal 1954]
Fouzia: column generation [Gilmore Gomory 1961]
Sadid: Lagrangean relaxation [Fisher 1985]
W13: A6-8 NLP (c'ed)
Interior point methods for LP 		NLP III (c'ed)
[notes interior point]
[text by Hillier]
(Hillier and Lieberman, Introduction to OR, 9th Ed, sect.7.4)
W14: A13-15 Exam Review Problems will be reviewed in class.

Projects

Submission guidelines

All projects require a project report to be handed in class, on our last class meeting of the sememster, April 15. You will be marked based on this project report paper. Your grade will be out of 20 points.

Marking scheme:

Projects

Students (especially graduate) are encouraged to choose an optimization problem that might be useful for their research.

  1. Solve Integer Programs for one of the problems suggested in the problems sections (or a problem of your choice; discuss with your instructor first). Implement B and B in Octave or another programming language; use glpk or other package to solve LP relaxations, but write your own routines for the search. Experiment at least 2 different search strategies (what variable to branch on and which subproblem to explore). Use the same problem data with each strategy and with Octave's glpk integer program solving capabilities. Use problems of increasing size and see at what problem size the methods seem to break down.
  2. Implement a simplex algorithm based on the Bartels-Golub method where the basis matrix is factored using L-U method. Octave has routines for L-U factorizations that you can use. Compare this method with your simplex implementation from Assignment 3 and with Octave's glpk simplex. The Bartels-Golub method is described in a 3 page paper here and here.
  3. (Not recommended for undergraduate level) Lagrangean relaxation (LR). Choose a problem and study a LR formulation. Focus on a clear and thorough project report. Write some code to test your ideas. If you have time, compare results with Octave's LP engine glpk.
  4. (Not recommended for undergraduates) Sensitivity analysis: choose a problem from the type of problems covered in your text (assignment, transportation, product mix, blending, diet, etc...). Given a range [a,b] and a variable, plot the optimal cost of the LP as the cost coefficient of the variable chosen varies in the interval [a,b].
  5. Write a visualisation tool for dual-simplex assignment algorithms, simplex transportation, or branch and bound, preferably in java and accessible from a web interface.
  6. Any other ideas? Discuss with your instructor first.

Problem list

Please research for the definition of each of these problems.

  1. Dominating set problem in graphs.
  2. Uncapacitated facility location problem in graphs.
  3. P-median facility location problem in graphs.
  4. Maximum clique problem in graphs.
  5. Other?

Paper presentations

March 2 and March 4: 4 papers presented by undergraduate students only. Please e-mail me with your choice of paper presentation. Choose a paper that has no presenter yet. If you are taking the class as undergraduate, this is your only chance to subscribe to a paper presentation.

Guidelines for presentations and marking scheme: [txt] .

  1. M2: An introduction to tabu-search, Gendreau (2003): [pdf] ;
    Presenter: Trevor Gowman
  2. M2: An evolutionary tabu search algorithm and NHL scheduling, Costa (1994): [pdf] ;
    Presenter: Kevin Kruger
  3. M4: Variable neighborhood decomposition search, Hansen etal (2001): [pdf] ;
    Presenter: Tom Arjannikov
  4. M4: Ant system: optimization by a colony of cooperating agents, Dorigo etal (2001): [pdf] ;
    Presenter: Michael Karst
  5. Outline of an algorithm for integer solutions to linear programs, Gomory, 1958. [pdf]
  6. An applications oriented guide to Lagrangean relaxation, Fisher, 1985. [pdf]
    Presenter: Sadid Hasan
  7. A linear programming approach to the cutting-stock problem, Gilmore and Gomory, 1961. [pdf]
    Presenter: Fouzia Mousumi
  8. Solution of a large scale TSP, Dantzig, Fulkerson, Johnson, 1954. [pdf]
    Presenter: Raqibur Rahman

Assignments

Assignment 1: Due Feb 9 (in class).
[questions]
Solutions: [P.1-3,5-7] ; [P.4] .

Assignment 2: Due Feb 25 (in class).
[questions]
Data for Problem 5:

Solutions: [P1-3]

Assignment 3: Due Mar 18 (in class). You need to submit your source code by e-mail before class.
[questions]
Solutions: [P2]

Assignment 4: Due Mar 30 (in class).
[questions]
[solutions]

Matlab/Octave resources

  • A database of nice matrices from real world applications: [url]

    Updated Apr 8, 2010.