On the integrality of the uncapacitated facility location polytope

We study a system of linear inequalities associated with the uncapacitated facility location problem. We show that this system defines a polytope with integer extreme points if and only if the graph does not contain a certain type of odd cycles. We also derive odd cycle inequalities and give a separation algorithm. Article Download View … Read more

The p-median polytope of restricted Y-graphs

We further study the effect of odd cycle inequalities in the description of the polytopes associated with the p-median and uncapacitated facility location problems. We show that the obvious integer linear programming formulation together with the odd cycle inequalities completely describe these polytopes for the class of restricted Y-graphs. This extends our results for the … Read more

On the p-median polytope of a special class of graphs

In this paper we consider a well known class of valid inequalities for the p-median and the uncapacitated facility location polytopes, the odd cycle inequalities. It is known that their separation problem is polynomially solvable. We give a new polynomial separation algorithm based on a reduction from the original graph. Then, we define a nontrivial … Read more

A linear programming approach to increasing the weight of all minimum spanning trees

Given a graph where increasing the weight of an edge has a nondecreasing convex piecewise linear cost, we study the problem of finding a minimum cost increase of the weights so that the value of all minimum spanning trees is equal to some target value. We formulate this as a combinatorial linear program and give … Read more

Network Reinforcement

We give an algorithm for the following problem: given a graph $G=(V,E)$ with edge-weights and a nonnegative integer $k$, find a minimum cost set of edges that contains $k$ disjoint spanning trees. This also solves the following {\it reinforcement problem}: given a network, a number $k$ and a set of candidate edges, each of them … Read more

Fractional Packing of T-joins

Given a graph with nonnegative capacities on its edges, it is well known that the weight of a minimum T-cut is equal to the value of a maximum packing of T-joins. Padberg-Rao’s algorithm finds a minimum weight T-cut but it does not produce a T-join packing, we present a polynomial combinatorial algorithm for finding an … Read more

Branch and cut based on the volume algorithm: Steiner trees in graphs and max-cut

We present a Branch-and-Cut algorithm where the Volume Algorithm is applied to the linear programming relaxations arising at each node of the search tree. This means we use fast approximate solutions to these linear programs instead of exact but slower solutions given by the traditionally used dual simplex method. Our claim is that such a … Read more

Robust Capacity Planning in Semiconductor Manufacturing

We present a stochastic programming approach to capacity planning under demand uncertainty in semiconductor manufacturing. Given multiple demand scenarios together with associated probabilities, our aim is to arrive at a set of tools that does well across all of these scenarios. We formulate the problem as a mixed-integer program in which expected value of the … Read more

Near-optimal solutions to large scale facility location problems

We investigate the solution of large scale instances of the capacitated and uncapacitated facility location problems. Let n be the number of customers and m the number of potential facility sites. For the uncapacitated case we solved instances of size m x n=3000 x 3000; for the capacitated case the largest instances were 1000 x … Read more

Solving Steiner tree problems in graphs with Lagrangian relaxation

This paper presents an algorithm to obtain near optimal solutions for the Steiner tree problem in graphs. It is based on a Lagrangian relaxation of a multi-commodity flow formulation of the problem. An extension of the subgradient algorithm, the volume algorithm, has been used to obtain lowe r bounds and to estimate primal solutions. Due … Read more