Dynamic Enumeration of All Mixed Cells
Tomohiko Mizutani (mizutan8is.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.
Entry Submitted: 01/28/2006
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|