In this dissertation, we consider extensions of dynamic programming for combinatorial optimization. We introduce two exact multiobjective optimization algorithms: the multistage optimization algorithm that optimizes the problem relative to the ordered sequence of objectives (lexicographic optimization) and the bicriteria optimization algorithm that simultaneously optimizes the problem relative to two objectives (Pareto optimization). We also introduce a counting algorithm to count optimal solution before and after every optimization stage of multistage optimization. We propose a fairly universal approach based on socalled circuits without repetitions in which each element is generated exactly one time. Such circuits represent the sets of elements under consideration (the sets of feasible solutions) and are used by counting, multistage, and bicriteria optimization algorithms. For a given optimization problem, we should describe an appropriate circuit and cost functions. Then, we can use the designed algorithms for which we already have proofs of their correctness and ways to evaluate the required number of operations and the time. We construct conventional (which work directly with elements) circuits without repetitions for matrix chain multiplication, global sequence alignment, optimal paths in directed graphs, binary search trees, convex polygon triangulation, line breaking (text justification), onedimensional clustering, optimal bitonic tour, and segmented least squares. For these problems, we evaluate the number of operations and the time required by the optimization and counting algorithms, and consider the results of computational experiments. If we cannot find a conventional circuit without repetitions for a problem, we can either create custom algorithms for optimization and counting from scratch or can transform a circuit with repetitions into a socalled syntactical circuit, which is a circuit without repetitions that works not with elements but with formulas representing these elements. We apply both approaches to the optimization of matchings in trees and apply the second approach to the 0/1 knapsack problem. We also briefly introduce our work in operation research with applications to health care. This work extends our interest in the optimization field from developing new methods included in this dissertation towards the practical application.
Date of Award  Oct 18 2020 

Original language  English (US) 

Awarding Institution   Computer, Electrical and Mathematical Science and Engineering


Supervisor  Mikhail Moshkov (Supervisor) 

 Dynamic Programming
 Combinatorial Optimization
 MultiObjective Optimization