Math 441 Section 201
Mathematical Modeling: Discrete Optimization Problems
Online Course Material 

NEWS

If you are using LINDO with some integer variables specified, then you should turn off the output to the reports window while LINDO is doing its branch and bound routine. You do this by clicking on EDIT -> OUTPUT and then click on TERSE OUTPUT. When the program terminates you can still get the final answer (assuming the program terminates!) by clicking on REPORTS -> SOLUTION

Hope you had a great summer. This course should be a lot of fun for students. It can be considered a capstone course, giving students an opportunity to use their mathematical maturity to work on `real world' problems. It also serves a Arts degree `research intensive approved course' which is a degree requirement for a B.A. If you are in a joint degree with another specialty in Arts such as Economics, you may be taking `research intensive approved course' in that other department but you are more than welcome to take this course.

The course has a reasonable amount of work and certainly the project takes a lot of time but students typically enjoy the experience. Also there is no final exam! This course does have MATH 340 as a prerequisite. You can discuss with me if this is missing.

This course uses discrete optimization techniques such as Linear programming and Integer Programming. We will be using software (LINDO, LINGO) for assignments and possibly the project. The course is organized with 50% for assignments and 50% for a project. The project is done in a groups of at most 3 and a polished write up is expected. There is no final exam. Contact me if you have questions before selecting this course.


The Course Outline gives a timeline for projects. It is important that groups and projects are chosen early. I will expect project proposals by Friday Oct 3. We will have about 15 minute group presentations as progress reports the week of October 27. Aim to have a nice overview of the problem (this will probably be useful later on when you are doing your write up) and give some sample input/output to indicate your progress to date.

Some changes are possible but I wish the groups to begin exploring their project early. In particular, I expect a written report and verbal report on or before Monday October 27. It is a chance for you to see how your group should be organized to produce a report. Hopefully you will have some initial computations done and are aware of the difficulties you might encounter. You should contemplate the scope of your project. Consultation with me is essential. I can help you identify the questions that you might focus on and indicate parts of the project that are likely to be hopeless. It is your responsibility to make the project interesting for me. There is no `right' answer. You might find useful information in the handout Project Information.
Groups formed:
  • Pooya,Radhika,Russell are exploring Exam Scheduling and graph colouring. It was pointed out that the letter u was missing on their slides. Russell gave an example where greedy colouring did not yield an optimal coloring. Radhika gave a discussion of how to look for lower bounds on colouring i.e. looking for a big clique.
  • Pacus, Jasmine, Phil are exploring choosing delicious food from some UBC food outlets. They have indicated which establishments they will consider but sadly a number of delicious foods exceed the dietary recommendations for lunch.
  • Samuel, Ricardo are going to find an optimal way to celebrate graduation in Europe using the TSP.
  • Ervin, Kyle, ZangYang are exploring how to cut out rugs from a roll so that there is little waste.
  • Ragnhild, Veronica are exploring multidimensional bin packing while under threat from a gangster. They gave a lovely presentation Wed Oct 29 about their progress and possible directions for their project.





  • The final project is due Friday November 21.

    Grading this course can be a challenge. It is disconcerting for students that they won't get 100% for the correct answer. We give the top marks only to those with clear and interesting writeups. The average in the course will probably be in the low 70's. The overall grading distribution will be reminiscent of an Arts course. I expect many good results but only the occasional stellar writeup.

    Some LINDO data files LINDO files

    The notes look authoritative when typed so be wary. They may look perfect but may still contain errors! I don't have an editor.
    I arrive most days by 9:00. I am scheduled to teach 10:00-11:00 MWF. I typically do not read my email from home (i.e. evenings and weekends).
  • Course Outline: grading scheme etc. 
  • Assignment 1 due Wednesday Sept 10. Solutions  
  • Assignment 2 due Friday Sept 19.   Hiring Firing input files , LINDO file, or LINGO file > Solutions
  • Assignment 3 due Friday Sept 26. Solutions  
  • Assignment 4 due Friday Oct 10 Solutions  
  • Assignment 5 due Friday Oct 24. Solutions  
  • Assignment 6 and spreadsheet due Monday Nov 10.  
  • Assignment 7 due Friday Nov 28.  


  • Slick Oil (vertically integrated oil company). Slick oil file problem file, Slick oil solution file, LINDO file for Slick Oil , LINDO file for Slick Oil with a number of variables as a constant

    Absorptivity files LINDO file, or speadsheet of data , LINGO file,

    Vista Properties Vista Property Development data, We will explore this in class. LINDO input file,

    Branch and bound examples showing how to use this to solve an integer (or mixed integer) programming problem.  

    Modeling Piecewise linear cuves whose constraints are called SOS2: Specially ordered sets of size two.  

    Fano Plane and Projective Planes by Integer Linear Programming LINGO file

    Jobshop Files Machine Shop job scheduling problem. , LINDO file , LINGO file

    Pit Mining Problem Cross section , Arcs ,Max Flow problem An intermediate flow and augmenting path , Max Flow , Min Cut identified as nodes that can be reached by augmenting paths, Optimal Pitmine  

    Network Flow template LINGO file, LINDO file

    An integer Linear Program selecting for chemicals to provide coverage over a range of wavelength. Chemical Coverage  

    Chemical Laboratory Remodelling Project. LINDO input file to determine longest paths using Network Flows. Excel spreadsheet to use Dynamic Programming to compute longest paths.

    Dynamic programming notes for basic formulation without or with discounting. Also spreadsheets for the two cases. Sheet 1 has the basic formulation. Sheet 2 has the version with discounting. A version with more formulas and less typing is alternate.

    Construction Project Speedup (not crashing). Problem statement. Excel spreadsheet to use Dynamic Programming to find optimal way to spend the $70,000.

    Stochastic Dynamic Programming example and spreadsheet We consider optimal ordering decisions to optimize profit in the face of stochastic demand. If we assume that optimal decisions become fixed with time then we have an interesting linear algebra idea that shows that in this case the profit per month is something like $1075.

    Graph Theory Drilling holes at minimum spacing in a metal plate. The minimum number of passes becomes the colouring number of a graph.

    Plotting Pen Problem (Old Technology) appeals to the minimum weight matching problem. This effort used heuristics to find low weight matchings. Plotting Problem , Tokyo Map , Extra motion after Random shuffling of plotting instructions , Result of an intelligent person ordering plotting instructions , Serpentine Buckets and ordering , Matching of extra motion , Triangular buckets ordered by Serpinski ordering , Matching of extra motion .

    Various Reference files. Some are some nice and short descriptions from the AMS but also other information as well. If you suggest a link, I'll add it.

  • Cookie recipe
  • Linear Programming Theorems  
  • Brief discussion of Travelling Salesman problem  
  • website with an enormous amount of information on the Travelling Salesman problem including the Concorde algorithm in a phone app!  
  • Brief version of the travelling salesman problem for the New York Subway 
  • Studying Sudokus  
  • Bin Packing  
  • website on unusual TSP algorithm, a bit too small to be useful.