The use of a special-purpose VLSI chip for solving a linear programming problem is presented. The chip is structured as a mesh of trees and is designed to implemented the well-known simplex algorithm. A high degree of parallelism is introduced in each pivot step, which can be carried out in O(log n) time using an m multiplied by m mesh of trees having an O(mn log m log**3 n) area where m-1 and n-1 are the number of constraints and variables, respectively. Two variants of the simplex algorithm are also considered: the two-phase method and the revised one. The proposed chip is intended as a possible basic block for a VLSI operations research machine.
A VLSI IMPLEMENTATION OF THE SIMPLEX ALGORITHM
BONUCCELLI, MAURIZIO ANGELO
1987-01-01
Abstract
The use of a special-purpose VLSI chip for solving a linear programming problem is presented. The chip is structured as a mesh of trees and is designed to implemented the well-known simplex algorithm. A high degree of parallelism is introduced in each pivot step, which can be carried out in O(log n) time using an m multiplied by m mesh of trees having an O(mn log m log**3 n) area where m-1 and n-1 are the number of constraints and variables, respectively. Two variants of the simplex algorithm are also considered: the two-phase method and the revised one. The proposed chip is intended as a possible basic block for a VLSI operations research machine.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.