Information representation in large-scale resource allocation problems: Theory, algorithms and applications.

摘要

We study the methodology of representing information in resource allocation problems characterizing many large-scale problems, for example, those that arise in freight logistics operations. Using a traditional cost-based approach to solve these models is inadequate since the real-world is characterized by incomplete information reflected in missing elements of data that is unknown to the modeler.; However, the modeler is able to observe actual decisions from a historical database that indirectly captures this missing information. We present a methodology based on pattern recognition methods to represent information from a historical database in resource allocation models. We separately consider decisions that are categorical (the set of decisions have no natural ordering) and patterns that are numerical (decisions that have a natural ordering). We modify the traditional pattern recognition approach to develop a probabilistic framework of information representation that takes into account missing elements of data.; The thesis is organized into two parts. In the first part we lay down the foundations of unifying pattern recognition approaches with optimization models as they relate to large-scale resource allocation problems. We present theoretical analysis of our methodology wherever applicable. We see that the function known as the “pattern metric” that we use for information representation is closely related to some popular goodness-of-fit metrics used in statistics. We present experimental results using real-world data in a laboratory setting in both the cases involving categorical and numerical patterns.; In the second part we apply our research to a class of resource allocation problems that are solved as time-staged optimization models. Many real-world problems that arise in freight logistics are often solved as a series of time-staged approximations due to stochastic data (time staged information processes) or computational complexity arising with problems with long time horizons. We present a methodology that allows us to represent information pertaining to static flow patterns such as “historical priors” that are aggregations of decisions made at different stages of a time-staged model. We use a standard Gauss-Siedel technique to develop our algorithm.