=Paper= {{Paper |id=Vol-1987/paper74 |storemode=property |title=Cutting Planes Algorithm for the Connected k-Factor Problem Using the Facet Inequalities |pdfUrl=https://ceur-ws.org/Vol-1987/paper74.pdf |volume=Vol-1987 |authors=Ruslan Yu. Simanchev,Inna V. Urazova,Alexander K. Skiba,Stepan P. Sorokin,Maxim V. Staritsyn,Alexander S. Strekalovsky,Anna Tatarczak,Nikolay P. Tikhomirov,Dmitry V. Aron,Alexey A. Tret'yakov,Sergey Trofimov,Aleksey Ivanov,Yury Fettser,Tatiana S. Zarodnyuk,Alexander Yu. Gornov,Anton S. Anikin,Evgeniya A. Finkelstein,Elena S. Zasukhina,Sergey V. Zasukhin,Vitaly Zhadan,Anna V. Zykina,Olga N. Kaneva }} ==Cutting Planes Algorithm for the Connected k-Factor Problem Using the Facet Inequalities== https://ceur-ws.org/Vol-1987/paper74.pdf

Cutting Planes Algorithm for the Connected k-Factor
Problem Using the Facet Inequalities

Ruslan Yu. Simanchev Inna V. Urazova
Omsk State University Omsk State University
Mira avenue 55a, 644077, Mira avenue 55a,
Omsk Scientific Center of SB RAS, 644077 Omsk, Russia
15 Marksa avenue, urazovainn@mail.ru
644024 Omsk, Russia.
osiman@rambler.ru

Abstract
The relevance of the search facet inequalities for polytopes of combi-
natorial problems caused to the eﬀect of their use in the algorithms
for solving problems of high dimensionality. At the stage of incorpo-
ration facet inequalities in the algorithm, the fundamental role played
the separation problem. The separation problem is a question exis-
tence 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 inequal-
ities on the polyhedron of connected k-factors is shown. In addition,
suﬃcient conditions (polynomial complexity) for the existence of a sep-
arating inequality for odd k are found.
Keywords: polytope, facet inequality, separation problem.

1 Introduction
Combinatorial methods for solving combinatorial optimization problems, that is, methods based on a “rea-
sonable” browsing of objects , are usually eﬀective 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, Grö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 ﬁnite
set on which an additive real functional c : E → R is given and H ⊂ 2E be a family of subsets of ∑ the set E.
Among the sets of the family H, we need to ﬁnd 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 PH . 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 PH . A wide class of algorithms that used to solve
the combinatorial optimization problems in such formulation is the cutting plain algorithms. The polyhedral

Copyright ⃝
c by the paper’s authors. Copying permitted for private and academic purposes.
In: Yu. G. Evtushenko, M. Yu. Khachay, O. V. Khamisov, Yu. A. Kochetov, V.U. Malkova, M.A. Posypkin (eds.): Proceedings of
the OPTIMA-2017 Conference, Petrovac, Montenegro, 02-Oct-2017, published at http://ceur-ws.org

517
approach aims to use the combinatorial structure of the elements of the family H ⊂ 2E when constructing the
cutting planes. The most eﬀective 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 oﬀ 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
ﬁnd an inequality that cuts oﬀ 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 deﬁning 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 speciﬁc classes of inequalities with respect to
speciﬁc 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 eﬃciency,
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 speciﬁc mass problems, the separation problem can turn out to be poly-
nomially 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 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 ﬁnding the
minimum cut with even shares in complete edge-weighted graph. On the basis of this suﬃcient 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 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 ﬁnite-
dimensional Euclidean space is called a polyhedron, if it is a convex hull of a ﬁnite 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 n 2−n by means of a one-to-one
2

E
correspondence between the set of edges E and the set of coordinate axes in R . 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

518
arbitrary graph G ⊆ Kn is the vector xG ∈ RE with components xG e = 1 for e ∈ EG and xe = 0 for e ∈
G
/ EG.
This rule deﬁnes 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 ﬁrst 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 eﬀorts 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 satisﬁes 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
∑ k|V K|
xe ≤ ⌈ − 1⌉ (1)
2
e∈EK

generate facet of Pk,n if and only if k < |V K| < n − k.
This result is generalizing with respect to the case k = 2 [Padberg & Rinaldi, 1990].

3 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 bT x ≤ b0 cuts oﬀ 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 ﬁnd an inequality from family
L that cuts oﬀ 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, suﬃcient conditions (polynomial complexity) for the existence of the separating inequality are obtained.
We will use the following result that obtained in [Simanchev, 1996].

519
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
∑
xe = k, u ∈ V. (2)
e∈δ(u)

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 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 deﬁned 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 oﬀ point x̄ if and only if in Kn there exists such cut γ[U, V \ U ]
that
∑ k|U | k|U |
x̄e < 2 + ⌊ ⌋−⌈ ⌉.
2 2
e∈γ[U,V \U ]

Hereby the cutting inequality is generated by the clique on the set U .
Proof.
Necessity. Let
∑ k|V K|
x̄e > ⌈ − 1⌉ (3)
2
e∈EK

be facet inequality of type (1) cutting oﬀ 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
∑ k|V \ V K|
x̄e > ⌈ − 1⌉. (4)
2
e∈E K̄

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 ∑ ∑ ∑ ∑
= x̄e = x̄e + x̄e + x̄e .
2
e∈E e∈EK e∈E K̄ e∈γ[V K,V K̄]

Consequently,
∑ kn ∑ ∑ kn k|V K| k|V \ V K|
x̄e = − x̄e − x̄e < −⌈ − 1⌉ − ⌈ − 1⌉ =
2 2 2 2
e∈γ[V K,V K̄] e∈EK e∈E K̄

kn k|V K| kn k|V K| k|V K| k|V K|
= −⌈ − 1⌉ − ( −⌊ + 1⌋) = ⌊ + 1⌋ − ⌈ − 1⌉ =
2 2 2 2 2 2
k|V K| k|V K|
=2+⌊ ⌋−⌈ ⌉. (5)
2 2
Now setting U = V K we obtain the proof of necessity.
Suﬃciency. Using (5) we see that the point x̄ is cut oﬀ by the inequality
∑ k|V K|
xe ≤ ⌈ − 1⌉,
2
e∈EK

520
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 satisﬁed. By ∑ virtue Lemma 1 it is suﬃcient 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)
∑ ∑
k|U | = 2 x̄e + x̄e .
e∈EK e∈γ[U,V \U ]

From here
∑ ∑ |U |2 − |U |
x̄e = k|U | − 2 x̄e ≥ k|U | − 2 ≥ |U |2 − |U |2 + |U | ≥ 2.
2
e∈γ[U,V \U ] e∈EK

We get a contradiction again.
The theorem is proved.
Let point x̄ ∈ RE satisfying (2) and 0 ≤ x̄e ≤ 1 for all e ∈ E . To each edge e ∈ E we associate the weight
∑ |
x̄e . The weight of the cut γ[U, V \ U ] is the number e∈γ[U,V \U ] x̄e . Since for an even-value k the values ⌊ k|U
2 ⌋
|
and ⌈ k|U
2 ⌉ 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 oﬀ 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 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 Pk,n , the next polyhedron was taken
∑
xe = k, u ∈ V,
e∈δ(u)

0 ≤ xe ≤ 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

521
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 ⌊ n2 ⌋ 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 ﬁxed
pairs k and n.

k n Clique ineq.,% t,sec
4 20 46 1,5
4 50 57 1,5
4 100 41 12,5
6 20 100 1
6 100 78 5
10 50 0 4
10 100 0 3,25
16 50 75 3,25
20 50 20 3,5
20 100 0 8,75
24 50 15 4,5
30 100 0 9,75
40 100 0 7,25

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 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. Suﬃcient conditions for the existence of a cutting oﬀ 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.

References
[Padberg & Rinaldi, 1991] Padberg M.W.,& Rinaldi G.(1991). A Branch and Cut Algorithm for the Resolution
of Large-scale Symmetric Traveling Salesman Problems.SIAM Review, 33, 60-100.
[Gröotschel & Holland, 1991] Gröotschel M., & O. Holland O.(1991). Solution of Large-scale Symmetric Travel-
ing Salesman Problems.Mathematical Programming, 51, 141-202.
[Crowder et al., 1983] Crowder H., Johnson E.L. and Padberg M.W.(1983). Solving Large-Scale Zero-One Linear
Programming Problems.Operations Research, 31(5), 803 - 834.
[Simanchev & Urazova, 2010] Simanchev R.Yu., Urazova I.V. (2010). An integer-valued model for the problem
of minimizing the total servicing time of unit claims with parallel devices with precedences.Autom. Remote
Control, 71(10), 2102-2108.
[Karp & Papadimitriu, 1982] Karp R.M.,& Papadimitriu C.H. (1982). On linear characterizations of combina-
torial optimization problems.SIAM Journal on Computing, 11, 620-632.
[Padberg & Rao, 1982] Padberg M.W.,& Rao M.R. (1982). Odd minimum cut-sets and b-matchings. Mathemat-
ics of Operations Research, 7, 67-80.
[Simanchev & Urazova, 2016] Simanchev R.Yu.,& Urazova I.V. (2016). Separation Problem for k-
parashutes.Proceedings of the Conference DOOR. CEUR-WS, 1623, (pp. 109-114). Vladivostok, Russia,
http://ceur-ws.org/Vol-1623/paperco16.pdf.
[Padberg & Rinaldi, 1990] Padberg M.W.,& Rinaldi G. (1990). Facet Identiﬁcation for the Symmetric Traveling
Salesman Polytope.Mathematical Programming, 47, 219-257.

522
[Simanchev, 1996] Simanchev R.Yu.(1996). On rank inequalities generating facets of a polytope of connected
k-factors. (Russian) Diskretn. Anal. Issled. Oper. 3(3), 84-110.
[Edmonds, 1965] Edmonds J.(1965). Maximum Matching and a Polyhedron With O,1-Vertices. Journal jf Re-
search of the National Bureau of Standards, Section B, 69, 125-130.
[Araoz et al., 1983] Araoz J., Cunningham W.H., Edmonds J., Green-Krotki J. (1983). Reductions to 1-matching
polyhedra. Networks, 13, 455-473.
[Gerards, 1995] Gerards A.M.H. (1995). Matching.in: Network Models [Handbooks in Operations Research and
Management Science, 7] Elsevier, Amsterdam, 135-224.
[Stoer & Wagner, 1997] Stoer M., Wagner F. (1997). A Simple Min-Cut Algorithm .Journal of the ACM, 44(4),
585-591.

523