Deterministic OR Models - C &O 370 - Fall 1997

"An applications-oriented course that illustrates how various mathematical models and methods of optimization can be used to solve problems arising in business, industry and science"

Contents

Conduct of Course

  • Instructor:
  • Tutors:
  • Office Hours:
  • Lectures:
  • Texts:
  • References:
  • Term Work:
  • Midterm Exam:
  • Final Exam:
  • Marking Scheme:

    COURSE TOPICS OUTLINE - C &O 370

    HOMEWORK INFORMATION - C &O 370

    There will be 4 homework assignments given throughout the term. Each will consist of problems and specified readings from the text, references and resource materials listed on the C&O 370 homepage. The problems are to be done individually and handed in for grading.
    Some problems will be computational exercises giving practice with implementing general algorithms, using available software; and others will be modelling exercises giving practice with extracting precise mathematical formulations from applied problems. The T.A.'s will mark a subset of the problems and will hold office hours to help resolve any difficulties you may have. The 10% contribution of homework to your course grade belies its importance, as both exams will be based upon homework readings and problems. Following are the homework assignments and their due dates.

    HOMEWORK LIST- C &O 370

    According to my calculations, the problem doesn't exist.

    CASE STUDIES INFORMATION - C&O 370

    Case Studies are definitive problems requiring a greater degree of analysis and thoroughness of presentation than do homework problems. Generally, computer software such as GAMS will be a required component of such problems. Case Studies should be formal reports, as if done for a customer. They should be concise, clearly written and self-contained.

    Format for Case Studies

    Each Case Study should be done in groups of 2 or 3 students. These groups may be comprised of students from either of the two sections of the course.
    On the given due dates each group should submit one paper only, with each group member's name, I.D. and course section number on the title page.
    Each case study will be graded and returned to you. The grading will be based upon both technical accuracy and clarity of presentation. It is imperative that you stretch your communication skills.
    Project and Case Evaluation Scheme.
    Following are the Case Studies and their due dates.

    CASE STUDIES LIST - C &O 370

    1. Cutting Stock Problem
      (Due: Thursday, Oct 2)

      1. Chvatal, pp. 211, #13.2a and b.
        (GAMS like outline- not proofread yet; please tell me of any errors/typos)
      2. Use GAMS to solve a simple linear programming relaxation of your project.

    2. Transshipment Problem
      (Due: Tuesday, Oct 21)

    3. Integer Programming (Warehouse Location)
      (Due: Thursday Nov. 6 )

      • B/H/M, Page 410, #9.
      • In addition, solve the model in part a) with some (reasonable) data of your choice.
      • How large do you think you can make m and n, in the original model, and still solve the problem (using GAMS) within a reasonable amount of time?
      • Case Study 3 Evaluation Scheme. Note that sensitivity analysis is a difficult topic for integer programming. The marking scheme will emphasize extensions rather than just sensitivity analysis. For the sensitivity analysis, please consider the case when the integer variables are fixed. In addition, try and estimate shadow prices using perturbations.

    RESEARCH PROJECTS INFORMATION - C &O 370

    General: In groups of three or less, you are to solve one of the attached problems. You must inform your instructor about your project choice before the first case study is due. (Choose your project early as there is a limit of four groups per project for projects 1-9. There is no limit to the number of groups in project 10.)
    You may use any resources as aids, provided you reference them carefully. You may consult with instructors/tutors concerning your planned approach and to obtain limited technical help. Projects should be clearly written self-contained reports with the narrative parts typed in English.
    Guidelines: The project problems tend to be real-world, open-ended and are unlikely to have unique solutions. It is a good idea to solve completely a restricted, or core, version of your problem by making appropriate simplifying assumptions and then to do what you can with each of a progression of harder versions, or extensions, obtained by relaxing the assumptions.
    Your project will be assessed primarily in terms of how well you communicate your knowledge of both the problem and your model. Accordingly, make your analysis as thorough as possible, and make certain that your model is an appropriate one. Your attitude should be one of an employee of a company or a consultant working for a company.
    Data: In many instances you are not given specific data for the problem. In this case, please make up your own data.
    Format: The format should be similar to that of the case studies, with the added components of a detailed model critique and analyses of core problem extensions. The report structure should include:
    title page/table of contents/abstract/summary of results/mainbody/references/appendices.
    The summary of results should offer motivation for the reader to want to read the rest of the report. It begins on a separate page (following the abstract), which is page number 1.
    The main body should contain: your model(s); clearly developed and annotated; your core problem analysis; your model and solution critique; and your extensions and avenues for further study. Divide the main body into subsections as appropriate. In addition, your critique can include a comparison with a manual (intuitive or other) solution of the problem, thus illustrating the strength of the model.
    References (not a bibliography) are associated with the citations in the text. Include books, papers, software and personal consultations. Please ensure that all references are included. Due to the ease with which related work can be found on the internet, it is important that you include references to all work that you have used.
    Appendices should be used for such things as extended background material, programmed versions of your model(s) and output and any kind of lengthy detail that would interfere with the flow of text.
    Include, as a separate enclosure, a reproduction of presentation materials which you would use for a 20 minute oral presentation of your work.
    Well in advance of the project due date arrange a meeting with your professor to discuss your overall study plan, your choice of model(s) and the resources which you anticipate using.
    Project Due Date: Tues. Nov. 18, in class.
    Presentation Dates: Nov 20-27.

    RESEARCH PROJECTS LIST - C &O 370

    1. Ellipsoidal Approximations

      Study and solve the following geometrical problems:
      • Outer Ellipsoid:
        • Find the ellipsoid of minimal volume that contains p given points in n-dimensional Euclidean space.
        • Find the ellipsoid of minimal volume that contains p given ellipsoids in n-dimensional Euclidean space.
      • Inner Ellipsoid:
        • Find the ellipsoid of maximal volume contained in a given polytope in n-dimensional Euclidean space.
        • Find the ellipsoid of maximal volume contained in the intersection of p given ellipsoids in n-dimensional Euclidean space.
      (Use random data to construct ellipsoids.)
      References:

    2. Designing a Parking Lot

      Develop a model for determining an optimum parking layout of a given rectangular paved lot. That is, determine the widths of access lanes and how the lines are to be painted (both subject to existing regulations) so as to accommodate as many cars as possible. In particular, show how Parking Lot B on the UW campus can be redesigned so as to accommodate more cars.
      Of interest: campus map

    3. Kitchener (Cambridge) Public Transit

      Both Kitchener and Cambridge Public Transit companies must assign bus drivers and determine work shift schedules to accommadate given run schedules while meeting the conditions of driver union contracts.
      Using a subset of at least eight different bus runs, develop a model for assigning bus drivers to cover these runs while minimizing total personnel costs.
      of possible interest: City of Kitchener and the City of Kitchener - Street Level Map

    4. Kitchener-Waterloo Record

      The Record must decide how many copies to leave at individual locations. There are many factors that can contribute to this decision, e.g. weather, day of the week, special news stories, ...
      How can they decide on the optimal number of copies to leave in order to minimize returns (unsold copies) and reduce sellouts (no copies left)?
      contact: Kevin Vaters, phone: 894-2250 x427, location: 225 Fairway Rd, Kitchener.

    5. A Bank Account Location Problem

      A business firm has clients in cities i=1 to m, and can maintain bank accounts at locations j=1 to n. When the payment for a client is mailed by a check, there is usually some time lag before the check is cashed (time for the mail to reach back and forth), in that time the firm continues to collect interest on that money. Depending on the volume of business in city i, and the time it takes for mail to go between city i and location j, one can estimate the float = expected benefit sij in the form of this interest if clients in city i are paid by checks drawn out of a bank account in location j, for i=1 to m, and j=1 to n. The following data is given.
      • cj = cost in money units for maintaining a bank account in location j, per year
      • sij = total float (=expected benefit in the form of interest on money between the time a check for it is mailed, and the time that check is cashed) per year, if payments due for customers in city i are mailed in the form of checks drawn out of a bank account in location j,.
      • N= upper bound on the total number of bank accounts that the firm is willing to maintain.

      Determine the subset of locations where bank accounts should be maintained and the bank accounts through which customers in each city should be paid. (Use test data with e.g. m=7, n=5, N=3. Contacting a local bank would be helpful.)

    6. Dial-A-Bartender

      A professional bartender who specializes in private parties offers 5 different drink-types. Being in a competitive business, he provides his customers with a list of guaranteed prices for each type. Before actually going to a party, he premixes various quantities of each drink-type in batches.
      Develop a model for determining the most profitable combination of drink-types to be premixed as a function of the costs of their ingredients. You can test your model on the following example: 
          DRINK                (ALCOHOL) INGREDIENTS                 PRICE
---------------------------------------------------------------------
 Wine Punch              White Wine (3 oz)                     $1.30
 Whiskey Sour            Rye (2 oz)                            $2.40
 Gin Fizz                Gin (2 oz)                            $2.40
 Martini                 Gin (3 oz), Vermouth (1 0z)           $3.70
 Manhattan               Rye (3 oz) , Vermouth (1 0z)          $3.80
      For other recipes you can look at: A Bartender's Alphabetical Drink Recipe Guide or Bartendar Magazine.
      ("A bartender is just a pharmacist with a limited inventory.")

    7. Portfolio Selection

      A professional manager has a large portfolio of securities, stocks and other investments. Develop a model to guide him in his investments which will take into account his concerns about expected gain and the risk associated with the investments.

    8. Optimal Flight Plan

      A search and rescue department needs to compute a flight profile and camera pointing sequence to reconnoitre a given area without gaps in the coverage. Develop a model for generating the optimal search strategy for a remotely piloted (or pilotless) vehicle.

    9. Personnel Assignments

      A school district has 10 special education teachers who must be assigned to 10 different schools. Each teacher is to spend the morning period in one school and the afternoon period in another. Teachers specify their preferences for schools, and schools specify their preferences for teachers.

      Develop a model for determining how the teachers should be assigned to the schools.

    10. Operational Analysis

      Select a local business, and determine in what ways it might benefit from some sort of operational analysis. For example, one might select a business such as Domino's Pizza and determine in what ways its delivery policy might be made more profitable. Alternatively, one might select a manufacturing business such as Brick Brewery and determine in what ways its production-inventory schedule might be improved. (In particular, Schneider's in Kitchener has an interesting "optimal mixing" problem.)