2018/03/14 by Masaya Tano, Tano, Masaya, Ryuhei Miyashiro +3
Computer Science · Engineering · Mathematics · #90C05 #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Packing Problems #Polynomial and algebraic computation #math.OC #msc:90C05
paper · pdf · doi:10.48550/arxiv.1803.05167
16 pages
arxiv created 2018/03/14 · openalex publication_date 2018/03/14 · arxiv updated 2018/03/15 · openalex created_date 2018/03/29 · openalex updated_date 2026/07/28
In this paper, we propose a p-norm rule, which is a generalization of the steepest-edge rule, as a pivoting rule for the simplex method. For a nondegenerate linear programming problem, we show upper bounds for the number of iterations of the simplex method with the steepest-edge and p-norm rules. One of the upper bounds is given by a function of the number of variables, that of constraints, and the minimum and maximum positive elements in all basic feasible solutions.