Premium
Finding all solutions of piecewise‐linear resistive circuits using the dual simplex method
Author(s) -
Yamamura Kiyotaka,
Tanaka Shigeru
Publication year - 2002
Publication title -
international journal of circuit theory and applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.364
H-Index - 52
eISSN - 1097-007X
pISSN - 0098-9886
DOI - 10.1002/cta.208
Subject(s) - simplex algorithm , linear programming , revised simplex method , piecewise linear function , simplex , mathematics , resistive touchscreen , computation , simple (philosophy) , algorithm , dual (grammatical number) , mathematical optimization , piecewise , computer science , combinatorics , mathematical analysis , art , philosophy , literature , epistemology , computer vision
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 non‐existence of a solution to a system of PWL equations in a given region. In the conventional LP test, the system of PWL equations is transformed into an LP problem, to which the simplex method is applied. However, this algorithm requires a very large number of pivotings because the simplex method is applied on many regions. In this paper, we introduce the dual simplex method to the LP test, which makes the average number of pivotings per region much smaller (less than one, for example) and makes the algorithm very efficient. By numerical examples, it is shown that the proposed algorithm could find all solutions of large‐scale problems, including those where the number of variables is 300 and the number of linear regions is 10 300 , in practical computation time. Copyright © 2002 John Wiley & Sons, Ltd.