Back to search

University of Alabama Birmingham

Modeling Probabilistic Combinational Optimization Problems on Graphs Using Communication Channel

Abstract

dc:description.abstract

This 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 × 5

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
University of Alabama Birmingham
Base URL
digitalcommons.library.uab.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Djakam, William Ngambou. Modeling Probabilistic Combinational Optimization Problems on Graphs Using Communication Channel. Dissertation thesis, https://digitalcommons.library.uab.edu/etd-collection/354