Data Structures and Algorithms

   

Geometry Inspired Algorithms for Linear Programming

Authors: Dhananjay P. Mehendale

In this paper we discuss some novel algorithms for linear programming inspired by geometrical considerations and use simple mathematics related to finding intersections of lines and planes. All these algorithms have a common aim: they all try to approach closer and closer to “centroid” or some “centrally located interior point” for speeding up the process of reaching an optimal solution! Imagine the “line” parallel to vector C, where CTx denotes the objective function to be optimized, and further suppose that this “line” is also passing through the “point” representing optimal solution. The new algorithms that we propose in this paper essentially try to reach at some feasible interior point which is in the close vicinity of this “line”, in successive steps. When one will be able to arrive finally at a point belonging to small neighborhood of some point on this “line” then by moving from this point parallel to vector C one can reach to the point belonging to the sufficiently small neighborhood of the “point” representing optimal solution.

Comments: 17 pages.

Download: PDF

Submission history

[v1] 2015-03-28 06:17:24

Unique-IP document downloads: 63 times

Add your own feedback and questions here:
You are equally welcome to be positive or negative about any paper but please be polite. If you are being critical you must mention at least one specific error, otherwise your comment will be deleted as unhelpful.

comments powered by Disqus