An exterior-point polytope sliding and deformation algorithm for linear programming problems

Article type: Research Article

Authors: Sherali, Hanif D. | Choi, Gyunghyun | Sen, Suvrajeet

Affiliations: Department of Industrial and Systems Engineering, Virginia Polytechnic Institute and State University, Blacksbur, Virginia 24061–0118. E-mail: [email protected], [email protected] | Department of Systems and Industrial Engineering, University of Arizona, Tucson, Arizona 85721. E-mail: [email protected]

Abstract: In this research, we develop an algorithm for linear programming problems based on a new interpretation of Karmarkar's representation for this problem. Accordingly, we examine a suitable polytope for which the origin is an exterior point, and in order to determine an optimal solution, we need to ascertain the minimum extent by which this polytope needs to be slid along a one-dimensional axis so that the origin belongs to it. To accomplish this, we employ strongly separating hyperplanes between the origin and the polytope using a closest point routine. The algorithm is further enhanced by the generation of dual solutions which enable us to deform the polytope so that it is favorably positioned with respect to the origin and the axis of sliding motion. The overall scheme is easy to implement, requires a minimal amount of storage, and produces quick good quality lower bounds for the problem in its infinite convergence process. A switchover to the simplex method or an interior point method is also possible, using the current available solution as an advanced start. Preliminary computational results are provided along with implementation guidelines.

Keywords: linear programming, exterior point method, Karmarkar's algorithm

DOI: 10.3233/INF-1997-8406

Journal: Informatica, vol. 8, no. 4, pp. 559-582, 1997