整数計画法を用いた区分的線形回路の全解探索法  [in Japanese] Finding All DC Solutions of Piecewise-Linear Circuits Using Integer Programming  [in Japanese]

非線形回路,あるいはそれを区分的線形近似することにより得られる区分的線形回路のすべての直流解を求める効率的かつ実用的なアルゴリズムを確立することは,集積画路設計における重要な未解決問題の一つである.この問題に対しては様々なアルゴリズムが提案され,特に最近のアルゴリズムでは数千〜数万変数クラスの大規模非線形方程式の全解探索にも成功している.しかしこれらのアルゴリズムはインプリメンテーションの際に高度な専門的知識と複雑なプログラミングを必要とするため,初心者や非専門家には敷居の高い方法であった.本稿では,初心者でも簡単にインプリメントすることのできる,実現容易な区分的線形回路の全解探索法を提案する.本手法は,区分的線形回路を記述する区分的線形方程式を混合整数計画問題に定式化し,それにGLPK,CPLEXといった無償/商用の優れた整数計画法のソフトウェアを適用するものである.このようなアプローチは近年の整数計画法の驚異的発展により初めて可能となったもので,初心者でも複雑なプログラムを作ることなく,簡単に区分的線形回路の全解探索を行うことができる.

Finding all DC solutions of nonlinear or piecewise-linear circuits is an important problem in circuit simulation. For this problem, many efficient algorithms have been proposed, and some of the recent algorithms succeeded in finding all solutions of 5,000-50,000 nonlinear circuit equations in practical computation time. However, the implementation of these algorithms is difficult for non-experts or beginners. In this paper, we propose a new method for finding all solutions of piecewise-linear circuits. In this method, we formulate the problem of finding all solutions into a mixed integer programming problem, and solve it by a sophisticated integer programming software such as GLPK or CPLEX. It is shown that the proposed method can be easily implemented without difficult theory nor making complicated programs. It is also shown that the proposed method can find all solutions in practical computation time.