Linear Programming Tools for Integer Programming

点击翻译按钮获取中文摘要

This research is directed towards simplex-based tools for integer and linear programming. The principal application is integer programming, but this work also provides an opportunity to study the simplex method as a method for solving any linear program. This research makes use of LOPT, an existing C implementation of the simplex method developed by the proposer. Principal aspects of the research are the following: o Developing effective data structures and reoptimization methods for dealing with a sequence related but dynamically changing linear programming problems. o Studying methods for dealing with the large-scale degeneracy that arises in combinatorial applications. o Further improvements in the basic elements of the LOPT implementation, including developing C implementations of sparse factorization routines, factorization update routines, and variations of these routines that exploit the special structure of combinatorially defines problems. This work is being carried out, in part, in collaboration with Martin Grotschel of the University of Augsburg. A joint research project on polyhedral methods for the max-cut problem is also underway together with Francisco Barahona of the University of Waterloo. This latter work is not formally part of the current proposal, but is an important parallel effort. Both the collaboration with Grotschel and that with Barahona will provide concrete integer programming instances central to the present investigation.