This research is to develop new methods, both theoretical and computational, for efficiently solving discrete-optimization problems. Though arising frequently in practice, such problems are extremely challenging due to their combinatorial nature; the solution space grows exponentially in terms of the number of decision variables. Effective procedures require cutting-edge theory coupled with high-speed computing. The approach used in this effort is to recast difficult problems into higher-variable spaces so as to partially avoid being encumbered by the exponential growth. A "reformulation-linearization-technique" (RLT) for programs wherein the discrete variables take binary "yes-no" values was earlier designed with this objective in mind. Computational successes have been realized for various classes of problems, and the idea of lifting lower-dimensional spaces into higher-dimensional counterparts has since drawn considerable attention. This research will blend contributions from the fields of Algebra and Operations Research to extend and enhance the entire RLT process in a novel manner. Preliminary studies show that the RLT generalizes to mixed-discrete problems, and that the arguments can be made more simple and elegant when viewed as special products of highly-structured matrices. This perspective provides valuable insights into reformulation methods, and opens up exciting new avenues for research. These avenues will be explored in depth.
The research is expected to contribute to the solving of complex problems for which optimal solutions cannot currently be obtained and/or verified. Discrete problems are evident in many contexts, including electric power distribution, facility layout, resource allocation, and scheduling. The study should also contribute to the general understanding of the mathematical structure of special decision programs, and lead to improved methods for combinatorial problems in general.
