Search

The famous eight queens problem with non-attacking queens placement on an 8 x 8 chessboard was first posed in the year 1848. The queens separation problem is the legal placement of the fewest number of pawns with the maximum number of independent queens placed on an N x N board which results in a separated board. Here a legal placement is defined as the separation of attacking queens by pawns. Using this concept, the current study extends the queens separation problem onto the rectangular board M x N, (M

The maximum separation problem is to find the maximum of the minimum pairwise distance of n points in a planar body $${\mathcal {B}}$$ on the Euclidean plane. In this paper this problem will be considered if $${\mathcal {B}}$$ is the equilateral triangle of side length 1 and the number of points is 13. We will present the exact separation distance of 13 points in the equilateral triangle of side length 1 and we will prove a conjecture of Melissen from 1993 and a conjecture of Graham and Lubachevsky from 1995.

We study the following separation problem: Given a collection of pairwise disjoint coloured objects in the plane withkdifferent colours, compute a shortest “fence”F, i.e., a union of curves of minimum total length, that separates every pair of objects of different colours. Two objects are separated ifFcontains a simple closed curve that has one object in the interior and the other in the exterior. We refer to the problem asgeometrick-cut, as it is a geometric analog to the well-studied multicut problem on graphs. We first give an$$O(n^4\log ^3\!n)$$O(n4log3n)-time algorithm that computes an optimal fence for the case where the input consists of polygons of two colours withncorners in total. We then show that the problem is NP-hard for the case of three colours. Finally, we give a randomised$$4/3\cdot 1.2965$$4/3·1.2965-approximation algorithm for polygons and any number of colours.

Forest algebras are defined for investigating languages of forests [ordered sequences] of unranked trees, where a node may have more than two [ordered] successors. They consist of two monoids, the horizontal and the vertical, with an action of the vertical monoid on the horizontal monoid, and a complementary axiom of faithfulness. A pseudovariety is a class of finite algebras of a given signature, closed under the taking of homomorphic images, subalgebras and finitary direct products. By looking at the syntactic congruence for monoids and as the natural extension in the case of forest algebras, we could define a version of syntactic congruence of a subset of the free forest algebra, not just a forest language. Let [Formula: see text] be a finite alphabet and [Formula: see text] be a pseudovariety of finite forest algebras. A language [Formula: see text] is [Formula: see text]-recognizable if its syntactic forest algebra belongs to [Formula: see text]. Separation is a classical problem in mathematics and computer science. It asks whether, given two sets belonging to some class, it is possible to separate them by another set of a smaller class. Suppose that a forest language [Formula: see text] and a forest [Formula: see text] are given. We want to find if there exists any proof for that [Formula: see text] does not belong to [Formula: see text] just by using [Formula: see text]-recognizable languages, i.e. given such [Formula: see text] and [Formula: see text], if there exists a [Formula: see text]-recognizable language [Formula: see text] which contains [Formula: see text] and does not contain [Formula: see text]. In this paper, we present how one can use profinite forest algebra to separate a forest language and a forest term and also to separate two forest languages.

We consider the following list coloring with separation problem of graphs: Given a graph $G$ and integers $a,b$, find the largest integer $c$ such that for any list assignment $L$ of $G$ with $|L(v)|\le a$ for any vertex $v$ and $|L(u)\cap L(v)|\le c$ for any edge $uv$ of $G$, there exists an assignment $\varphi$ of sets of integers to the vertices of $G$ such that $\varphi(u)\subset L(u)$ and $|\varphi(v)|=b$ for any vertex $v$ and $\varphi(u)\cap \varphi(v)=\emptyset$ for any edge $uv$. Such a value of $c$ is called the separation number of $(G,a,b)$. We also study the variant called the free-separation number which is defined analogously but assuming that one arbitrary vertex is precolored. We determine the separation number and free-separation number of the cycle and derive from them the free-separation number of a cactus. We also present a lower bound for the separation and free-separation numbers of outerplanar graphs of girth $g\ge 5$.

International audience; We study the problem of orienting the edges of a graph such that the minimum over all the vertices of the absolute difference between the outdegree and the indegree of a vertex is maximized. We call this minimum the imbalance of the orientation, i.e. the higher it gets, the more imbalanced the orientation is. The studied problem is denoted by MAXIM. We first characterize graphs for which the optimal objective value of MAXIM is zero. Next we show that MAXIM is generally NP-hard and cannot be approximated within a ratio of 1 2 + ε for any constant ε > 0 in polynomial time unless P = NP even if the minimum degree of the graph δ equals 2. Then we describe a polynomial-time approximation algorithm whose ratio is almost equal to 1 2. An exact polynomial-time algorithm is also derived for cacti. Finally, two mixed integer linear programming formulations are presented. Several valid inequalities are exhibited with the related separation algorithms. The performance of the strengthened formulations is assessed through several numerical experiments.

A k-club is a subset of vertices of a graph that induces a subgraph of diameter at most k, where k is a positive integer. By definition, 1-clubs are cliques and the model is a distance-based relaxation of the clique definition for larger values of k. The k-club model is particularly interesting to study from a polyhedral perspective as the property is not hereditary on induced subgraphs when k is larger than one. This article introduces a new family of facet-defining inequalities for the 2-club polytope that unifies all previously known facets through a less restrictive combinatorial property, namely, independent (distance) 2-domination. The complexity of separation over this new family of inequalities is shown to be NP-hard. An exact formulation of this separation problem and a greedy separation heuristic are also proposed. The polytope described by the new inequalities (and nonnegativity) is then investigated and shown to be integral for acyclic graphs. An additional family of facets is also demonstrated for cycles of length indivisible by three. The effectiveness of these new facets as cutting planes and the difficulty of solving the separation problem in practice are then investigated via computational experiments on a test bed of benchmark instances.

Consider the bi-harmonic differential expression of the form $ A=\triangle _{M}^{2}+q\ $ on a manifold of bounded geometry (M,g) with metric g, where △M is the scalar Laplacian on M and q≥0 is a locally integrable function on M. In the terminology of Everitt and Giertz, the differential expression A is said to be separated in Lp(M), if for all u∈Lp(M) such that Au∈Lp(M), we have qu∈Lp(M). In this paper, we give sufficient conditions for A to be separated in Lp(M),where 1

Given polyhedron P and and a point $$x^*$$ , the separation problem for polyhedra asks to certify that $$x^*\in P$$ and if not, to determine an inequality that is satisfied by P and violated by $$x^*$$ . This problem is repeatedly solved in cutting plane methods for Integer Programming and the quality of the violated inequality is an essential feature in the performance of such methods. In this paper we address the problem of finding efficiently an inequality that is violated by $$x^*$$ and either defines an improper face or a facet of P. We show that, by solving a single linear program, one almost surely obtains such an improper face or facet.

We consider the task to compute the pathwidth of a graph which has been shown to be equivalent to the vertex separation problem. The latter is naturally modeled as a linear ordering problem w.r.t. the vertices of the graph. Mixed-integer programs proposed so far express linear orders using either position or set assignment variables. As we show, the lower bound on the pathwidth obtained when solving their linear programming relaxations is zero for any directed graph. We then present a new formulation based on conventional linear ordering variables and a slightly different perspective on the problem that sustains stronger lower bounds. An experimental evaluation of three mixed-integer programs, each representing one of the different modeling schemes, displays their potentials and limitations when used to solve the problem to optimality.

The final publication is available at Springer via http://dx.doi.org/10.1007/s11750-017-0437-4 This paper focuses on the generalized arc routing problem. This problem is stated on an undirected graph in which some clusters are defined as pairwise-disjoint connected subgraphs, and a route is sought that traverses at least one edge of each cluster. Broadly speaking, the generalized arc routing problem is the arc routing counterpart of the generalized traveling salesman problem, where the set of vertices of a given graph is partitioned into clusters and a route is sought that visits at least one vertex of each cluster. A mathematical programming formulation that exploits the structure of the problem and uses only binary variables is proposed. Facets and families of valid inequalities are presented for the polyhedron associated with the formulation and the corresponding separation problem studied. The numerical results of a series of computational experiments with an exact branch and cut algorithm are presented and analyzed.

In this article, we analyze "the survivable cutset," a basic polyhedron related to most models describing survivable networks. Its importance stems from the fact that it is the analogous of the cutset inequality for survivable networks and cutset inequalities have proved fundamental for solving networks problems via cutting-plane algorithms. We are able to characterize completely the "survivable cutset" via its extreme points, and we describe some important classes of its facets. We prove also that the separation problem is polynomial in the size of the cutset. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 644, 234-261 2014

In this paper, we investigate the separation problem on some valid inequalities for the s - t elementary shortest path problem in digraphs containing negative directed cycles. As we will see, these inequalities depend to a given parameter k ∈ ℕ. To show the NP-hardness of the separation problem of these valid inequalities, considering the parameter k ∈ ℕ, we establish a polynomial reduction from the problem of the existence of k + 2 vertex-disjoint paths between k + 2 pairs of vertices (s1, t1), (s2, t2) ... (sk+2, t k+2) in a digraph to the decision problem associated to the separation of these valid inequalities. Through some illustrative instances, we exhibit the evoked polynomial reduction in the cases k = 0 and k = 1.

International audience; Consider a {0, 1} assignment matrix where each column contains exactly one coefficient equal to 1 and let h be the index of the lowest row that is not identically equal to the zero row. We give a full description of the convex hull of all feasible assignments appended with the extra parameter h. This poly-tope and some of its variants naturally appear in the context of several combi-natorial optimization problems including frequency assignment, job scheduling, graph orientation, maximum clique, etc. We also show that the underlying separation problems are solvable in polynomial time and thus optimization over those polytopes can be done in polynomial time.

The Vertex Separation Problem (VSP) is an NP-hard combinatorial optimization problem in the context of graph theory. The importance of studying VSP lies in its close relation with other problems. Thus, VSP has important practical applications in the contexts of very large scale integration design, computer language compiler design, natural language processing, order processing of manufactured products and bioinformatics. Up to our knowledge, there are only two trajectory-based metaheuristic algorithms for VSP documented in the literature. The main contribution of this chapter is that we extend the available heuristics to solve VSP by proposing a genetic algorithm (GA). It is of particular interest to study the impact of four different crossover operators in the algorithm performance. The experimental results showed that the order-based crossover is the best. Moreover, the best GA variant was compared with the best algorithm for VSP: GVNS. The results of this comparison showed that GVNS outperforms our best GA variant by approximately 1.54 times in solution quality.

We prove several complexity results about the gap inequalities for the max-cut problem, including (i) the gap- 1 inequalities do not imply the other gap inequalities, unless NP = Co NP ; (ii) there must exist non-redundant gap inequalities with exponentially large coefficients, unless NP = Co NP ; (iii) the associated separation problem can be solved in finite (doubly exponential) time.

Many inequalities for Mixed-Integer Linear Programs (MILPs) or pure Integer Linear Programs (ILPs) are derived from the Gomory corner relaxation, where all the nonbinding constraints at an optimal LP vertex are relaxed. Computational results show that the corner relaxation gives a good approximation of the integer hull for problems with general-integer variables, but the approximation is less satisfactory for problems with 0-1 variables only. A possible explanation is that, for 0-1 ILPs, even the non-binding variable bound constraints x j ⩾ 0 or x j ⩽ 1 play an important role, hence their relaxation produces weaker bounds. In this note we address a relaxation for 0-1 ILPs that explicitly takes all variable bound constraints into account. More specifically, we introduce the concept of knapsack closure as a tightening of the classical Chvatal-Gomory (CG) closure. The knapsack closure is obtained as follows: for all inequalities w T x ⩽ w 0 valid for the LP relaxation, add to the original system all the valid inequalities for the knapsack polytope c o n v { x ∈ { 0 , 1 } n : w T x ⩽ w 0 } . A MILP model for the corresponding separation problem is also introduced.

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.

In this chapter, \( A = \left( {S,\,E,\,\Delta ,\,s_0 } \right) \) is a possibly infinite initialized transition system, reachable and reduced, and \( E = \left\{ {e_1 , \ldots ,\,e_n } \right\} \). A particular case is when A = L represents an infinite prefix-closed language \( L \subseteq E^* ,\,i.e.\,S = L,\,s_0 = \varepsilon \), and for every \( u \in E^* \) and \( e \in E,\,\delta \left( {u,\,e} \right) \) is defined and equal to ue if and only if \( ue \in L \).

In this paper we study lift-and-project polyhedral operators defined by Lovász and Schrijver and Balas, Ceria and Cornuéjols on the clique relaxation of the stable set polytope of webs. We compute the disjunctive rank of all webs and consequently of antiwebs. We also obtain the disjunctive rank of the antiweb constraints for which the complexity of the separation problem is still unknown. Finally, we use our results to provide bounds of the disjunctive rank of larger classes of graphs as joined a-perfect graphs, where near-bipartite graphs belong to. Fil: Bianchi, S. Universidad Nacional de Rosario; Argentina Fil: Escalante, Mariana Silvina. Universidad Nacional de Rosario; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina Fil: Montelar, María Susana. Universidad Nacional de Rosario; Argentina

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).

We study the problem of separating n points in the plane, no two of which have the same x- or y-coordinate, using a minimum number of vertical and horizontal lines avoiding the points, so that each cell of the subdivision contains at most one point. Extending previous NP-hardness results due to Freimer et al. we prove that this problem and some variants of it are APX-hard. We give a 2-approximation algorithm for this problem, and a d-approximation algorithm for the d-dimensional variant, in which the points are to be separated using axis-parallel hyperplanes. To this end, we reduce the point separation problem to the rectangle stabbing problem studied by Gaur et al. Their approximation algorithm uses LP-rounding. We present an alternative LP-rounding procedure which also works for the rectangle stabbing problem. We show that the integrality ratio of the LP is exactly 2.

Given a graph G=(V,E) with edge costs and an integer vector [email protected]?Z"+^V associated with the nodes of V, the survivable network design problem is to find a minimum cost subgraph of G such that between every pair of nodes s,t of V, there are at least min{r(s),r(t)} edge-disjoint paths. In this paper we consider that problem when [email protected]?{1,2}^V. This case is of particular interest to the telecommunication industry. We show that the separation problem for the so-called partition inequalities reduces to minimizing a submodular function. This yields a polynomial time separation algorithm for these inequalities in that case.

International audience; Given G = (V;E) an undirected graph and a nonnegative cost function c : E → ℚ, the 2-edge connected spanning subgraph problem (TECSP for short) is to find a two-edge connected subgraph HP = (V; F) of G with minimum cost (i.e., c(F) = Σe∈F c(e) is minimum). If c(e) > 0 for all e ∈ E then every optimal solution for TECSP is an inclusionwise minimal two-edge connected subgraph. In this paper we provide preliminary results, from a polyhedral point of view, concerning the inclusionwise minimal solutions of TECSP. This problem is clearly NP-Hard. We propose an ILP formulation for the problem and study the associated polytope for the wheels. Morever, we describe some valid inequalities and propose a branch-and-cut algorithm for the problem.

A tower between two regular languages is a sequence of strings such that all strings on odd positions belong to one of the languages, all strings on even positions belong to the other language, and each string can be embedded into the next string in the sequence. It is known that if there are towers of any length, then there also exists an infinite tower. We investigate upper and lower bounds on the length of finite towers between two regular languages with respect to the size of the automata representing the languages in the case there is no infinite tower. This problem is relevant to the separation problem of regular languages by piecewise testable languages.

Given a graph G = (V, E) with nonnegative weights x(e) for each edge e, a partition inequality is of the form x(δ(S1,…,Sp)) ≥ ap + b. Here δ(S1,…,Sp) denotes the multicut defined by a partition S1,…,Sp of V. Partition inequalities arise as valid inequalities for optimization problems related to k-connectivity. We give a polynomial algorithm for the associated separation problem. This is based on an algorithm for finding the minimum of x(δ(S1,…,Sp)) − p that reduces to minimizing a symmetric submodular function. This is handled with the recent algorithm of Queyranne. We also survey some applications of partition inequalities.

Crowder et al. (Oper. Res. 31 (1983) 803-834) conjectured that the separation problem for cover inequalities for binary integer programs is polynomially solvable. We show that the general problem is NP-hard but a special case is solvable in linear time.

In this paper we deal with a separation problem of stat-shaped sets. It is shown that under natural assumptions two star-shaped subsets of n-dimensional Euclidean space R ncan be separated by a finite set of linear functionals. The number of this functionals is determined by the dimension of the space R n The separation theorem for star-shaped sets is used in studying of global minimum conditions

Separation is a classical problem asking whether, given two sets belonging to some class, it is possible to separate them by a set from a smaller class. We discuss the separation problem for regular languages. We give a Ptime algorithm to check whether two given regular languages are separable by a piecewise testable language, that is, whether a $B{\Sigma}1(, Comment: arXiv admin note: text overlap with arXiv:1303.2143

We study the following separation problem: given $$n$$n connected curves and two points $$s$$s and $$t$$t in the plane, compute the minimum number of curves one needs to retain so that any path connecting $$s$$s to $$t$$t intersects some of the retained curves. We give the first polynomial $$(\fancyscript{O}(n^3))$$(O(n3)) time algorithm for the problem, assuming that the curves have reasonable computational properties. The algorithm is based on considering the intersection graph of the curves, defining an appropriate family of closed walks in the intersection graph that satisfies the 3-path-condition, and arguing that a shortest cycle in the family gives an optimal solution. The 3-path-condition has been used mainly in topological graph theory, and thus its use here makes the connection to topology clear. We also show that the generalized version, where several input points are to be separated, is NP-hard for natural families of curves, like segments in two directions or unit circles.

The study of cohesive subgroups is an important aspect of social network analysis. Cohesive subgroups are studied using different relaxations of the notion of clique in a graph. For instance, given a graph and an integer k, the maximum edge subgraph problem consists of finding a k-vertex subset such that the number of edges within the subset is maximum. This work proposes a polyhedral approach for this NP-hard problem. We study the polytope associated to an integer programming formulation of the problem, present several families of facet-inducing valid inequalities, and discuss the separation problem associated to these families. Finally, we implement a branch and cut algorithm for this problem. This computational study illustrates the effectiveness of the classes of inequalities presented in this work. © 2011 Elsevier B.V. All rights reserved. Fil:Bonomo, F. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Marenco, J. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Saban, D. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Stier-Moses, N.E. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina.

A class of strong valid inequalities is described for the single-item uncapacitated economic lot-sizing problem with start-up costs. It is shown that these inequalities yield a complete polyhedral characterization of the problem. The corresponding separation problem is formulated as a shortest path problem. Finally, a reformulation as a plant location problem is shown to imply the class of strong valid inequalities, which shows that this reformulation is tight, also.

In this paper we describe a cutting plane algorithm to solve max-cut problems on complete graphs. We show that the separation problem over the cut polytope can be reduced to the separation problem ...

The NP-complete separation problem for the knapsack polyhedron is formulated as a side-constrained network flow problem with a pseudopolynomial number of vertices and edges. It is demonstrated that the primal polyhedron associated with this formulation can be projected onto an appropriate subspace to yield and that the dual polyhedron can be projected onto an appropriate subspace to yield the polar of . Practical consequences of the formulation are discussed.

In this paper, we study the Steiner 2-edge connected subgraph polytope. We introduce a large class of valid inequalities for this polytope called the generalized Steiner F-partition inequalities, that generalizes the so-called Steiner F-partition inequalities. We show that these inequalities together with the trivial and the Steiner cut inequalities completely describe the polytope on a class of graphs that generalizes the wheels. We also describe necessary conditions for these inequalities to be facet defining, and as a consequence, we obtain that the separation problem over the Steiner 2-edge connected subgraph polytope for that class of graphs can be solved in polynomial time. Moreover, we discuss that polytope in the graphs that decompose by 3-edge cutsets. And we show that the generalized Steiner F-partition inequalities together with the trivial and the Steiner cut inequalities suffice to describe the polytope in a class of graphs that generalizes the class of Halin graphs when the terminals have a particular disposition. This generalizes a result of Barahona and Mahjoub [4] for Halin graphs. This also yields a polynomial time cutting plane algorithm for the Steiner 2-edge connected subgraph problem in that class of graphs.

We derive valid inequalities for the knapsack problem with generalised upper bound (GUB) constraints, and show that the separation problem for a subclass of the inequalities is again a knapsack problem with GUB constraints. It is shown that the inequalities are “strong” by showing that in one special case, they suffice to describe the convex hull of solutions, and for other models it is possible to obtain violated inequalities by using constraint aggregation followed by the above separation procedure.

Thompson and King (1 972) presented a closed form expression for the number of different possible separation sequences arising when an n-component mixture is separated into pure products using sharp component separators with one input and two outputs. Subsequently, Shoaei and Sommerfeld (1986) pointed out that the number of sequences is the series of Catalan numbers (Alter, 1971), but they did not show how to derive the closed form formula. This paper will demonstrate that this may be done using a general mathematical technique-generating functions. The analysis is extended to combinatorics of sequences of sharp separators with more than two outputs. Finally expressions for the number of distinct separators will be derived. An underlying assumption throughout the paper is that the components in any stream are “sorted”; components appearing together will always appear in the same order. Sequences of Two-Output Sharp Separators A sharp two-output-component separator is a device where a subset of the feed components leave entirely in the separator’s top stream and the rest leave entirely in the other, the bottom stream. Thus, the remaining separation problem originating from the top stream will be totally independent of the one originating from the bottom stream. The different separation sequences may be represented as paths in a tree, as illustrated in Figure 1 for a four-component example. It is seen from the figure that this example involves five different paths; five alternative separation sequences are possible. The number of separation sequences may be defined recursively for the general case: a stream consisting of n components may be split in n - 1 different ways in one sharp two-output separator. For each of these alternative splits, the number of different separation sequences is equal to the number of separation sequences originating from the separator’s top stream multiplied by the number of separation sequences originating from the separator’s bottom stream. A stream with only one

Let $A$ be the edge-node incidence matrix of a bipartite graph $G = (U, V ; E)$, $I$ be a subset of the nodes of $G$, and $b$ be a vector such that $2b$ is integral. We consider the following mixed-integer set: $X(G, b, I) = {x : Ax ≥ b, x ≥ 0, x_i$ integer for all $i ∈ I}$. We characterize conv$(X(G, b, I))$ in its original space. That is, we describe a matrix $(C, d)$ such that conv$(X(G, b, I)) = {x : Cx ≥ d}$. This is accomplished by computing the projection onto the space of the $x$-variables of an extended formulation, given in [1], for $conv(X(G, b, I))$. We then give a polynomial-time algorithm for the separation problem for conv$(X(G, b, I))$, thus showing that the problem of optimizing a linear function over the set $X(G, b, I)$ is solvable in polynomial time.

We study the mixed-integer rounding (MIR) closure of polyhedra. The MIR closure of a polyhedron is equal to its split closure and the associated separation problem is NP-hard. We describe a mixed-integer programming (MIP) model with linear constraints and a non-linear objective for separating an arbitrary point from the MIR closure of a given mixed-integer set. We linearize the objective using additional variables to produce a linear MIP model that solves the separation problem approximately, with an accuracy that depends on the number of additional variables used. Our analysis yields a short proof of the result of Cook, Kannan and Schrijver (1990) that the split closure of a polyhedron is again a polyhedron. We also present some computational results with our approximate separation model.

The 0/1 primal separation problem is: Given an extreme point $\bar{x}$ of a 0/1 polytope $P$ and some point $x^*$, find an inequality which is tight at $\bar{x}$, violated by $x^*$ and valid for $P$ or assert that no such inequality exists. It is known that this separation variant can be reduced to the standard separation problem for $P$. We show that 0/1 optimization and 0/1 primal separation are polynomial time equivalent. This implies that the problems 0/1 optimization, 0/1 standard separation, 0/1 augmentation, and 0/1 primal separation are polynomial time equivalent. Then we provide polynomial time primal separation procedures for matching, stable set, maximum cut, and maximum bipartite graph problems, giving evidence that these algorithms are conceptually simpler and easier to implement than their corresponding counterparts for standard separation. In particular, for perfect matching we present an algorithm for primal separation that rests only on simple max-flow computations. Consequently, we obtain a very simple proof that a maximum weight perfect matching of a graph can be computed in polynomial time. In contrast, the known standard separation method involves Padberg and Rao's minimum odd cut algorithm, which itself is based on the construction of a Gomory-Hu tree.

Hypermetric inequalities have many applications, most recently in the approximate solution of max-cut problems by linear and semidefinite programming. However, not much is known about the separation problem for these inequalities. Previously Avis and Grishukhin showed that certain special cases of the separation problem for hypermetric inequalities are NP-hard, as evidence that the separation problem is itself hard. In this paper we show that similar results hold for inequalities of negative type, even though the separation problem for negative type inequalities is well known to be solvable in polynomial time. We also show similar results hold for the more general k-gonal and gap inequalities.

We have seen in Chapter 28 that a valid inequality for CUT n , namely the hyper-metric inequality Q(b) T x ≤ 0, can be constructed for any integer vector b ∈ ℤ n with . More generally, how can we construct a valid inequality if we have an arbitrary integer vector b ∈ ℤ n ?

The problem of finding a connected subgraph S of a given graph G = (V,E) containing exactly k edges which is minimal with respect to edge weights w(e) ∈ ℝ is considered. After stating that the problem is NP-hard an integer programming formulation will be given. Some classes of inequalities are shown to be facet-defining for the corresponding polytope. An algorithm for the separation problem for the most important class of inequalities is given which has been implemented in a branch-and-cut approach. Finally the results of this algorithm are compared with a heuristic based on Prim’s algorithm.

The author proves the following theorem: Let A0 be a closed 1-dimensional semianalytic germ at the origin 0∈Rn. Let Z be a semianalytic set in Rn whose germ Z0 at 0 is closed and A0∩Z0={0}. Then there exists a polynomial h∈R[x1,⋯,xn] such that h∣Z∖{0}>0 and h∣A0∖{0}

An efficient and algorithmic procedure is developed for the synthesis of multicomponent separation sequences. The procedure involves list processing of the prossible separation subproblems followed by an ordered branch search to find the optimal sequence with respect to system structure. The technique is conveniently represented by an and/or directed graph. The distribution of sequence costs for a separation problem is considered. When a wide distribution exists, only a minimum of separators need be analyzed to find the optimal sequence. Even when a narrow distribution of sequence costs exists, not all sequences must be developed. The importance of near optimal sequences is examined, and the search procedure is extended to find those sequences whose costs are within a specified factor of the cost of the optimal sequence.

This paper studies the graphs for which the 2-edge connected spanning subgraph polytope is completely described by the trivial inequalities and the so-called cut inequalities. These graphs are called perfectly 2-edge connected. The class of perfectly 2-edge connected graphs contains for instance the class of series-parallel graphs. We introduce a new class of perfectly 2-edge connected graphs. We discuss some structural properties of graphs which are (minimally with respect to some reduction operations) nonperfectly 2-edge connected. Using this we give sufficient conditions for a graph to be perfectly 2-edge connected.

We consider the problem of computing the shortest schedule of the intervals [ j 2 − i ,( j + 1)2 − i ), for 0 ⩽ j ⩽ 2 i − 1 and 1 ⩽ i ⩽ k such that separation of intersecting intervals is at least R . This problem arises in an application of wavelets to medical imaging. It is a generalization of the graph separation problem for the intersection graph of the intervals, which is to assign the numbers 1 to 2 k + 1 − 2 to the vertices, other than the root, of a complete binary tree of height k in such a way as to maximize the minimum difference between all ancestor descendent pairs. We give an efficient algorithm to construct optimal schedules.