Volume 24, No 4, 2017, P. 95–110

UDC 519.8
R. Yu. Simanchev
On facet-inducing inequalities for combinatorial polytopes

Abstract:
One of the central questions of polyhedral combinatorics is the question of the algorithmic relationship between the vertex and facet descriptions of convex polytopes. From the standpoint of combinatorial optimization, the main reason for the actuality of this question is the possibility of applying the methods of convex analysis to solving the extremal combinatorial problems. In this paper, we consider the combinatorial polytopes of a sufficiently general form. We obtain a few of necessary conditions and a sufficient condition for a supporting inequality of a polytope to be a facet inequality and give an illustration of the use of the developed technology to the polytope of some graph approximation problem.
Bibliogr. 20.

Keywords: polytope, facet, $M$-graph, supporting inequality.

DOI: 10.17377/daio.2017.24.563

Ruslan Yu. Simanchev ^1,2
1. Omsk Scientific Center SB RAS,
15 Karl Marx Ave., 644024 Omsk, Russia
2. Dostoevsky Omsk State University,
55A Mira Ave., 630077 Omsk, Russia
e-mail: osiman@rambler.ru

Received 18 January 2017
Revised 12 May 2017

References

[1] A. A. Ageev, V. P. Il’ev, A. V. Kononov, and A. S. Talevnin, Computational complexity of the graph approximation problem, Diskretn. Anal. Issled. Oper., Ser. 1, 13, No. 1, 3–15, 2006 [Russian]. Translated in J. Appl. Ind. Math., 1, No. 1, 1–8, 2007.

[2] S. I. Bastrakov and N. Yu. Zolotykh, Fast method for verifying Chernikov rules in Fourier — Motzkin elimination, Zh. Vychisl. Mat. Mat. Fiz., 55, No. 1, 165–172, 2015 [Russian]. Translated in Comput. Math. Math. Phys., 55, No. 1, 160–167, 2015.

[3] V. A. Emelichev, M. M. Kovalev, and M. K. Kravtsov, Mnogogranniki. Grafy. Optimizatsiya, Nauka, Moscow, 1981 [Russian]. Translated under the title Polytopes, Graphs and Optimization, Camb. Univ. Press, New York, 1984.

[4] V. P. Il’ev, S. D. Il’eva, and A. A. Navrotskaya, Approximation algorithms for graph approximation problems, Diskretn. Anal. Issled. Oper., 18, No. 1, 41–60, 2011 [Russian]. Translated in J. Appl. Ind. Math., 5, No. 4, 569–581, 2011.

[5] R. Yu. Simanchev, On rank inequalities that generate facets of the connected $k$-factors polytope, Diskretn. Anal. Issled. Oper., 3, No. 3, 84–110, 1996 [Russian].

[6] R. Yu. Simanchev and I. V. Urazova, An integer-valued model for the problem of minimizing the total servicing time of unit claims with parallel devices with precedences, Avtom. Telemekh., No. 10, 100–106, 2010 [Russian]. Translated in Autom. Remote Control, 71, No. 10, 2102–2108, 2010.

[7] R. Yu. Simanchev and I. V. Urazova, On the polytope faces of the graph approximation problem, Diskretn. Anal. Issled. Oper., 22, No. 2, 86–101, 2015 [Russian]. Translated in J. Appl. Ind. Math., 9, No. 2, 283–291, 2015.

[8] V. N. Shevchenko, Kachestvennye voprosy tselochislennogo programmirovaniya, Fizmatlit, Moscow, 1995 [Russian]. Translated under the title Qualitative Topics in Integer Linear Programming, AMS, Providence, RI, 1997 (Transl. Math. Monogr., Vol. 156).

[9] H. Crowder, E. L. Johnson, and M. W. Padberg, Solving large-scale zero-one linear programming problems, Oper. Res., 31, No. 5, 803–834, 1983.

[10] E. S. Gottlieb and M. R. Rao, The generalized assignment problem: Valid inequalities and facets, Math. Program., 46, No. 1–3, 31–52, 1990.

[11] M. Grötschel and O. Holland, Solution of large-scale symmetric travelling salesman problems, Math. Program., 51, No. 1–3, 141–202, 1991.

[12] M. Grötschel and W. R. Pulleyblank, Clique tree inequalities and the symmetric traveling salesman problem, Math. Oper. Res., 11, No. 4, 537–569, 1986.

[13] B. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithm, Springer, Heidelberg, 2006 (Algorithms Comb., Vol. 21).

[14] M. Krivánek and J. Morávek, NP-hard problems in hierarchical-tree clustering, Acta Inform., 23, No. 3, 311–323, 1986.

[15] M. W. Padberg, ($1, k$)-configurations and facets for packing problems, Math. Program., 18, 94–99, 1980.

[16] M. W. Padberg and G. Rinaldi, Facet identification for the symmetric traveling salesman polytope, Math. Program., 47, 219–257, 1990.

[17] M. W. Padberg and G. Rinaldi, A branch and cut algorithm for the resolution of large-scale symmetric traveling salesman problems, SIAM Rev., 33, 60–100, 1991.

[18] A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Springer, Heidelberg, 2004 (Algorithms Comb., Vol. 24).

[19] R. Yu. Simanchev and I. V. Urazova, On the facets of combinatorial polytopes, in Discrete Optimization and Operations Research (Proc. 9th Int. Conf. DOOR, Vladivostok, Russia, Sept. 19–23, 2016), pp. 159–170, Springer, Cham, 2016 (Lect. Notes Comput. Sci., Vol. 9869).

[20] L. A. Wolsey, Valid inequalities for 0-1 knapsacks and MIPs with generalised upper bound constraints, Discrete Appl. Math., 29, No. 2–3, 251–261, 1990.