Linear Programming Tools for Integer Programming

这项研究是针对单纯形为基础的工具，整数和 线性规划 主要应用是整数规划， 但这项工作也提供了一个机会，研究单纯形法 作为求解任何线性规划的方法。 本研究利用LOPT，一个现有的C实现的 提议者开发的单纯形法。 的主要方面 研究如下： O 开发有效的数据结构和重新优化方法 为 处理与序列相关但动态变化的线性 编程问题。 O 研究处理大尺度简并的方法， 出现 在组合应用中。 O 进一步改进LOPT的基本要素 实现， 包括开发稀疏分解的C实现 例行程序， 因子分解更新例程以及这些例程的变体 的 利用组合定义的特殊结构 问题 这项工作正在进行，部分是与马丁合作进行的。 奥格斯堡大学的格罗切尔。 联合研究项目， 最大割问题的多面体方法也在一起进行 和滑铁卢大学的弗朗西斯科·巴拉奥纳一起。 后一 工作不是目前提案的正式组成部分，但却是一项重要的 平行的努力 无论是与格罗切尔的合作， 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.