Deterministic OR Models C&O 370
fall 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: Tuesday, Sept. 29.

      Reading

      Problems

      1. B/H/M, pp. 39, #17 (LP/Modelling)
      2. B/H/M, pp 45, #25 (cutting stock model).
      3. (simplex method) Consider the LP:
        max cx s.t. Ax <= b, Bx=d, l<=x<=u,
        where (using matlab notation - ; denotes a new row)
        c=[5,2,-3,3,6,1], A=[3, 1, -4, 2, 5, 1;-5, 4, 2, -3, 2, 3], b=[3;25] B=[1,1,2,1,1,2], d=4, l=[0,2,-infinity,-3] u=[infinity,10,0,3]. Variables 5,6 are unconstrained.
        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.)
      4. B/H/M, pp 148-152 #26 (sensitivity analysis).
      5. marker comments on assignment 1

    2. Homework #2 (Duality-Practice)
      Due: Thursday, Oct. 22.

      Reading

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

      Problems

    3. Homework #??? (Network Programming)
      Due: not this semester!! But please do the reading!!

      Reading

      Problems

      • ???

    4. Homework #3 (Mixed Integer and Dynamic Programming)
      Due: Tuesday, Nov. 24.

      Reading

      Problems

      • B/H/M, pp. 408 #6 (MIP Models)
      • B/H/M, pp. 411 #13 (Branch and Bound and Implicit Enumeration)
      • B/H/M, pp. 415 #19 (Cuttting Planes)

    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. Diet Problem, BHM Pages 193-4 #6
      (Due: Thursday, Oct. 15.)

    2. B/H/M, pp 148-152 #26 (sensitivity analysis from assignment 1)
      (Due: Thursday, Nov. 5 - I will accept this until Monday noon Nov 8.)

      • Write a GAMS program to solve this problem from the text. Please model it appropriately in GAMS, e.g. self-documentation.
      • Add some constraints to the problem to help management solve certain problems. Illustrate how GAMS can be used to quickly make changes in your model. Be inventive. For example: suppose that some of the variables are restricted to be integers; add a logical constraint on the inventory such as no teflon cannot be stored unless a certain amount of plastic is stored; etc...
      • Here is a a local copy of the Oct/98 version of the annotated bibliography on sensitivity analysis for MIP maintained by Harvey Greenberg.

      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 choices before the first case study is due. Please decide on a first, second, and third choice.
      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: (Thursday, Nov. 19 originally) postponed till Tuesday Nov. 24 in class.
      Presentation Dates: Nov. 26-Dec 3.

      RESEARCH PROJECTS LIST - C&O 370

      student groups and choices

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

        Suppose that you are given 18 aircraft and 68 legs. (A leg is one piece of the aircraft route, e.g. one aircraft may fly 3 legs as its route: 1. Montreal-Toronto, 2. Toronto-Chicago, 3 Chicago-L.A.)
        1. Find the best aircraft routing.
        2. Then suppose that you have to delete 8 legs. Find the best aircraft rerouting.

        (Use your own data. You can see a small example of a routing problem in the file crewschd.gms.gz in the miscfiles directory. You can also use the following real world data from Delta Airlines (courtesy of Qing Zhao at Delta.) )

      3. Skiving Addition to the Cutting Stock Problem in the Paper Industry

        Some paper mills receive orders for paper rolls with relatively large widths compared with a master reel to be cut into the ordered sizes. For example, when all ordered sizes exceed half the widtho fthe master reel, the trim results are disastrous.
        Skiving assumes that, along with finished rolls, several auxiliary rolls will be cut from a amaster reel. The auxiliary rolls will be skived together to form finished rolls of the require sizes. (reference pp. 472-483 in Volume 39, Number 3 in SIAM Review.)
        1. Solve a standard cutting stock problem using LP and approximation techniques. (Use your own data.)
        2. Create some data that would be appropriate for the skiving technology and solve it. (The sample data in the article, page 480, can be modified.)

      4. Snow Removal

        After a snowfall, three snowplows are dispatched to the Old Beechwood area of Waterloo. All streets in that area must be plowed twice, one in each direction, in order to remove all of the snow.
        Develp and solve a model for determining how the three plows should be used in order to finish all plowing in the minimum amount of time.

      5. Oil Lease Problem

        An oil company has shown an interest in an oil field containing several potential oil wells. The dollar value of each well is assumed known based upon estimated production. A plot of land of known dimensions containing each well must be leased by the company if the well is selected. The plots of land associated with various sets of wells may overlap. There is a major road running parallel to the southern boundary of the oil field, and a side road must be built joining any selected well to this major road.
        The net value of any set of selected wells is the sum of the values of the wells minus the land lease and side road construction costs.
        Develop a model by which the oil company can select a set of wells of maximum net value. Illustrate your model numerically using parameter values of your choice.

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