Optimisation

Since my early training was in optimisation, I still retain an interest in this topic.  I like teaching it and recently taught a small group of Ph.D. students some material on matchings and other discrete optimisation problems (in a very discreet manner, not too many other people knew about it).  The basic premise was that almost all discrete optimisation problems that can be solved 'efficiently' can be solved because of good calculus, through linear programming, which has good characterization of solutions, a very useful theory of duality, good search directions and so forth.  While this connection is clear in network flow problems and related problems (shortest path, assignment, bipartite matching, min cut etc) it is a little less clear for those problems arising from greedy matriod optimization problems (e.g. minimum spanning tree, where we do not have very efficient formulations but nevertheless have very efficient algorithms which can be interpreted as simplex iterations) and so with non-bipartite matchings.  In all the above, the polyhedral approach to these problems has proved to be useful (resulting in good, if not best-known algorithms) and definitely insightful.  I'm looking for discrete optimization problems that can be solved efficiently where this line of thought is NOT useful.

In applications of optimisation, there are many, many interesting possibilities and some that I am interested in are: sports scheduling and transport timetabling.

Some notes that I had writte up for a course many years ago (in IIT Guwahati) are here.  They cover basic material, but list many points and some exercises which may be written over a few hundred pages in good text books.  They may be of some use to those preparing for qualifiers or a general glance at the subject.

AttachmentSize
PDF icon optimization-notes.pdf1.13 MB