INTEGRAL LATTICES ON A PLANE IN DISCRETE OPTIMIZATION PROBLEMS

The proposed work consists of two parts. The first of these is devoted to the analytical image of integer lattices on the Cartesian plane. Numbering of points with integral coordinates, i. e. integral points, was carried out using the scheme described by the famous Polish mathematician V. Sierpinski without giving any functional dependencies. Its gist is as follows: starting from the origin, point number 1, a polygonal spiral is built, in an anticlockwise direction which passes through the integral points with the links of unit length. Vertices of the polygon are sequentially assigned numbers 2, 3, ... . (Traversal of the lattice can be performed against the clockwise direction.) Analytical description of such numbering was carried out (via entier) through representation in closed form – with one formula – of sums of sequences composed of series (tuples) whose elements are constants. The found ratios made it possible to reproduce, in the parametric form, functional relationship between the numbers of integral points – lattice sites – and their coordinates: and , as well as determine the number of the site through the given point coordinates: . On this basis, the second part of the paper considers the possibility of using an analytical description of the numbering of lattice points to solve discrete (integer) optimization problems. The use of integer lattice allows avoidance of preliminary solution of the mathematical programming problem with the weakened constraints, i. e. excluding the requirements of an integer variable, as is done in the methods of pruning and combinatorial methods. Finding the optimum of the objective function is carried out directly on the set of lattice points – a subset of the domain of admissible values of the variables. This approach is called the method of Applying the Integer Lattice (AIL). AIL method implementation is shown in the illustrative example. Bibliographic search of information on scientific papers concerning numbering of all the points on the integer plane and its application to discrete optimization problems gave no positive results