Finding all solutions of piecewise-linear circuits by using linear programming

✍ Scribed by Kiyotaka Yamamura; Shigeru Tanaka

• Publisher: John Wiley and Sons
• Year: 2001
• Tongue: English
• Weight: 254 KB
• Volume: 84
• Category: Article
• ISSN: 1042-0967
• DOI: 10.1002/ecjc.1016

✦ Synopsis

Abstract

An efficient algorithm is proposed for finding all solutions of piecewise‐linear (PWL) resistive circuits using linear programming (LP). This algorithm is based on a simple test (termed the LP test) for nonexistence of a solution to a system of PWL equations of the form Pg(x) + Qx – s = 0 in a given region. In the LP test, the system of PWL equations is transformed into an LP problem, to which the simplex method is applied. Such an LP problem is obtained by surrounding the PWL functions by rectangles. In this paper, it is shown that the LP test can be performed very efficiently mostly by Phase II of the simplex method. Using the proposed techniques, the number of pivotings in the LP test becomes much smaller, which makes the algorithm very efficient. By numerical examples, it is shown that the proposed algorithm could find all solutions of relatively large scale circuits (including those where the number of variables is 200 and the number of linear regions is 10^200^) in practical computation time. © 2001 Scripta Technica, Electron Comm Jpn Pt 3, 84(7): 1–11, 2001