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.     

An $$\mathcal{O}(m\log n)$$ algorithm for the weighted stable set problem in claw-free graphs with $$\alpha ({G}) \le 3$$

Mathematical Programming - In this paper we show how to solve the Maximum Weight Stable Set Problem in a claw-free graph G(V, E) with $$\alpha (G) \le 3$$ in time $$\mathcal{O}(|E|\log...     

Kinetics and bioenergetics of Spirulina platensis cultivation by fed-batch addition of urea as nitrogen source

The cyanobacterium Spirulina platensis was cultivated in bench-scale miniponds on bicarbonate/carbonate solutions using urea as nitrogen source. To minimize limitation and inhibition phenomena, urea was supplied semicontinuously using exponentially increasing feeding rates. The average growth rates obtained alternately varying the total mass of urea added per unit reactor volume (275<m _T<725 mg/L) and the total feeding time (9<t _T<15 d) clearly evidenced nitrogen limitation for m _T<500 mg/L and excess nitrogen inhibition above this threshold. The time behavior of the specific growth rate at variable urea feeding patterns allowed estimation of the time-dependent Gibbsenergy dissipation for cell growth under the actual depletion conditions of fed-batch cultivations. Comparison of the yield of growth on Gibbs energy obtained using either urea or KNO₃ pointed to the preference of S. platensis for the former nitrogen source, likely owing to more favorable bioenergetic conditions.     

The equipartition polytope. I: Formulations,dimension and basic facets

The following basic clustering problem arises in different domains, ranging from physics, statistics and Boolean function minimization.Given a graphG = (V, E) and edge weightsc _e , partition the setV into two sets of 1/2|V| and 1/2|V| nodes in such a way that the sum of the weights of edges not having both endnodes in the same set is maximized or minimized.Anequicut is a feasible solution of the above problem and theequicut polytope Q(G) is the convex hull of the incidence vectors of equicuts inG. In this paper we give some integer programming formulations of the equicut problem, study the dimension of the equicut polytope and describe some basic classes of facet-inducing inequalities forQ(G). Partial support of NSF grants DMS 8606188 and ECS 8800281.This work was done while these two authors visited IASI, Rome, in Spring 1987.