A Test Set of Real-World Mixed Integer Programming Problems
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1992
- Accession Number
- ADA455431
Entities
People
- E. A. Boyd
- Robert E. Bixby
- Ronni R. Indovina
Organizations
- Rice University