On deterministic parallel implementation of the branch-and-bound method on monotonic objects
Abstract:
This paper continues the authors’ research into development of a two-level system of deterministic parallel programming and creation of libraries of so-called monotone classes implemented in a universal object-oriented language, which constitutes the lower level of the system. The input language of the higher-level subsystem is like a functional language with the additional possibility of creating and using immutable and monotonic objects. The libraries of monotonic classes ensure that all programs in the higher-level sublanguage that use only monotonic classes are deterministic and idempotent when they are parallelized in the classical way by asynchronous calls of all functions. An essential part of the development of such a system is creation of the libraries of monotonic classes for various specific domains and examples of solving particular problems with their use. The paper is devoted to the specific task of implementing the search for the minimum weight of paths in a graph with edges labeled with nonnegative weights by the branch-and-bound method. A solution referred to as conditionally monotonic is given, where the monotonicity holds for nonnegative arc weights. The problem of the exact implementation of the branch-and-bound method on monotonic objects is stated.
Keywords:
models of parallel computation, deterministic programs, monotonic objects, branch-and-bound method
