Deterministic OR Models - C &O 370 - Winter 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

    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.
    Following are the Case Studies and their due dates.

    CASE STUDIES LIST - C &O 370

    1. Cutting Stock Problem
      (Due: Thursday January 23)

      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. Inner Approximation of Intersection of Ellipsoids
      OR Outer Approximation of Given Points
      (Due: Tuesday February 11)

        1. Find the ellipsoid of maximal volume contained in the intersection of p given ellipsoids in n-dimensional Euclidean space. (Use random data to construct 5 ellipsoids.)
        2. Alternatively, find the ellipsoid of minimal volume containing p given points in n-dimensional Euclidean space. (Use random data to construct 9 points.)

        References:
        • The software (matlab) for this problem has been copied and installed in the directory: /u3/co370/maxdet on the undergrad.math environment. Please use cayley, napier, or descartes machines. You can copy the startup.m file to your directory; which will set the path properly when you start matlab. You will then be able to use these files from your own directory.
        • local notes on geometrical problems (from notes by Boyd and Vandenberghe) (Note that page 204 contains a description of the outer approximation of given points problem.)
          (URL: ftp://orion.uwaterloo.ca/pub/henry/teaching/w97/370.w97/geomprobs.ps)
        • local copy of MAXDET complete package (from Boyd and Vandenberghe)
          (URL: ftp://orion.uwaterloo.ca/pub/henry/teaching/w97/370.w97/miscfiles/maxdet.tar.gz,
          Note that the complete package can be obtained by anonymous ftp to orion - if you encounter problems with downloading this using mosaic.)
        • Determinant maximization with linear matrix inequality constraints
          (URL: http://WWW-ISL.Stanford.EDU/~boyd/maxdet.html)
        • MAXDET: software for determinant maximization problems.
          (URL: http://WWW-ISL.Stanford.EDU/~boyd/MAXDET.html)
          Use SDPSOL for maxdet problems.
          (URL: http://WWW-ISL.Stanford.EDU/~boyd/SDPSOL.html)
      2. Discuss the linearity/nonlinearity of your research project, e.g.: What type of nonlinear equations (if any) do you expect? What degree of nonlinearity do you hope to deal with? Will using nonlinearity help in your project?

      3. B/H/M, pp 360 #21
        (Due: March 13 )

      4. B/H/M, pp 422 #27
        (Due: April 3 )

      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.
      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: Tuesday, Mar 25, in class.
      Presentation Dates: Thursday, Mar 27 through Thursday, Apr 3.

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

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

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

      5. Selecting a Gymnastics Team

        In women's gymnastics competition there are four events: vault, uneven bars, balance beam and floor exercise. Each team can enter up to six gymnasts in each of these events. The top five scores from the six entrants are included in the team score. A major constraint in selecting the six entrants for each event is that there must be at least four ``all-arounders" who must compete in all four events.
        Develop a model for assisting the coach in selecting the entrants for each event so as to maximize the expected total team score. Test your model using the following data: 
        Events: Gymnast Vault      Bars      Beam     Floor 
          1      9.80      9.10      9.15      8.90 
          2      9.00      8.90      9.10      8.50 
          3      8.50      8.30      9.20      9.00 
          4      7.00      9.00      8.30      8.65 
          5      9.40      8.30      9.00      8.50 
          6      8.90      8.80      7.90      9.00 
          7      8.50      8.90      8.80      8.10 
          8      9.10      9.20      8.50      8.20 
          9      7.90      7.30      8.00      8.80 
         10      8.90      8.80      9.10      8.70  

Table:  Scores (0 to 10 in each event) Expected by the Coach for each
Gymnast in each Event.

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

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