No description available.

No description available.

Many fundamental combinatorial optimization problems involve the search for subsets of graph elements which satisfy some notion of independence. This thesis develops techniques for optimizing over a class of independence systems and focuses on systems having the vertex set of a finite graph as a ground set. The search for maximum stable sets in a graph offers a well-studied example of such a problem. More generally, for any integer k ≥ 1, the maximum co-k-plex problem fits into this framework as well. Co-k-plexes are defined as a relaxation of stable sets. This thesis studies co-k-plexes from polyhedral, algorithmic, and enumerative perspectives. The polyhedral analysis explores the relationship between the stable set polytope and co-k-plex polyhedra. Results include generalizations of odd holes, webs, wheels, and the claw. Sufficient conditions for the integrality of some related linear systems and results on the composition of stable set polyhedra are also given. The algorithmic analysis involves the development of heuristic and exact algorithms for finding maximum k-plexes. This problem is closely related to the search for co-k-plexes. The final chapter includes results on the enumerative structure of co-k-plexes in certain graphs.

General integer programming is an important mathematical approach for many decision-making problems. In this field, a major theoretical breakthrough came in 1983 when H. W. Lenstra, Jr. proposed a polynomial-time algorithm for general integer programs while the number of variables is fixed. Two key ingredients of Lenstra's algorithm are ellipsoidal approximation of polytopes and lattice basis reduction. However, the lack of practically efficient algorithms and software for the ellipsoidal approximation of polytopes has made it difficult to study the computational properties of Lenstra's algorithm. To bridge the gap between theory and computational practice for Lenstra's algorithm, we study both the ellipsoidal approximation to polytopes and computational properties of Lenstra's algorithm in this thesis. We have developed a reliable and efficient algorithm for computing the maximum volume ellipsoid inscribing a given polytope. This algorithm effectively exploits the problem-specific structures and utilizes a primal-dual type, interior point method. We show that this algorithm has a sound theoretical foundation, and demonstrate that it performs considerably better than a number of other algorithms through extensive numerical experiments. Using our ellipsoidal approximation algorithm as a subroutine, we have implemented a version of Lenstra's algorithm for general integer programming feasibility problems. At each node, the method uses ellipsoidal approximation and lattice basis reduction to find a "thin" direction of the polytope, and branches on hyperplanes, rather than on variables as in the traditional branch-and-bound method. In this procedure, it is guaranteed that the number of branches at each node is bounded and small. Our numerical results on small- to medium-sized test instances suggest that Lenstra's algorithm examine much fewer nodes than the traditional branch-and-bound method. However, there is a tradeoff between many nodes and fast reoptimization as in the traditional branch-and-bound method and fewer nodes but more time-consuming decisions on branching as in Lenstra's algorithm. Currently, the main bottle-neck in the performance of the algorithm lies at the step of lattice basis reduction. If this step is sufficiently improved, then Lenstra's algorithm, when combined with other techniques such as cutting planes, promises to be efficient for certain classes of difficult problems.

The notions of pathwidth and the closely related treewidth have become more and more important recently. The importance lies not only in theory but also in practice. Theoretically, lots of NP-hard problems become polynomially solvable when restricted in graphs with bounded pathwidth (or treewidth). Practically, pathwidth and treewidth have significant applications in many different fields such as searching games, VLSI design, matrix computation, etc. Computing pathwidth is an NP-complete problem for general graphs, but polynomially solvable for treewidth-bounded graphs. However, there is no known practical algorithm to compute pathwidth for treewidth-bounded graphs. In this dissertation, a new algorithm for computing pathwidth and finding an optimal pathwidth-decomposition for treewidth-bounded graph is presented. This algorithm uses an interval completion technique and the branch-and-bound method to make the pathwidth computation process more efficient, practical, and easy to implement. It can also be easily converted to a parallel algorithm. The data structure for implementing this algorithm is presented, and some computational results are shown. Some heuristic methods to approximate pathwidth for general graphs are also given, especially for series-parallel graphs.

No description available.

No description available.

No description available.

No description available.

In cascaded inference tasks there is not a direct logical connection between an observable event (datum) and the hypothesis of interest. Instead there is interposed at least one logical reasoning stage, consisting of intervening variables or intermediate event states. This paper is concerned with the modification or extension of Bayes' rule to render it more specific as a normative model for cascaded inference. In particular, the work reported here is directed towards simplifying the task of the researcher who wishes to use Bayes' rule as a standard for inferential behavior and of the analyst who wishes to use task decomposition in aiding inference. This is achieved by the development of some general principles of inference, the use of concepts from graph theory for the representation of inference tasks, and the application of computer technology.