A finite procedure to generate feasible points for the extreme point mathematical programming problem (Q1103529): Difference between revisions

The author considers the extreme point mathematical programming problem: min\(\{\) c Tx: \(x\in Q\cap vert P\}\), where \(P=\{x:\) \(Ax=b\), \(x\geq 0\}\) and \(Q=\{x:\) Dx\(\leq d\}\). A is an \(m\times n\) matrix of full rank, and vert P denotes the set of the extreme points of P. In the paper a procedure is presented, which leads after a finite number of simplex iterations to one of the following three cases: (1) an original vertex \(x\in vert P\) is found, (2) \(Q\cap vert P=\emptyset\) or (3) a face \(P_ z\) of P is found with \(P_ z\cap Q\neq \emptyset\) and \(P_ z\cap Q\cap vert P=\emptyset.\) In case (3) so-called face cuts are applied which cut off the face \(P_ z\) but not an original vertex of P which belongs to Q, and the procedure is repeated. The construction of the face cuts is based on the following theorem: If a polyhedron \(\bar P\) contains an original vertex \(x\in vert P\), then the optimum of a corresponding set covering problem does not exceed m. Instead, solving the set covering problem, which is computationally expensive, lower and upper bounds are determined obtained by linear programming relaxation and heuristics, respectively. The presented procedure is applied to algorithms for the extreme point mathematical programming problem and the concave minimization problem with linear restrictions. Computational experience on both problems are also provided.