The group Steiner tree problem consists of, given a graph G, a collection M of subsets of V (G) and a cost c(e) for each edge of G, finding a minimum-cost subtree that connects at least one vertex from each R is an el...
详细信息
The group Steiner tree problem consists of, given a graph G, a collection M of subsets of V (G) and a cost c(e) for each edge of G, finding a minimum-cost subtree that connects at least one vertex from each R is an element of R. It is a generalization of the well-known Steiner tree problem that arises naturally in the design of VLSI chips. In this paper, we study a polyhedron associated with this problem and some extended formulations. We give facet defining inequalities and explore the relationship between the group Steiner tree problem and other combinatorial optimization problems. (c) 2006 Elsevier B.V. All rights reserved.
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 polynomia...
详细信息
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 non-trivial class of graphs, where the odd cycle inequalities together with the linear relaxations of both the p-median and uncapacitated facility location problems, suffice to describe the associated polytope. To do this, we first give a complete description of the fractional extreme points of the linear relaxation for the p-median polytope in this class of graphs. (c) 2007 Elsevier B.V. All rights reserved.
Let G = (V, E) be a undirected k-edge connected graph with weights c, on edges and w(v) on nodes. The minimum 2-edge connected subgraph problem, 2ECSP for short, is to find a 2-edge connected subgraph of G, of minimum...
详细信息
Let G = (V, E) be a undirected k-edge connected graph with weights c, on edges and w(v) on nodes. The minimum 2-edge connected subgraph problem, 2ECSP for short, is to find a 2-edge connected subgraph of G, of minimum total weight. The 2ECSP aeneralizes the well-known Steiner 2-edge connected subgraph problem. In this paper we study the convex hull of the incidence vectors corresponding to feasible solutions of 2ECSP. First, a natural integer programming formulation is given and it is shown that its linear relaxation is not sufficient to describe the polytope associated with 2ECSP even when G is series-parallel. Then, we introduce two families of new valid inequalities and we give sufficient conditions for them to be facet-clefining. Later, we concentrate on the separation problem. We find polynomial time algorithms to solve the separation of important subclasses of the introduced inequalities, concluding that the separation of the new inequalities, when G is series-parallel, is polynomially solvable. (c) 2006 Elsevier B.V. All rights reserved.
Cardinality constraints have received considerable attention from the Constraint Programming community as (so-called) global constraints that appear in the formulation of several real-life problems, while also having ...
详细信息
Cardinality constraints have received considerable attention from the Constraint Programming community as (so-called) global constraints that appear in the formulation of several real-life problems, while also having an interesting combinatorial structure. After discussing the relation of cardinality constraints with well-known combinatorial problems (e.g., systems of restricted representatives), we study the polytope defined by the convex hull of vectors satisfying two such constraints, in the case where all variables share a common domain. We provide families of facet-defining inequalities that are polytime separable, together with a condition for when these families of inequalities define a convex hull relaxation. Our results also hold for the case of a single such constraint.
Latin squares of order n have a 1-1 correspondence with the feasible solutions of the 3-index planar assignment problem (3PAP(n)). In this paper, we present a new class of facets for the associated polytope, induced b...
详细信息
Latin squares of order n have a 1-1 correspondence with the feasible solutions of the 3-index planar assignment problem (3PAP(n)). In this paper, we present a new class of facets for the associated polytope, induced by odd-hole inequalities. (c) 2005 Elsevier B.V. All rights reserved.
Motivated by classical Euler's Tonnetz, we introduce and study the combinatorics and topology of more general simplicial complexes Tonn(n,k)(L) of Tonnetz type. Out main result is that for a sufficiently generic c...
详细信息
Motivated by classical Euler's Tonnetz, we introduce and study the combinatorics and topology of more general simplicial complexes Tonn(n,k)(L) of Tonnetz type. Out main result is that for a sufficiently generic choice of parameters the generalized Tonnetz Tonn(nk)(L) is a triangulation of a (k - 1)-dimensional torus Tk-1. In the proof we construct and use the properties of a discrete Abel-Jacobi map, which takes values in the torus Tk-1 congruent to Rk-1 where Lambda congruent to A(k-1)* is the permutohedral lattice.
A subsetA of the edge set of a graphG = (V, E) is called a clique partitioning ofG is there is a partition of the node setV into disjoint setsW 1,?,W k such that eachW i induces a clique, i.e., a complete (but not nec...
详细信息
A subsetA of the edge set of a graphG = (V, E) is called a clique partitioning ofG is there is a partition of the node setV into disjoint setsW 1,?,W k such that eachW i induces a clique, i.e., a complete (but not necessarily maximal) subgraph ofG, and such thatA = ∪ i=1 k 1{uv|u, v ∈ W i ,u ≠ v}. Given weightsw e ∈? for alle ∈ E, the clique partitioning problem is to find a clique partitioningA ofG such that ∑ e∈A w e is as small as possible. This problem—known to be -hard, see Wakabayashi (1986)—comes up, for instance, in data analysis, and here, the underlying graphG is typically a complete graph. In this paper we study the clique partitioning polytope of the complete graphK n , i.e., is the convex hull of the incidence vectors of the clique partitionings ofK n . We show that triangles, 2-chorded odd cycles, 2-chorded even wheels and other subgraphs ofK n induce facets of . The theoretical results described here have been used to design an (empirically) efficient cutting plane algorithm with which large (real-world) instances of the clique partitioning problem could be solved. These computational results can be found in Gr?tschel and Wakabayashi (1989).
Several procedures for the identification of facet inducing inequalities for the symmetric traveling salesman polytope are given. An identification procedure accepts as input the support graph of a point which does no...
详细信息
Several procedures for the identification of facet inducing inequalities for the symmetric traveling salesman polytope are given. An identification procedure accepts as input the support graph of a point which does not belong to the polytope, and returns as output some of the facet inducing inequalities violated by the point. A procedure which always accomplishes this task is calledexact, otherwise it is calledheuristic. We give exact procedures for the subtour elimination and the 2-matching constraints, based on the Gomory—Hu and Padberg—Rao algorithms respectively. Efficient reduction procedures for the input graph are proposed which accelerate these two algorithms substantially. Exact and heuristic shrinking conditions for the input graph are also given that yield efficient procedures for the identification of simple and general comb inequalities and of some elementary clique tree inequalities. These procedures constitute the core of a polytopal cutting plane algorithm that we have devised and programmed to solve a substantial number of large-scale problem instances with sizes up to 2392 nodes to optimality.
Biorders, also called Ferrers relations, formalize Guttman scales. Irreflexive biorders on a set are exactly the interval orders on that set. The biorder polytope is the convex hull of the characteristic matrices of b...
详细信息
Biorders, also called Ferrers relations, formalize Guttman scales. Irreflexive biorders on a set are exactly the interval orders on that set. The biorder polytope is the convex hull of the characteristic matrices of biorders. Its definition is thus similar to the definition of other order polytopes, the linear ordering polytope being the proeminent example. We investigate the combinatorial structure of the biorder polytope, thus obtaining a complete linear description in a specific case, and the automorphism group in all cases. Moreover, a class of facet-defining inequalities defined from weighted graphs is thoroughly analyzed. A weighted generalization of stability-critical graphs is presented, which leads to new facets even for the well-studied linear ordering polytope.
This survey is concerned with the size of perfect formulations for combinatorial optimization problems. By "perfect formulation", we mean a system of linear inequalities that describes the convex hull of fea...
详细信息
This survey is concerned with the size of perfect formulations for combinatorial optimization problems. By "perfect formulation", we mean a system of linear inequalities that describes the convex hull of feasible solutions, viewed as vectors. Natural perfect formulations often have a number of inequalities that is exponential in the size of the data needed to describe the problem. Here we are particularly interested in situations where the addition of a polynomial number of extra variables allows a formulation with a polynomial number of inequalities. Such formulations are called "compact extended formulations". We survey various tools for deriving and studying extended formulations, such as Fourier's procedure for projection, Minkowski-Weyl's theorem, Balas' theorem for the union of polyhedra, Yannakakis' theorem on the size of an extended formulation, dynamic programming, and variable discretization. For each tool that we introduce, we present one or several examples of how this tool is applied. In particular, we present compact extended formulations for several graph problems involving cuts, trees, cycles and matchings, and for the mixing set. We also present Bienstock's approximate compact extended formulation for the knapsack problem, Goemans' result on the size of an extended formulation for the permutahedron, and the Faenza-Kaibel extended formulation for orbitopes.
暂无评论