Skip to main content
Сроки выполнения

Abstract of the Project. The purpose of the project is the development of effective numerical methods, algorithms and programs of solving the problems of rectangular cutting for a broad class of practical problems.

Actuality. The combinatorial optimization is one of the most important parts of mathematical programming. Already from the  origin of combinatorial optimization it has become clear, that the use of discrete models expands an orb of application of methods of optimization. The computational complexity of problems of combinatorial optimization forces the contributors to go on a way of construction of approximate algorithms, and also on a way of constant accumulation of private(individual) models, for which the construction of effective polynomial algorithms is possible.

As rectangular cutting is the important applied section of combinatorial optimization, the indicated tendencies are characteristic and for it too. In the papers of the scientific chief of the project the scientific direction was generated which roughly is possible to call « polynomial algorithms of rectangular cutting », which is unique and is confirmed by the publications in the journals with IF..

The methodology of a scientific research. The following ways of investiagtion are assumed: choice of appropriate means of number theory (method of continuous fractions), theory of algorithms and methods of linear integer programming.

Expected outcomes. In an outcome of realization of the project will be obtained next results: the mathematical models of diverse problems of rectangular cutting; the effective polynomial algorithms of solving rectangular cutting problems for a broad class of practical problems, the implementation of programs of solving rectangular cutting problems for a broad class of practical problems.

The potential consumers. The enterprises of machine-building complex, metallurgical enterprises, wood and grass enterprises of Kazakhstan, Russia and other countries.

The goal and problems of project: The goal of project is development of mathematical models, numerical methods and complex of the programs of rectangular cutting problems for wide number of practical rectangular cutting problems.

Keywords: rectangular cutting, polynomial algorithms, knapsack problems, decomposition of problems.