Linear Programming Tools for Integer Programming

用于整数规划的线性规划工具

• 批准号: 8815914
• 负责人: Robert Bixby
• 金额: --
• 依托单位: William Marsh Rice University
• 依托单位国家: 美国
• 项目类别: Continuing grant
• 财政年份: 1989
• 资助国家: 美国
• 起止时间: 1989-02-15 至 1993-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8815914&HistoricalAwards=false
• 关键词: Linear; Programming; Tools; Integer

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.

这项研究是针对基于单纯形的整数和线性规划工具。主要的应用是整数规划，但这项工作也提供了一个机会来研究单纯形法作为一种方法来解决任何线性规划。这项研究利用了Lopt，这是作者开发的单纯形法的现有C实现。研究的主要方面如下：o开发有效的数据结构和重新优化方法处理与序列相关但动态变化的线性规划问题。O研究处理组合应用中出现的大规模退化的方法。O进一步改进LOPT实现的基本要素，包括开发稀疏因式分解例程的C实现、因式分解更新例程、这些例程的变体利用了组合定义问题的特殊结构。这项工作部分是与奥格斯堡大学的马丁·格罗谢尔合作进行的。与滑铁卢大学的弗朗西斯科·巴拉奥纳一起开展的关于多面体方法解决最大割问题的联合研究项目也在进行中。后一项工作不是当前提案的正式组成部分，但是一项重要的平行工作。无论是与Grotschel的合作，还是与Barahona的合作，都将提供对本研究至关重要的具体整数规划实例。