Essec\Faculty\Model\Contribution {#2216
  #_index: "academ_contributions"
  #_id: "13114"
  #_source: array:26 [
    "id" => "13114"
    "slug" => "the-minimum-chromatic-violation-problem-a-polyhedral-study"
    "yearMonth" => "2020-07"
    "year" => "2020"
    "title" => "The minimum chromatic violation problem: a polyhedral study"
    "description" => "BRAGA, M., DELLE DONNE, D., ESCALANTE, M., MARENCO, J. et VARALDO, M.C. (2020). The minimum chromatic violation problem: a polyhedral study. <i>Discrete Applied Mathematics</i>, 281(1), pp. 69-80."
    "authors" => array:5 [
      0 => array:3 [
        "name" => "DELLE DONNE Diego"
        "bid" => "B00788133"
        "slug" => "delle-donne-diego"
      ]
      1 => array:1 [
        "name" => "BRAGA Mónica"
      ]
      2 => array:1 [
        "name" => "ESCALANTE Mariana"
      ]
      3 => array:1 [
        "name" => "MARENCO Javier"
      ]
      4 => array:1 [
        "name" => "VARALDO M.C."
      ]
    ]
    "ouvrage" => ""
    "keywords" => array:4 [
      0 => "Chromatic violation"
      1 => "Graph coloring"
      2 => "Polyhedral study"
      3 => "partition"
    ]
    "updatedAt" => "2023-01-27 01:00:44"
    "publicationUrl" => "https://doi.org/10.1016/j.dam.2019.05.010"
    "publicationInfo" => array:3 [
      "pages" => "69-80"
      "volume" => "281"
      "number" => "1"
    ]
    "type" => array:2 [
      "fr" => "Articles"
      "en" => "Journal articles"
    ]
    "support_type" => array:2 [
      "fr" => "Revue scientifique"
      "en" => "Scientific journal"
    ]
    "countries" => array:2 [
      "fr" => null
      "en" => null
    ]
    "abstract" => array:2 [
      "fr" => "In this paper we define a generalization of the classical vertex coloring problem of a graph, where some pairs of adjacent vertices can be assigned to the same color. We call weak an edge connecting two such vertices. We look for a coloring of the graph minimizing the number of weak edges having its endpoints assigned to the same color. This problem is called the minimum chromatic violation problem (MCVP). We present an integer programming formulation for this problem and provide an initial polyhedral study of the polytope arising from this formulation. We give partial characterizations of facet-inducing inequalities and we show how facets from different instances of MCVP are related. We then introduce general lifting procedures which generate (sometimes facet-inducing) valid inequalities from generic valid inequalities. We exhibit several facet-inducing families arising from these procedures and we present a family of facet-inducing inequalities which is not obtained from the prior lifting procedures, associated with certain substructures in the given graph. Finally, we analyze the extreme case of all weak edges and its relationship with the well-known -partition problem."
      "en" => "In this paper we define a generalization of the classical vertex coloring problem of a graph, where some pairs of adjacent vertices can be assigned to the same color. We call weak an edge connecting two such vertices. We look for a coloring of the graph minimizing the number of weak edges having its endpoints assigned to the same color. This problem is called the minimum chromatic violation problem (MCVP). We present an integer programming formulation for this problem and provide an initial polyhedral study of the polytope arising from this formulation. We give partial characterizations of facet-inducing inequalities and we show how facets from different instances of MCVP are related. We then introduce general lifting procedures which generate (sometimes facet-inducing) valid inequalities from generic valid inequalities. We exhibit several facet-inducing families arising from these procedures and we present a family of facet-inducing inequalities which is not obtained from the prior lifting procedures, associated with certain substructures in the given graph. Finally, we analyze the extreme case of all weak edges and its relationship with the well-known -partition problem."
    ]
    "authors_fields" => array:2 [
      "fr" => "Systèmes d'Information, Data Analytics et Opérations"
      "en" => "Information Systems, Data Analytics and Operations"
    ]
    "indexedAt" => "2024-11-21T15:21:45.000Z"
    "docTitle" => "The minimum chromatic violation problem: a polyhedral study"
    "docSurtitle" => "Journal articles"
    "authorNames" => "<a href="/cv/delle-donne-diego">DELLE DONNE Diego</a>, BRAGA Mónica, ESCALANTE Mariana, MARENCO Javier, VARALDO M.C."
    "docDescription" => "<span class="document-property-authors">DELLE DONNE Diego, BRAGA Mónica, ESCALANTE Mariana, MARENCO Javier, VARALDO M.C.</span><br><span class="document-property-authors_fields">Information Systems, Data Analytics and Operations</span> | <span class="document-property-year">2020</span>"
    "keywordList" => "<a href="#">Chromatic violation</a>, <a href="#">Graph coloring</a>, <a href="#">Polyhedral study</a>, <a href="#">partition</a>"
    "docPreview" => "<b>The minimum chromatic violation problem: a polyhedral study</b><br><span>2020-07 | Journal articles </span>"
    "docType" => "research"
    "publicationLink" => "<a href="https://doi.org/10.1016/j.dam.2019.05.010" target="_blank">The minimum chromatic violation problem: a polyhedral study</a>"
  ]
  +lang: "en"
  +"_type": "_doc"
  +"_score": 8.68352
  +"parent": null
}