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

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.
Bertossi, Aa; Bonuccelli, MAURIZIO ANGELO
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11568/10510
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 4
social impact