Large scale group network optimization

Shortest path;Column generation;Large scale optimization;Minimal word problem;Rubik's cube;Lifting;Network flow;Cayley digraph;Geometric group theory;Integer programming

Shim, Sangho ; Industrial and Systems Engineering

University:Georgia Institute of Technology

Department:Industrial and Systems Engineering

关键词: Shortest path;    Column generation;    Large scale optimization;    Minimal word problem;    Rubik's cube;    Lifting;    Network flow;    Cayley digraph;    Geometric group theory;    Integer programming;   

Others  :  https://smartech.gatech.edu/bitstream/1853/31737/1/shim_sangho_200912_phd.pdf

美国|英语

来源: SMARTech Repository

【 摘 要 】

Every knapsack problem may be relaxed to a cyclic group problem. In 1969, Gomory found the subadditive characterization of facets of the master cyclic group problem. We simplify the subadditive relations by the substitution of complementarities and discover a minimal representation of the subadditive polytope for the master cyclic group problem. By using the minimal representation, we characterize the vertices of cardinality length 3 and implement the shooting experiment from the natural interior point.The shooting from the natural interior pointis a shooting from the inside of the plus level set of the subadditive polytope. It inducesthe shooting for the knapsack problem. From the shooting experiment for the knapsack problemwe conclude that the most hit facet is the knapsack mixed integer cut which is the 2-fold lifting of a mixed integer cut.We develop a cutting plane algorithm augmenting cutting planes generated by shooting, and implement it on Wong-Coppersmith digraphs observing that only small number of cutting planesare enough to produce the optimal solution. We discuss a relaxation of shooting as a clue to quick shooting. A max flow model on covering spaceis shown to be equivalent to the dual of shooting linear programming problem.