Title: Knapsack problems as nondeterministic sequential decision processes and its solution method

Speaker: Yukihiro Maruyama

Summary:

Yukihiro Maruyama has been studying the relation between a given nondeterministic discrete decision process (nd-ddp) and a nondeterministic sequential decision process (nd-sdp), which is a finite nondeterministic automaton with a cost function, and its subclasses (nd-msdp, nd-pmsdp, nd-smsdp). He showed super-strong representation theorems for nd-sdp and its subclasses, for which the functional equations of nondeterministic dynamic programming are obtainable. The theorems provide necessary and sufficient conditions for the existence of the nd-sdp and its subclasses with the same set of feasible policies and the same cost value for every feasible policy as the given process nd-ddp. The process (nd-ddp) represented by the sequential decision process (nd-sdp) is applicable for various types of discrete optimization problems, for example, nondeterministic shortest path problem (nd-msdp), an egg-dropping problem (nd-pmsdp), and 0-1 knapsack problems. This talk will concentrate on the knapsack problems as nondeterministic sequential decision processes and its solution method. First, it will show that a nondeterministic knapsack problem can be formulated as the process (nd-ddp) and a nondeterministic finite automaton with objective function, namely, the process (nd-msdp) can super-strongly represent the process (nd-ddp). Next, it will describe some solution methods to obtain optimal solutions by using recursive equations.

Biography:
Yukihiro Maruyama is a Professor of Decision Making at Nagasaki University in Japan, and now visiting academic of OPTIMA until 18th of September. He also had been a visiting academic of the University of Melbourne from 2000 to 2001. His major study is nondeterministic sequential decision processes (nd-sdp) and its applications, namely, shortest path problems and knapsack problems. Another research area is Data Envelopment Analysis. He educates PhD students of the Faculty of Economics in Nagasaki University about the Data Envelopment Analysis and its applications to various areas, for example, medical sector, entrepreneurship education and so on. Recently, he is so interested in some practical problems formulated as the process (nd-sdp).

MEETING ID: 873 1557 5255; PASSWORD: 778635

WED 23 August 15:30-17:00 (AEST, Melbourne Time)
Hybrid Event: Melbourne Connect: Combined M01+M02 and Zoom