Primal-dual simplex method for shooting

Gomory [R.E. Gomory, Some polyhedra related to combinatorial problems, Linear Algebra and its Applications 2 (1969), 451–558] solved the cyclic group problem by a dynamic programming algorithm. We discuss its complexity and introduce a (fractional) cutting plane algorithm as an alternative algorithm. Each cutting plane is generated by solving a shooting linear programming problem. We implement primal-dual simplex method to solve the shooting linear programming problem. A computational result is given on a Wong-Coppersmith digraph.