Yury V. Smirnov

Hybrid Algorithms for On-Line Search and Combinatorial Optimization Problems Degree Type: Ph.D. in Algorithms, Combinatorics and Optimization
Advisor(s): Manuela Veloso
Graduated: August 1997

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 beneficial 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.

We also address various groups of problems, that arise in agent-centered search. In particular, we consider goal-directed exploration, in which search by a physical or fictitious agent with limited lookahead occurs in partially or completely unknown domains. The resulting Variable Edge Cost Algorithm (VECA) becomes the first method of solving goal-directed exploration problems that incorporates strong guidance from heuristic knowledge, yet is still capable of providing linear worst-case guarantees, even for complex search domains and misleading heuristics.

This work aims at expanding the handset of AI tools that concern search efficiency and provides the foundation for further development of hybrid methods, cross-fertilization and successful applications across AI, CS theory, OR and other Computational Sciences.

Keywords:
Hybrid algorithms, cross-fertilization, agent-centered search, limited lookahead, pigeonhole principle, linear programming relaxation