Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

A Computational Test of Khachian's Algorithm for Linear Inequalities

IP.com Disclosure Number: IPCOM000128558D
Original Publication Date: 1979-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 5 page(s) / 20K

Publishing Venue

Software Patent Institute

Related People

J.B. Rosen: AUTHOR [+4]

Abstract

Khachian's algorithm for solving a system of linear inequalities is tested computationally for very simple problems. For these problems it is very inefficient, compared to the Simplex method, and appears to be numerically unstable. *This research was supported by the Computer Science Section of the National Science Foundation under Grant MCS 76-23311.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 30% of the total text.

Page 1 of 5

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

A Computational Test of Khachian's Algorithm for Linear Inequalities

by J.B. Rosen and Gail Frawley

Computer Science Department

136 Lind Hall Institute of Technology University of Minnesota Minneapolis, Minnesota Technical Report 79-28 November 1979 Cover design courtesy of Ruth and Jay Leavitt. A Computational Test of Khachian's Algorithm for Linear Inequalities*

by J.B. Rosen and Gail Frawley

Abstract

Khachian's algorithm for solving a system of linear inequalities is tested computationally for very simple problems. For these problems it is very inefficient, compared to the Simplex method, and appears to be numerically unstable. *This research was supported by the Computer Science Section of the National Science Foundation under Grant MCS 76-23311.

1. Introduction

The algorithm for solving a system of linear inequalities with integer coefficients published recently by Khachian [lJ has justifiably attracted considerable interest. Khachian's algorithm will determine if the system of linear inequalities

(Equation Omitted)

has a solution, and if so, it will find one in no more than 6n2L steps, where L is the space needed to state the problem. The calculations must be carried out to high precision to achieve this result.

More recently, Gacs and Lovasz j2] have analyzed Khachian's algorithm and supplied the proofs not given in the original publication.

The theoretical significance of Khachian's algorithm is that its worst case behavior is polynomial, as compared to the worst case behavior of the Simplex algorithm which is exponential.

A very important practical question is how the typical behavior of Khachian's algorithm compares with that of the Simplex method for the type of problems normally encountered. A general answer to this question will probably require computational tests of Khachian's algorithm for a variety of problems.

Nevertheless some insight into the practical behavior of Khachian's algorithm can be obtained by relatively easy computational tests. This note gives the results obtained for two simple test problems. The con-clusion is that at least for small problems Khachian's algorithm is very inefficient and apparently numerically unstable.

University of Minnesota Page 1 Dec 31, 1979

Page 2 of 5

A Computational Test of Khachian's Algorithm for Linear Inequalities

2. The Algorithm and Test Problems The Khachian algorithm may be stated as follows: Start with x0 = 0, and AO = 2LI, where I is the nxn identity matrix. Step 1. Given

(Equation Omitted)

for feasibility. Compute

(Equation Omitted)

If

(Equation Omitted)

Stop. xk is a feasible point. Step 2. Find max

(Equation Omitted)

Update xk and A k: i

> <> 2

(Equation Omitted)

where

(Equation Omitted)

Return to step 1.

Note that the initial step from the origin is in the direction - at, so as to satisfy the most violated constraint. In the original version of [2], there was a sign error in the expression for upd...