A note on probability assignments in estimating the time to solve linear programs

AbstractExterior-point linear programming algorithms have been modelled as a Markov chain in order to model the transitions between extreme points. This approach is useful in that it ultimately provides a confidence interval on the expected number of pivots.This paper provides an alternative to the assumption of equally likelihood from one state to animproved state. Other considerations such as cycling and multiple solutions are considered