Dynamic Enumeration of All Mixed Cells

Tomohiko Mizutani (mizutan8is.titech.ac.jp)
Akiko Takeda (takedais.titech.ac.jp)
Masakazu Kojima (kojimais.titech.ac.jp)

Abstract: The polyhedral homotopy method, which has been known as a powerful numerical method for computing all isolated zeros of a polynomial system, requires all mixed cells of the support of the system to construct a family of homotopy functions. Finding the mixed cells is formulated in terms of a linear inequality system with an additional combinatorial condition. It is essential in computational efficiency how we construct an enumeration tree among a family of linear inequalities induced from it such that every mixed cell corresponds to a unique feasible leaf node. This paper proposes a dynamic construction of an enumeration tree, which branches each parent node into its child nodes so that the number of feasible child nodes is expected to be small; hence we can prune a lot of subtrees which do not contain any mixed cell. Numerical results exhibit that our dynamic construction of an enumeration tree works very efficiently for large scale polynomial systems; for example, it generated all mixed cells of the cyclic-15 problem for the first time in less than 16 hours.

Keywords: Mixed Cell, Polyhedral Homotopy Method, Polynomial System, Dynamic Enumeration, Linear Programming

Category 1: Combinatorial Optimization (Branch and Cut Algorithms )

Category 2: Integer Programming (0-1 Programming )

Category 3: Combinatorial Optimization (Polyhedra )

Citation: Research Report B-422, Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology, Meguro, Tokyo 152-8552, Japan, January 2006.

Download: [PDF]

Entry Submitted: 01/28/2006
Entry Accepted: 01/30/2006
Entry Last Modified: 02/05/2006

Modify/Update this entry