A Theoretical Approach and a Numerical Method for Finding a Quasi-Optimal Solution to a Nonlinear High-Dimensional Discrete Problem

Mark Gorskiy
Additional contact information
Mark Gorskiy: GK Rest-Group, Moscow, Russia

HSE Economic Journal, 2019, vol. 23, issue 3, 465-482

Abstract: At present, the class of NP-complete problems is represented not only by the «classical» issue of the travelling salesman problem and many tasks in the theory of graphs and networks, resolved into it, but also by the problems of nonlinear and stochastic optimization, including, in the discrete setting. The peculiarity of these problems is the lack of constructive algorithms forfinding the optimal solution in polynomial time from the dimension of the problem, which «dooms» the researcher to use non-constructive methods in solving these problems, for example, the exhaustive algorithm. However, these algorithms, being applied to discrete optimization problems, do not allow to solve the problem in a complex way: for example, such methods do not let us obtain dual constraints estimation that are important for the subsequent analysis of the optimal solution. In the article, for a wide class of problems of production and financial planning, which, in the production plan, are reduced to the problems of discrete nonlinear convex optimization of large dimension, the author offers an original numerical method for finding a quasi-optimal solution with a high (predetermined) accuracy of approximation to the optimum. For the specified class of problems, the proposed method is universal, i.e. it can be applied without additional adaptation of the numerical procedure.

Keywords: NP-complete problem; linear and nonlinear optimization; nonlinear discrete problem; production and financial planning problems; constructive algorithm; quasi-optimal solution (search for similar items in EconPapers)
JEL-codes: C65 D29 (search for similar items in EconPapers)
Date: 2019
References: Add references at CitEc
Citations:

Downloads: (external link)
https://ej.hse.ru/en/2019-23-3/316319210.html (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hig:ecohse:2019:3:6

Access Statistics for this article

More articles in HSE Economic Journal from National Research University Higher School of Economics
Bibliographic data for series maintained by Editorial board () and Editorial board ().