A feasibility conjecture related to the Hirsch conjecture
Operations Research Center, Institute of Engineering Research, University of California, 1964 - Mathematics - 28 pages
A very important unsolved problem in linear programming today is the validity or nonvalidity of the conjecture which follows: Hirsch Conjecture: Let X and Y be feasible bases to the linear programming problem Y > or = O, X > or = O, IY + BX = b and let m be the rank of this system. Then the conjecture is that there exists a sequence of m feasible pivot operations that transforms the system into Y > or = O , X > or = O, (1/B)Y + IX = (1/B)b. That is to say a sequence such that each of the m - l intermediate bases is feasible.
What people are saying - Write a review
We haven't found any reviews in the usual places.
actually false bases basic solution obtained basic variable BERKELEY canonical form Clearinghouse column vector components of b^m conditions of corollary conditions of lemma Conjecture is actually contain at least corresponding counter counter-example Dantzig conjecture holds DEFENSE DOCUMENTATION CENTER Deleting Department of Commerce diagonal drop equivalent problem exists a pair FEASIBILITY CONJECTURE RELATED feasible basis feasible pivot operations feasible pivots going feasible pivots required follows form with respect HIRSCH CONJECTURE introduced linear programming Multiply nondegenerate nonsingular square matrix number of feasible number required original problem pair of variables pair Xj pivot operations required positive element problem of rank Proof properties Replace required to go RESEARCH CENTER respect to Y^m Richard Wollmer satisfied sequence of feasible strictly positive successive feasible sufficiently small Suppose theorem tion unique unity University of California USERS variables Xj X2 1 xl yields Yj^j yk(j yl 1 Table zero