An interior feasible direction method with constraint projections for linear programming

AbstractA new feasible direction method for linear programming problems is presented. The method is not boundary following. The method proceeds from a feasible interior point in a direction that improves the objective function until a point on a constraint surface is met. At this point searches are initiated in the hyperplane of constant function value by using projections of the bounding constraints until n bounding constraints are identified that yield a vertex as candidate solution. If the vertex is not feasible or feasible with a worse function value, the next iteration is started from the centre of the simplex defined by the identified points on the bounding constraint surfaces. Otherwise the feasible vertex is tested for optimality. If not optimal a perturbed point with improved function value on an edge emanating from the vertex is calculated from which the next iteration is started. The method has successfully been applied to many test problems