Semester
Fall
Date of Graduation
2005
Document Type
Thesis
Degree Type
MS
College
Statler College of Engineering and Mineral Resources
Department
Lane Department of Computer Science and Electrical Engineering
Committee Chair
K. Subramani.
Abstract
Chain Programming is a restricted form of linear programming in which there exists a total ordering over the program variables. In other words, the constraints x1 ≤ x 2 ≤ ... ≤ xn are either implicitly or explicitly part of the constraint system. At the present juncture, it is not clear whether an arbitrary Chain Program is easier to solve than a linear program, either asymptotically or computationally. This thesis presents a variety of interesting properties pertaining to the case in which a Chain Program is constituted entirely of difference constraints. Deciding the feasibility of a system of difference constraints is a well-studied problem. When a system of difference constraints includes the constraints x 1 ≤ x2 ≤ ... ≤ xn, it is an instance of Chain Programming over Difference Constraints. Existing methods for deciding the feasibility of systems of difference constraints may be used for Chain Programs over Difference Constraints, but the properties of this problem strongly suggest that a more efficient method may exist.
Recommended Citation
Argentieri, John E., "Properties of chain programs over difference constraints" (2005). Graduate Theses, Dissertations, and Problem Reports. 2297.
https://researchrepository.wvu.edu/etd/2297