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

      Reading

      Problems

      • 1.1 B/H/M, pp. 45, #25 (cutting stock model).
      • 1.2 B/H/M, pp. 86, #11 (simplex method). Please solve the problem using GAMS or the Optimization Technology Center facility. Please show the basic feasible solution for each iteration. (GAMS will be the main tool that you will need for the final project. Here are one and two sample GAMS files that use the LP model.)
      • 1.3 B/H/M, pp 87, #14 (parametric LP).
      • 1.4 B/H/M, pp 135, #13 (sensitivity analysis).
      comments from the marker on assignment 1.

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

      Reading

      • B/H/M, pp. 157-229 (Duality-Practice)

      Problems

      • B/H/M, pp. 192-3 #3
      • B/H/M, pp. 193 #5
      • B/H/M, pp. 199 #13
      • B/H/M, pp. 201 #16
      comments from the marker on assignment 2.

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

      Reading

      Problems

    4. Homework #4 (Mixed Integer and Dynamic Programming)
      Due: Thursday Mar. 19.

      Reading

      Problems

    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. Oil Refinery Optimization
      (Due: Thursday, Jan 29)

    2. Faculty - Course Assignment
      (Due: Tuesday, Mar. 3)

      In 1973, the Graduate School of Management at UCLA revamped its M.B.A. 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 three quarters) 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 quarters (fall, winter, and spring). Some courses can be taught in either of the two specified quarters; this information is available. A faculty member might not be available in all the quarters (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 quarters when a faculty member will be available and the total number of courses he will be teaching in those quarters. 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.
      Build a model for determining a teaching schedule. Test this model on some sample data.
    3. comments from the marker on case study 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.
    Include, as a separate enclosure, a reproduction of presentation materials which you would use for a 15-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. Mar. 24, in class.
    Presentation Dates: Thurs. Mar. 26 to Thurs. Apr. 2.

    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. Electric Power Planning

      This problem concerns an electric utility which produces power using three types of generating facilities. Each type i is characterized by technical and cost parameters which include: minimum output, maximum output, minimum cost per hour, incremental cost per megawatt hour and start-up cost. At any point in the day, the capacity of operating generators must exceed expected demand by 15%. This `spinning reserve' requirement means that the model must distinguish between the number of generators in use and the generating output.
      The objective is to schedule start-ups, shut-downs and generating profiles for each of Ni type i units, in order to satisfy demand and reserve requirements at minimum overall cost per day.

      Some possible data: 

      time of day:     12am-6am    6am-9am  9am-3pm   3pm-6pm   6pm-12am
Demand (1000MW):    15         30       25        40        27


          Min-Pow   Max-Pow  Cost-Min  Cost-Inc  Start    Number
          (1000MW)  (1000MW)  (L/H)    (L/H/MW)  (L)      (Units)
Types:
1           .85       2.      1000       2.      2000       12
2          1.25       1.75    2600       1.3     1000       10
3          1.5        4.      3000       3.       500        5

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

    4. 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. In addition, consider the problem of choosing an optimal subset of the investments (e.g. one third).

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