CONNECTIONIST NETWORKS FOR PIVOT SELECTION IN LINEAR-PROGRAMMING

Linear programming (LP) has sparked great interest among scientists du e to its practical and theoretical importance. LP plays a special role in optimization theory: in one sense, it is a continuous optimization problem (first optimization problem) because the decision variables a re real numbers, but it also may be considered a combinatorial optimiz ation problem to identify an optimal basis containing certain columns from the constraint matrix (second optimization problem). As a case st udy, we describe a novel transformation from clausal form Conjunctive Normal Form Satisfaction problem (CNF-SAT) to an integer linear progra mming model. The resulting matrix has a regular structure and is no lo nger problem-specific. It depends just on the number of clauses and th e number of variables, but not on the structure of the clauses. The st ructure of the integer program allows to solve it by means of standard linear programming techniques. Then we describe several connectionist network paradigms to solve the second optimization problem. Some of t hese networks are effective in solving this problem as shown in signif icant tests. The connectionist approach is compared with a standard Li near Programming (LP) procedure, and with a more recent hybrid LP tech nique. A performance summary and final comments show the usefulness of the neural network proposal.