Linear Programming Tools for Integer Programming

这项研究是针对基于简单的整数和线性规划工具。它的主要应用是整数规划，但这项工作也提供了一个机会来研究单纯形法作为求解任何线性规划的方法。本研究利用了LOPT，这是一种由作者开发的单纯形法的现有C实现。本研究的主要内容如下：开发有效的数据结构和再优化方法，以处理与序列相关但动态变化的线性规划问题。​研究处理组合应用中出现的大规模退化的方法。o进一步改进LOPT实现的基本元素，包括开发稀疏分解例程的C实现，分解更新例程，这些例程的变体利用了组合定义问题的特殊结构。这项工作的一部分是与奥格斯堡大学的马丁·格罗舍尔合作进行的。与滑铁卢大学的Francisco Barahona共同开展了一个关于最大切问题多面体方法的联合研究项目。后一项工作不是当前提案的正式组成部分，但却是一项重要的并行工作。与Grotschel的合作以及与Barahona的合作都将为本研究提供具体的整数规划实例。

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.