Automatic structural identification and relaxation for integer programming

摘要

This research investigates the automatic identification of typical embedded structures in the Integer Programming (IP) models and automatic transformation of the problem to an adequate Lagrangian problem which can provide tight bounds within the acceptable run time. For this purpose, the structural distinctivenesses of variables, constants, blocks of terms, and constraint chunks are identified to specify the structure of the IP model. To assist the identification of the structural distinctiveness, the representation by the knowledge based IP model formulator, UNIK-IP, is adopted. To reason for the structural identification, the hybrid of bottom-up, top-down, and case-based approaches are proposed. A system UNIK-RELAX is developed to implement the approaches proposed in this research.