.png){kind=icon}
.png){kind=icon}
Return
A long-step, cutting plane algorithm for linear and convex programming
.png){kind=icon}
PRE
AI
DOI：10.1023/A:1019288816566.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
A cutting plane method for linear programming is described. This method is an extension of Atkinson and Vaidya's algorithm, and uses the central trajectory. The logarithmic barrier function is used explicitly, motivated partly by the successful implementation of such algorithms. This makes it possible to maintain primal and dual iterates, thus allowing termination at will, instead of having to solve to completion. This algorithm has the same complexity (O(nL(2)) iterations) as Atkinson and Vaidya's algorithm, but improves upon it in that it is a long-step version, while theirs is a short-step one in some sense. For this reason, this algorithm is computationally much more promising as well. This algorithm can be of use in solving combinatorial optimization problems with large numbers of constraints, such as the Traveling Salesman Problem.
Keywords:
cutting plane
path following
analytic center
linear programming
convex programming
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
4.5
Papers:
8.0K
Citations:
2.1W
Organization
No organization information available