On the facial structure of the set covering polytope

Given a bipartite graphG = (V, U, E), a cover ofG is a subset with the property that each nodeu U is adjacent to at least one nodev D. If a positive weightc _v is associated with each nodev V, the covering problem (CP) is to find a cover ofG having minimum total weight.In this paper we study the properties of the polytopeQ(G) ^|V| , the convex hull of the incidence vectors of all the covers inG. After discussing some general properties ofQ(G) we introduce a large class of bipartite graphs with special structure and describe several types of rank facets of the associated polytopes.Furthermore we present two lifting procedures to derive valid inequalities and facets of the polytopeQ(G) from the facets of any polytopeQ(G) associated with a subgraphG ofG. An example of the application of the theory to a class of hard instances of the covering problem is also presented.     

An exact algorithm for the maximum stable set problem

We describe a new branch-and-bound algorithm for the exact solution of the maximum cardinality stable set problem. The bounding phase is based on a variation of the standard greedy algorithm for finding a colouring of a graph. Two different node-fixing heuristics are also described. Computational tests on random and structured graphs and very large graphs corresponding to real-life problems show that the algorithm is competitive with the fastest algorithms known so far.This work has been supported by Agenzia Spaziale Italiana.     

Metric inequalities and the Network Loading Problem

Given a simple graph G(V,E) and a set of traffic demands between the nodes of G, the Network Loading Problem consists of installing minimum cost integer capacities on the edges of G allowing routing of traffic demands.In this paper we study the Capacity Formulation of the Network Loading Problem, introducing the new class of Tight Metric Inequalities, that completely characterize the convex hull of the integer feasible solutions of the problem.We present separation algorithms for Tight Metric Inequalities and a cutting plane algorithm, reporting on computational experience.     

Chair-Free Berge Graphs Are Perfect

A graph G is called Berge if neither G nor its complement contains a chordless cycle with an odd number of nodes. The famous Berge’s Strong Perfect Graph Conjecture asserts that every Berge graph is perfect. A chair is a graph with nodes {a, b, c, d, e} and edges {ab, bc, cd}, eb. We prove that a Berge graph with no induced chair (chair-free) is perfect or, equivalently, that the Strong Perfect Graph Conjecture is true for chair-free graphs.     

Planning wireless networks by shortest path

Transmitters and receivers are the basic elements of wireless networks and are characterized by a number of radio-electrical parameters. The generic planning problem consists of establishing suitable values for these parameters so as to optimize some network performance indicator. The version here addressed, namely the Power Assignment Problem (pap), is the problem of assigning transmission powers to the transmitters of a wireless network so as to maximize the satisfied demand. This problem has relevant practical applications both in radio-broadcasting and in mobile telephony. Typical solution approaches make use of mixed integer linear programs with huge coefficients in the constraint matrix yielding numerical inaccuracy and poor bounds, and so cannot be exploited to solve large instances of practical interest. In order to overcome these inconveniences, we developed a two-phase heuristic to solve large instances of pap, namely a constructive heuristic followed by an improving local search. Both phases are based on successive shortest path computations on suitable directed graphs. Computational tests on a number of instances arising in the design of the national Italian Digital Video Broadcasting (DVB) network are presented.