Geodesic
On facet-inducing inequalities for combinatorial polytopes
Diskretnyj analiz i issledovanie operacij, Tome 24 (2017) no. 4, pp. 95-110.

Voir la notice de l'article provenant de la source Math-Net.Ru

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, $M$-graph, supporting inequality.
Mots-clés : facet 
@article{DA_2017_24_4_a6,
     author = {R. Yu. Simanchev},
     title = {On facet-inducing inequalities for combinatorial polytopes},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {95--110},
     publisher = {mathdoc},
     volume = {24},
     number = {4},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2017_24_4_a6/}
}
TY  - JOUR
AU  - R. Yu. Simanchev
TI  - On facet-inducing inequalities for combinatorial polytopes
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2017
SP  - 95
EP  - 110
VL  - 24
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2017_24_4_a6/
LA  - ru
ID  - DA_2017_24_4_a6
ER  - 
%0 Journal Article
%A R. Yu. Simanchev
%T On facet-inducing inequalities for combinatorial polytopes
%J Diskretnyj analiz i issledovanie operacij
%D 2017
%P 95-110
%V 24
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2017_24_4_a6/
%G ru
%F DA_2017_24_4_a6
R. Yu. Simanchev. On facet-inducing inequalities for combinatorial polytopes. Diskretnyj analiz i issledovanie operacij, Tome 24 (2017) no. 4, pp. 95-110. http://geodesic.mathdoc.fr/item/DA_2017_24_4_a6/

[1] A. A. Ageev, V. P. Il'ev, A. V. Kononov, A. S. Talevnin, “Computational complexity of the graph approximation problem”, J. Appl. Ind. Math., 1:1 (2007), 1–8 | DOI | MR | Zbl

[2] S. I. Bastrakov, N. Yu. Zolotykh, “Fast method for verifying Chernikov rules in Fourier–Motzkin elimination”, Comput. Math. Math. Phys., 55:1 (2015), 160–167 | DOI | DOI | MR | Zbl

[3] V. A. Emelichev, M. M. Kovalev, M. K. Kravtsov, Polytopes, Graphs and Optimization, Camb. Univ. Press, New York, 1984 | MR | MR

[4] V. P. Il'ev, S. D. Il'eva, A. A. Navrotskaya, “Approximation algorithms for graph approximation problems”, J. Appl. Ind. Math., 5:4 (2011), 569–581 | DOI | MR | Zbl

[5] R. Yu. Simanchev, “On rank inequalities that generate facets of the connected $k$-factors polytope”, Diskretn. Anal. Issled. Oper., 3:3 (1996), 84–110 (Russian) | MR | Zbl

[6] R. Yu. Simanchev, I. V. Urazova, “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 (2010), 2102–2108 | DOI | MR | Zbl

[7] R. Yu. Simanchev, I. V. Urazova, “On the polytope faces of the graph approximation problem”, J. Appl. Ind. Math., 9:2 (2015), 283–291 | DOI | DOI | MR | Zbl

[8] V. N. Shevchenko, Qualitative Topics in Integer Linear Programming, Transl. Math. Monogr., 156, AMS, Providence, RI, 1997 | MR | MR

[9] Crowder H., Johnson E. L., Padberg M. W., “Solving large-scale zero-one linear programming problems”, Oper. Res., 31:5 (1983), 803–834 | DOI | Zbl

[10] Gottlieb E. S., Rao M. R., “The generalized assignment problem: Valid inequalities and facets”, Math. Program., 46:1–3 (1990), 31–52 | DOI | MR | Zbl

[11] Grötschel M., Holland O., “Solution of large-scale symmetric traveling salesman problems”, Math. Program., 51:1–3 (1991), 141–202 | DOI | MR | Zbl

[12] Grötschel M., Pulleyblank W. R., “Clique tree inequalities and the symmetric traveling salesman problem”, Math. Oper. Res., 11:4 (1986), 537–569 | DOI | MR | Zbl

[13] Korte B., Vygen J., Combinatorial optimization: Theory and algorithms, Algorithms Comb., 21, Springer, Heidelberg, 2006 | MR

[14] Křivánek M., Morávek J., “NP-hard problems in hierarchical-tree clustering”, Acta Inf., 23:3 (1986), 311–323 | DOI | MR

[15] Padberg M. W., “$(1,k)$-Configurations and facets for packing problems”, Math. Program., 18 (1980), 94–99 | DOI | MR | Zbl

[16] Padberg M. W., Rinaldi G., “Facet identification for the symmetric traveling salesman polytope”, Math. Program., 47 (1990), 219–257 | DOI | MR | Zbl

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

[18] Schrijver A., Combinatorial optimization. Polyhedra and efficiency, Algorithms Comb., 24, Springer, Heidelberg, 2004 | MR | Zbl

[19] Simanchev R. Yu., Urazova I. V., “On the facets of combinatorial polytopes”, Discrete Optimization and Operations Research, Proc. 9th Int. Conf. (Vladivostok, Russia, Sept. 19–23, 2016), Lect. Notes Comput. Sci., 9869, Springer, Cham, 2016, 233–243 | DOI | MR

[20] Wolsey L.A., “Valid inequalities for 0-1 knapsacks and MIPs with generalised upper bound constraints”, Discrete App. Math., 29:2–3 (1990), 251–261 | DOI | MR | Zbl