Picture of DNA strand

Pioneering chemical biology & medicinal chemistry through Open Access research...

Strathprints makes available scholarly Open Access content by researchers in the Department of Pure & Applied Chemistry, based within the Faculty of Science.

Research here spans a wide range of topics from analytical chemistry to materials science, and from biological chemistry to theoretical chemistry. The specific work in chemical biology and medicinal chemistry, as an example, encompasses pioneering techniques in synthesis, bioinformatics, nucleic acid chemistry, amino acid chemistry, heterocyclic chemistry, biophysical chemistry and NMR spectroscopy.

Explore the Open Access research of the Department of Pure & Applied Chemistry. Or explore all of Strathclyde's Open Access research...

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

Agra, Agostinho and Doostmohammadi, Mahdi and Carvalho de Souza, Cid (2016) Valid inequalities for a single constrained 0-1 MIP set intersected with a conflict graph. Discrete Optimization, 21. pp. 42-70.

Text (Agra-etal-DO-2016-Valid-inequalities-for-a-single-constrained-0-1-MIP-set)
Accepted Author Manuscript
License: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 logo

Download (285kB)| Preview


    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.