Optimization Online


A polynomial algorithm for linear optimization which is strongly polynomial under certain conditions on optimal solutions

Sergei Chubanov (sergei.chubanov***at***uni-siegen.de)

Abstract: This paper proposes a polynomial algorithm for linear programming which is strongly polynomial for linear optimization problems $\min\{c^Tx : Ax = b, x\ge {\bf 0}\}$ having optimal solutions where each non-zero component $x_j$ belongs to an interval of the form $[\alpha_j, \alpha_j\cdot 2^{p(n)}],$ where $\alpha_j$ is some positive value and $p(n)$ is a polynomial of the number of variables. We do not impose any additional restrictions on $c$ and $A.$ This class of problems includes linear optimization problems having 0-1 optimal solutions and the Markov Decision Problem with a fixed discount factor as special cases. We also discuss a class of linear-programming relaxations of 0-1 integer problems that can be solved in strongly polynomial time by our algorithm.

Keywords: Linear programming, polynomial algorithm, strongly polynomial algorithm.

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )


Download: [PDF]

Entry Submitted: 12/28/2014
Entry Accepted: 12/29/2014
Entry Last Modified: 02/01/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society