Accession Number:

ADA455431

Title:

A Test Set of Real-World Mixed Integer Programming Problems

Descriptive Note:

Technical rept.

Corporate Author:

RICE UNIV HOUSTON TX

Personal Author(s):

• Bixby, Robert E.
• Boyd, E. A.
• Indovina, Ronni R.

Report Date:

1992-01-01

Pagination or Media Count:

10.0

Abstract:

Integer programming problems, both pure and mixed, have traditionally been considered very difficult. Indeed, there are currently no guaranteed polynomial-time algorithms available for general integer programming. Within the last ten years, however, major advances in preprocessing methods and cutting plane techniques have provided more insight into what makes these problems so difficult. These breakthroughs have sparked much interest and have led to new research in the field of integer programming. Integer programs are problems that consist of maximizing or minimizing a linear function on a linearly defined constraint set with some or all of the variables restricted to take on integer values. If only some of the variables have this restriction, the problem is a mixed integer program. These problems have applications in many diverse areas. Among these applications are fiber optic network design, modeling the acquisition, manufacturing and distribution of natural gas, machine and job scheduling, vehicle routing, drainage system design, generator scheduling, airline crew and flight scheduling, modeling automobile acquisition and selling. This wide applicability of integer programming presents a real need for efficient methods for solving both pure and mixed integer programming problems. One hindrance to research in this area has been a lack of general availability of real models.

Descriptors:

• *INTEGER PROGRAMMING
• *SCHEDULING
• *ROUTING
• ALGORITHMS
• FIBER OPTICS
• TEST SETS
• PREPROCESSING
• PROBLEM SOLVING
• MARKETING
• PROBABILITY DISTRIBUTION FUNCTIONS

Subject Categories:

• Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE