Research Planning Grant: Developing Test Problems for the General Integer Programming Problem

研究计划资助：为一般整数规划问题开发测试问题

• 批准号: 9622104
• 负责人: Anito Joseph
• 金额: $ 1.8万
• 依托单位: University of Miami
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1996
• 资助国家: 美国
• 起止时间: 1996-06-01 至 1997-11-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9622104&HistoricalAwards=false
• 关键词: Research; Planning; Grant; Developing; Test

Joseph 9622104 This research planning grant involves developing a new set of problems to be used as a testbed for general integer programming (IP) problems. Although many special case IP have been well studied, the general IP problem remains relatively unexplored. Consequently test problems used in early exploration of general IP problems are still in use today and are insignificant in size when measured against modern computing power. A novel technique for developing a modern testbed of general IP problems will be utilized which differs from conventional methods in several ways: first, an optimal solution is determined by solving a knapsack problem over a given solution area; second, constraints are constructed to maintain feasibility of this optimal solution and implicitly enforce specified bounds. This approach provides a convenient mechanism by which the problem structure around a known solution can be changed, thereby expanding opportunities for study of the general IP problem and its characteristics. This technique places no limit on problem size and should be able to generate problems of reasonable size. The research planning grant activities include an in-depth study of a methodology for generation of test problems with known optimal solutions. The results of this activity will lay the foundation for a joint effort undertaking a full project including the design of procedures for problem generation, software development and validation, statistical studies and analyses. Development of a modern set of test problems for the general IP problem will fill an important gap and accelerate progress in IP research. IP problems abound in manufacturing areas such as sequencing, scheduling, planning, facility layout and design.

Joseph 9622104 这项研究计划资助涉及开发一组新问题，用作一般整数规划 (IP) 问题的测试平台。 尽管许多特殊情况的知识产权已经得到了很好的研究，但一般的知识产权问题仍然相对未被探索。 因此，早期探索一般 IP 问题时使用的测试问题至今仍在使用，并且与现代计算能力相比，其规模微不足道。 将利用一种新技术来开发一般知识产权问题的现代测试平台，该技术在几个方面与传统方法不同：首先，通过在给定解决方案区域上解决背包问题来确定最佳解决方案；其次，构造约束以维持该最优解决方案的可行性并隐式强制执行指定的边界。 这种方法提供了一种方便的机制，通过该机制可以改变已知解决方案周围的问题结构，从而扩大了研究一般知识产权问题及其特征的机会。 该技术对问题大小没有限制，并且应该能够生成合理大小的问题。 研究计划资助活动包括对使用已知最佳解决方案生成测试问题的方法进行深入研究。 这项活动的结果将为共同努力开展一个完整的项目奠定基础，包括问题生成程序的设计、软件开发和验证、统计研究和分析。 开发一套针对一般知识产权问题的现代测试问题将填补知识产权研究的重要空白并加速进展。 知识产权问题在排序、调度、规划、设施布局和设计等制造领域比比皆是。