Deterministic OR Models - C &O 370 - Fall 1996

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. Diet Problem
      (Due: Thursday September 26)

      B/H/M, pp. 193-194, #6; include the solution of a sample problem using the       Optimization Technology Center facility, i.e. their Diet Problem model. (Note: You will save a lot of time by checking out - clicking - on their diet problem model. For those with no netscape: no tables Diet Problem model for mosaic.) Include sensitivity analysis information, e.g. what happens if: the prices of the foods change; the nutrient requirements change; new foods are added?
      marking scheme for case study 1
      marker comments for case study 1

    2. Outer Approximation of Union of Ellipsoids
      (Due: Tuesday October 15)
      due date postponed to Thursday Oct 17 - Happy Thanksgiving.

      Find the smallest volume ellipsoid that covers the union of p given ellipsoids. Each ellipsoid is expressed via an associated quadratic function. (Use random data to construct 5 ellipsoids.)
      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. (Thanks to Colin Campbell in DCS for many hours of help to get this installed. Thanks also to Shao-Po Wu at Stanford for quick changes so that the installation could proceed.)
      • local notes on geometrical problems (from notes by Boyd and Vandenberghe)
        (URL: ftp://orion.uwaterloo.ca/pub/henry/teaching/f96/370.f96/geomprobs.ps)
      • local copy of MAXDET complete package (from Boyd and Vandenberghe)
        (URL: ftp://orion.uwaterloo.ca/pub/henry/teaching/f96/370.f96/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)
      marker comments for case study 2

    3. Faculty-Course Assignments (Ahuja, Magnanti, Orlin, 1993)
      (Due: Thursday, November 7)

      A graduate school of Management Science revamped its curriculum. This change necessitated an increased centralization of the annual scheduling of faculty to courses. The large size of the problem (100 faculty, 500 courses, and 3 semesters) suggested that a mathematical model would be useful for determining an initial solution. The administration knows the courses to be taught in each of the three teaching semesters (fall, winter, and spring). Some courses can be taught in either of the two specified semesters; this information is available. A faculty member might not be available in all the semesters (due to leaves, sabbaticals, or other special circumstances) and when he is available he might be relieved from teaching some courses by using his project grants for "faculty offset time." Suppose that the administration knows the semesters when a faculty member will be available and the total number of courses he will be teaching in those semesters. The school would like to maximize the preferences of the faculty for teaching the courses. The administration determines these preferences through an annual faculty questionnaire. The preference weights range from -2 to +2 and the administration occasionally revises the weights to reflect teaching ability and student inputs. Suggest a network model for determining a teaching schedule. (Use your own sample data to test the model.)

    RESEARCH PROJECTS INFORMATION - C &O 370

    General: In groups of three or less, you are to solve one of the attached problems. 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 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.
    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 extensions and avenues for further study. Divide the main body into subsections as appropriate.
    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, November 19, in class.
    Presentation Dates: Tuesday, November 26 through Tuesday, December 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. Routing and Oil Distribution

      This project deals with routing sea-going vessels which carry oil products from refineries to delivery depots.
      Suggested problem data:
      • three oil refineries
      • twelve to fifteen depots (customers)
      • five different oil products
      • 10 vessels (roughly 8 compartments per vessel)
        • 5 vessels are owned but there is a daily cost to operate them.
        • 5 vessels are rented and the demurrage (overtime) costs are very high (say 10 x daily rate ); while the regular daily rate is the same as the "owned" vessels.
      Each depot has unique storage and consumption patterns for each product (assume a linear consumption rate), and of course, an inventory at any point in time. Not all the refineries produce each product. Travel times are unknown and vary slightly. A normal travel time is in the order of days with about a 10\% error. Constraints:
      • Since the depots do not place orders, it is part of the project to determine order quantities to guarantee that a customer never runs out of any product.
      • Depot storage capacities cannot be exceeded.
      • Only one product per compartment is allowed. All of this product must be delivered to one customer (i.e. it cannot be split).
      • Refineries have unlimited capacity.
      Objective: Minimize expected long run total distribution cost (not including inventory holding costs), by developing a set of orders and vessel routes.
      Reference: W.J. Bell et al, "Improving the Distribution of Industrial Gases with an On-line Computerized Routing and Scheduling Optimizer", INTERFACES, Vol 13, No. 6, pp4-23, 1983.

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

    5. Courier Service

      Loomis Couriers of Mississauga is a company with a mandate to deliver parcels anywhere in Canada in an economical and QUICK manner. One of the most unstructured delivery routes in Canada is that of Toronto's downtown core. The driver can not simply park on the side of the road as is done for all other routes. He would block traffic and get parking tickets. Besides, this method would be much too slow.
      The current solution is to have four "walkers" who are roughly stationed at the four corners of downtown. The driver comes down off the freeway and chooses a walker to go see. He drops the first batch of parcels to that walker and then makes a decision as to whom he should see next. He continues until all parcels are delivered.
      Develop a model by which the driver can minimize his total delivery time.
      In general, the following information must be supplied to the model:
      1. A map labelled with the times required for the driver to get from corner to corner
      2. The number of parcels that each walker has to deliver
      3. The time required for the walkers to deliver a parcel and for the driver to deliver parcels to the walkers
      4. The number of parcels that one walker can can carry at a time.
      Test your model using the following data:
      Walker.............Intersection............Parcels to deliver
      A............York & Wellington...............49
      B............York & Queen......................31
      C............Younge & Shuter..................43
      D............Younge & King.....................22

    6. Coal Tipple Operations

      The Aspen-Boulder Coal Company runs a loading facility consisting of a single large coal tipple. When coal trains arrive, they are loaded from the tipple. The standard train takes 3 hours to load and the tipple's capacity is 1-1/2 standard trainloads of coal. Each day, the railroad sends three standard trains to the loading facility and they arrive any time between 5 AM and 8 PM local time. Each of these trains has three engines. If a train arrives and sits idle while waiting to be loaded, the railroad charges a special fee, called a demurrage. The fee is $5000 per engine per hour. In addition, a high capacity train arrives once a week every Thursday between 11AM and 1 PM. This special train has five engines and holds twice as much coal as a standard train. An empty tipple can be loaded directly from the mine to its capacity in 6 hours by a single loading crew. This crew (and its associated equipment) costs $9000 per hour. A second crew can be called to increase the loading rate by conducting an additional tipple-loading operation at the cost of $12,000 per hour. Because of safety requirements, during tipple loading, no trains can be loaded. Whenever train loading is interrupted to load the tipple, demurrage charges are in effect.
      The management of the Coal Company has asked you to determine the expected annual costs of this tipple's loading operations. Your analysis should include the following considerations:
      1. How often should the second crew be called out?
      2. What are the expected monthly demurrage costs?
      3. If the standard trains could be scheduled to arrive at precise times, what daily schedule would minimize loading costs?
      4. Can this tipple support a fourth standard train every day?

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