The minimum mean cycle-canceling algorithm for linear programs

doi:10.1016/j.ejor.2021.09.022

The minimum mean cycle-canceling algorithm for linear programs

2022-04-01

2

OA

AI

J

Jean Bertrand Gauthier *

J

Jacques Desrosiers

DOI：10.1016/j.ejor.2021.09.022

原文链接

查看原文

摘要

En 中文

This paper presents the properties of the minimum mean cycle-canceling algorithm for solving linear programming models. Originally designed for solving network flow problems for which it runs in strongly polynomial time, most of its properties are preserved. This is at the price of adapting the fundamental decomposition theorem of a network flow solution together with various definitions: that of a cycle and the way to calculate its cost, the residual problem, and the improvement factor at the end of a phase. We also use the primal and dual necessary and sufficient optimality conditions stated on the residual problem for establishing the pricing step giving its name to the algorithm. It turns out that the successive solutions need not be basic, there are no degenerate pivots, and the improving directions are potentially interior in addition to those on edges. For solving an m x n linear program, it requires a pseudo-polynomial number O (n A) of so-called phases, where A depends on the number of rows and the coefficient matrix. (c) 2021 Elsevier B.V. All rights reserved.

Keyword:

Linear program

Residual problem

Cycle cancellation

Complexity analysis

Interior direction

The minimum mean cycle-canceling algorithm for linear programs

摘要

AI总结

期刊

机构