On three combinatorial optimization problems with an applicatio to network design

Abstract

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