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...

Full description

Saved in:
Bibliographic Details
Published in:Electronic notes in discrete mathematics 2010-08, Vol.36, p.719-726
Main Authors: Shim, Sangho, Johnson, Ellis L., Cao, Wenwei
Format: Article
Language:English
Subjects:
cutting plane algorithm
cyclic group problem
primal-dual simplex method
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1571-0653
1571-0653
DOI:10.1016/j.endm.2010.05.091