Branch-and-Cut algorithm for the connected-cut problem
| hal.structure.identifier | Laboratoire d'Informatique de Paris-Nord [LIPN] | |
| dc.contributor.author | BORNE, Sylvie | |
| hal.structure.identifier | Recherche Opérationnelle [RO] | |
| dc.contributor.author | FOUILHOUX, Pierre | |
| hal.structure.identifier | Laboratoire d'Informatique de Paris-Nord [LIPN] | |
| dc.contributor.author | GRAPPE, Roland | |
| hal.structure.identifier | Laboratoire d'Informatique de Paris-Nord [LIPN] | |
| dc.contributor.author | LACROIX, Mathieu | |
| hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| dc.contributor.author | PESNEAU, Pierre | |
| dc.date.accessioned | 2024-04-04T02:19:47Z | |
| dc.date.available | 2024-04-04T02:19:47Z | |
| dc.date.created | 2014 | |
| dc.date.conference | 2014-02-26 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/189437 | |
| dc.description.abstractEn | <p align="JUSTIFY">Let G=(V,E) be an undirected connected graph. Let W be a subset of V, distinct from V. The set W is said proper when it is non-empty. We denote by δ(W), the set of edges of E having exactly one endnode in W. A set F is called a cut of G, if there exists a proper subset W of V such that F=δ(W). Note that removing from a graph the edges of a cut can leave more than 2 connected components. Consequently, a cut is said to be connected if both subgraphs G[W] =(W,E(W)) and G[V\W] =(V\W,E(V\W)) are connected.</p> <p align="JUSTIFY">Let c be a cost function defined on the edges of E, the maximum cut problem (Max-C) consists in finding a cut of maximum weight (where the weight of a cut is given by the summation of the costs of all the edges composing the cut). The particular case where the cost function is non-positive is called the minimum cut problem (Min-C). In a similar way, we can define the maximum (resp. minimum) connected cut problem Max-CC (resp. Min-CC) as finding a maximum cost connected cut.</p> <p align="JUSTIFY">It is easily seen that an optimal solution of the Min-C will be a connected cut and thus an optimal solution of the Min-CC. Consequently the Min-CC can be solved in polynomial time. The Max-C is strongly NP-hard. However, when the graph is planar, the Max-C problem can be solved in polynomial time [1], whereas the Max-CC is still NP-hard [2].</p> <p align="JUSTIFY">In this talk, we present integer formulations for the Max-CC together with preliminary results on the associated polytope. We also propose a Branch-and-Cut algorithm in order to solve instances generated from the TSPLIB.</p> <p align="JUSTIFY">[1] F. Hadlock, Finding a maximum cut of a planar graph in polynomial time, SIAM Journal of Computing vol. 4 (1975) 221-225.<br />[2] Haglin, Venkatesan, Approximation and Intractability results for the maximum cut problem and its variants, IEEE Trans. on computers 40 (1991) 110-113.</p> <p> </p> | |
| dc.language.iso | fr | |
| dc.subject.en | cut | |
| dc.subject.en | polyedral approach | |
| dc.subject.en | Branch | |
| dc.subject.en | and | |
| dc.subject.en | Graph | |
| dc.title.en | Branch-and-Cut algorithm for the connected-cut problem | |
| dc.type | Communication dans un congrès | |
| dc.subject.hal | Informatique [cs]/Recherche opérationnelle [cs.RO] | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.conference.title | ROADEF - 15ème congrès annuel de la Société française de recherche opérationnelle et d'aide à la décision | |
| bordeaux.country | FR | |
| bordeaux.conference.city | Bordeaux | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-00946285 | |
| hal.version | 1 | |
| hal.invited | non | |
| hal.proceedings | non | |
| hal.conference.organizer | Société française de recherche opérationnelle et d'aide à la décision | |
| hal.conference.end | 2014-02-28 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-00946285v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.au=BORNE,%20Sylvie&FOUILHOUX,%20Pierre&GRAPPE,%20Roland&LACROIX,%20Mathieu&PESNEAU,%20Pierre&rft.genre=unknown |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||