A0382
Title: Feasibility probability of random linear programming
Authors: Wei Zhang - South China University of Technology (China) [presenting]
Abstract: The linear feasibility problem, that is, $Ax=b$, $x>0$ is basic in linear programming, statistical physics and biological mathematics. When the system has a solution, i.e., the system is feasible. It is noticed that when the elements of matrix A and vector b are stochastically generated according to some probability distribution, there is a transition between feasibility and infeasibility. Especially when the mean value and variance of the distribution vary or when the number of rows and columns of A varies, the fraction of the feasible instances will change accordingly. An analytical method is given to derive the feasibility probability of the system to tell how many random instances have a solution.
