Dynamic Programming Multi-Objective Combinatorial Optimization

Overview

Abstract

In this dissertation, we consider extensions of dynamic programming for combinatorial optimization. We introduce two exact multi-objective optimization algorithms: the multi-stage optimization algorithm that optimizes the problem relative to the ordered sequence of objectives (lexicographic optimization) and the bi-criteria optimization algorithm that simultaneously optimizes the problem relative to two objectives (Pareto optimization). We also introduce a counting algorithm to count optimal solutions before and after every optimization stage of multi-stage optimization. As applications, Michal studies eleven known combinatorial optimization problems: matrix chain multiplication, global sequence alignment, optimal paths in directed graphs, binary search trees, convex polygon triangulation, line breaking (text justification), one-dimensional clustering, optimal bitonic tour, segmented least squares, optimization of matchings in trees, and 0/1 knapsack problem. Michal will also briefly introduce his work in operation research with applications to health care. This work extends his interest in the optimization field from developing new methods included in this dissertation towards the real-life application.

Brief Biography

Michal Mankowski, a Ph.D. candidate in Computer Science working on optimization and its application to healthcare operations. Michal has developed a new framework for multi-objective combinatorial optimization using dynamic programming. Independently, he has been working on modeling of US organ allocation policies through his collaboration with a lab from Johns Hopkins University School of Medicine. Currently, Michal works with a number of in-Kingdom clinical and governmental partners such as the Ministry of Health or the Saudi Center for Organ Transplantation to improve health of the Saudi population.