# Extensions of Dynamic Programming for Combinatorial Optimization and Data Mining

Mikhail Moshkov

► To cite this version:

Mikhail Moshkov. Extensions of Dynamic Programming for Combinatorial Optimization and Data Mining. 4th International Conference on Intelligence Science (ICIS), Feb 2021, Durgapur, India. pp.313-317, 10.1007/978-3-030-74826-5. hal-03744111

HAL Id: hal-03744111

https://inria.hal.science/hal-03744111v1

Submitted on 2 Aug 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
Extended Abstract
Extensions of Dynamic Programming
for Combinatorial Optimization
and Data Mining

Mikhail Moshkov

Computer, Electrical and Mathematical Sciences & Engineering Division,
King Abdullah University of Science and Technology (KAUST),
Thuwal 23955-6900, Saudi Arabia
mikhail.moshkov@kaust.edu.sa

**Abstract.** In contrast with conventional dynamic programming algorithms that return one solution, extensions of dynamic programming allows us to work with the whole set of solutions or its essential part, to perform multi-stage optimization relative to different criteria, to count the number of solutions, and to find the set of Pareto optimal points for bi-criteria optimization problems. The presentation is based on the results considered in three books published or accepted by Springer.

**Keywords:** Dynamic programming extensions · Bi-criteria optimization · Multi-stage optimization

The conventional dynamic programming algorithms for optimization problems include a structure of sub-problems of the initial problem, a way to construct a solution for a sub-problem from solutions of smaller sub-problems, and solutions for the smallest sub-problems. Such algorithms return only one solution.

In books [1–3] we consider extensions of dynamic programming that allow us (i) to make multi-stage optimization relative to a sequence of criteria, (ii) to describe the whole set of solutions or its essential part, (iii) to count the described solutions, and (iv) to construct the set of Pareto optimal points for a bi-criteria optimization problem. In this presentation, we discuss mainly results considered in the book [1] and mention some results presented in the books [2, 3].

In [1], we apply extensions of dynamic programming to the study of decision trees and rules for conventional decision tables with single-valued decisions, to the optimization of element partition trees for rectangular meshes which are used in finite element methods for solving PDEs, and to multi-stage optimization for such classic combinatorial optimization problems as matrix chain multiplication, binary search trees, global sequence alignment, and shortest paths.

In particular, for the decision trees, the applications of multi-stage optimization include the study of totally optimal (simultaneously optimal relative to a number of cost functions) decision trees for Boolean functions, improvements on the bounds on the depth of decision trees for diagnosis of constant faults in read-once circuits over monotone basis, computation of minimum average depth for a decision tree for sorting eight elements (a problem that was open since 1968), study of optimal reducts and
decision trees for modified majority problem, and designing an algorithm for the problem of reduct optimization.

The applications of bi-criteria optimization include the comparison of different greedy algorithms for construction of decision trees, analysis of trade-offs for decision trees for corner point detection (used in computer vision), study of derivation of decision rules from decision trees, and a new technique called multi-pruning of decision trees which is used for data mining, knowledge representation, and classification. The classifiers constructed by multi-pruning process often have better accuracy than the classifiers constructed by CART.

In [2], we generalize the considered tools to the case of decision tables with many-valued decisions. We also study inhibitory trees and rules, which instead of expressions "decision = value" use expressions "decision ≠ value". Inhibitory trees and rules can, sometimes, describe more information derivable from a decision table than decision trees and rules.

In [3], we apply the extensions of dynamic programming including multi-stage and bi-criteria optimization, and counting of optimal solutions to the following 11 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, matchings in trees, and 0/1 knapsack problem.

**Acknowledgments.** Research reported in this publication was supported by King Abdullah University of Science and Technology (KAUST).

## References

1. AbouEisha, H., Amin, T., Chikalov, I., Hussain, S., Moshkov, M.: Extensions of Dynamic Programming for Combinatorial Optimization and Data Mining, Intelligent Systems Reference Library, vol. 146. Springer (2019). https://doi.org/10.1007/978-3-319-91839-6

2. Alsolami, F., Azad, M., Chikalov, I., Moshkov, M.: Decision and Inhibitory Trees and Rules for Decision Tables with Many-valued Decisions, Intelligent Systems Reference Library, vol. 156. Springer (2020). https://doi.org/10.1007/978-3-030-12854-8

3. Mankowski, M., Moshkov, M.: Dynamic Programming Multi-Objective Combinatorial Optimization, Studies in Systems, Decision and Control, vol. 331. Springer (2021). https://doi.org/10.1007/978-3-030-63920-4
Author Index

Atan, Özkan 255

Behera, Shreetam 217

Bera, Subrata 263

Beziau, Jean-Yves 25

Bhattacharjee, Kamalika 273

Biswas, Mainak 285

Castillo, Oscar 255

Chakraborty, Basabi 149, 241

Chakraborty, Moitri 285

Chatterjee, Sayan 285

Das, Sukanta 273

Datta, D. 196

De, Anupam 229, 291

Dogra, Debi Prosad 217

Dubois, Didier 79

Dutta, Dipanwita 285

Dutta, Soma 37

Gajjala, Kavya Sree 149, 241

Ganesan, K. 196

Ghosh, Madhumita 285

Han, Bin 185

Hirano, Shoji 173

Jayaraman, Premaladha 303

Jian, Zhiwen 137

Kádek, Tamás 93

Kar, Samarjit 209, 303

Khatua, Debnarayan 229

Kimura, Tomohiro 173

Kothamachu Ramesh, Ashika 149, 241

Krishankumar, R. 209, 303

Kurra, Shaily Preetham 217

Kutlu, Fatih 255

Liu, Ga-Qiong 185

Lu, Chenguang 103

Maiti, Manoranjan 229, 291

Maity, Akash 285

Maity, Kalipada 229, 291

Manyam, Rajsekhar Reddy 209

Mihálydeák, Tamás 66, 93

Moshkov, Mikhail 315

Nagy, Dávid 93

Nakano, Kotaro 149, 241

Ofori, Kwame Dwomoh 185

Pagliani, Piero 49

Panigrahi, Goutam 229, 291

Prade, Henri 79

Prasad, Dilip K. 125

Quek, Chai 125

Ramesh, G. 196

Ravichandran, K. S. 209, 303

Sakai, Hiroshi 137

Sangeetha, V. 209

Sekh, Arif Ahmed 125

Shi, Chengjun 115

Shi, Zhongzhi 3

Silahtar, Onur 255

Sivagami, R. 209

Skowron, Andrzej 37

Sudha, G. 196

Sundaram, Ramakrishnan 303

Tsumoto, Shusaku 173

Wang, Dong-Sheng 185

Wang, Hua-Yu 185

Wang, Maoguang 159

Wang, Qi 185

Wang, Shi 185

Xiong, Chuyu 13

Yang, Hang 159

Yao, Yiyu 115

Zhang, Jing 185

Zhao, Cui-Ping 185

Zhe, Quah En 125