The relevance of the search facet inequalities for polytopes of combinatorial problems caused to the effect of their use in the algorithms for solving problems of high dimensionality. At the stage of incorporation facet inequalities in the algorithm, the fundamental role played the separation problem. The separation problem is a question existence in class of inequalities such inequality, which strictly separates the noninteger optimum and polytope. In this paper, for even k, the polynomial solvability of the separation problem for the clique inequalities on the polyhedron of connected k-factors is shown. In addition, sufficient conditions (polynomial complexity) for the existence of a separating inequality for odd k are found.
approach aims to use the combinatorial structure of the elements of the family H ⊂ 2E when constructing the
cutting planes. The most effective cutting plane in the algorithmic sense is considered to be the inequalities
that generate the facets of the polytope PH. One of the main ways to apply facet inequalities is as follows. We
take the polyhedral relaxation of a polytope PH with a polynomial in |E| number of constraints. As cutting
planes uses facet inequalities when possible. The current optimum of the relaxed problem is cut off either by
some of the known facet inequalities or by an inequality of general form such as the Gomory inequalities that
formed on the basis of information about this current optimum. At this stage the separation problem for the
existing class of faceted inequalities comes to the fore. The separation problem for the class of inequalities is to
find an inequality that cuts off the current optimum, or to prove that there is no such inequality in this class.
Karp and Papadimitriou in [Karp & Papadimitriu, 1982] showed that under N P ̸= co − N P for a polytope of
general form (not necessarily integer) and a class of inequalities that defining all the facets of the convex hull
of its integer points, there is no polynomial algorithm for solving the separation problem . In this connection
it is advisable to consider the separation problem with respect to specific classes of inequalities with respect to
specific combinatorial problems. Heuristics are often used with this strategy aside from precise procedures for
solving separation problem
Unfortunately theoretical results of a comparative nature in favor of the use of facet inequalities in algorithms and general methods of their construction do not exist today. Nevertheless, in addition to algorithmic efficiency, facet inequalities are relevant in the following case. Any description of the polytope PH in the form of a polyhedron necessarily contains all its facets (up to equivalence). In addition one of the empirical arguments in favor of facet inequalities is that the facet inequalities most subtly take into account the combinatorial structure of the family H and structure of the polytope PH. Any hyperplane other than a facet can be “tweaked” put on the face of a larger dimension in other words, make it more “deep”.
When considering the polytopes of specific mass problems, the separation problem can turn out to be polynomially solvable. This, for example, is for the matching polytope for which a full faceted description is known [Padberg & Rao, 1982]. It makes sense to consider partial faceted descriptions of polytope with respect to the cutting plane algorithms.
For example, the separation problem for clique facets relatively to the symmetric traveling salesman polytope
is polynomially solvable, but for comb inequalities and clique tree inequalities for the same problem is NP-hard
[Padberg & Rinaldi, 1990]
Thus, in the framework of the polyhedral approach to solving a particular mass combinatorial optimization problem we need in following. First, it is necessary to have a class or classes of inequalities that generate the facets of the polytope PH. Secondly, be able to solve the the separation problem for the cutting plane class used in the algorithm.
In this paper the cutting plane algorithm for the weighted connected k-factor problem on a complete undirected graph is described. In this algorithm the inequalities generated by cliques are used. The algorithm iteration consists in the following. For the current continuous optimum the separation problem for the clique inequalities is solved. If the separation problem had positive result, the clique inequality found was used as the cutting plane. Otherwise inequality of general form was used. The polynomial solvability of separation problem for even-value k for clique inequalities is shown. For odd-value k the separation problem reduces to the problem of finding the minimum cut with even shares in complete edge-weighted graph. On the basis of this sufficient conditions for the existence of a cutting clique inequality for odd-value k are obtained. For even-value k the results of the paper are generalizing with respect to the case k = 2 that is a widely known symmetric traveling salesman polytope. 2
We now turn to the description of the polytopes that are the subject of this article. The set P in a finitedimensional Euclidean space is called a polyhedron, if it is a convex hull of a finite number of points.
Let Kn = (V; E) be a complete undirected graph without loops and multiple edges with the vertex set V and the edge set E, |V | = n. For every subgraph G ⊂ Kn we denote by V G and EG its sets of vertices and edges, respectively. The subgraph H ⊆ Kn is called a k-factor if the degree of each vertex from V with respect to the subgraph H is equal to k. Every k-factor is a spanning subgraph of the graph Kn. Therefore we assume that kn is even.
With the graph Kn we associate the Euclidean space RE of dimension n2−n by means of a one-to-one 2 correspondence between the set of edges E and the set of coordinate axes in RE . This space can be considered as a set of vector-columns whose components are indexed by elements of the set E. The Incidence vector of an arbitrary graph G ⊆ Kn is the vector xG ∈ RE with components xeG = 1 for e ∈ EG and xeG = 0 for e ∈= EG. This rule defines a one-to-one correspondence between the set of edge-generated subgraphs of Kn and the set of vertices of the unit cube in RE .
We denote by k;n the set of all k-factors of the graph Kn. A polytope of k-factors is the set
Qk;n = conv{xH ∈ RE | H ∈ k;n}:
A full linear description of the matching polytope was the first result in the direction of using the polyhedral approach to the combinatorial optimization problems [Edmonds, 1965]. The consequence of this is a description of the perfect matching polytope Q1;n. In [Edmonds, 1965] an analogous result for the polytope Qk;n was announced. The strict proof of this in [Araoz et al., 1983] is given. This later allowed to substantiate the polynomial solvability of the minimal k-factor problem in an edge-weighted graph Kn [Gerards, 1995] .
However, the situation changes radically if we impose the connectivity condition on k-factors. The problem becoming NP-hard. The case k = 2 is most widely known and studied. This case corresponds to the symmetric travelling salesman problem. The connectivity condition does not allow to arrange a reduction to the case k = 1. Therefore, the study of the polytope of connected k-factors required the development of new approaches that are clearly visible on the Hamiltonian cycles polytope. The hopes for obtaining a complete linear description of the polyhedron under the condition of connectivity are rather illusory. The main efforts in the framework of the polyhedral approach are aimed at algorithmic aspects and to obtain records in solving individual traveling salesman problems.
We denote by k;n the set of all connected k-factors of the graph Kn. The polytope of connected k-factors is a set
Pk;n = conv{xH ∈ RE | H ∈ k;n}: It is clear that Pk;n ⊂ Qk;n.
The linear inequality aT x ≤ a0 is called “support” to polytope P if it satisfies the conditions 1. aT x ≤ a0 for any x ∈ P ; 2. there exist x′; x′′ ∈ P such that aT x′ = a0 and aT x′′ < a0.
Every support inequality to P generates the set {x ∈ P | aT x = a0}. Such a set is called the face of P . The maximal by inclusion faces are called facets. In [Simanchev, 1996] a class of facet inequalities for the polytope Pk;n generated by cliques of Kn was described.
Theorem 1. [Simanchev, 1996].
Let K = (V K; EK) is a clique in Kn. The inequality ∑ e∈EK As already mentioned, at the stage of using support inequalities in the cutting plane algorithms the separation problem comes to the fore. We say that the support inequality to P bT x ≤ b0 cuts off the point x¯ ∈ RE if bT x¯ > b0. The separation problem is the following. Let point x¯ ∈ RE satisfying (2) and 0 ≤ x¯e ≤ 1 for all e ∈ E and the family L of support inequalities to Pk;n be given. It is required either to find an inequality from family L that cuts off the point barx or prove that there is no such inequality in L.
For a polytope of connected k-factors and clique inequalities the polynomial solvability of the separation problem was proved by reducing to the minimal cut problem in an edge-weighted graph. We apply this approach to arbitrary k. As a result, we have proved the polynomial solvability of the separation problem for even k. For odd k, sufficient conditions (polynomial complexity) for the existence of the separating inequality are obtained.
We will use the following result that obtained in [Simanchev, 1996].
Two support inequalities are said to be equivalent if they generate the same face of the polytope. We denote by (u) the set of all edges of the graph Kn incident to the vertex u ∈ V . It is obvious that all points of polytopes Pk;n and Qk;n satisfy the system of equations
Let cliques K and K¯ satisfy the condition V K¯ = V \ V K. Then inequalities of (1) type generated by cliques K and K¯ are equivalent relative to Pk;n.
For two non-overlapping sets U; W ⊂ V , we will denote a set of edges with one end in U and the other in W as [U; W ]. The cut in Kn is defined by the set [U; V \ U ] . Hereby the sets U andV \ U are called “shores of cut”.
Theorem 2.
Let point x¯ ∈ RE satisfying (2) and 0 ≤ x¯e ≤ 1 for all e ∈ E . In the class of clique inequalities generating the facets of Pk;n there will be an inequality cutting off point x¯ if and only if in Kn there exists such cut [U; V \ U ] that
∑ Hereby the cutting inequality is generated by the clique on the set U .
Proof.
Necessity. Let be facet inequality of type (1) cutting off point x¯. Let K¯ be clique on the set V \ V K. By virtue of (2) and Lemma 1 for clique K¯ a similar inequality is performed ∑ x¯e > ⌈ e∈EK k|V K| 2
− 1⌉ ∑ x¯e > ⌈ e∈EK k|V \ V K| 2
− 1⌉:
E = EK ∪ EK¯ ∪ [V K; V K¯ ]: kn 2 = ∑ x¯e = ∑ x¯e + ∑ x¯e + ∑
x¯e: e∈E e∈EK e∈EK e∈ [V K;V K] (2) (3) (4) (5)
Then, by virtue of (2),Lemma 1 and the fact that these three sets are pairwise disjoint, we have ∑ e∈ [V K;V K] x¯e = kn 2 − ∑ e∈EK x¯e − ∑ x¯e < e∈EK kn 2 − ⌈ where V K = U . To prove the fact that this inequality generate facet of Pk;n it is necessary to show that the condition k < |U | < n − k from Theorem 1 is satisfied. By virtue Lemma 1 it is sufficient to assume that |U | < n2 . We prove a somewhat more general assertion, namely: if ∑e∈ [U;V \U] x¯e < 2 then k < |U |.
Suppose that |U | < k. If U = {u} then [U; V \U ] = (u). Then by (2) we have ∑e∈ [U;V \U] x¯e = ∑e∈ (u) x¯e = k ≥ 2. This contradicts the condition.
Now let 2 ≤ |U | < k. Summarize over u ∈ U the equalities from (2) From here k|U | = 2 ∑ x¯e + e∈EK
∑ x¯e = k|U | − 2 ∑ x¯e ≥ k|U | − 2 e∈EK |U |2 − |U | 2 ≥ |U |2 − |U |2 + |U | ≥ 2: and ⌈ k|2U| ⌉ are equal the separation problem for polytope of connected k-factors and clique inequalities for an even-value k reduces to the minimal cut problem in an edge-weighted graph. Therefore, we have Corollary 1.
Let point x¯ ∈ RE satisfying (2) and 0 ≤ x¯e ≤ 1 for all e ∈ E, k be even. In the class of facet clique inequalities there exists an inequality cutting off the point x¯ only if in Kn with edge weights x¯e, e ∈ E the minimum cut has a weight less than 2.
This means the polynomial solvability of the separation problem for clique inequalities with respect to the polytope of connected k-factors.
For odd-value k this reduction is carried out only in one direction. The direct corollaries of Theorem 2 are: Corollary 2.
At an odd-value k in the class of facet clique inequalities there will be an inequality cutting the point x¯ if in Kn with the edge weights x¯e, e ∈ E, among the cuts with even shores the minimum cut has the weight smaller than 2.
Corollary 3.
At an odd-value k in the class of facet clique inequalities there will be an inequality cutting the point x¯ if in Kn with the edge weights x¯e, e ∈ E, the minimum cut has the weight smaller than 1. 4
The cutting plane algorithm with facet clique inequalities for the minimal connected k-factor problem for even k was implemented. The iteration of the algorithm is as follows. For the current continuous optimum the separation problem for the clique inequalities is solved. If the separation problem had positive result, the clique inequality found was used as the cutting plane. Otherwise Gomory’s cutting was used. To search minimum cut the Stor-Wagner algorithm was used [Stoer & Wagner, 1997]. The objective function was chosen randomly from interval [1; 100]. As the initial relaxation of the polytope Pk;n, the next polyhedron was taken Note that such relaxation does not lead to the standard linear integer program since this polyhedron contains “excess” integer vertices. In is incidence vectors of disconnected k-factors. However, this does not interfere with our algorithm. The incidence vector of the disconnected k -factor is easily determined by the Stor-Wagner algorithm (the minimal cut has weight 0).
The algorithm was implemented on C++ programming language. To solve the linear programs arising during the operation of the algorithm, the IBM ILOG CPLEX package was used. The calculations were carried out on Asus Intel Celeron 2.16 GHz 64bit. The aim of the experiment was to estimate the frequency of the positive response in the separation problem for the facet clique inequalities. 85 problems with a parameter n from 20 to n 100 and an even parameter k from 4 to ⌊ 2 ⌋ were solved. The table shows the fractions of the number of clique cutting planes used from the total number of iterations and the average time for solving the problem for fixed pairs k and n.
For small values of k the clique facets are much more common than for large ones. This looks quite natural, since in the graph Kn the number of cliques satisfying the condition k < |V K| < n − k decreases with increasing k. 5
In this paper we consider the minimal connected k-factor problem. A cutting plane algorithm that use a facet clique inequalities is proposed. The polynomial solvability for separation problem for clique facets for even-value k is shown. Sufficient conditions for the existence of a cutting off clique inequality for odd-value k are obtained. To evaluate the frequency of a positive response in the separation problem for clique inequalities a computer experiment was carried out. On average in 30 percent of iterations facet cutting planes were used.