Valid inequalities for a single constrained 0-1 MIP set intersected with a conflict graph

Agostinho Agra, Mahdi Doostmohammadi, Cid C. de Souza

Research output: Contribution to journalArticle

2 Citations (Scopus)
10 Downloads (Pure)

Abstract

We consider a mixed integer set which results from the intersection of a single constrained mixed 0-1 set with the vertex packing set. This set arises as a subproblem of more general mixed integer problems. We describe families of strong valid inequalities that consider the structure of the simple mixed integer set and the vertex packing set simultaneously. In particular, a class of valid inequalities that generalizes the well-known mixed integer rounding inequalities to the case where incompatibility between binary variables is considered, is derived. We discuss the separation problems associated to those valid inequalities and present a preliminary computational experiment.
Original languageEnglish
Pages (from-to)42-70
Number of pages29
JournalDiscrete Optimization
Volume21
Early online date21 Jul 2016
DOIs
Publication statusPublished - 31 Aug 2016

    Fingerprint

Keywords

  • mixed integer programming
  • valid inequalities
  • vertex packing set
  • conflict graph
  • independent sets

Cite this