University of Alabama Birmingham
Modeling Probabilistic Combinational Optimization Problems on Graphs Using Communication Channel
Abstract
dc:description.abstractThis thesis studies Combinatorial Optimization Problems (COPs) on graphs that integrate uncertainty in the problem definition. We focus on Probabilistic Combinatorial Optimization Problems (PCOPs), where uncertainty is associated with the presence or absence of subsets of vertices that describe the problem. In general, combinatorial optimization problems are formulated as a Mixed Integer Linear Programming (MILP) model. This process aims to convert elements of decision-making into variables considering related constraints and choosing an objective function. In such cases, it is recommended to define an objective function that is a linear function with linear constraints. Also, when practical problems are formulated as combinatorial optimization models, one must often include logical implications. Yet, the Least Action Principle (LAP) of information theory has been exploited to achieve optimization goal using the least amount of resources. Therefore, we approach combinatorial optimization problems on graphs by modeling them with a noisy communication channel using the maximum independent set as a tool of the least action of information theory. Subsequently, we propose an information-theoretic modeling approach for a class of PCOP that transformable into bipartite graphs. Using the a priori approach, we construct a communication channel and obtain any sub-instance solution with the noisy communication model. This communication channel model is used to a portfolio optimization problem as a case study.
Degree
thesis:*- Level thesis:degree_level
- Dissertation
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Djakam, William Ngambou
- Contributors dc:contributor
-
- Murat M Tanik
- Leon Jololian
- Karthikeyan Lingasubramanian
- Arie Nakhmani
- Buren Earl Wells
Subjects
dc:subject × 5Identifiers
dc:identifier.*- Repository record dc:identifier
- https://digitalcommons.library.uab.edu/etd-collection/354