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

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

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.