Extensions of dynamic programming for multi-stage combinatorial optimization

Michal Mankowski*, Mikhail Moshkov

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

7 Citations (Scopus)
30 Downloads (Pure)


We propose a dynamic programming framework for an exact multi-stage (lexicographic) combinatorial optimization. Unlike conventional algorithms of dynamic programming that return one optimal solution, two dynamic programming algorithms proposed in this paper are coping with the whole set of optimal solutions or with its essential part. We describe the set of elements for optimization by a labeled directed acyclic graph, which in some sense, is similar to the structure of subproblems of the considered problem. For a given cost function (objective), the first algorithm constructs a subgraph of this graph that describes the whole set of optimal elements or its essential part. This algorithm can be used for multi-stage optimization of elements relative to a sequence of cost functions. The second algorithm counts elements before the optimization and after each optimization step. The considered labeled directed acyclic graph is a kind of circuit. This circuit builds the set of elements for optimization from one-element sets attached to input nodes. It uses the operation of union of sets attached to unifying nodes and functional operations attached to functional nodes. The algorithms for optimization and counting elements are defined for an arbitrary circuit without repetitions in which each element is generated exactly one time. For a considered problem with a known conventional dynamic programming solution algorithm, usually, it is easy to construct a corresponding circuit without repetitions. Once the circuit and cost functions are defined, our framework provides the correctness proofs and detailed time complexity analysis for the proposed algorithms. To make this approach more intuitive, we consider an illustrative example related to the maximum subarray problem. We tested our approach on the following nine combinatorial optimization problems: matrix chain multiplication, global sequence alignment, optimal paths in directed graphs, binary search trees, optimal bitonic tour, segmented least squares, convex polygon triangulation, one-dimensional clustering, and line breaking (text justification). We consider the last three problems in detail: construct a circuit without repetitions, describe at least two cost functions, evaluate a number of operations and time required by the algorithms, discuss an example, and consider the results of computer experiments with randomly generated instances of the problem.

Original languageEnglish
Pages (from-to)106-132
Number of pages27
JournalTheoretical Computer Science
Publication statusPublished - 6 Dec 2020

Bibliographical note

Funding Information:
Research reported in this publication was supported by King Abdullah University of Science and Technology (KAUST). The authors wish to express their thanks to Hassan Alsibyani for his collaboration in preparation illustrative example related to the maximum subarray problem. The authors are greatly indebted to the anonymous reviewers for useful comments and suggestions.

Publisher Copyright:
© 2020 Elsevier B.V.


Dive into the research topics of 'Extensions of dynamic programming for multi-stage combinatorial optimization'. Together they form a unique fingerprint.

Cite this