Please use this identifier to cite or link to this item: http://hdl.handle.net/10773/16477
Title: Valid inequalities for a single constrained 0-1 MIP set intersected with a conflict graph
Author: Agra, Agostinho
Doostmohammadi, Mahdi
Souza, Cid C. de
Keywords: Mixed integer programming
Valid inequality
Separation
Vertex packing set
Conflict graph
Independent set
Issue Date: Aug-2016
Publisher: Elsevier
Abstract: 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.
Peer review: yes
URI: http://hdl.handle.net/10773/16477
DOI: 10.1016/j.disopt.2016.05.005
ISSN: 1572-5286
Appears in Collections:CIDMA - Artigos
OGTCG - Artigos

Files in This Item:
File Description SizeFormat 
MixingMIRwithCG_2revision_preprint.pdfDocumento principal307.25 kBAdobe PDFView/Open


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.