[pt] A construção de árvores de decisão é um problema central em diversas áreas da ciência da computação, por exemplo, teoria de banco de dados e aprendizado computacional. Este problema pode ser visto como o problema de avaliar uma função discreta, onde para verificar o valor de cada variável da função temos que pagar um custo, e os pontos onde a função está definida estão associados a uma distribuição de probabilidade. O objetivo do problema é avaliar a função minimizando o custo gasto (no pior caso ou no caso médio). Nesta tese, apresentamos quatro contribuições relacionadas a esse problema. A primeira é um algoritmo que alcança uma aproximação de O(log(n)) em relação a tanto o custo esperado quanto ao pior custo. A segunda é um método que combina duas árvores, uma com pior custo W e outra com custo esperado E, e produz uma árvore com pior custo de no máximo (1+p)W e custo esperado no máximo (1/(1-e-p))E, onde p é um parâmetro dado. Nós também provamos que esta é uma caracterização justa do melhor trade-off alcançável, mostrando que existe um número infinito de instâncias para as quais não podemos obter uma árvore de decisão com tanto o pior custo menor que (1 + p)OPTW(I) quanto o custo esperado menor que (1/(1 - e - p))OPTE(I), onde OPTW(I) (resp. OPTE(I)) denota o pior custo da árvore de decisão que minimiza o pior custo (resp. custo esperado) para uma instância I do problema. A terceira contribuição é um algoritmo de aproximação de O(log(n)) para a minimização do pior custo para uma variante do problema onde o custo de ler uma variável depende do seu valor. Nossa última contribuição é um algoritmo randomized rounding que, dada uma instância do problema (com um inteiro adicional (k > 0) e um parâmetro 0 < e < 1/2, produz uma árvore de decisão oblivious com custo no máximo (3/(1 - 2e))ln(n)OPT(I) e que produz no máximo (k/e) erros, onde OPT(I) denota o custo da árvore de decisão oblivious com o menor custo entre todas as árvores oblivious para a instância I que produzem no máximo k erros de classificação. / [en] Decision tree construction is a central problem in several areas of computer science, for example, data base theory and computational learning. This problem can be viewed as the problem of evaluating a discrete function, where to check the value of each variable of the function we have to pay a cost, and the points where the function is defined are associated with a probability distribution. The goal of the problem is to evaluate the function minimizing the cost spent (in the worst case or in expectation). In this Thesis, we present four contributions related to this problem. The first one is an algorithm that achieves an O(log(n)) approximation with respect to both the expected and the worst costs. The second one is a procedure that combines two trees, one with worst costW and another with expected cost E, and produces a tree with worst cost at most (1+p)W and expected cost at most (1/(1-e-p))E, where p is a given parameter. We also prove that this is a sharp characterization of the best possible trade-off attainable, showing that there are infinitely many instances for which we cannot obtain a decision tree with both worst cost smaller than (1+p)OPTW(I) and expected cost smaller than (1/(1-e-p))OPTE(I), where OPTW(I) (resp. OPTE(I)) denotes the cost of the decision tree that minimizes the worst cost (resp. expected cost) for an instance I of the problem. The third contribution is an O(log(n)) approximation algorithm for the minimization of the worst cost for a variant of the problem where the cost of reading a variable depends on its value. Our final contribution is a randomized rounding algorithm that, given an instance of the problem (with an additional integer k > 0) and a parameter 0 < e < 1/2, builds an oblivious decision tree with cost at most (3/(1 - 2e))ln(n)OPT(I) and produces at most (k/e) errors, where OPT(I) denotes the cost of the oblivious decision tree with minimum cost among all oblivious decision trees for instance I that make at most k classification errors.

京都大学 / 新制・課程博士 / 博士(情報学) / 甲第25443号 / 情博第881号 / 新制||情||148(附属図書館) / 京都大学大学院情報学研究科通信情報システム専攻 / (主査)教授 湊 真一, 教授 大木 英司, 教授 山本 章博 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

Let X be the affine flag manifold of Lie type A_n-1⁽¹⁾ where n ≥ 3 and let W_aff be the associated affine Weyl group. The moment graph for X encodes the torus fixed points (which are elements of the affine Weyl group W_aff and the torus stable curves in X. Given a fixed point u ∈ W_aff and a degree d = (d₀, d₁, ..., d_n−1) ∈ ℤ_≥0ⁿ, the combinatorial curve neighborhood is the set of maximal elements in the moment graph of X which can be reached from u′ ≤ u by a chain of curves of total degree ≤ d. In this thesis we give combinatorial formulas and algorithms for calculating these elements. / Doctor of Philosophy / The study of curves on flag manifolds is motivated by questions in enumerative geometry and physics. To a space of curves and incidence conditions one can associate a combinatorial object called the ‘combinatorial curve neighborhood’. For a fixed degree d and a (Schubert) cycle, the curve neighborhood consists of the set of all elements in the Weyl group which can be reached from the given cycle by a path of fixed degree in the moment graph of the flag manifold, and are also Bruhat maximal with respect to this property. For finite dimensional flag manifolds, a description of the curve neighborhoods helped answer questions related to the quantum cohomology and quantum K theory rings, and ultimately about enumerative geometry of the flag manifolds. In this thesis we study the situation of the affine flag manifolds, which are infinite dimensional. We obtain explicit combinatorial formulas and recursions which characterize the curve neighborhoods for flag manifolds of affine Lie type A. Among the conclusions, we mention that, unlike in the finite dimensional case, the curve neighborhoods have more than one component, although all components have the same length. In general, calculations reflect a close connection between the curve neighborhoods and the Lie combinatorics of the affine root system, especially the imaginary roots.

Yes / In this paper, a new population-based and nature-inspired metaheuristic algorithm, Discrete Flower Pollination Algorithm (DFPA), is presented to solve the Resource Constrained Project Scheduling Problem (RCPSP). The DFPA is a modification of existing Flower Pollination Algorithm adapted for solving combinatorial optimization problems by changing some of the algorithm's core concepts, such as flower, global pollination, Lévy flight, local pollination. The proposed DFPA is then tested on sets of benchmark instances and its performance is compared against other existing metaheuristic algorithms. The numerical results have shown that the proposed algorithm is efficient and outperforms several other popular metaheuristic algorithms, both in terms of quality of the results and execution time. Being discrete, the proposed algorithm can be used to solve any other combinatorial optimization problems. / Innovate UK / Awarded 'Best paper of the Month'

<p dir="ltr">Combinatorial graph theory is an essential tool in the design and analysis of cryptographic primitives such as Memory-Hard Functions (MHFs) and Proofs of Sequential Work (PoSWs). MHFs are used to design egalitarian Proofs of Work and to help protect low-entropy secrets such as user passwords against brute-force attacks in password hashing. A PoSW is a protocol for proving that one spent significant sequential computation work to validate some statement. PoSWs have many applications, including time-stamping, blockchain design, and universally verifiable CPU benchmarks. Prior work has used combinatorial properties of graphs to construct provably secure MHFs and PoSWs. However, some open problems still exist, such as improving security bounds for MHFs, finding approximation algorithms for measuring their memory hardness, and analyzing the post-quantum security of MHFs and PoSWs. This dissertation addresses these challenges in the security analysis of MHFs and PoSWs using combinatorial graph theory. </p><p dir="ltr">We first improve the understanding of the classical security of MHFs in the following ways. (1) We present improved security bounds for MHF candidates such as Argon2i and DRSample under plausible graph-theoretic conjectures. (2) We prove that it is Unique Games-hard to approximate the cumulative pebbling complexity of a directed acyclic graph, which is an important metric to understand the memory-hardness of data-independent MHFs. (3) We provide the first explicit construction of extremely depth-robust graphs with small indegree. Here, (extreme) depth-robustness is a crucial combinatorial tool to construct secure MHFs and PoSWs. (4) We build a new family of graphs that achieves better provable parameters for concrete depth-robustness.</p><p dir="ltr">Second, as we progress toward developing quantum computers, we initiate the post-quantum security analysis of MHFs and PoSWs. Specifically, we make the following contributions. (1) We introduce the parallel reversible pebbling game, which captures additional restrictions in quantum computing. We use combinatorial graph theory as a tool to analyze the space-time complexity and the cumulative pebbling complexity of MHF candidates such as Argon2i and DRSample in a reversible setting, which we call reversible space-time/cumulative pebbling cost, respectively. (2) We prove that the reversible cumulative pebbling cost is never too much larger than the classical cumulative pebbling cost, along with the separation result that, in some instances, the reversible cumulative pebbling cost is asymptotically larger than the classical one. (3) We prove that it is also Unique Games-hard to approximate the reversible cumulative pebbling cost of a directed acyclic graph. (4) Finally, we establish the post-quantum security of a PoSW from Cohen and Pietrzak (EUROCRYPT 2018) in the parallel quantum random oracle model by extending Zhandry's compressed oracle technique (CRYPTO 2019) and utilizing underlying combinatorial techniques of PoSWs.</p>

No description available.

This research deals with a study of the polyhedral structure of three important combinatorial optimization problems, namely, the generalized upper bounding (GUS) constrained knapsack problem, the set partitioning problem, and the quadratic zero-one programming problem, and applies related techniques to solve a practical combinatorial naval defense problem. In Part I of this research effort, we present new results on the polyhedral structure of the foregoing combinatorial optimization problems. First, we characterize a new family of facets for the GUS constrained knapsack polytope. This family of facets is obtained by sequential and simultaneous lifting procedures of minimal GUS cover inequalities. Second, we develop a new family of cutting planes for the set partitioning polytope for deleting any fractional basic feasible solutions to its underlying linear programming relaxation. We also show that all the known classes of valid inequalities belong to this family of cutting planes, and hence, this provides a unifying framework for a broad class of such valid inequalities. Finally, we present a new class of facets for the boolean quadric polytope, obtained by applying a simultaneous lifting procedure. The strong valid inequalities developed in Part I, such as facets and cutting planes, can be implemented for obtaining exact and approximate solutions for various combinatorial optimization problems in the context of a branch-and-cut procedure. In particular, facets and valid cutting planes developed for the GUS constrained knapsack polytope and the set partitioning polytope can be directly used in generating tight linear programming relaxations for a certain scheduling polytope that arises from a combinatorial naval defense problem. Furthermore, these tight formulations are intended not only to develop exact solution algorithms, but also to design powerful heuristics that provide good quality solutions within a reasonable amount of computational effort. Accordingly, in Part ll of this dissertation, we present an application of such polyhedral results in order to construct effective approximate and exact algorithms for solving a naval defense problem. tn this problem, the objective is to schedule a set of illuminators in order to strike a given set of targets using surface-to-air missiles in naval battle-group engagement scenarios. The problem is conceptualized as a production floor shop scheduling problem of minimizing the total weighted flow time subject to time-window job availability and machine-downtime unavailability side constraints. A polynomial-time algorithm is developed for the case when ail the job processing times are equal (and unity without loss of generality) and the data are all integer. For the general case of scheduling jobs with unequal processing times, we develop three alternative formulations and analyze their relative strengths by comparing their respective linear programming relaxations. The special structures inherent in a particular strong zero-one integer programming model of the problem enable us to derive some classes of strong valid inequalities from the facets of the GUB constrained knapsack polytope and the set-packing polytope. Furthermore, these special structures enable us to construct several effective approximate and exact algorithms that provide solutions within specified tolerances of optimality, with an effort that admits real-time processing in the naval battle-group engagement scenario. Computational results are presented using suitable realistic test data. / Ph. D.

Group (pooled) testing, i.e., testing multiple subjects simultaneously with a single test, is essential for classifying a large population of subjects as positive or negative for a binary characteristic (e.g., presence of a disease, genetic disorder, or a product defect). While group testing is used in various contexts (e.g., screening donated blood or for sexually transmitted diseases), a lack of understanding of how an optimal grouping scheme should be designed to maximize classification accuracy under a budget constraint hampers screening efforts. We study Dorfman and Array group testing designs under subject-specific risk characteristics, operational constraints, and imperfect tests, considering classification accuracy-, efficiency-, robustness-, and equity-based objectives, and characterize important structural properties of optimal testing designs. These properties provide us with key insights and allow us to model the testing design problems as network flow problems, develop efficient algorithms, and derive insights on equity and robustness versus accuracy trade-off. One of our models reduces to a constrained shortest path problem, for a special case of which we develop a polynomial-time algorithm. We also show that determining an optimal risk-based Dorfman testing scheme that minimizes the expected number of tests is tractable, resolving an open conjecture. Our case studies, on chlamydia screening and screening of donated blood, demonstrate the value of optimal risk-based testing designs, which are shown to be less expensive, more accurate, more equitable, and more robust than current screening practices. / PHD / Group (pooled) testing, i.e., testing multiple subjects simultaneously with a single test, is essential for classifying a large population of subjects as positive or negative for a binary characteristic (e.g., presence of a disease, genetic disorder, or a product defect). While group testing is used in various contexts (e.g., screening donated blood or for sexually transmitted diseases), a lack of understanding of how an optimal grouping scheme should be designed to maximize classification accuracy under a budget constraint hampers screening efforts. We study Dorfman and Array group testing designs under subject-specific risk characteristics, operational constraints, and imperfect tests, considering classification accuracy-, efficiency-, robustness-, and equity-based objectives, and characterize important structural properties of optimal testing designs. These properties provide us with key insights and allow us to model the testing design problems as network flow problems, develop efficient algorithms, and derive insights on equity and robustness versus accuracy trade-off. We also show that determining an optimal risk-based Dorfman testing scheme that minimizes the expected number of tests is tractable, resolving an open conjecture. Our case studies, on chlamydia screening and screening of donated blood, demonstrate the value of optimal risk-based testing designs, which are shown to be less expensive, more accurate, more equitable, and more robust than current screening practices.

Tesis por compendio / [ES] La tesis "Teoría Combinatoria de Números, Recurrencia de Operadores y Dinámica Lineal" se sitúa dentro del estudio de la dinámica de operadores lineales, o Dinámica Lineal. El objetivo de este trabajo es estudiar múltiples nociones de recurrencia, que pueden presentar los sistemas dinámicos lineales, y que clasificaremos mediante la Teoría Combinatoria de Números. La Dinámica Lineal estudia las órbitas generadas por las iteraciones de una transformación lineal. Las propiedades más estudiadas en esta rama durante los últimos 30 años han sido la hiperciclicidad (existencia de órbitas densas) y el caos (con sus múltiples definiciones), siendo esta un área de investigación muy activa y obteniéndose un considerable número de resultados profundos e interesantes. Nosotros nos centraremos en la recurrencia, propiedad muy estudiada para sistemas dinámicos clásicos no lineales, pero prácticamente nueva en Dinámica Lineal pues no es hasta 2014, con el artículo de Costakis, Manoussos y Parissis titulado "Recurrent linear operators", cuando se empieza a estudiar esta noción de manera sistemática en el contexto de operadores actuando en espacios de Banach. La situación básica de la que parte nuestro estudio es la siguiente: "T : X ---> X" será un operador lineal y continuo actuando sobre un F-espacio "X" , aunque a veces necesitaremos que el espacio subyacente "X" sea un espacio de Fréchet, de Banach o de Hilbert. Dado un vector "x" y un entorno "U" de "x" estudiaremos el conjunto de retorno "N_T(x,U) = { n : T^n(x) está en U }" y dependiendo de su tamaño, observado mediante la Teoría Combinatoria de Números, diremos que el vector "x" presenta una propiedad de recurrencia u otra. La memoria de la tesis se ha realizado por compendio de artículos y consta de cuatro capítulos y un apéndice: 1. Adaptación de la "versión de autor" del artículo "Frequently recurrent operators. Journal of Functional Analysis, 283 (12) (2022), artículo núm. 109713, 36 páginas". En este se definen por primera vez las fuertes nociones de recurrencia reiterada, U-frecuente y frecuente, y sus propiedades básicas son estudiadas. Finalmente se generaliza el estudio mediante el concepto de F-recurrencia, que se conecta con la noción de F-hiperciclicidad. 2. Adaptación al formato de la tesis de la "versión de autor" revisada del artículo "Recurrence properties: An approach via invariant measures. Journal de Mathématiques Pures et Appliquées, 169 (2023), 155-188". En este se relaciona la recurrencia de operadores con la Teoría Ergódica y los sistemas dinámicos que conservan la medida. 3. Adaptación de la "versión de autor" del preprint "Questions in linear recurrence: From the T+T-problem to lineability". Se resuelve negativamente un problema abierto de 2014: Sea "T : X ---> X" un operador recurrente. ¿Es cierto que el operador "T+T" es recurrente en "X+X"? Para resolverlo introducimos la casi-rigidez, que será, para la recurrencia, la noción análoga a la propiedad débil-mezclante (topológica) para la transitividad/hiperciclicidad; y luego construimos operadores recurrentes pero no casi-rígidos en todo espacio de Banach infinito-dimensional y separable. 4. Adaptación de la "versión de autor" revisada del preprint " Recurrent subspaces in Banach spaces". En este se estudia la propiedad de espaciabilidad (existencia de un subespacio vectorial cerrado y de dimensión infinita) para el conjunto de vectores recurrentes. - Apéndice. Para conseguir un carácter auto-contenido hemos añadido un apéndice con los resultados básicos de Teoría Combinatoria de Números que se han utilizado en los trabajos que componen la memoria. Siguiendo la normativa establecida por la Escuela de Doctorado también se incluye: - Introducción; - Discusión general de los resultados; - Conclusiones. / [CAT] La tesi "Teoria Combinatòria de Nombres, Recurrència d'Operadors i Dinàmica Lineal" se situa dins de l'estudi de la dinàmica d'operadors lineals, o simplement Dinàmica Lineal. L'objectiu d'aquest treball és estudiar múltiples nocions de recurrència, que poden presentar els sistemes dinàmics lineals, i que classificarem mitjançant la Teoria Combinatòria de Nombres. La Dinàmica Lineal estudia les òrbites generades per les iteracions d'una transformació lineal. Les propietats més estudiades en aquesta branca de les matemàtiques als darrers 30 anys han estat la hiperciclicitat (existència d'òrbites denses) i el caos (amb les seves múltiples definicions), sent aquesta una àrea de recerca molt activa i obtenint-se un considerable nombre de resultats profunds i interessants. Nosaltres ens centrarem en la recurrència, propietat molt estudiada per a sistemes dinàmics clàssics no lineals, però, pràcticament nova en Dinàmica Lineal doncs no és fins al 2014, amb l'article de Costakis, Manoussos i Parissis titulat "Recurrent linear operators", quan es comença a estudiar aquesta noció de manera sistemàtica en el context d'operadors actuant en espais de Banach. La situació bàsica de la qual parteix el nostre estudi és la següent: "T : X ---> X" serà un operador lineal i continu actuant sobre un F-espai "X", encara que de vegades necessitarem que l'espai subjacent X siga un espai de Fréchet, de Banach o de Hilbert. Llavors, donat un vector "x" i un entorn "U" de "x" estudiarem el conjunt de retorn "N_T(x,U) = { n : T^n(x) està en U }" i depenent de la seva mida, observada des del punt de vista de la Teoria Combinatòria de Nombres, direm que el vector "x" presenta una o altra propietat de recurrència. La memòria de la tesi s'ha realitzat per compendi d'articles i consta de quatre capítols i un apèndix: 1. Adaptació de la "versió d'autor" revisada de l'article "Frequently recurrent operators. Journal of Functional Analysis, 283 (12) (2022), article núm. 109713, 36 pàgines". En aquest es defineixen per primera vegada les nocions de recurrència reiterada, U-freqüent i freqüent, i les seves propietats bàsiques són estudiades. Finalment es generalitza l'estudi mitjançant el concepte de F-recurrència, que es connecta amb la noció de F-hiperciclicitat. 2. Adaptació al format de la tesi de la "versió d'autor" revisada de l'article "Recurrence properties: An approach via invariant measures. Journal de Mathématiques Pures et Appliquées, 169 (2023), 155-188". Es relaciona la recurrència d'operadors amb la Teoria Ergòdica i els sistemes dinàmics que conserven la mesura. 3. Adaptació de la "versió d'autor" del preprint "Questions in linear recurrence: From the T+T-problem to lineability". En aquest es resol un problema obert de l'any 2014: Siga "T : X ---> X" un operador recurrent. És cert que l'operador "T+T" és recurrent en "X+X"? Per resoldre'l introduïm la quasi-rigidesa, que serà, per a la recurrència, la noció anàloga a la propietat feble-barrejant (topològica) per a la transitivitat/hiperciclicitat; i després construïm operadors recurrents però no quasi-rígids en tot espai de Banach infinit-dimensional i separable. 4. Adaptació de la "versió d'autor" del preprint "Recurrent subspaces in Banach spaces". S'inclou l'estudi de la propietat d'espaiabilitat (existència d'un subespai vectorial tancat i de dimensió infinita) per al conjunt de vectors recurrents. - Apèndix:Per aconseguir un caràcter auto-contingut hem afegit un apèndix amb resultats bàsics de Teoria Combinatòria de Nombres que es donen per suposats en els treballs que componen la memòria. Seguint la normativa establerta per l'Escola de Doctorat també s'inclou: - Introducció; - Discussió general dels resultats; - Conclusions. / [EN] The thesis "Combinatorial Number Theory, Recurrence of Operators and Linear Dynamics" is part of the study of the dynamics of linear operators, simply called Linear Dynamics. The objective of this work is to study multiple notions of recurrence, that linear dynamical systems can present, and which will be classified through Combinatorial Number Theory. Linear Dynamics studies the orbits generated by the iterations of a linear transformation. The two most studied properties in this branch of mathematics during the last 30 years have been hypercyclicity (existence of dense orbits) and chaos (with its multiple definitions), being this a very active research area with a considerable number of exceptionally deep but also interesting results. We will focus on recurrence, a property widely studied in the classical setting of non-linear dynamical systems, but practically new with respect to Linear Dynamics since it was not until 2014, with the article by Costakis, Manoussos and Parissis entitled "Recurrent linear operators", when this notion started to be systematically studied in the context of operators acting on Banach spaces. The basic situation from which our study starts is the following: "T : X ---> X" will be a continuous linear operator acting on an F-space "X", although sometimes we will need the underlying space X to be a Fréchet, Banach or Hilbert space. Given a vector "x" and a neighbourhood "U" of "x" we will study the return set "N_T(x,U) = { n : T^n(x) is in U }" and depending on its size, observed from the Combinatorial Number Theory point of view, we will say that the vector "x" presents one property of recurrence or another. The thesis memoir is a compendium of articles and it has four chapters and one appendix: 1. Adaptation of the revised "author version" of article "Frequently recurrent operators. Journal of Functional Analysis, 283 (12) (2022), paper no. 109713, 36 pages". Here, the strong notions of reiterative, U-frequent and frequent recurrence are defined for the first time, and their basic properties are studied. The theory is finally generalized through the concept of F-recurrence, which is connected to the notion of F-hypercyclicity. 2. Adaptation of the revised "author version" of article "Recurrence properties: An approach via invariant measures. Journal de Mathématiques Pures et Appliquées, 169 (2023), 155-188". In this chapter the recurrence properties for linear operators are related to Ergodic Theory and measure preserving systems. 3. Adaptation of the revised "author version" of the preprint "Questions in linear recurrence: From the T+T-problem to lineability". We solve in the negative an open problem posed in 2014: Let "T : X ---> X" be a recurrent operator. Is it true that the operator "T+T" is recurrent on "X+X"? In order to do that we establish the analogous notion, for recurrence, to that of (topological) weak-mixing for transitivity/hypercyclicity, namely quasi-rigidity; and then we construct recurrent but not quasi-rigid operators on every separable infinite-dimensional Banach space. 4. Adaptation of the revised "author version" of the preprint "Recurrent subspaces in Banach spaces". In this chapter we study the spaceability (existence of an infinite-dimensional closed subspace) for the set of recurrent vectors. - Appendix. Looking for a self-contained text we have added an appendix with some of the basic Combinatorial Number Theory results that are taken for granted along the different chapters/articles forming this memoir. Following the regulations established by the Doctoral School the next sections are also included: - Introduction; - General discussion of the results; - Conclusions. / This thesis has been written at the “Institut Universitari de Matemàtica Pura i Aplicada” (IUMPA) of the “Universitat Politècnica de València” (UPV), during the period of enjoyment of a scholarship of the “Programa de Formación de Profesorado Universitario” granted by the “Ministerio de Ciencia, Innovación y Universidades”, reference number: FPU2019/04094. The research exposed has also been partially funded by the project “Dinámica de operadores” (MCIN/AEI/10.13039/501100011033, Project PID2019-105011GB-I00), thanks to which the author carried out a 3-month research stay in Lille, France (September-December 2021), that was supervised by Professor Sophie Grivaux; and also by the travel grant awarded by the “Fundació Ferran Sunyer i Balaguer” which allowed the author to carry out a 3-month research stay in Mons, Belgium (April-June 2023), supervised by Professor Karl Grosse-Erdmann. / López Martínez, A. (2023). Combinatorial Number Theory, Recurrence of Operators and Linear Dynamics [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/196101 / Compendio

One of the major planning problems faced by medium and large manufacturing enterprises is the distribution of production over various (production) facilities. The need for cross-facility capacity management is most evident in the high-tech industries having capital-intensive equipment and short technology life cycle. There have been solutions proposed in the literature that are based on the lagragian decomposition method which separate the overall multiple product problem into a number of single product problems. We believe that multi-agent systems, given their distributed problem solving approach can be used to solve this problem, in its entirety, more effectively. According to other researchers who have worked in this field, auction theoretic mechanisms are a good way to solve complex production planning problems. This research study develops a multi-agent system and negotiation protocol based on combinatorial auction framework to solve the given multi-facility planning problem. The output of this research is a software library, which can be used as a multi-agent system model of the multi-product, multi-facility capacity allocation problem. The negotiation protocol for the agents is based on an iterative combinatorial auction framework which can be used for making allocation decisions in this environment in real-time. A simulator based on this library is created to validate the multi-agent model as well as the auction theoretic framework for different scenarios in the problem domain. The planning software library is created using open source standards so that it can be seamlessly integrated with scheduling library being developed as a part of the Advanced Planning and Scheduling (APS) system project or any other software suite which might require this functionality. The research contribution of this study is in terms of a new multi-agent architecture for an Advanced Planning and Control (APS) system as well as a novel iterative combinatorial auction mechanism which can be used as an agent negotiation protocol within this architecture. The theoretical concepts introduced by this research are implemented in the MultiPlanner production planning tool which can be used for generating master production plans for manufacturing enterprises. The validation process carried out on both the iterative combinatorial framework and the agent-based production planning methodology demonstrate that the proposed solution strategies can be used for integrated decision making in the multi-product, multi-facility production planning domain. Also, the software tool developed as part of this research is a robust, platform independent tool which can be used by manufacturing enterprises to make relevant production planning decisions. / Master of Science