Back to search

Georgia Institute of Technology

Large scale group network optimization

Abstract

dc:description.abstract

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 point is a shooting from the inside of the plus level set of the subadditive polytope. It induces the shooting for the knapsack problem. From the shooting experiment for the knapsack problem we 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 planes are enough to produce the optimal solution. We discuss a relaxation of shooting as a clue to quick shooting. A max flow model on covering space is shown to be equivalent to the dual of shooting linear programming problem.

Degree

thesis:*
Department dc:contributor.department
Industrial and Systems Engineering
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2009

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Shim, Sangho
Advisor dc:contributor.advisor
  • Johnson, Ellis L.
Committee members dc:contributor.committeemember
  • Hunsaker, Brady
  • Nemhauser, George L.
  • Siran, Jozef
  • Ahmed, Shabbir
  • Cook, William J.

Subjects

dc:subject × 12

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/31737

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Shim, Sangho. Large scale group network optimization. Georgia Institute of Technology, 2009. http://hdl.handle.net/1853/31737