| Автор | De Simone, C. |
| Автор | Rinaldi, G. |
| Дата выпуска | 1994 |
| dc.description | In this paper we describe a cutting plane algorithm to solve max-cut problems on complete graphs. We show that the separation problem over the cut polytope can be reduced to the separation problem over the cut cone and we give a separation algorithm for a class of inequalities valid over the cut cone: the hypermetric inequalities. Computational results are given. |
| Формат | application.pdf |
| Издатель | Gordon and Breach Science Publishers |
| Копирайт | Copyright Taylor and Francis Group, LLC |
| Тема | Polyhedral Combinatorics |
| Тема | Separation Problem |
| Тема | Maximum Cut Problem |
| Тема | Hypermetric Inequality |
| Название | A cutting plane algorithm for the max-cut problem |
| Тип | other |
| DOI | 10.1080/10556789408805564 |
| Electronic ISSN | 1029-4937 |
| Print ISSN | 1055-6788 |
| Журнал | Optimization Methods and Software |
| Том | 3 |
| Первая страница | 195 |
| Последняя страница | 214 |
| Аффилиация | De Simone, C.; Istituto di Analisi dei Sistemi ed Inforrnatica del CNR |
| Аффилиация | Rinaldi, G.; Istituto di Analisi dei Sistemi ed Inforrnatica del CNR |
| Выпуск | 1-3 |
| Библиографическая ссылка | Barahona, F. and Mahjoub, A. R. 1986. On the cut polytope. Mathematical Programming, 36: 157–173. |
| Библиографическая ссылка | Barahona, F., Jünger, M. and Reinelt, G. 1989. Experiments in quadratic 0-1 Programming. Mathematical Programming, 44: 127–137. |
| Библиографическая ссылка | Carter, M. W. 1984. The indefinite zero-one quadratic problem. Discrete Applied Mathematics, 7: 23–44. |
| Библиографическая ссылка | De Simone, C. 1989. The Cut Polytope and the Boolean Quadric Polytope. Discrete Mathematics, 79: 71–75. |
| Библиографическая ссылка | De Simone, C., Deza, M. and Laurent, M. Proceedings of the Second Japan Conference on Graph Theory and Combinatorics . August. pp.18–22. Hakone, , Japan |
| Библиографическая ссылка | De Simone, C. 1991. The Max Cut Problem, Rutgers University. Ph. D. Thesis |
| Библиографическая ссылка | Deza, M. and Laurent, M. 1992. Facets for the cut cone I. Mathematical Programming, 56: 121–160. |
| Библиографическая ссылка | Grishukhin, V. P. 1990. All facets of the Hamming cone for n=7 are known. European Journal of Combinatorics, 11: 115–117. |
| Библиографическая ссылка | Padberg, M. and Rinaldi, G. 1991. A Branch-and Cut Algorithm for the Resolution of Large-Scale Symmetric Travelling Salesman Problems. SIAM Review , 11: 60–100. |
| Библиографическая ссылка | Williams, A. C. 1985. “Quadratic 0-1 programming using the roof dual with computational results, RUTCOR Research Report 8-85”. The State Univ. of New Jersey.. |
