Back to search

North Dakota State University

Two Applications of Combinatorial Branch-and-Bound in Complex Networks and Transportation

Abstract

dc:description.abstract

In this dissertation, we show two significant applications of combinatorial branch-and-bound as an exact solution methodology in combinatorial optimization problems. In the first problem, we propose a set of new group centrality metrics and show their performance in estimating protein importance in protein-protein interaction networks. The centrality metrics introduced here are extensions of well-known nodal metrics (degree, betweenness, and closeness) for a set of nodes which is required to induce a specific pattern. The structures investigated range from the ``stricter'' induced stars and cliques, to a ``looser'' definition of a representative structure. We derive the computational complexity for each of the newly proposed metrics. Then, we provide mixed integer programming formulations to solve the problems exactly; due to the computational complexity of the problem and the sheer size of protein-protein interaction networks, using a commercial solver with the formulations is not always a viable option. Hence, we also propose a combinatorial branch-and-bound approach to solve the problems introduced. Finally, we conclude this work with a presentation of the performance of the proposed centrality metrics in identifying essential proteins in helicobacter pylori. In the second problem, we introduce the asymmetric probabilistic minimum-cost Hamiltonian cycle problem (APMCHCP) where arcs and vertices in the graph are possible to fail. APMCHCP has applications in many emerging areas, such as post-disaster recovery, electronic circuit design, and security maintenance of wireless sensor networks. For each vertex, we define a chance-constraint to guarantee that the probability of arriving at the vertex must be greater than or equal to a given threshold. Four mixed-integer programming (MIP) formulations are proposed for modeling the problem, including two direct formulations and two recursive formulations. A combinatorial branch-and-bound (CBB) algorithm is proposed for solving the APMCHCP, where data preprocessing steps, feasibility rules, and approaches of finding upper and lower bounds are developed. In the numerical experiments, the CBB algorithm is compared with formulations on a test-bed of two popular benchmark instance sets. The results show that the proposed CBB algorithm significantly outperforms Gurobi solver in terms of both the size of optimally solved instances and the computing time.

Degree

thesis:*
Grantor dc:publisher
North Dakota State University
Year dc:date.issued
2020

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Rasti, Saeid

Subjects

dc:subject × 6

Rights

dc:rights
Statement dc:rights
  • NDSU policy 190.6.2

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10365/32335

Chain of custody

source
Harvested from
North Dakota State University
Base URL
library.ndsu.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Rasti, Saeid. Two Applications of Combinatorial Branch-and-Bound in Complex Networks and Transportation. North Dakota State University, 2020. https://hdl.handle.net/10365/32335