We present a strongly polynomial algorithm for linear optimization problems of the form min{cx|Ax = b, x >= 0} having 0-1 vectors among their optimal solutions. The algorithm runs in time O(n^4*max\{m,log n}), where n is the number of variables and m is the number of equations. The algorithm also constructs necessary and sufficient optimality conditions for 0-1 solutions in the form of a linear system.
Article
View A strongly polynomial algorithm for linear optimization problems having 0-1 optimal solutions