Recently, tremendous advancements have been made in the solution of the set partitioning problem (SPP), which finds application in numerous real-world industrial scheduling problems such as fleet assignment and airline crew scheduling. Two major thrusts in the development of solution procedures for SPP have been variable reduction and the use of, either inherent or enforced, special structures in the element-set incidence matrix on which the problem is defined. This dissertation demonstrates the use of hidden network structures for the solution of SPP. The hidden network structures in the element-set incidence matrix are revealed via preprocessing. The importance of problem preprocessing in the development of efficient computational techniques has been well established. We develop heuristic procedures to extract hidden network submatrices in a (0,1) matrix. The heuristics are based on Fujishige's PQ-graph algorithm (1980), which is one of the most computationally efficient algorithms for testing the graph realizability of a (0,$\pm$1) matrix. The computational implementation of the algorithm is the first of its kind and the computational experience in this dissertation validates the almost linear time computational complexity of graph realizability. Fujishige's algorithm lends itself to modification for the development of heuristic procedures to identify submatrices that transform to pure network. The heuristics we develop are based on rules that use Fujishige's PQ-graph characteristics so that the computational efficiencies afforded by PQ-graphs are retained. By finding an embedded network row submatrix, SPP is transformed to a network with side constraints. Flow conditions on the revealed pure network are then used in a procedure for effecting variable reduction. Variable reduction has been recognized to be essential for efficient solution of SPP. By finding an embedded network column submatrix SPP is transformed to a network with side columns. The resulting formulation is used in finding a feasible solution for SPP quickly. For the purpose of obtaining optimal and suboptimal solutions to SPP we use a reformulation of the problem. By repetitive application of the heuristic to obtain an embedded network column submatrix, SPP is reformulated by transforming the element-set incidence matrix to a concatenation of pure network submatrices. This reformulation is to be used within an enumerative procedure which allows significant variable reduction. The research is summarized as follows: (i) Fujishige's PQ-graph algorithm is implemented by supplementing algorithmic details which have never been published; (ii) Heuristic procedures to extract hidden network submatrices are developed using rules which have been developed to maintain Fujishige's PQ-graph characteristics; (iii) The use of embedded network structures is demonstrated for the solution of SPP via variable reduction procedures and procedures for efficient generation of a feasible solution; (iv) Procedure that use a reformulation to find optimal solutions for set partitioning problems is developed.
| Identifer | oai:union.ndltd.org:UMASS/oai:scholarworks.umass.edu:dissertations-6257 |
| Date | 01 January 1994 |
| Creators | Han, Hyun-Soo |
| Publisher | ScholarWorks@UMass Amherst |
| Source Sets | University of Massachusetts, Amherst |
| Language | English |
| Detected Language | English |
| Type | text |
| Source | Doctoral Dissertations Available from Proquest |
Page generated in 0.0017 seconds