Volume 19, No 5, 2012, P. 83-100

UDC 519.87+519.854
A. V. Plyasunov, A. A. Panin
The pricing problem. Part I. Exact and approximate algorithms

Abstract:
We consider the mill pricing problem which is shown to be NP-hard in the strong sense. To solve this problem, some exact and approximate algorithms based on decomposition, genetic local search, and tabu search are developed. Results of the computing experiments are given.
Tab. 3, bibliogr. 25.

Keywords: NP-hard in the strong sense, the bilevel pricing problem, minimax problem, decomposition, local search, tabu search, genetic algorithm, hybrid algorithm.

Plyasunov Alexander Vladimirovich ^1,2
Panin Artem Alexandrovich ^1,2
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
2. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: apljas@math.nsc.ru, arteam1897@gmail.com