Gravity Sliding Algorithm for Linear Programming

Pei-Zhuang Wang (), Ho-Chung Lui (), Hai-Tao Liu () and Si-Cong Guo ()
Additional contact information
Pei-Zhuang Wang: Liaoning Technical University
Ho-Chung Lui: Eagle IP Ltd
Hai-Tao Liu: Liaoning Technical University
Si-Cong Guo: Liaoning Technical University

Annals of Data Science, 2017, vol. 4, issue 2, No 3, 193-210

Abstract: Abstract An algorithm named Gravity Sliding is presented in the paper, which emulates the gravity sliding motion in a feasible region D constrained by a group of hyper planes in $$R^{m}$$ R m . At each stage point P of the sliding path, we need to calculate the projection of gravity vector g on constraint planes: if a constraint plane blocks the way at P, then it may change the direction of sliding path. The core technique is the synthetical treatment for multiple blocking planes, which is a basic problem of structural adjustment in practice; while the whole path provides the solution of a linear programming. Existing LP algorithms have no intuitive vision to emulate gravity sliding, therefore, their paths are not able to avoid circling and roving, and they could not provide a best direction at each step for structural adjustment. The first author presented the algorithm Cone Cutting (Wang in Inf Technol Decis Mak 10(1):65–82, 2011), which provides an intuitive explanation for Simplex pivoting. And then the algorithm Gradient Falling (Wang in Ann Data Sci 1(1):41–71, 2014. doi: 10.1007/s40745-014-0005-9 ) was presented, which emulates the gradient motion on the feasible region. This paper is an improvement of gradient falling algorithm: in place of the description focusing on the null subspace of norm vectors, we focus the description on the expanding subspace of the very vectors in this paper. It makes the projection calculation easier and faster. We guess that the sliding path realized by the algorithm is the optimal path and the number of stage points of the path is limited by a polynomial function of the dimension number and the number of constraint planes.

Keywords: Strongly polynomial algorithm; Cone-cutting; Gravity sliding path; Projection calculation; Structural adjustment; 90C05 (search for similar items in EconPapers)
Date: 2017
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s40745-017-0108-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:aodasc:v:4:y:2017:i:2:d:10.1007_s40745-017-0108-1

Ordering information: This journal article can be ordered from
https://www.springer ... gement/journal/40745

DOI: 10.1007/s40745-017-0108-1

Access Statistics for this article

Annals of Data Science is currently edited by Yong Shi

More articles in Annals of Data Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().