This research presents a systematic and iterative procedure, as well as theoretical study, on expository sermon construction. The basic approach to sermon design involves the treatment of this subject matter as a design problem, utilizing advanced methodology in engineering design. This includes the modeling technique, the flow-chart method, and the optimization theory. In addition, we use heuristics as the search engine for seeking intelligent and efficient optimum design solutions. The heuristics can best be compared to the "artificial intelligence" or the "wisdom bank," involving six sources of wisdom; these include: talents, gifts, creativity, knowledge, experience and spiritual insights. The results represented in this thesis are believed to have demonstrated original findings in the following areas. First, the subject matter is found to be of a design nature, sharing the common characteristics of a general class of the design discipline, namely, having a 3-stage iterative procedure of the ABA' model. Secondly, a mathematical as well as physical model of the sermon design problem is developed in this study, using both homiletic and hermeneutic principles. The human body is used as the physical model, making it possible for simple visualization of the sermon structure and for performance evaluation. A mathematical model is found to be the "Heuristic Combinatorial Optimization Problem" and consists of eight design variables. Although it is not yet possible to develop a computer-aided protocol to seek solutions, an alternative approach called the "Web-Chart Method" can potentially be adaptable to an interactive computer system in the future. It serves as a two-dimensional "design chart" on paper, in which iterative procedures can be performed manually. The advantage is that the designer can direct his or her heuristic search for optimum solutions with the help of a number of design tools, including the "Insight-Recording Sheet" and the "Analogical Analysis Chart." With these tools, the designer has, at his or her disposal, the ability to search for solutions in sermon design, while still maintaining a global view with all the design variables controlled for. In this research, the principles of combinatorial heuristics applicable to the field of optimum design of expository sermons have been described. They are based on heuristic combinatorial optimization methods in the engineering design field with refinements geared to the homiletic as well as hermeneutic nature of the problem. The approaches represented here would allow a designer to utilize resources that are not otherwise available and/or are not easily manageable. With these research results, one would be able to design sermons innovatively and optimally in a systematic and heuristic-guided manner. Further extension of this work would lead to a new field of research and development in the computer-aided design of expository sermons. Key words: preaching; homiletics; expository preaching; design for preaching; sermon construction; computer-aided sermon design; sermon design optimization; heuristic sermon design; heuristic sermon optimization; heuristic combinatorial optimization. / Practical Theology / D. Th.(Practical Theology)

This research presents a systematic and iterative procedure, as well as theoretical study, on expository sermon construction. The basic approach to sermon design involves the treatment of this subject matter as a design problem, utilizing advanced methodology in engineering design. This includes the modeling technique, the flow-chart method, and the optimization theory. In addition, we use heuristics as the search engine for seeking intelligent and efficient optimum design solutions. The heuristics can best be compared to the "artificial intelligence" or the "wisdom bank," involving six sources of wisdom; these include: talents, gifts, creativity, knowledge, experience and spiritual insights. The results represented in this thesis are believed to have demonstrated original findings in the following areas. First, the subject matter is found to be of a design nature, sharing the common characteristics of a general class of the design discipline, namely, having a 3-stage iterative procedure of the ABA' model. Secondly, a mathematical as well as physical model of the sermon design problem is developed in this study, using both homiletic and hermeneutic principles. The human body is used as the physical model, making it possible for simple visualization of the sermon structure and for performance evaluation. A mathematical model is found to be the "Heuristic Combinatorial Optimization Problem" and consists of eight design variables. Although it is not yet possible to develop a computer-aided protocol to seek solutions, an alternative approach called the "Web-Chart Method" can potentially be adaptable to an interactive computer system in the future. It serves as a two-dimensional "design chart" on paper, in which iterative procedures can be performed manually. The advantage is that the designer can direct his or her heuristic search for optimum solutions with the help of a number of design tools, including the "Insight-Recording Sheet" and the "Analogical Analysis Chart." With these tools, the designer has, at his or her disposal, the ability to search for solutions in sermon design, while still maintaining a global view with all the design variables controlled for. In this research, the principles of combinatorial heuristics applicable to the field of optimum design of expository sermons have been described. They are based on heuristic combinatorial optimization methods in the engineering design field with refinements geared to the homiletic as well as hermeneutic nature of the problem. The approaches represented here would allow a designer to utilize resources that are not otherwise available and/or are not easily manageable. With these research results, one would be able to design sermons innovatively and optimally in a systematic and heuristic-guided manner. Further extension of this work would lead to a new field of research and development in the computer-aided design of expository sermons. Key words: preaching; homiletics; expository preaching; design for preaching; sermon construction; computer-aided sermon design; sermon design optimization; heuristic sermon design; heuristic sermon optimization; heuristic combinatorial optimization. / Philosophy, Practical and Systematic Theology / D. Th.(Practical Theology)

Un des buts principaux de la biologie évolutive et de la médecine moléculaire consiste à reconstruire les relations phylogénétiques entre organismes à partir de leurs séquences moléculaires. En littérature, cette question est connue sous le nom d’inférence phylogénétique et a d'importantes applications dans la recherche médicale et pharmaceutique, ainsi que dans l’immunologie, l’épidémiologie, et la dynamique des populations. L’accumulation récente de données de séquences d’ADN dans les bases de données publiques, ainsi que la facilité relative avec laquelle des données nouvelles peuvent être obtenues, rend l’inférence phylogénétique particulièrement difficile (l'inférence phylogénétique est un problème NP-Hard sous tous les critères d’optimalité connus), de telle manière que des nouveaux critères et des algorithmes efficaces doivent être développés. Cette thèse a pour but: (i) d’analyser les limites mathématiques et biologiques des critères utilisés en inférence phylogénétique, (ii) de développer de nouveaux algorithmes efficaces permettant d’analyser de plus grands jeux de données. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Consider the problem of maximizing the revenue generated by tolls set on a subset <p>of arcs of a transportation network, where origin-destination flows (commodities) are assigned to shortest paths with respect to the sum of tolls and initial costs. <p>This thesis is concerned with a particular case of the above problem, in which all toll arcs are connected and constitute a path, as occurs on highways. Further, as toll levels are usually computed using the highway entry and exit points, a complete toll subgraph is considered, where each toll arc corresponds to a toll subpath. Two <p>variants of the problem are studied, with or without specific constraints linking together the tolls on the arcs. <p>The problem is modelled as a linear mixed integer program, and proved to be NP-hard. Next, several classes of valid inequalities are proposed, which strengthen important constraints of the initial model. Their efficiency is first shown theoretically, as these are facet defining for the restricted one and two commodity problems. <p>Also, we prove that some of the valid inequalities proposed, together with several <p>constraints of the linear program, provide a complete description of the convex hull <p>of feasible solutions for a single commodity problem. Numerical tests have also been conducted, and highlight the real efficiency of the valid inequalities for the multi-commodity case. Finally, we point out the links between the problem studied in the thesis and a more classical design and pricing problem in economics. /<p><p><p>Considérons le problème qui consiste à maximiser les profits issus de la tarification d’un sous-ensemble d’arcs d’un réseau de transport, où les flots origine-destination (produits) sont affectés aux plus courts chemins par rapport aux tarifs et aux coûts initiaux. Cette thèse porte sur une structure de réseau particulière du problème ci-dessus, dans laquelle tous les arcs tarifables sont connectés et forment un chemin, <p>comme c’est le cas sur une autoroute. Étant donné que les tarifs sont habituellement déterminés selon les points d’entrée et de sortie sur l’autoroute, nous considérons un sous-graphe tarifable complet, où chaque arc correspond en réalité à un sous-chemin. Deux variantes de ce problème sont étudiées, avec ou sans contraintes <p>spécifiques reliant les niveaux de tarifs sur les arcs. <p>Ce problème peut être modélisé comme un programme linéaire mixte entier. Nous prouvons qu’il est <p>NP-difficile. Plusieurs familles d’inégalités valides sont ensuite proposées, celles-ci renforçant certaines contraintes du modèle initial. Leur efficacité est d’abord démontrée de manière théorique, puisqu’il s’agit de facettes <p>des problèmes restreints à un ou deux produits. Certaines des inégalités valides proposées, ainsi que plusieurs contraintes du modèle initial, permettent aussi de donner une description complète de l’enveloppe convexe des solutions réalisables d’un problème restreint à un seul produit. Des tests numériques ont également <p>été menés, et mettent en évidence l’efficacité réelle des inégalités valides pour le problème général à plusieurs produits. Enfin, nous soulignons les liens entre le problème de tarification de réseau étudié dans cette thèse et un problème plus classique de tarification de produits en gestion. <p> / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Combinatorial optimization problems are of high academical as well as practical importance. Many instances of relevant combinatorial optimization problems are, due to their dimensions, intractable for complete methods such as branch and bound. Therefore, approximate algorithms such as metaheuristics received much attention in the past 20 years. Examples of metaheuristics are simulated annealing, tabu search, and evolutionary computation. One of the most recent metaheuristics is ant colony optimization (ACO), which was developed by Prof. M. Dorigo (who is the supervisor of this thesis) and colleagues. This thesis deals with theoretical as well as practical aspects of ant colony optimization.<p><p>* A survey of metaheuristics. Chapter 1 gives an extensive overview on the nowadays most important metaheuristics. This overview points out the importance of two important concepts in metaheuristics: intensification and diversification. <p><p>* The hyper-cube framework. Chapter 2 introduces a new framework for implementing ACO algorithms. This framework brings two main benefits to ACO researchers. First, from the point of view of the theoretician: we prove that Ant System (the first ACO algorithm to be proposed in the literature) in the hyper-cube framework generates solutions whose expected quality monotonically increases with the number of algorithm iterations when applied to unconstrained problems. Second, from the point of view of the experimental researcher, we show through examples that the implementation of ACO algorithms in the hyper-cube framework increases their robustness and makes the handling of the pheromone values easier.<p><p>* Deception. In the first part of Chapter 3 we formally define the notions of first and second order deception in ant colony optimization. Hereby, first order deception corresponds to deception as defined in the field of evolutionary computation and is therefore a bias introduced by the problem (instance) to be solved. Second order deception is an ACO-specific phenomenon. It describes the observation that the quality of the solutions generated by ACO algorithms may decrease over time in certain settings. In the second part of Chapter 3 we propose different ways of avoiding second order deception.<p><p>* ACO for the KCT problem. In Chapter 4 we outline an ACO algorithm for the edge-weighted k-cardinality tree (KCT) problem. This algorithm is implemented in the hyper-cube framework and uses a pheromone model that was determined to be well-working in Chapter 3. Together with the evolutionary computation and the tabu search approaches that we develop in Chapter 4, this ACO algorithm belongs to the current state-of-the-art algorithms for the KCT problem.<p><p>* ACO for the GSS problem. Chapter 5 describes a new ACO algorithm for the group shop scheduling (GSS) problem, which is a general shop scheduling problem that includes among others the well-known job shop scheduling (JSS) and the open shop scheduling (OSS) problems. This ACO algorithm, which is implemented in the hyper-cube framework and which uses a new pheromone model that was experimentally tested in Chapter 3, is currently the best ACO algorithm for the JSS as well as the OSS problem. In particular when applied to OSS problem instances, this algorithm obtains excellent results, improving the best known solution for several OSS benchmark instances. A final contribution of this thesis is the development of a general method for the solution of combinatorial optimization problems which we refer to as Beam-ACO. This method is a hybrid between ACO and a tree search technique known as beam search. We show that Beam-ACO is currently a state-of-the-art method for the application to the existing open shop scheduling (OSS) problem instances.<p><p> / Doctorat en sciences appliquées / info:eu-repo/semantics/nonPublished

Graph cuts have emerged as an important combinatorial optimization tool for many problems in vision. Most of the computer vision problems are discrete labeling problems. For example, in stereopsis, labels represent disparity and in image restoration, labels correspond to image intensities. Finding a good labeling involves optimization of an Energy Function. In computer vision, energy functions for discrete labeling problems can be elegantly formulated through Markov Random Field (MRF) based modeling and graph cut algorithms have been found to efficiently optimize wide class of such energy functions. The main contribution of this thesis lies in developing an efficient combinatorial optimization algorithm which can be applied to a wide class of energy functions. Generally, graph cut algorithms deal sequentially with each label in the labeling problem at hand. The time complexity of these algorithms increases linearly with number of labels. Our algorithm, finds a solution/labeling in logarithmic time complexity without compromising on quality of solution. In our work, we present an improved Logcut algorithm [24]. Logcut algorithm [24] deals with finding individual bit values in integer representation of labels. It has logarithmic time complexity, but requires training over data set. Our improved Logcut (Heuristic-Logcut or H-Logcut) algorithm eliminates the need for training and obtains comparable results in respect to original Logcut algorithm. Original Logcut algorithm cannot be initialized by a known labeling. We present a new algorithm, Sequential Bit Plane Correction (SBPC) which overcomes this drawback of Logcut algorithm. SBPC algorithm starts from a known labeling and individually corrects each bit of a label. This algorithm too has logarithmic time complexity. SBPC in combination with H-Logcut algorithm, further improves rate of convergence and quality of results. Finally, a hierarchical approach to graph cut optimization is used to further improve on rate of convergence of our algorithm. Generally, in a hierarchical approach first, a solution at coarser level is computed and then its result is used to initialize algorithm at a finer level. Here we have presented a novel way of initializing the algorithm at finer level through fusion move [25]. The SBPC and H-Logcut algorithms are extended to accommodate for hierarchical approach. It is found that this approach drastically improves the rate of convergence and attains a very low energy labeling. The effectiveness of our approach is demonstrated on stereopsis. It is found that the algorithm significantly out performs all existing algorithms in terms of quality of solution as well as rate of convergence.

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.

Nous détaillons dans cette thèse des algorithmes modérément exponentiels pour l'approximation du problème MAX SAT. Nous discutons d'une méthode générique pour la conception d'algorithmes exponentiels réalisant des schémas d'approximation dans un cadre plus général. Enfin, nous présentons des résultats paramétrés pour des problèmes de coupe à cardinalité contrainte. / We give in this thesis some moderately exponential algorithms for the MAX SAT problem. We discuss a very general method to conceive efficient exponential algorithms that give approximation scheme. In the end, we present some parameterized results for CUT problem with constrained cardinality.

L'objectif de la thèse est de créer et développer de nouvelles méthodes de résolution efficaces des problèmes combinatoires en configuration des lignes de fabrication. Deux problèmes ont été particulièrement étudiés: le problème d'équilibrage et de choix d'équipement pour des lignes dédiées et le problème de minimisation des coûts de changements de séries pour des lignes multi-produits. Une solution du premier problème consiste en une affectation admissible des ressources à un nombre de stations à déterminer de sorte que le coût total soit minimal. Afin de résoudre ce problème, nous l'avons réduit au problème de partition d'ensemble et l'avons résolu par des heuristiques gloutonnes et une méthode exacte de génération de contraintes. Les expérimentations sur différentes instances ont montré que la nouvelle approche de résolution surclasse les approches antérieures de la littérature en termes de qualité de solution et de temps de calcul. Pour le second problème deux critères sont considérés lexicographiquement : la minimisation du nombre de stations et la minimisation du coût de changement de séries. Nous avons examiné successivement les cas d'exécution parallèle et séquentielle des opérations. Des solutions approchées ont été trouvées par des heuristiques gloutonnes. Ensuite, nous avons proposé deux modèles de programmation linéaire en nombres entiers (PLNE) afin de trouver le nombre de stations minimal et ensuite d'obtenir le coût de changement de séries minimal. Les résultats des expérimentations sur ces nouveaux problèmes se sont avérés prometteurs à la fois en termes de qualité de solution et de temps de calcul. / The objective of this thesis is to create and develop new effective solution methods for production line configuration problems. Two problems were studied: the equipment selection and balancing problem for dedicated lines and the setup cost minimization problem for multi-product lines. A solution for the first problem consists in a feasible assignment of the resources to an unknown number of stations so that the total cost is minimized. In order to solve this problem, we reduced it to the set partitioning problem and solved it by greedy heuristics and an exact method of constraint generation. The computer experiments on different problem instances showed that the new solution approach outperforms the previous methods from the literature both in terms of solution quality and computational time. For the second problem two criteria were considered lexicographically: the minimization of the number of stations and the minimization of the total setup cost. We examined successively the cases with parallel and sequential execution of operations. Approximate solutions were found by greedy heuristics. Then, we proposed two integer programming models in order to obtain the minimal number of stations and then the minimal setup cost. The experimental results for this new problem proved to be promising both in terms of solution quality and computational time.

Esta dissertação trata do problema da k-árvore de custo mínimo (kMST): dados um grafo conexo G, um custo não-negativo c_e para cada aresta e e um número inteiro positivo k, encontrar uma árvore com k vértices que tenha custo mínimo. O kMST é um problema NP-difícil e portanto não se conhece um algoritmo polinomial para resolvê-lo. Nesta dissertação discutimos alguns casos em que é possível resolver o problema em tempo polinomial. Também são estudados algoritmos de aproximação para o kMST. Entre os algoritmos de aproximação estudados, apresentamos a 2-aproximação desenvolvida por Naveen Garg, que atualmente é o algoritmo com melhor fator de aproximação. / This dissertation studies the minimum cost k-tree problem (kMST): given a connected graph G, a nonnegative cost function c_e for each edge e and a positive integer k, find a minimum cost tree with k vertices. The kMST is an NP-hard problem, which implies that it is not known a polynomial algorithm to solve it. In this dissertation we discuss some cases that can be solved in polynomial time. We also study approximation algorithms for the kMST. Among the approximation algorithms we present the 2-approximation developed by Naveen Garg, which is currently the algorithm with the best approximation factor.