Страница публикации

Using Merging Variables-Based Local Search to Solve Special Variants of MaxSAT Problem

Авторы: Otpuschennikov I.V., Semenov A.A.

Журнал: Communications in Computer and Information Science: 19th Intern. Conf. on Mathematical Optimization Theory and Operations Research (MOTOR 2020; Novosibirsk, 6-10 July 2020)

Том: 1275

Номер:

Год: 2020

Отчётный год: 2020

Издательство:

Местоположение издательства:

URL:

Проекты:

DOI: 10.1007/978-3-030-58657-7_29

Аннотация: In this paper we study the inversion of discrete functions associated with some hard combinatorial problems. Inversion of such a function is considered in the form of a special variant of the well-known MaxSAT problem. To solve the latter we apply the previously developed local search method based on the Merging Variables Principle (MVP). The main novelty is that we combine MVP with evolutionary strategies to leave local extrema generated by Merging Variables Hill Climbing algorithm. The results of computational experiments show the effectiveness of the proposed technique in application to inversion of several cryptographic hash functions and to one problem of combinatorial optimization, which is a variant of the Facility Location Problem.

Индексируется WOS: Нет

Индексируется Scopus: Нет

Индексируется УБС: Нет

Индексируется РИНЦ: Нет

Индексируется ВАК: Нет

Индексируется CORE: Нет

Публикация в печати: 0