Loading...

Decomposition Approaches to Set Covering and Set Packing Problems through Exploiting Special Structures (Case Sturdy: Crew Pairing Problem)

Radman, Maryam | 2021

541 Viewed
  1. Type of Document: Ph.D. Dissertation
  2. Language: Farsi
  3. Document No: 53679 (01)
  4. University: Sharif University of Technology
  5. Department: Industrial Engineering
  6. Advisor(s): Eshghi, Kourosh
  7. Abstract:
  8. In this thesis, a decomposition approach is developed to solve Set Covering Problems (SCPs) through exploiting special structures of their coefficient matrices. The coefficient matrix of an SCP is so large in practical problems, but due to its low density, most of its entries are zero. Based on this observation, some methods can be developed to aggregate the 1's of the coefficient matrix in order to create special structures involving smaller dense subproblems. In this theisis, four structures called "block-angular", "semi-block angular", "partitioned" and "nested block-angular" structures are proposed and examined. For this purpose, First, some heuristic methods based on constraint partitioning are presented to exploit these structures from the coefficient matrices of SCPs; then through developing some theorems, lower and upper bounds for the optimal solution value and a feasible solution are generated for the original problem through the optimal solutions of the smaller subproblems of these structures. As subproblems involve much fewer variables and constraints than the original problem, the complexity of solving the problem is greatly reduced. The experimental results demonstrate the ability of the developed approach to exploit the proposed structures and achieve optimal solutions on some generated test problems. In addition, the performance of the proposed approach on benchmark instances of OR-Library is examined and shown to be comparable with some of the recently-developed methods to solve SCPs. The explained framework is also developed for the set packing problems, the related theorems are proved and their computational results are reported.As a practical example of the SCP, the Crew Pairing Problem (CPP), which has an overriding importance in the airline industry, is considered in this thesis and a new decomposition technique based on constraint partitioning is developed to solve it. The proposed algorithm is applied to a case study from the literature as well as some randomly-generated test problems. One advantage of the proposed method is finding multiple feasible solutions in lower time than the previous algorithm in the literature which shows the efficiency of the algorithm in real-case situation
  9. Keywords:
  10. Airline Industry ; Decomposition Technique ; Set Cover Problem ; Crew Constraints ; Block-Angular Structure ; Constraint Partitioning ; Crew Pairing Problem ; Parsing Algorithms

 Digital Object List

 Bookmark

No TOC