A complex-systems paradigm for modeling and solving finite large-scale discrete resources allocation problems
|Director of thesis||Prof. Giovanna Di Marzo Serugendo|
|Co-director of thesis|
|Summary of thesis||
Allocating resources to achieve stated goals under defined constraints is a relevant problem in many industries. This problem is encountered in a variety of applications, including capacity planning in manufacturing, computer networks workload allocation, production planning, transports, logistics, capital budgeting, scheduling, timetabling, etc. Hence, finding good / optimal solutions to these problems has been the topic of intense research for several decades in the field of combinatorics and closely related areas of mathematics as well as in artificial intelligence and operational research. Depending on the application domain, the solutions might consist of arrangements, sequences, combinations, choices of objects, subsets, subgraphs, chains, routes in a network, assignments, schedules of jobs, packing schemes, etc. The two main categories of approaches to solving these problems are exact methods, that find solutions in a finite computational time, and heuristics, which have no guarantee for neither completeness nor optimality. However, heuristics are preferred when the problem might take too long or is computationally too intensive to be solved using exact methods. Over the years, many heuristics have been developed and successfully applied to model and solve the problem. Popular approaches to create such heuristics include: • Statistical analysis based on information derived from the problem's data itself such as, for instance, the size distribution of the variables' domain definition, the distribution of the number of variables in the constraints, etc. • Biological analogies based on structures and behaviors observed in living organisms such as, for instance, genetic pool recombination, swarm, slime molds growth, ant colony optimization, etc. • Physical analogies based on processes such as, for instance, simulated annealing in solid-state physics, local entropy reduction in thermodynamics, etc. However, to our knowledge, there is no general underlying theory to support these analogies and the heuristics that implement them. It is actually unclear why these heuristics actually work and their validation is mainly empirical. Our goal is to elaborate a general theory to model and solve large-scale discrete resources allocations problems. We intend to test the theory by developing and benchmarking a tool. The traditional approach in solving the problem is to consider separately, on one hand, the problem and on the other hand the heuristic to be applied to search for solutions. Our intuition is that to go beyond the empirical method, a paradigm shift is required in framing the problem and its resolution. In this research, we will explore a holistic approach to the problem and its resolution based on the concepts of the general system theory. The problem and its resolution method will be considered together as a whole, forming a complex system whose evolution converges towards the solutions.
|Administrative delay for the defence||2025|