Introduction

Combinatorial methods for solving combinatorial optimization problems, that is, methods based on a "reasonable" browsing of objects , are usually effective on problems of relatively small dimension. Moreover, for small dimension they work better than polyhedral methods such as cutting plain, branch and bound. On the other hand since combinatorial optimization problems usually are NP-hard the growth of dimension makes combinatorial methods practically inapplicable (in time) with large initial data. The most impressive records for the exact solution of individual combinatorial optimization problems were obtained with the use of polyhedral sets (see for example [Padberg & Rinaldi, 1991, Gröotschel & Holland, 1991, Crowder et al., 1983, Simanchev & Urazova, 2010]).

A large number of combinatorial optimization problems allow the following formalization. Let E be a finite set on which an additive real functional c : E → R is given and H ⊂ 2 E be a family of subsets of the set E. Among the sets of the family H, we need to find a set that maximizes (minimizes) the function c(S) = ∑ e∈S c(e), S ⊆ E. The polyhedral approach consists in correlation to the family H the special polytope P H . This polytope is the convex hull of the incidence vectors of sets from H. After this we obtain the problem that maximizes (minimizes) a linear functional on the vertex set of the polytope P H . A wide class of algorithms that used to solve the combinatorial optimization problems in such formulation is the cutting plain algorithms. The polyhedral approach aims to use the combinatorial structure of the elements of the family H ⊂ 2 E 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 P H . One of the main ways to apply facet inequalities is as follows. We take the polyhedral relaxation of a polytope P H 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 (see for example [Padberg & Rinaldi, 1990]).

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 P H 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 P H . 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] (see also [Simanchev & Urazova, 2010, Simanchev & Urazova, 2016] ).

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 P H . 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.

The Polytopes of k-factors and Clique Facets

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 K n = (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 ⊂ K n we denote by V G and EG its sets of vertices and edges, respectively. The subgraph H ⊆ K n 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 K n . Therefore we assume that kn is even.

With the graph K n we associate the Euclidean space R E of dimension n 2 −n 2 by means of a one-to-one correspondence between the set of edges E and the set of coordinate axes in R E . 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 ⊆ K n is the vector x G ∈ R E with components x G e = 1 for e ∈ EG and x G e = 0 for e / ∈ EG. This rule defines a one-to-one correspondence between the set of edge-generated subgraphs of K n and the set of vertices of the unit cube in R E .

We denote by β k,n the set of all k-factors of the graph K n . A polytope of k-factors is the set

Q k,n = conv{x H ∈ R E | 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 Q 1,n . In [Edmonds, 1965] an analogous result for the polytope Q k,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 K n [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 K n . The polytope of connected k-factors is a set

P k,n = conv{x H ∈ R E | H ∈ τ k,n }. It is clear that P k,n ⊂ Q k,n .

The linear inequality a T x ≤ a 0 is called "support" to polytope P if it satisfies the conditions 1. a T x ≤ a 0 for any x ∈ P ;

2. there exist x ′ , x ′′ ∈ P such that a T x ′ = a 0 and a T x ′′ < a 0 .

Every support inequality to P generates the set {x ∈ P | a T x = a 0 }. 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 P k,n generated by cliques of K n was described.

Theorem 1. [Simanchev, 1996].

Let K = (V K, EK) is a clique in K n . The inequality ∑ e∈EK x e ≤ ⌈ k|V K| 2 − 1⌉ (1) generate facet of P k,n if and only if k < |V K| < n − k.

This result is generalizing with respect to the case k = 2 [Padberg & Rinaldi, 1990].

The Separation Problem for Clique Inequalities

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 b T x ≤ b 0 cuts off the point x ∈ R E if b T x > b 0 .

The separation problem is the following. Let point x ∈ R E satisfying (2) and 0 ≤ xe ≤ 1 for all e ∈ E and the family L of support inequalities to P k,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 K n incident to the vertex u ∈ V . It is obvious that all points of polytopes P k,n and Q k,n satisfy the system of equations ∑ e∈δ(u)

x e = k, u ∈ V.

(2)

Lemma 1. [Simanchev, 1996]. 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 P k,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 K n is defined by the set γ[U, V \ U ] . Hereby the sets U andV \ U are called "shores of cut".

Theorem 2.

Let point x ∈ R E satisfying (2) and 0 ≤ xe ≤ 1 for all e ∈ E . In the class of clique inequalities generating the facets of P k,n there will be an inequality cutting off point x if and only if in

K n there exists such cut γ[U, V \ U ] that ∑ e∈γ[U,V \U ] xe < 2 + ⌊ k|U | 2 ⌋ − ⌈ k|U | 2 ⌉.

Hereby the cutting inequality is generated by the clique on the set U . Proof.

Necessity. Let ∑ e∈EK xe > ⌈ k|V K| 2 − 1⌉(3)

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

∑ e∈E K xe > ⌈ k|V \ V K| 2 − 1⌉.(4)

It is obvious that

E = EK ∪ E K ∪ γ[V K, V K].

Then, by virtue of (2),Lemma 1 and the fact that these three sets are pairwise disjoint, we have

kn 2 = ∑ e∈E xe = ∑ e∈EK xe + ∑ e∈E K xe + ∑ e∈γ[V K,V K] xe . Consequently, ∑ e∈γ[V K,V K] xe = kn 2 − ∑ e∈EK xe − ∑ e∈E K xe < kn 2 − ⌈ k|V K| 2 − 1⌉ − ⌈ k|V \ V K| 2 − 1⌉ = = kn 2 − ⌈ k|V K| 2 − 1⌉ − ( kn 2 − ⌊ k|V K| 2 + 1⌋) = ⌊ k|V K| 2 + 1⌋ − ⌈ k|V K| 2 − 1⌉ = = 2 + ⌊ k|V K| 2 ⌋ − ⌈ k|V K| 2 ⌉. (5)

Now setting U = V K we obtain the proof of necessity. Sufficiency. Using (5) we see that the point x is cut off by the inequality

∑ e∈EK x e ≤ ⌈ k|V K| 2 − 1⌉,

where V K = U . To prove the fact that this inequality generate facet of P k,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 | < n 2 . We prove a somewhat more general assertion, namely: if

∑ e∈γ[U,V \U ] xe < 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 ] xe = ∑ e∈δ(u) xe = k ≥ 2. This contradicts the condition. Now let 2 ≤ |U | < k. Summarize over u ∈ U the equalities from (2) k|U | = 2 ∑ e∈EK xe + ∑ e∈γ[U,V \U ]

xe .

From here

∑ e∈γ[U,V \U ] xe = k|U | − 2 ∑ e∈EK xe ≥ k|U | − 2 |U | 2 − |U | 2 ≥ |U | 2 − |U | 2 + |U | ≥ 2.

We get a contradiction again.

The theorem is proved. 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 K n with the edge weights xe , 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 K n with the edge weights xe , e ∈ E, the minimum cut has the weight smaller than 1.

The Cutting Plane Algorithm and Computational Experiment

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 P k,n , the next polyhedron was taken ∑ e∈δ(u)

x e = k, u ∈ V, 0 ≤ x e ≤ 1, e ∈ E.

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 100 and an even parameter k from 4 to ⌊ n 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 K n the number of cliques satisfying the condition k < |V K| < n − k decreases with increasing k.

Conclusion

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.