Hybrid Algorithms for On-Line Search and Combinatorial Optimization Problems
Abstract
By now Artificial Intelligence (AI), Theoretical Computer Science (CS theory) and Operations Research (OR) have investigated a variety of search and optimization problems. However, methods from these scientific areas use different problem descriptions, models, and tools. They also address problems with particular efficiency requirements. For example, approaches from CS theory are mainly concerned with the worst-case scenarios and are not focused on empirical performance. A few efforts have tried to apply methods across areas. Usually a significant amount of work is required to make different approaches "talk the same language," be successfully implemented, and, finally, solve the actual same problem with an overall acceptable efficiency. This thesis presents a systematic approach that attempts to advance the state of the art in the transfer of knowledge across the above mentioned areas. In this work we investigate a number of problems that belong to or are close to the intersection of areas of interest of AI, OR and CS theory. We illustrate the advantages of considering knowledge available in different scientific areas and of applying algorithms across distinct disciplines through successful applications of novel hybrid algorithms that utilize benefitial features of known efficient approaches. Testbeds for such applications in this thesis work include both open theoretical problems and ones of significant practical importance. We introduce a representation change that enables us to question the relation between the Pigeonhole Principle and Linear Programming Relaxation. We show that both methods have exactly the same bounding power. Furthermore, even stronger relation appears to be between the two methods: The Pigeonhole Principle is the Dual of Linear Programming Relaxation. Such a relation explains the "hidden magic" of the Pigeonhole Principle, namely its power in establishing upper bounds and its effectiveness in constructing optimal solutions.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 28, 1997
- Accession Number
- ADA352356
Entities
People
- Yury V. Smirnov
Organizations
- Carnegie Mellon University