On three combinatorial optimization problems with an applicatio to network design = 조합최적화문제의 다면체적 연구 및 망설계에의 응용

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 297
  • Download : 0
Recent successes in the resolution of large-scale integer programming (IP) problems are based on the polyhedral studies which can yield tight linear programming (LP) relaxations. This thesis considers three basic combinatorial optimization problems with polyhedral viewpoints and presents results that are useful to solve many potential applications. They are the precedence-constrained knapsack problem, the edge-weighted maximal clique problem, and the extended node packing problem. After presenting results on those problems, we consider an application of the results to solve a hard clustering problem arising in the design of telecommunication networks. The precedence-constrained knapsack problem is the knapsack problem with precedence constraints imposed on the set of variables. The modification of the cover inequality for the usual knapsack problem is presented. Then a lifting procedure is presented which can strengthen the modified cover inequality. The proposed lifting procedure is computationally very simple and can produce much stronger inequality than the original one. The strength of the modified cover inequality lifted by the procedure is discussed and the problem of finding optimal order of lifting is addressed and solved. The natural LP relaxation is analyzed and it is shown that its fractional vertices can be cut off by the modified cover inequalities. Finally a lifting heuristic to further strengthen the inequality is proposed. The edge-weighted maximal clique problem finds a clique of maximum weight whose size is less than or equal to a prespecified number in the complete graph. The problem is analyzed by using an extended formulation with additional variables. Classes of facets are proposed for the extended formulation and it is compared with the natural formulation using projection method. Also by using the projection, new facets are proposed for the polytope associated with the natural formulation. To investigate the empirical performance of th...
Park, Sung-Sooresearcher박성수researcher
한국과학기술원 : 산업공학과,
Issue Date
108877/325007 / 000935134

학위논문(박사) - 한국과학기술원 : 산업공학과, 1996.8, [ vii, 145 p. ; ]


정수계획법; Network; 네트워크; Combinatorial optimization; 다면체적 연구; 조합최적화; Polyhedral studies; Integer programming

Appears in Collection
Files in This Item
There are no files associated with this item.


  • mendeley


rss_1.0 rss_2.0 atom_1.0