NETWORK CONSTRAINED SECURITY CONTROL USING AN INTERIOR-POINT ALGORITHM

Karmarkar's interior point method, said to perform much faster than the simplex method in solving large scale linear programming problems, has attracted a great deal of attention in recent years. In this paper we present a preliminary implementation of the interior point algorithm and test results on the network constrained security control problem. Test results indicate that when solving various sizes of network constrained security control linear programming problems with increasing numbers of controls and constraints, both the total number of iterations and the overall execution time grow at a slower rate in the interior point method than in the simplex method. The number of iterations required by the interior point method is relatively insensitive to problem size and composition, while iteration counts for the simplex method tend to be much higher in the presence of large numbers of control variables and/or constraints.