Home Events OPTIMA Seminar 23 Aug 2023 15:30 (AEST)


Aug 23 2023


3:30 pm - 5:00 pm



OPTIMA Seminar 23 Aug 2023 15:30 (AEST)

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

Speaker: Yukihiro Maruyama


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.

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

More Info


The event is finished.


Aug 23 2023


Melbourne Connect
Level M, 700 Swanston St, Carton

Advancing an industry-ready optimisation toolkit, while training a new generation of industry practitioners and over 120 young researchers, who will vanguard a highly skilled workforce of change agents for industrial transformation.

Monash University
Clayton, Victoria, 3080

University of Melbourne
Parkville, Victoria, 3010

© 2021 ARC Industrial Transformation Training Centre in Optimisation Technologies, Integrated Methodologies and Applications (OPTIMA)

Privacy Preference Center