UNIVERSITY OF WISCONSIN-MADISON
                             COMPUTER SCIENCES DEPARTMENT

                              SEMESTER I    YEAR 1993-94



           COURSE NO.                COURSE TITLE                 INSTRUCTOR
           CS 720                 Integer Programming            R. R. Meyer

           COURSE DESCRIPTION
           CS 720 will deal with  both  the  qualitative  and  quantitative
           aspects  of  integer  and  mixed  integer  programming.  On  the
           qualitative  side,  we  will  discuss  conditions  under   which
           problems can be formulated via integer and mixed integer models,
           and  why  these  problems  are  among  the   most   economically
           significant    applications    of    mathematical   programming.
           Quantitatively, we will consider a rigorous technique  of  model
           formulation,  the  structure of the feasible region, and branch-
           and-bound, branch-and-cut, cutting plane and other  methods  for
           solution.  Techniques for important special problem classes such
           as plant location and the traveling  salesman  problem  will  be
           treated.

           LECTURES
             Time:2:30 - 3:45  TR
             Place:1257 Comp. Sci.

           WRITTEN ASSIGNMENTS AND EXAMS
             Five problem sets.  Mid-term exam.  Programming projects using
           courseware packaged with text.
             Choice of additional computing project, oral presentation,  or
           oral final exam.

           GRADING SYSTEM
             Weightings:Problems - 1/2
                      Mid-term - 1/6
                      Oral final or alternative - 1/3

           REQUIRED TEXT
             AMPL, by Fourer et al.  Notes for a forthcoming book available
           at MACC documentation desk.

           COURSE OUTLINE
             Week   Topic
                 1-5Examples of  integer  and  mixed  integer  programming.
                    Review   of  important  results  from  LP.   Optimality
                    conditions.  Formulating problems involving  piecewise-
                    linear  functions  as mixed-integer programs.  Good vs.
                    bad formulations.
               6-10 The branch-and-bound method:  the  basic  approach  and
                    computationally   important   refinements.   Optimality
                    tolerances.
             11-15  Other  methods,  including   cutting   plane   methods,
                    branch-and-cut,  and  methods  related to the traveling
                    salesman problem.