Volume 24, No 4, 2017, P. 95–110
UDC 519.8
R. Yu. Simanchev
On facetinducing 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
email: 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 integervalued 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 largescale zeroone 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 largescale 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, NPhard problems in hierarchicaltree 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 largescale 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 01 knapsacks and MIPs with generalised upper bound constraints, Discrete Appl. Math., 29, No. 2–3, 251–261, 1990.
