Premium
A feasible‐point algorithm for structured design systems in chemical engineering
Author(s) -
Debrosse Charles J.,
Westerberg Arthur W.
Publication year - 1973
Publication title -
aiche journal
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.958
H-Index - 167
eISSN - 1547-5905
pISSN - 0001-1541
DOI - 10.1002/aic.690190208
Subject(s) - simplex algorithm , point (geometry) , mathematical optimization , simplex , algorithm , linear programming , mathematics , interior point method , feasible region , conjecture , computer science , discrete mathematics , combinatorics , geometry
Structured design systems are systems in which the equations representing the equality and inequality constraints are sparse and highly precedenc orderable. An algorithm has been developed for such systems which is guaranteed, under certain assumptions, to arrive in a finite number of steps at a feasible point (that is, one which satisfies all the constraints) or to identify a subset of the constraints for which no feasible point can be found. The algorithm can be applied to a system with only inequality constraints or to a system with both equality and inequality constraints. The algorithm uses an indirect approach. It hypothesizes that a subset of constraints has no feasible region and then attempts to verify this conjecture. If successful, the subset is identified as infeasible and obviously no feasible point exists. If unsuccessful, either a new hypothesis can be generated or the algorithm has indirectly found a feasible point. Limited computational experience with the algorithm indicates that the number of steps required to find a feasible point for a system of constraints has been of the same order of magnitude as the total number of constraints in the system. For linear constraints, the efficiency of the algorithm has been comparable to phase one of the Simplex algorithm of Linear Programming.