Speaker
Description
Nowadays, the simplex method and the method of interior points remain the most popular methods for solving LP problems. The main issue with these methods is their limited scalability when solving large LP problems. The presentation is devoted to a new linear programming method called AlEMANN (Along Edges Movement with Artificial Neural Network), which uses an artificial neural network when choosing the directions of movement along the edges of the feasible polytope to the optimum point of the objective function. When solving the LP problem of dimension n with m constraints, at each iteration of the main loop, all edges originating from the current vertex are considered. The edge is a "segment" of a linear manifold L, which is an intersection of n-1 hyperplanes defined by constraints. To select an edge for movement, a local multidimensional visual image of the manifold L is constructed at the startpoint. This image consists of O(n) "pixels". Each pixel is represented by one real number. This image is fed to the feedforward neural network. The output of neural network is a set of n-2 cosines, which are used to compute the movement vector along the investigated edge in the direction of increasing of the objective function. As a result of the selection, an edge is chosen that has the largest value of the objective function at the endpoint. The AlEMANN method has exponential time complexity. The space complexity of the AlEMANN method is O(nm). The described method is highly scalable, since each edge can be processed independently. The neural network consists of 4 fully connected layers with the ReLU activation functions. To build the training dataset, we used a random LP problem generator and the AlEM algorithm, which requires performing the time-consuming pseudoprojecting operation. Network training and hyperparameter optimization were performed on the "Neurocomputer SUSU" computing system. A parallel implementation of the AlEMANN method in C++ using the MPI library and OpenMP technology is performed. The large-scale computational experiments have been conducted on the supercomputer "Tornado SUSU" to solve large-scale LP problems. The experiments have confirmed the efficiency of the proposed approaches.
