Dissertations / Theses on the topic 'Set partitioning problems'

Thesis (M.S. in Operations Research)--Naval Postgraduate School, March 1990.
Thesis Advisor(s): Wood, R. Kevin. Second Reader: Brown, Gerald Gerard. "March 1990." Description based on signature page as viewed on October 21, 2009. Author(s) subject terms: Set partitioning problem, constraint branch and bound method, enumeration tree. Includes bibliographical references (p. 34-36). Also available online.

Cette thèse traite des problèmes qui peuvent être considérés comme un problème de partitionnement. Ces problèmes peuvent être distingués en deux familles : les problèmes dont le coût dépend de la séquence et ceux dont le coût est indépendant de la séquence. Cette thèse se concentre sur cette dernière famille, et en particulier sur la planification des salles opératoires et le problème de découpe en deux dimensions. Bien que le problème de partitionnement soit largement étudié, la littérature est encore pauvre en heuristiques, par rapport aux algorithmes exacts. Cette thèse développe une heuristique pour résoudre une série de problèmes de partitionnement basée sur un schéma général émanant de la programmation dynamique. Dans ce schéma, on doit résoudre un sous-problème qui consiste à contenir une configuration de coût réduit minium en affectant une ressource à un sous-ensemble activités doit être résolu. Un tel sous problème est résolu différemment pour chaque application. Pour chaque problème, nous décrivons les formulations mathématiques, les réalisations d'algorithmes. La performance des algorithmes proposés est évaluée à l’aide des instances, en comparant les solutions obtenues avec des bornes inférieures ou les solutions approchées connues. Les résultats montrent que les algorithmes développés sont très efficaces, tant en termes de qualité de solution qu’en termes de temps de calcul. En outre, les algorithmes peuvent être facilement implémentés. Ces résultats satisfaisants nous laissent penser que le schéma proposé peut devenir une approche générale pour résoudre une série de problèmes de partitionnement
This thesis considers problems that can be considered as set partitioning. Such problems can be distinguished into two families: problems with sequence-dependent costs and those with sequence-independent costs. This thesis is focused on the latter family, in particular operating room scheduling and two-dimensional bin packing. Although the set partitioning problem is widely studied, the literature is still very limited in heuristics, compared to exact algorithms. This thesis develops heuristic algorithms to solve a series of set partitioning problems based on a general schema stemming from dynamic programming idea. In this schema, a subproblem consisting of constructing a pattern with the least cost by affecting a resource to a subset of activities must be solved. Such a subproblem is solved differently for each application. For each problem, we describe mathematical formulations, implementation of algorithms. The performance of the proposed algorithms is evaluated on benchmark instances found in the literature, by comparing the obtained solutions with lower bounds or known near optimal solutions. The computational results show that the developed algorithms are very efficient both in terms of the quality of the solutions and in terms of computation time. Further-more, the algorithms can be easily implemented. The satisfactory results make us believe that the proposed schema can become a general approach to solve a series of set partitioning problems

CONSELHO NACIONAL DE DESENVOLVIMENTO CIENTÍFICO E TECNOLÓGICO
Este trabalho consiste da aplicação de métodos de planos de corte (euclideano acelerado e cortes disjuntivos) na solução de problemas de programação inteira pura do tipo 0- 1 e suas especializações para o problemas de particionamento, quando combinados com técnicas de penalidades para fixação de variáveis. Desenvolve-se um estudo de técnicas de penalidades, que permitem fixar variáveis a valores inteiros a partir da solução ótima da relaxação linear do problema inteiro. As variáveis fixadas são eliminadas do problema e este é reescrito, tendo suas dimensões originais reduzidas. Sugerem-se melhorias no cálculo destas penalidades, levando-se em conta a estrutura particular do problema de particionamento. Finalmente, propõe-se um novo enfoque para a solução de problemas de particionamento: um algoritmo de planos de corte que utiliza técnicas de penalidades, com a finalidade de acelerar a convergência dos métodos puros de planos de corte e de reduzir os problemas por estes apresentados. Resultados computacionais são apresentados, comparando-se o desempenho (i) do algoritmo euclideano acelerado, (ii) do algoritmo de cortes disjuntivos e (iii) do algoritmo de cortes disjuntivos utilizando-se técnicas de penalidades. Para este último algoritmo, são comparados os resultados obtidos utilizando-se técnicas de penalidades genéricas para problemas inteiros do tipo 0-1 e as melhorias destas penalidades, especificas para problemas de particionamento. Considerando-se o problemas de particionamento e as melhorias propostas no cálculo de penalidades, mostra-se que é, freqüentemente, possível fixar um maior número de variáveis ou até mesmo resolver-se diretamente o problema 0-1 original. Em alguns casos, ao aplicar-se o algoritmo de planos de corte com técnicas de penalidades não só pode- se acelerar a convergência, como também superar os problemas de degenerescência dual e erros por arredondamento apresentados pelos algoritmos puros de plano de corte.
This work consists on the application of cutting plane techniques (accelerated euclidean algorithm and disjunctive cuts) for solving pure 0-1 integer problems and their specializations for the set partitioning problem, when combined to penalty techniques for fixing variables. A study on penalty techniques, which allows the fixation of variables to integer values, is also developed. These penalties are directly derived from the optimal tableau nof the linear relaxation of the integer problem. The variables fixed due to penalties are eliminated and the problem is reformulated, having its initial dimensions reduced. Some improvements on the evaluation of penalties are suggested, taking into account the special structure of the set partitioning problem. Finally, a new approach to the solution of set partitioning problems is proposed: a cutting plane algorithm which uses penalty techniques, in order to accelerate the convergence of pure cutting plane methods and overcome the problems arising from their use. Computational results are shown, allowing to compare the performance of (i) the accelerated euclidean algorithm, (ii) the disjunctive cut algorithm and (iii) the last one combined with penalty techniques. For the latter, the results obained by the use of generic penalties for 0-1 integer programs are compared with those obtained by the use of the improved penalties for ser partitioning problems. Taking into account set partitioninng problems and the improvements proposed for the evaluation of penalties, it is shown that very often it is possible to fix more variables to integer values and even to solve directly the original 0-1 problem. For some cases, by applying the cutting plane algorithm together with penalties, it is possible to accelerate the convergence and overcome dual degeneracy and round-off errors arising from the use of pure cutting plane algorithms.

In this thesis a method for solving the Generalized Assignment Problem (GAP) is described. It is based on a reformulation of the original problem into a Set Partitioning Problem (SPP), in which the columns represent partial solutions to the original problem. For solving this problem, column generation, with systematic overgeneration of columns, is used. Conditions that guarantee that an optimal solution to a restricted SPP is optimal also in the original problem are given. In order to satisfy these conditions, not only columns with the most negative Lagrangian reduced costs need to be generated, but also others; this observation leads to the use of overgeneration of columns.

The Generalized Assignment Problem has shown to be NP-hard and therefore efficient algorithms are needed, especially for large problems. The application of the proposed method decomposes GAP into several knapsack problems via Lagrangian relaxation, and enumerates solutions to each of these problems. The solutions obtained from the knapsack problems form a Set Partitioning Problem, which consists of combining one solution from each knapsack problem to obtain a solution to the original problem. The algorithm has been tested on problems with 10 agents and 60 jobs. This leads to 10 knapsack problems, each with 60 variables.

Crew pairing and vehicle routing are combinatorial optimization problems that have been studied for many years by researchers worldwide. The aim of this research work is to investigate effective methods for solving large scale crew pairing problems and vehicle routing problems. In the airline industry, to address the complex nature of crew pairing problems, we propose a duty tree method followed by a primal-dual subproblem simplex method. The duty tree approach captures the constraints that apply to crew pairings and generate candidate pairings taking advantage of various proposed strategies. A huge number of legal pairings are stored in the duty tree and can be enumerated. A set partitioning formulation is then constructed, and the problem is solved using a primal-dual subproblem simplex method tailored to the duty tree approach. Computational experiments are conducted to show the effectiveness of the methods. We also present our efforts addressing the capacitated vehicle routing problem (CVRP) that is the basic version of many other variants of the problem. We do not attempt to solve the CVRP instances that have been solved to optimality. Instead, we focus on investigating good solutions for large CVRP instances, with particular emphasis on those benchmark problems from the public online library that have not yet been solved to optimality by other researchers and determine whether we can find new best-known solutions. In this research, we propose a route network that can store a huge number of routes with all routes being legal, a set partitioning formulation that can handle many columns, and the primal-dual subproblem simplex method to find a solution. The computational results show that our proposed methods can achieve better solutions than the existing best-known solutions for some difficult instances. Upon convergence of the primal-dual subproblem simplex method on the giant-tour based networks, we use the near optimal primal and dual solution as well as solve the elementary shortest path problem with resource constraints to achieve the linear programming relaxation global optimal solution.

Integer programming can be used to provide solutionsto complex decision and planning problems occurring in a wide varietyof situations. Applying integer programming to a real life problembasically involves a first phase where a mathematical model isconstructed, and a second phase where the problem described by themodel is solved. While the nature of the challenges involved in therespective two phases differ, the strong relationship between theproperties of models, and which methods that are appropriate for theirsolution, links the two phases. This thesis constitutes of threepapers, of which the third one considers the modeling phase, while thefirst and second one consider the solution phase.

 

Many applications of column generation yield master problems of setpartitioning type, and the first and second papers presentmethodologies for solving such problems. The characteristics of themethodologies presented are that all successively found solutions arefeasible and integral, where the retention of integrality is a majordistinction from other column generation methods presented in theliterature.

 

The third paper concerns nurse scheduling and describes the results ofa pilot implementation of a scheduling tool at a Swedish nursing ward.This paper focuses on the practical aspects of modeling and thechallenges of providing a solution to a complex real life problem.

We propose a novel branch-and-price (B&P) approach to solve the maximum weighted independent set problem (MWISP). Our approach uses clones of vertices to create edge-disjoint partitions from vertex-disjoint partitions. We solve the MWISP on sub-problems based on these edge-disjoint partitions using a B&P framework, which coordinates sub-problem solutions by involving an equivalence relationship between a vertex and each of its clones. We present test results for standard instances and randomly generated graphs for comparison. We show analytically and computationally that our approach gives tight bounds and it solves both dense and sparse graphs quite quickly.

Orientador: Cid Carvalho de Souza
Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação
Made available in DSpace on 2018-08-19T04:31:47Z (GMT). No. of bitstreams: 1 Braga_AndreideAlmeidaSampaio_M.pdf: 1060769 bytes, checksum: 789d9000e49ebe5d5a54a275c6018cb6 (MD5) Previous issue date: 2011
Resumo: O problema de particionamento de conjuntos (SPP, do inglês set partitioning problem) é considerado um dos problemas de otimização combinatória com mais vasta gama de aplicações. Para solucioná-lo, utilizam-se comumente métodos tradicionais para a resolução de problemas NP - Difíceis. Nesta dissertação, estuda-se o uso da combinação de relaxação Lagrangiana com planos de corte. Relaxação Lagrangiana é uma técnica que tem sido usada com bastante sucesso para atacar vários problemas NP-Difíceis. Os algoritmos relax-and-cut, em especial, onde se adicionam dinamicamente planos de corte a relaxações Lagrangianas, têm ganhado bastante destaque nas últimas décadas. Em [15], Cavalcante et al. aplicam um algoritmo relax-and-cut ao SPP e obtém ótimos resultados. No entanto, tal algoritmo, bem como implementações em geral da citada combinação, são ainda passíveis de refinamentos e extensões. O estudo proposto aqui é realizado por meio das seguintes extensões do referido algoritmo: a implementação de uma partida quente para o multiplicador de uma inequação adicionada; a incorporação do algoritmo a uma enumeração, gerando, assim, um branch-and-cut baseado em relaxação Lagrangiana para o SPP; a implementação do citado branch-and-cut com o emprego de relaxações alternativas e a implementação de uma versão distribuída do algoritmo
Abstract: The set partitioning problem (SPP) is considered one of the combinatorial optimization problems with the widest range of applications. To solve the SPP, one commonly uses traditional methods for NP-Hard problem solving. In this dissertation, we study the use of the combination of Lagrangean relaxation with cutting planes. Lagrangean relaxation is a technique that has been used quite successfully to tackle several NP-Hard problems. In particular, relax-and-cut algorithms, in which cutting planes are added dynamically to Lagrangean relaxations, have gained much importance in the last decades. In [15], Cavalcante et al. applied a relax-and-cut algorithm to the SPP and obtained promising results. However, that algorithm, as well as implementations of the mentioned combination in general, are still subject to refinements and extensions. The study proposed here is carried out through the following extensions of that algorithm: the implementation of a warm start to the multiplier of an added inequality; the incorporation of the algorithm to an enumeration, thus generating a Lagrangean relaxation based branch-and-cut for the SPP; the implementation of that branch-and-cut with the use of alternative relaxations and the implementation of a distributed version of the algorithm
Mestrado
Ciência da Computação
Mestre em Ciência da Computação

Orientador: Prof. Dr. Daniel Morgato Martin
Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Ciências da Computação, 2014.
Neste trabalho estudamos o Problema do Isomorfismo de Grafos e a sua complexidade para resolvê-lo. Nossa principal contribuição é a proposta de um algoritmo para o caso geral do Problema, baseado no particionamento do conjunto de vértices e em emparelhamentos perfeitos de grafos bipartidos. Estudamos também o algoritmo de Brendan McKay, que é o mais rápido algoritmo para o Problema do Isomorfismo de Grafos conhecido. Ao final, implementamos o algoritmo proposto nesta dissertação e o algoritmo de McKay. Após a comparação dos dois algoritmos, verificamos que os resultados obtidos pelo algoritmo proposto não foram satisfatórios, porém apresentamos possíveis melhorias de como deixá-lo mais eficiente.
In this work we study the Graph Isomorphism Problem and their complexity to solve it. Our main contribution is to propose an algorithm for the general case of the Problem, based on partitioning the set vertex and perfect matchings of bipartite graphs. We also studied the Brendan McKay¿s algorithm, who is the fastest algorithm for the Graph Isomorphism Problem known. At the end, we implemented the algorithm proposed in this dissertation and McKay¿s algorithm. After comparison of the two algorithms, we found that the results obtained by the proposed algorithm were not satisfactory, but improvements are possible as to make it more efficient.

Le concept d'auto-stabilisation a été introduit par Dijkstra en 1973. Un système distribué est auto-stabilisant s'il peut démarrer de n'importe quelle configuration initiale et retrouver une configuration légitime en un temps fini par lui-même et sans aucune intervention extérieure. La convergence est également garantie lorsque le système est affecté par des fautes transitoires, ce qui en fait une approche élégante, non masquante, pour la tolérance aux pannes. L'auto-stabilisation a été étudiée dans divers domaines des systèmes distribués tels que les problèmes de synchronisation de l'horloge, de la communication et les protocoles de routage. Vu l'importance des paramètres de graphes notamment pour l'organisation et l'optimisation des communications dans les réseaux et les systèmes distribués, plusieurs algorithmes auto-stabilisants pour des paramètres de graphe ont été proposés dans la littérature, tels que les algorithmes autostabilisants permettant de trouver les ensembles dominants minimaux, coloration des graphes, couplage maximal et arbres de recouvrement. Dans cette perspective, nous proposons, dans cette thèse, des algorithmes distribués et autostabilisants pour certains problèmes de graphes bien connus, en particulier pour les décompositions de graphes et les ensembles dominants qui n'ont pas encore été abordés avec le concept de l'autostabilisation. Les quatre problèmes majeurs considérés dans cette thèse sont: partitionnement en triangles, décomposition en p-étoiles, Monitoring des arêtes, fort ensemble dominant et indépendant. Ainsi, le point commun entre ces problèmes, est qu'ils sont tous considérés comme des variantes des problèmes de domination et de couplage dans les graphes et leur traitement se fait d'une manière auto-stabilisante
The concept of self-stabilization was first introduced by Dijkstra in 1973. A distributed system is self-stabilizing if it can start from any possible configuration and converges to a desired configuration in finite time by itself without using any external intervention. Convergence is also guaranteed when the system is affected by transient faults. This makes self-stabilization an effective approach for non-masking fault-tolerance. The self-stabilization was studied in various fields in distributed systems such as the problems of clock synchronization, communication and routing protocols. Given the importance of graph parameters, especially for organization and communication of networks and distributed systems, several self-stabilizing algorithms for classic graph parameters have been developed in this direction, such as self-stabilizing algorithms for finding minimal dominating sets, coloring, maximal matching, spanning tree and so on. Thence, we propose in this thesis, distributed and self-stabilizing algorithms to some wellknown graphs problems, particularly for graph decompositions and dominating sets problems that have not yet been addressed in a view of self-stabilization. The four major problems considered in this thesis are: the partitioning into triangles, p-star decomposition, edge monitoring set and independent strong dominating set problems. The common point between these four problems is that they are considered as variants of dominating set and matching problems and all propositions deal with the self-stabilization paradigm

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.

碩士
國立臺灣大學
資訊工程學系
86
Because there are many important applications on Set Partitioning Problems (SPP), a number of algorithms have been developed for solving this problem. In this thesis, we discuss how to solve set partitioning problems by genetic algorithm (GA). For solving SPP, we construct two Local Search Heuristic Operators . With these operators, we can get optimal solution in shorter time than the original heuristic operator. One heuristic operator is called Less Coverage First (LCF) heuristic, the other is called LCF Branch-and-Bound (LCFBB). Both of these heuristic has it's own advantage to solve SPP. The advantage of LCF is increasing the probability to find a optimal solution. And the advantage of LCFBB is increasing the feasible solution rate, so that we have more probability to meet the optimal one.

博士
國立中央大學
資訊管理研究所
96
Set partitioning problems’ (SPPs) plural nature makes them essentially individual problem specific, with various informative information and specific hard constraints in each occasion, and therefore SPPs do not have any general framework to serve as an integrated problem solver. This dissertation proposes a GA-based general framework for solving various classes of SPPs efficiently. The framework is based on new relation-based genetic algorithms named relational genetic algorithms (RGAs) which are generalized from the state-of-the-art grouping genetic algorithm (GGA). This framework also naturally integrates a set of constraint handling schemes into RGAs to handle various classes of hard constraints for SPPs. In our RGAs, a phenotypic set-based abstract representation and a genotypic relation-based representation named relational encoding are adopted, and sets of corresponding genetic operators are redesigned. In genotypic RGA, the relational encoding is represented by the equivalence relation matrix which has a 1-1 and onto correspondence with the collection of all possible partitions. It eliminates the redundancy and infeasibility of previous GA representations, and improves the performance of genetic search. The generalized problem-independent operators that we redesigned manipulate the genes without requiring problem-specific heuristics during the process of evolution. In addition, our RGAs allow the number of subsets to vary, instead of fixing it at a predetermined number. We perform experiments for solving four representative classic SPPs with various classes of hard constraints by RGAs with one-point, two-point and grouping crossovers, respectively. Experiment results show that our proposed general framework works well for solving all tested SPPs and successfully handles all classes of hard constraints that we have identified. We also demonstrate an extended application for developing optimized partitioned portfolio insurance strategies and how to solve the induced portfolio partitioning problem by RGAs.

碩士
國立臺灣大學
資訊工程研究所
82
Set partitioning problems appear in a wide range of applications such as resource allocation ,political distinct and scheduling. Genetic algorithm is a general purpose optimization algorithm. Normally, they are directly applicable only to uncosntrained problems. Local serach heuristic is important to solve set partitioning problem. Without it , there may be a low probability to find a feasible solution of set partitioning problem. Local saerch hueristic itself can use only to solve Set Partitioning problem. The empirical results show our local search heuristic in a faster and more effective way to find a feasible solution. The consuming time is fewer, and the minimun cost of the Set Partitioning Problem is lower.

本文分為個部分：多技能員工調問題，和集合覆蓋、裝運和劃分混合問題多面體研究，其中第一部分問題啟發我們第二部分的探。
首先，我們研究在一個大型機場的國際客運站中客戶服務人員的調問題。員工有同的技能和技能水平。技能定義是二維的，包括操作技能和語言能。在學模型中，我們也考慮用餐和休息時間的調和多處工作地點。我們證明該問題是NP-hard 的。我們推導出有效等式，以方計算過程。我們的學模型能夠幫助規劃者做出決策，及可計算同型的活性對業務的影響。我們的模型也可以幫助決策者計劃長遠工作調和培訓。
多技能人員調問題啟發我們這篇文的第二部分：集合覆蓋、裝運和劃分混合問題多面體研究。我們首先證明如覆蓋（或裝運）的等式被删去，該多面體是相當於一個放寬的裝運（或覆蓋）多面體的投影。然後我們考慮混合奇穴多面體（即是一個由覆蓋和裝運等式組成的多面體），並採用圖方法研究，通過考慮同型的等式的互動，推導出混合奇穴等式和完全描繪多面體的特徵。我們再推導出集合覆蓋和裝運混合問題的混合奇穴等式。計算結果顯示，混合奇穴等式有助於減少計算時間。我們還提供子明如何用等式幫助決策。
This thesis is divided into two parts: Multi-Skilled Staff-Scheduling Problem and a polyhedral study on the Mixed Set Covering, Packing and Partitioning Problem, where the first part is a motivating example of the latter.
In the multi-skilled staff-scheduling problem, we study the problem of scheduling customer service agents at an international terminal of a large airport. The staff members are heterogeneous with different skills and skill levels. The skill specification is two-dimensional, defined by operational skills and language proficiency. In the mathematical model, we also consider the scheduling of meal and rest breaks, and multiple locations. The problem is shown to be NP-hard. We derive valid inequalities to speed up the computational procedure. With our mathematical model, we are able to help schedule planners make decisions and examine the impacts of different types of flexibility on the level of service provided. Our model can also help decision makers with long-term work-schedule planning.
Motivated by the staff-scheduling problem, the second part of this thesis studies the polyhedral structure of the mixed set covering, packing and partitioning problem, i.e., a problem that contains set covering, set packing and set partitioning constraints. We first study the mixed odd hole polytope, which is the polytope associated with a mixed odd hole consisting of covering and packing "edges". Adopting a graphical approach and considering the "interactions" between the different types of inequalities, we derive the mixed odd hole inequality, thereby completely characterizing the mixed odd hole polytope. We then generalize the mixed odd hole inequality for the general mixed covering and packing polytope. Computational results show that the mixed odd hole inequalities are helpful in reducing solution time. We also provide examples of problem settings in which the inequalities can be used to help decision making.
Detailed summary in vernacular field only.
Detailed summary in vernacular field only.
Detailed summary in vernacular field only.
Kuo, Yong Hong.
Thesis (Ph.D.)--Chinese University of Hong Kong, 2013.
Includes bibliographical references (leaves 119-129).
Abstracts also in Chinese.
Abstract --- p.i
Acknowledgement --- p.iii
Chapter I --- Scheduling of Multi-skilled Staff Across Multiple Locations --- p.1
Chapter 1 --- Introduction --- p.2
Chapter 2 --- Literature Review --- p.8
Chapter 3 --- Mathematical Model --- p.14
Chapter 3.1 --- Problem Formulation --- p.14
Chapter 3.2 --- Valid Inequalities --- p.20
Chapter 3.3 --- Shift Scheduling and Longer-Term Work-Schedule Planning --- p.21
Chapter 4 --- Computational Studies --- p.24
Chapter 4.1 --- Dataset and Input Parameters --- p.24
Chapter 4.1.1 --- Staffing Requirements and Shortage Penalties --- p.24
Chapter 4.2 --- Computational Study: Managerial Insights --- p.26
Chapter 4.2.1 --- Effect of Three Types of Flexibility --- p.26
Chapter 4.2.2 --- Impact of Different Types of Flexibility --- p.28
Chapter 4.3 --- Computational Study: Benefits Compared with Benchmarks --- p.33
Chapter 4.3.1 --- Heuristic H1: CSA Assignment by Time Period --- p.35
Chapter 4.3.2 --- Heuristic H2: CSA Assignment by Criticality --- p.35
Chapter 4.3.3 --- Comparison with Benchmarks --- p.37
Chapter 4.4 --- Computational Study: Computational Efficiency --- p.40
Chapter 5 --- Conclusions --- p.44
Chapter II --- On the Polyhedral Structure of the Mixed Set Covering, Packing and Partitioning Polytope --- p.47
Chapter 6 --- Introduction --- p.48
Chapter 7 --- Preliminaries --- p.51
Chapter 8 --- Overview of Packing, Covering and Partitioning Polyhedra --- p.58
Chapter 8.1 --- Set Packing Polytope --- p.58
Chapter 8.1.1 --- Intersection Graph --- p.59
Chapter 8.1.2 --- Lifting Procedures --- p.63
Chapter 8.1.3 --- Facet-Producing Subgraphs --- p.66
Chapter 8.2 --- Set Covering Polytope --- p.71
Chapter 8.2.1 --- Polyhedral Structure and the Associated Graphs --- p.71
Chapter 8.3 --- Set Partitioning Polytope --- p.76
Chapter 8.4 --- Blocking and Anti-Blocking Pairs --- p.78
Chapter 8.4.1 --- Blocking polyhedra --- p.78
Chapter 8.4.2 --- Anti-blocking polyhedra --- p.80
Chapter 8.5 --- Perfect, Ideal and Balanced Matrices --- p.81
Chapter 8.5.1 --- Perfect Matrices --- p.81
Chapter 8.5.2 --- Ideal Matrices --- p.83
Chapter 8.5.3 --- Balanced Matrices --- p.84
Chapter 9 --- Mixed Set Covering, Packing and Partitioning Polytope --- p.87
Chapter 9.1 --- Mixed Set Partitioning and Covering/Packing Polytope --- p.87
Chapter 9.2 --- Mixed Set Covering and Packing Polytope --- p.88
Chapter 9.2.1 --- Mixed odd hole --- p.90
Chapter 9.2.2 --- General Mixed Covering and Packing Polytope --- p.97
Chapter 9.3 --- Computational Experiments --- p.108
Chapter 9.4 --- Applications of the Mixed Odd Hole Inequality --- p.112
Chapter 9.4.1 --- Railway Time-Tabling --- p.112
Chapter 9.4.2 --- Team Formation --- p.113
Chapter 9.4.3 --- Course Registration --- p.114
Chapter 10 --- Conclusions --- p.117
Bibliography --- p.119

Le problème d'allocation de postes d'amarrage (PAPA) est l'un des principaux problèmes de décision aux terminaux portuaires qui a été largement étudié. Dans des recherches antérieures, le PAPA a été reformulé comme étant un problème de partitionnement généralisé (PPG) et résolu en utilisant un solveur standard. Les affectations (colonnes) ont été générées a priori de manière statique et fournies comme entrée au modèle %d'optimisation. Cette méthode est capable de fournir une solution optimale au problème pour des instances de tailles moyennes. Cependant, son inconvénient principal est l'explosion du nombre d'affectations avec l'augmentation de la taille du problème, qui fait en sorte que le solveur d'optimisation se trouve à court de mémoire. Dans ce mémoire, nous nous intéressons aux limites de la reformulation PPG. Nous présentons un cadre de génération de colonnes où les affectations sont générées de manière dynamique pour résoudre les grandes instances du PAPA. Nous proposons un algorithme de génération de colonnes qui peut être facilement adapté pour résoudre toutes les variantes du PAPA en se basant sur différents attributs spatiaux et temporels. Nous avons testé notre méthode sur un modèle d'allocation dans lequel les postes d'amarrage sont considérés discrets, l'arrivée des navires est dynamique et finalement les temps de manutention dépendent des postes d'amarrage où les bateaux vont être amarrés. Les résultats expérimentaux des tests sur un ensemble d'instances artificielles indiquent que la méthode proposée permet de fournir une solution optimale ou proche de l'optimalité même pour des problème de très grandes tailles en seulement quelques minutes.
The berth allocation problem (BAP) is one of the key decision problems at port terminals and it has been widely studied. In previous research, the BAP has been formulated as a generalized set partitioning problem (GSPP) and solved using standard solver. The assignments (columns) were generated a priori in a static manner and provided as an input to the optimization model. The GSPP approach is able to solve to optimality relatively large size problems. However, a main drawback of this approach is the explosion in the number of feasible assignments of vessels with increase in problem size which leads in turn to the optimization solver to run out of memory. In this research, we address the limitation of the GSPP approach and present a column generation framework where assignments are generated dynamically to solve large problem instances of the berth allocation problem at port terminals. We propose a column generation based algorithm to address the problem that can be easily adapted to solve any variant of the BAP based on different spatial and temporal attributes. We test and validate the proposed approach on a discrete berth allocation model with dynamic vessel arrivals and berth dependent handling times. Computational experiments on a set of artificial instances indicate that the proposed methodology can solve even very large problem sizes to optimality or near optimality in computational time of only a few minutes.