Deterministic OR Models C&O 370
Winter 1999
Handout

"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.

    HOMEWORK LIST- C&O 370

    According to my calculations, the problem doesn't exist.
    1. Homework #1 (Linear Programming)
      Due: Thursday, Jan. 21

      Reading

      Problems

    2. Homework #2 (Duality-Practice)
      Due: Thursday Feb. 11

      Reading

      • M, pp. 140-162, 227-264 (Duality, Optimality Conditions, Simplex Method)

      Problems

      • text Page 265, # 7.3. Try and use the diet problem at the optimization technology center.
      • text Page 267, # 7.5.
      • text Page 268, # 7.7-8. (You may find GAMS with CPLEX helpful.)

    3. Homework #3 (Network Programming)
      Due: Thursday Mar. 4.

      Reading

      Problems

    4. Homework #4 (Mixed Integer Programming)
      Due: Thursday Mar. 18.

      Reading

      Problems (done by hand)

      • text Page 346, # 9.44 (network).
      • text Page 403, # 10.5 (knapsack B. and B.)
      • text Page 408, # 10.11 (B. and B.)

    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.
    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.

    CASE STUDIES LIST - C&O 370

    1. Crude Oil Production, text Page 73, Problem 2.43.
      (Due: Tuesday, Feb 2)

    2. Assigning Students to Field Study Projects, text Page 336, Problem 9.32.
      (Due: Tuesday, Mar. 2)

    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.
    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.
    Presentation Each group will give a 15-20 minute presentation in class on their project.

    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. Mar. 23, in class.
    Presentation Dates: Thurs. Mar. 25 to Thurs. Apr. 1.

    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. 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.

    3. 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.)

    4. Vehicle Loading

      • Given a parking lot full of vehicles, it is required to load them onto rail cars for shipment to car dealers. The vehicles are grouped by destination on the lot. Usually it is desired to ship the vehicles that have been on the lot the longest first.
      • The rail cars are such that they can load 2 or 3 levels of vehicle (depending on type of railcar). Larger vehicles can only be loaded to bi-level railcars.
      • Often there are exceptions to the loading requirement which would require a different set of cars to be loaded first.
      • Sometimes cars have to be first unloaded from the rail cars, i.e. their are inbound shipments as well as outbound.
      • The inputs to the algorithm are the curent inventory of vehicles and rail types. The output is a set of vehicle movements resulting in the loading of the rail cars prior to the scheduled departure of the train. An objective function would be to minimize the loading time.
        Possible questions and assumptions:
        • Does each group of cars have a clear lane to the loading ramp, or is shifting vehicles to get at particular groups an issue?
        • Does the load factor vary? Typically a bi-level will load 10 and a tri-level 16.
        • What type of exceptions, and how are the vehicles grouped or identified?
        • Does unloading arriving vehicles clog the ramp? Is part of the decision problem to identify their storage location on the ramp?

    5. Truck Scheduling

      A division of an international trucking firm provides emergency freight services with a fleet of over 200 trucks covering a geographic area east of the Mississipi in the U.S. and Ontario and Quebec in Canada.
      Their problem is to provide a level of service (response time) to customers within this large service area. They want to get a vehicle (power unit) to a customer's site within 90 minutes. Considering the time it takes to get a vehicle moving, etc., this usually means they need a vehicle to be within 60 miles of a customer when the emergency call is fielded.
      The company would like to set up "service centers" that could be anything where a truck (or set of trucks) could hang out. These service centers (they could be truck stops, donut shops, etc...) would be located such that a large number of the shipments (loads, pick ups) could be handled within the 90 minute pick up tolerance level.
      Construct a network where the nodes would be the "service centers" and the arcs would be the roads used to connect the "service centers". The weighting on the nodes would be the number of loads (pick ups) expected in a certain timeframe (i.e. within the next 12 hours). The weighting on the links would be the number of times we travel between the adjacent nodes. There might be two weightings on the links - since they should probably be bi-directional.
      Assume that several years worth of trip experience is known. (Use fictitious data.) Find the best placement for their trucks so that customer service (time to respond to an emergency pick up) is minimized; running trucks empty is minimized; and turn downs (cannot take a load because we don't have the right truck in the service center) is minimized. In short, find a way to optimally position the fleet of trucks.
      Some other points to consider:
      1. Assume orders arrive randomly in time.
      2. All vehicles are equipped with satellite tracking and communication devices so they can begin the repositioning of a vehicle relatively quickly.
      3. All vehicles must adhere to the legal driving time regulations - which may impact their ability to reposition quickly.
      4. Vehicles travel at 45 mph on average.
      5. Vehicles are 6 different types - minivan, cargo van, 1-ton, 3-ton, 5-ton and tractor trailer. Demand and supply for each vehicle size needs to be in the optimization equation.
      6. Most of the time there is one load per vehicle.
      7. To move a truck empty costs 50 cents a mile. A truck under load is generating revenue. They want to minimize empty mile costs.

    6. Designing a University Campus

      Suppose that a new university is to be built on a given parcel of land. After some preliminary analysis, certain fixed locations are chosen for the buildings. Decide which buildings should go into which locations. You should take into account the cost of the building and the flow (people) between different buildings. (As a possible scenario, pick U. of W. and decide if the buildings can be relocated in a more optimal way.)

    7. 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.)