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

点击翻译按钮获取中文摘要

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.