The maximum weight-independent set problem (MWISP) is one of the most well-known and well-studied NP-hard problems in the field of combinatorial optimization. In the first part of the dissertation, I explore efficient branch-and-price (B&P) approaches to solve MWISP exactly. B&P is a useful integer-programming tool for solving NP-hard optimization problems. Specifically, I look at vertex- and edge-disjoint decompositions of the underlying graph. MWISP’s on the resulting subgraphs are less challenging, on average, to solve. I use the B&P framework to solve MWISP on the original graph G using these specially constructed subproblems to generate columns. I demonstrate that vertex-disjoint partitioning scheme gives an effective approach for relatively sparse graphs. I also show that the edge-disjoint approach is less effective than the vertex-disjoint scheme because the associated DWD reformulation of the latter entails a slow rate of convergence. In the second part of the dissertation, I address convergence properties associated with Dantzig-Wolfe Decomposition (DWD). I discuss prevalent methods for improving the rate of convergence of DWD. I also implement specific methods in application to the edge-disjoint B&P scheme and show that these methods improve the rate of convergence. In the third part of the dissertation, I focus on identifying new cut-generation methods within the B&P framework. Such methods have not been explored in the literature. I present two new methodologies for generating generic cutting planes within the B&P framework. These techniques are not limited to MWISP and can be used in general applications of B&P. The first methodology generates cuts by identifying faces (facets) of subproblem polytopes and lifting associated inequalities; the second methodology computes Lift-and-Project (L&P) cuts within B&P. I successfully demonstrate the feasibility of both approaches and present preliminary computational tests of each.

We propose a novel branch-and-price (B&P) approach to solve the maximum weighted independent set problem (MWISP). Our approach uses clones of vertices to create edge-disjoint partitions from vertex-disjoint partitions. We solve the MWISP on sub-problems based on these edge-disjoint partitions using a B&P framework, which coordinates sub-problem solutions by involving an equivalence relationship between a vertex and each of its clones. We present test results for standard instances and randomly generated graphs for comparison. We show analytically and computationally that our approach gives tight bounds and it solves both dense and sparse graphs quite quickly.

We propose a novel branch-and-price (B&P) approach to solve the maximum weighted independent set problem (MWISP). Our approach uses clones of vertices to create edge-disjoint partitions from vertex-disjoint partitions. We solve the MWISP on sub-problems based on these edge-disjoint partitions using a B&P framework, which coordinates sub-problem solutions by involving an equivalence relationship between a vertex and each of its clones. We present test results for standard instances and randomly generated graphs for comparison. We show analytically and computationally that our approach gives tight bounds and it solves both dense and sparse graphs quite quickly.

We study the facial structure of the independent set polytope using the concept of conflict hypergraphs. A conflict hypergraph is a hypergraph whose vertices correspond to the binary variables, and edges correspond to covers in the constraint matrix of the independent set polytope. Various structures such as cliques, odd holes, odd anti-holes, webs and anti-webs are identified on the conflict hypergraph. These hypergraph structures are shown to be generalization of traditional graph structures. Valid inequalities are derived from these hypergraph structures, and the facet defining conditions are studied. Chvatal-Gomory ranks are derived for odd hole and clique inequalities. To test the hypergraph cuts, we conduct computational experiments on market-share (also referred to as market-split) problems. These instances consist of 100% dense multiple-knapsack constraints. They are small in size but are extremely hard to solve by traditional means. Their difficult nature is attributed mainly to the dense and symmetrical structure. We employ a special branching strategy in combination with the hypergraph inequalities to solve many of the particularly difficult instances. Results are reported for serial as well as parallel implementations.

La classe des graphes sans P5, c'est-à-dire des graphes ne contenant pas de chaîne induite à cinq sommets, est d'un intérêt particulier en théorie des graphes. Il s'agit en effet de la plus petite classe définie par un seul sous-graphe connexe interdit pour laquelle on ignore encore s'il existe un algorithme polynomial permettant de résoudre le problème du stable maximum. Or ce problème, dont on sait qu'il est difficile en général, est d'une grande importance en pratique (problèmes de planification, d'allocation de registres dans un processeur, biologie moléculaire...). Dans cette thèse, nous commençons par dresser un état de l'art complet des méthodes utilisées pour résoudre le problème dans des sous-classes de graphes sans P5, puis nous étudions et résolvons ce problème dans une sous-classe particulière, la classe des graphes sans P5 3-colorables. Nous apportons également des solutions aux problèmes de la reconnaissance et de la coloration de ces graphes, chaque fois en temps linéaire. Enfin, nous définissons, caractérisons et sommes capables de reconnaître les graphes "chain-probe", qui sont les graphes auxquels il est possible de rajouter des arêtes entre certains sommets de sorte qu'ils soient bipartis et sans P5. Les problèmes de ce type proviennent de la génétique et ont également des applications en intelligence artificielle. / The class of P5-free graphs, namely the graphs without induced chains with five vertices, is of particular interest in graph theory. Indeed, it is the smallest class defined by only one forbidden connected induced subgraph for which the complexity of the Maximum Independent Set problem is unknown. This problem has many applications in planning, CPU register allocation, molecular biology... In this thesis, we first give a complete state of art of the methods used to solve the problem in P5-free graphs subclasses; then we study and solve this problem in a particular subclass, the class of 3-colorable P5-free graphs. We also bring solutions to recognition and coloring problems of these graphs, each time in linear time. Finally, we define, characterize, and are able to recognize "chain-probe" graphs, namely the graphs for which we can add edges between particular vertices such that the resulting graph is bipartite and P5-free. Problems of this type come from genetics and have application in I.A.