TY - JOUR
T1 - Valid inequalities for a single constrained 0-1 MIP set intersected with a conflict graph
AU - Agra, Agostinho
AU - Doostmohammadi, Mahdi
AU - De Souza, Cid C.
PY - 2016/8/1
Y1 - 2016/8/1
N2 - In this paper a mixed integer set resulting from the intersection of a single constrained mixed 0-1 set with the vertex packing set is investigated. This set arises as a subproblem of more general mixed integer problems such as inventory routing and facility location problems. Families of strong valid inequalities that take into account the structure of the simple mixed integer set and that of the vertex packing set simultaneously are introduced. In particular, the well-known mixed integer rounding inequality is generalized to the case where incompatibilities between binary variables are present. Exact and heuristic algorithms are designed to solve the separation problems associated to the proposed valid inequalities. Preliminary computational experiments show that these inequalities can be useful to reduce the integrality gaps and to solve integer programming problems.
AB - In this paper a mixed integer set resulting from the intersection of a single constrained mixed 0-1 set with the vertex packing set is investigated. This set arises as a subproblem of more general mixed integer problems such as inventory routing and facility location problems. Families of strong valid inequalities that take into account the structure of the simple mixed integer set and that of the vertex packing set simultaneously are introduced. In particular, the well-known mixed integer rounding inequality is generalized to the case where incompatibilities between binary variables are present. Exact and heuristic algorithms are designed to solve the separation problems associated to the proposed valid inequalities. Preliminary computational experiments show that these inequalities can be useful to reduce the integrality gaps and to solve integer programming problems.
KW - Conflict graph
KW - Independent set
KW - Mixed integer programming
KW - Separation
KW - Valid inequality
KW - Vertex packing set
UR - http://www.scopus.com/inward/record.url?scp=84975721625&partnerID=8YFLogxK
U2 - 10.1016/j.disopt.2016.05.005
DO - 10.1016/j.disopt.2016.05.005
M3 - Article
AN - SCOPUS:84975721625
VL - 21
SP - 42
EP - 70
JO - Discrete Optimization
JF - Discrete Optimization
SN - 1572-5286
ER -