Improving the solvability of combinatorial optimization problems
Guide(s)
Desai, Jitamitra
Department
Decision Sciences
Area
Decision Sciences
University
Indian Institute of Management Bangalore
Place
Bangalore
Publication Date
3-31-2024
Year Awarded
March 2024
Year Completed
March 2024
Year Registered
June 2018
Abstract
This Ph.D. thesis presents structured approaches to addressing challenging combinatorial optimization problems where the objective is to uncover an optimal integer or discrete solution. These strategies demonstrate remarkable success in the real world, demanding that we strike a balance between formulation size and computational effort. Combinatorial optimization is related to operations research, algorithm theory, and computational complexity theory showcasing its far-reaching implications across emerging areas such as machine learning and artificial intelligence. These optimization problems are NP-hard, that can be extremely hard in practice and in the worst case undecidable. Typically, a large-scale combinatorial optimization problem can be formulated using a (Min) Mixed-Integer Program (MIP) which is conventionally solved by the Branch-and-Bound algorithm. The Branch-and-Bound algorithm is essentially an iterative partitioning mechanism of the total feasible search space. At every stage, the algorithm checks the "LP-IP gap", characterized as the difference between the best upper bound and incumbent solution, and declares optimality (if one exists) when this gap is equal to zero. It is fairly evident that the efficacy of such a search process is highly predicated on quickly reducing the LP-IP gap, which in turn is contingent on two phenomenons: 1) increasing the lower (primal) bound and 2) reducing the resulting upper (dual) bounds. This thesis bilaterally targets both these aspects of Branch-and-Bound algorithm. The first two essays targets on the enhancement of the lower bound by developing a new disaggregated formulation and exploiting the extended polyhedral structure using valid inequalities and cuts for two important class of combinatorial optimization problem: Unsplittable Multicommodity Capacitated Network Design Problem (UMCND) and Steiner Tree Problem (STP), In the UMCND, the task is to select singular optimal paths and flows for all commodities in the network at a minimal cost, while respecting flow balance constraints at each node and capacity constraints along each are. In the STP, the task is to select singular optimal paths for all commodities to their respective terminal nodes from a common root node for an uncapacitated network. The disaggregated formulation is basically developing a new cardinality-based extended formulation for the network problems, wherein we associate new variables based on the cardinality of each are, where are-cardinality is defined as the maximum number of possible commodities that can flow along each are in the network. The polyhedral structure of the higher dimensioned extended problem is exploited to generate specialized cuts and valid inequalities based on cardinality and/or cutsets. The third essay works on reducing the upper bound by introducing an interior point line-search method referred as Branch-Line-and-Search (BLS) algorithm, built on the principle of tracing collinear integer points along the line segment formed by joining two integer points in an integer lattice. Several cases have been dealt in detail based on the position of the two base integer points with respect to the feasible space. Computational results on randomly generated instances demonstrate substantial savings in the number of subproblems taken in a branch-and-bound process as well as computational time taken to aforementioned approaches. The thesis primarily revolves around the research problems based on developing new techniques for resolving specific classes of mixed-integer problems, acquiring robust continuous relaxations, explore and develop alternative formulations and algorithms. This can be overall summarized as a goal to design and implement methodologies to address specific categories of computationally intractable or challenging optimization problems.
Pagination
x, 119p.
Copyright
Indian Institute of Management Bangalore
Document Type
Dissertation
DAC Chairperson
Desai, Jitamitra
DAC Members
Murthy, Ishwar; Sastry, Trilochan; Mahajan, Ashutosh
Type of Degree
Ph.D.
Recommended Citation
Anjum, MD Shahrukh, "Improving the solvability of combinatorial optimization problems" (2024). Doctoral Dissertations. 11.
https://research.iimb.ac.in/doc_dissertations/11
Relation
DIS-IIMB-FPM-P24-11
