Inverse <Emphasis Type="Italic">p</Emphasis>-median problems with variable edge lengths

The inverse p-median problem with variable edge lengths on graphs is to modify the edge lengths at minimum total cost with respect to given modification bounds such that a prespecified set of p vertices becomes a p-median with respect to the new edge lengths. The problem is shown to be strongly NP{\mathcal{NP}}-hard on general graphs and weakly NP{\mathcal{NP}}-hard on series-parallel graphs. Therefore, the special case on a tree is considered: It is shown that the inverse 2-median problem with variable edge lengths on trees is solvable in polynomial time. For the special case of a star graph we suggest a linear time algorithm.     

The inverse problem for certain tree parameters

Let p be a graph parameter that assigns a positive integer value to every graph. The inverse problem for p asks for a graph within a prescribed class (here, we will only be concerned with trees), given the value of p. In this context, it is of interest to know whether such a graph can be found for all or at least almost all integer values of p. We will provide a very general setting for this type of problem over the set of all trees, describe some simple examples and finally consider the interesting parameter “number of subtrees”, where the problem can be reduced to some number-theoretic considerations. Specifically, we will prove that every positive integer, with only 34 exceptions, is the number of subtrees of some tree.     

A large class of facets for the K-median polytope

The polyhedral structure of the K-median problem is examined. We present an extended formulation that is integral but grows exponentially with the number of nodes. Then, some extra variables are projected out. Based on the reduced formulation, we develop two basic properties for facets of K-median problem. By applying the two properties, we generalize two known classes of facets, de Vries facets and de Farias facets. The computational study illustrates that the generalization is significant.     

Two-edge connected subgraphs with bounded rings: Polyhedral results and Branch-and-Cut

We consider the network design problem which consists in determining at minimum cost a 2-edge connected network such that the shortest cycle (a “ring”) to which each edge belongs, does not exceed a given length K. We identify a class of inequalities, called cycle inequalities, valid for the problem and show that these inequalities together with the so-called cut inequalities yield an integer programming formulation of the problem in the space of the natural design variables. We then study the polytope associated with that problem and describe further classes of valid inequalities. We give necessary and sufficient conditions for these inequalities to be facet defining. We study the separation problem associated with these inequalities. In particular, we show that the cycle inequalities can be separated in polynomial time when K≤4. We develop a Branch-and-Cut algorithm based on these results and present extensive computational results.     

A branch-and-cut method for the obnoxious p-median problem

The obnoxious p-median (OpM) problem is the repulsive counterpart of the ore known attractive p-median problem. Given a set I of cities and a set J of possible locations for obnoxious plants, a p-cardinality subset Q of J is sought, such that the sum of the distances between each city of I and the nearest obnoxious site in Q is maximised. We formulate (OpM) as a {0,1} linear programming problem and propose three families of valid inequalities whose separation problem is polynomial. We describe a branch-and-cut approach based on these inequalities and apply it to a set of instances found in the location literature. The computational results presented show the effectiveness of these inequalities for (OpM). The work of the first author has been partially supported by the Coordinated Project C.A.M.P.O. and that of the third author by a short mobility grant, both of the Italian National Research Council.     

Packing Steiner trees: polyhedral investigations

LetG=(V, E) be a graph andT⊆V be a node set. We call an edge setS a Steiner tree forT ifS connects all pairs of nodes inT. In this paper we address the following problem, which we call the weighted Steiner tree packing problem. Given a graphG=(V, E) with edge weightsw _e , edge capacitiesc _e ,e∈E, and node setT ₁,…,T _N , find edge setsS ₁,…,S _N such that eachS _k is a Steiner tree forT _k , at mostc _e of these edge sets use edgee for eache∈E, and the sum of the weights of the edge sets is minimal. Our motivation for studying this problem arises from a routing problem in VLSI-design, where given sets of points have to be connected by wires. We consider the Steiner tree packing problem from a polyhedral point of view and define an associated polyhedron, called the Steiner tree packing polyhedron. The goal of this paper is to (partially) describe this polyhedron by means of inequalities. It turns out that, under mild assumptions, each inequality that defines a facet for the (single) Steiner tree polyhedron can be lifted to a facet-defining inequality for the Steiner tree packing polyhedron. The main emphasis of this paper lies on the presentation of so-called joint inequalities that are valid and facet-defining for this polyhedron. Inequalities of this kind involve at least two Steiner trees. The classes of inequalities we have found form the basis of a branch & cut algorithm. This algorithm is described in our companion paper (in this issue).     

On the polyhedral structure of a multi–item production planning model with setup times

 We present and study a mixed integer programming model that arises as a substructure in many industrial applications. This model generalizes a number of structured MIP models previously studied, and it provides a relaxation of various capacitated production planning problems and other fixed charge network flow problems. We analyze the polyhedral structure of the convex hull of this model, as well as of a strengthened LP relaxation. Among other results, we present valid inequalities that induce facets of the convex hull under certain conditions. We also discuss how to strengthen these inequalities by using known results for lifting valid inequalities for 0–1 continuous knapsack problems. Received: 30 October 2000 / Accepted: 25 March 2002 Published online: September 27, 2002 Key words. mixed integer programming – production planning – polyhedral combinatorics – capacitated lot–sizing – fixed charge network flow Some of the results of this paper have appeared in condensed form in ``Facets, algorithms, and polyhedral characterizations of a multi-item production planning model with setup times', Proceedings of the Eighth Annual IPCO conference, pp. 318-332, by the same authors. This paper presents research results of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian State, Prime Minister's Office, Science Policy Programming. The scientific responsibility is assumed by the authors. This research was also supported by NSF Grant No. DMI-9700285 and by Philips Electronics North America.     

Ramsey theory and integrality gap for the independent set problem

We discuss the effectiveness of integer programming for solving large instances of the independent set problem. Typical LP formulations, even strengthened by clique inequalities, yield poor bounds for this problem. We show that a strong bound can be obtained by the use of the so-called rank inequalities, which generalize the clique inequalities. For some problems the clique inequalities imply the rank inequalities, and then a strong bound is guaranteed already by the simpler formulation.     

An application of the Lovász–Schrijver <Emphasis Type="Italic">M</Emphasis>(<Emphasis Type="Italic">K</Emphasis>, <Emphasis Type="Italic">K</Emphasis>) operator to the stable set problem

Although the lift-and-project operators of Lovász and Schrijver have been the subject of intense study, their M(K, K) operator has received little attention. We consider an application of this operator to the stable set problem. We begin with an initial linear programming (LP) relaxation consisting of clique and non-negativity inequalities, and then apply the operator to obtain a stronger extended LP relaxation. We discuss theoretical properties of the resulting relaxation, describe the issues that must be overcome to obtain an effective practical implementation, and give extensive computational results. Remarkably, the upper bounds obtained are sometimes stronger than those obtained with semidefinite programming techniques.      

On the probabilistic analysis of an approximation algorithm for solving the <Emphasis Type="Italic">p</Emphasis>-median problem

In order to solve the location problem in the p-median form we present an approximation algorithm with time complexity O(n ₂) and the results of its probabilistic analysis. The input data are defined on a complete graph with distances between the vertices expressed by the independent random variables with the same uniform distribution. The value of the objective function produced by the algorithm amounts to a certain sum of the random variables that we analyze basing on an estimate for the probabilities of large deviations of these sums. We use a limit theorem in the form of the Petrov inequalities, taking into account the dependence of the random variables in the sum. The probabilistic analysis yields some estimates for the relative error and the failure probability of our algorithm, as well as conditions for its asymptotic exactness.     

A multi-item production planning model with setup times: algorithms, reformulations, and polyhedral characterizations for a special case

 We study a special case of a structured mixed integer programming model that arises in production planning. For the most general case of the model, called PI, we have earlier identified families of facet–defining valid inequalities: (l, S) inequalities (introduced for the uncapacitated lot–sizing problem by Barany, Van Roy, and Wolsey), cover inequalities, and reverse cover inequalities. PI is 𝒩𝒫–hard; in this paper we focus on a special case, called PIC. We describe a polynomial algorithm for PIC, and we use this algorithm to derive an extended formulation of polynomial size for PIC. Projecting from this extended formulation onto the original space of variables, we show that (l, S) inequalities, cover inequalities, and reverse cover inequalities suffice to solve the special case PIC by linear programming. We also describe fast combinatorial separation algorithms for cover and reverse cover inequalities for PIC. Finally, we discuss the relationship between our results for PIC and a model studied previously by Goemans. Received: December 13, 2000 / Accepted: December 13, 2001 Published online: October 9, 2002 RID="★" ID="★" Some of the results in this paper have appeared in condensed form in Miller et al. (2001). Key words. mixed integer programming – polyhedral combinatorics – production planning – capacitated lot–sizing – fixed charge network flow – setup times This paper presents research results of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian State, Prime Minister's Office, Science Policy Programming. The scientific responsibility is assumed by the authors. This research was also supported by NSF Grant No. DMI-9700285 and by Philips Electronics North America.     

Multicolored trees in complete graphs

A multicolored tree is a tree whose edges have different colors. Brualdi and Hollingsworth 5 proved in any proper edge coloring of the complete graph K_2n(n > 2) with 2n ? 1 colors, there are two edge‐disjoint multicolored spanning trees. In this paper we generalize this result showing that if (a₁,…, a_k) is a color distribution for the complete graph K_n, n ≥ 5, such that , then there exist two edge‐disjoint multicolored spanning trees. Moreover, we prove that for any edge coloring of the complete graph K_n with the above distribution if T is a non‐star multicolored spanning tree of K_n, then there exists a multicolored spanning tree T' of K_n such that T and T' are edge‐disjoint. Also it is shown that if K_n, n ≥ 6, is edge colored with k colors and , then there exist two edge‐disjoint multicolored spanning trees. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 221–232, 2007     

Some Remarks about the FM-partners of <Emphasis Type="Italic">K</Emphasis>3 Surfaces with Picard Numbers 1 and 2

In this paper we describe some results about K3 surfaces with Picard number 1 and 2. In particular, we give a new simple proof of a theorem due to Oguiso which shows that, given an integer N, there is a K3 surface with Picard number 2 and at least N non-isomorphic FM-partners. We describe also the Mukai vectors of the moduli spaces associated to the FM-partners of K3 surfaces with Picard number 1.     

Polyhedral study of the connected subgraph problem

In this paper, we study the connected subgraph polytope which is the convex hull of the solutions to a related combinatorial optimization problem called the maximum weight connected subgraph problem. We strengthen a cut-based formulation by considering some new partition inequalities for which we give necessary and sufficient conditions to be facet defining. Based on the separation problem associated with these inequalities, we give a complete polyhedral characterization of the connected subgraph polytope on cycles and trees.     

Optimal Forest Harvesting with Ordered Site Access

A long-standing problem in forestry management is the optimal harvesting of a growing population of trees to maximize the resulting discounted aggregate net revenue. For an ongoing forest, the trees are harvested and replanted repeatedly; for a once-and-for-all forest, there is no replanting after a single harvest. In this paper, we outline a new formulation for the optimal-harvest problem which avoids difficulties associated with functional-differential equations or partial differential equations of state in the relevant optimal-control problem encountered in recent studies of the ongoing-forest problem. Our new formulation is based on the observation that tree logging is necessarily ordered by practical and/or regulatory considerations (e.g., it is illegal to cut the younger trees first in some jurisdictions); random access to tree sites does not occur in practice. The new formulation is described here for the simpler problem of a once-and-for-all forest. New results for nonuniform initial age distributions and variable unit harvest costs for this simpler problem are reported herein; results for an ongoing forest will be reported in [10]. The new model is also of interest from a control-theoretic viewpoint, as it exhibits the unique feature of having time as a state variable, in contrast to its usual role as an independent variable in conventional control problems.     

Restricted 2-factor polytopes

The optimal k-restricted 2-factor problem consists of finding, in a complete undirected graph K _n , a minimum cost 2-factor (subgraph having degree 2 at every node) with all components having more than k nodes. The problem is a relaxation of the well-known symmetric travelling salesman problem, and is equivalent to it when ≤k≤n−1. We study the k-restricted 2-factor polytope. We present a large class of valid inequalities, called bipartition inequalities, and describe some of their properties; some of these results are new even for the travelling salesman polytope. For the case k=3, the triangle-free 2-factor polytope, we derive a necessary and sufficient condition for such inequalities to be facet inducing. Received March 4, 1997 / Revised version received September 7, 1998?Published online November 9, 1999     

‘Multidimensional’ extensions and a nested dual approach for the m-median problem

A general framework for modeling median type locational decisions, where (i) travel costs and demands may be stochastic, (ii) multiple services or commodities need to be considered, and/or (iii) multiple median type objectives might exist, is presented—using the concept of “multidimensional networks”. The classical m-median problem, the stochastic m-median problem, the multicommodity m-median problem and and multiobjective m-median problem are defined within this framework.By an appropriate transformation of variables, the multidimensional m-median problem simplifies to the classical m-median problem but with a K-fold increase in the number of nodes, where K is the number of dimensions of the network. A nested dual approach to solve the resulting classical m-median problem, that uses Erlenkotter's facility location scheme as a subroutine, is presented. Computational results indicate that the procedure may perhaps be the best available one to solve the m-median problem exactly.     

Restricted b‐factors in bipartite graphs and t‐designs

We present a new equivalence result between restricted b‐factors in bipartite graphs and combinatorial t‐designs. This result is useful in the construction of t‐designs by polyhedral methods. We propose a novel linear integer programming formulation, which we call GDP, for the problem of finding t‐designs that has a noteworthy advantage compared to the traditional set‐covering formulation. We analyze some polyhedral properties of GPD, implement a branch‐and‐cut algorithm using it and solve several instances of small designs to compare with another point‐block formulation found in the literature. © 2006 Wiley Periodicals, Inc. J Combin Designs 14: 169–182, 2006