Structural Complexity of Adjacency on 0-1 Convex Polytopes.

Abstract

This thesis is concerned with the problem of determining whether a pair of 0-1 feasible solutions are adjacent on K(,I), the 0-1 convex polytope which is the convex hull of all 0-1 feasible solutions to a 0-1 integer programming problem. Recent results suggest that in general the 0-1 convex polytope tends to have too many facets (their number growing faster than exponentially or even factorially with the dimension), and that the structure of these facets is very complicated. Our study is motivated by the desire to explore the structure of this polytope K(,I) through a characterization of the adjacency relationship of extreme points of K(,I) on K(,I). The first chapter is an introductory chapter. The second chapter, discusses the "NP-complete class", which is the most important class of problems in the computational complexity theory. The original result in chapter 2 is the proof that the Linear Complementarity Problem associated with a general matrix, is NP-complete in the strong sense. Chapter 3 and chapter 4 provides necessary definitions for studying adjacency, some preliminary lemmas, and a literature survey of known results in the area. In chapter 5 we provide a positive result by developing an efficient polynomial time algorithm for checking the adjacency relationship of two integer feasible solutions of the edge covering problem or the general 1-matching/covering problem on their convex hull. However, in chapter 6 we establish that checking the adjacency relationship on the convex hull of integer feasible solutions of several important problems, like the Knapsack problem, the Set covering problem and the 0-1 Integer programming problem, is itself NP-hard (that is; as hard as the original optimization problem itself).