Автор |
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.. |