EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

3263. A generalization of the Weight Reduction algorithm

Invited abstract in session WB-30: Specialized Optimization Algorithms, stream Software for Optimization.

Wednesday, 10:30-12:00
Room: 064 (building: 208)

Authors (first author is the speaker)

1. Aurelio Oliveira
Computational & Applied Mathematics, UNICAMP
2. Carla Ghidini
University of Campinas
3. Jonathan Solis Hidalgo
Universidade Estadual de Campinas

Abstract

We propose a new linear programming algorithm that arises from the generalization of the weight reduction algorithm, which, in its turn, is based on the von Neumann algorithm. The algorithm developed by von Neumann has important features, such as fast initial convergence and low computational cost to obtain the search direction, which are inherited by both: the weight reduction algorithm and by the present generalization. However, its usefulness is limited due to considerably slow convergence. Thus, with the objective of improving the performance of the weight reduction algorithm, the idea is to consider more than two columns to compute the direction. It is computed considering p coordinates, choosing p/2 columns that form the smallest angles with the residue and p/2 columns for the largest angles. The advantage of this new algorithm is that by using more columns it is possible to find a better direction. Computational experiments are performed and the results show that with the new algorithm there is a faster decrease in the residual value as the p value increases. Also, the number of iterations and processing time necessary to determine a good solution for the problem, reduces with the value of p. The generalized algorithm can also be used together with other methods, such as interior point methods. It can be used, for instance, to obtain an advanced starting point and, thus, improving its efficiency.

Keywords

Status: accepted

Back to the list of papers