Two New Reformulation Convexification Based Hierarchies for 0-1 MIPs
Author
Source
Advances in Operations Research
Issue
Vol. 2015, Issue 2015 (31 Dec. 2015), pp.1-13, 13 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2015-11-29
Country of Publication
Egypt
No. of Pages
13
Main Subjects
Information Technology and Computer Science
Abstract EN
First, we introduce two new reformulation convexification based hierarchies called RTC and RSC for which the rank d continuous relaxations are denoted by P ^ R T C d and P ^ R S C d , respectively.
These two hierarchies are obtained using two different convexification schemes: term convexification in the case of the RTC hierarchy and standard convexification in the case of the RSC hierarchy.
Secondly, we compare the strength of these two hierarchies.
We will prove that (i) the hierarchy RTC is equivalent to the RLT hierarchy of Sherali-Adams, (ii) the hierarchy RTC dominates the hierarchy RSC, and (iii) the hierarchy RSC is dominated by the Lift-and-Project hierarchy.
Thirdly, for every rank d , we will prove that conv T d ∩ E t d ⊆ P ^ R T C d ⊆ T d and conv S d ∩ E s d ⊆ P ^ R S C d ⊆ S d where the sets T d and S d are convex, while E t d and E s d are two nonconvex sets with empty interior (all these sets depend on the convexification step).
The first inclusions allow, in some cases, an explicit characterization (in the space of the original variables) of the RLT relaxations.
Finally, we will discuss weak version of both RTC and RSC hierarchies and we will emphasize some connections between them.
American Psychological Association (APA)
Ouzia, Hacene. 2015. Two New Reformulation Convexification Based Hierarchies for 0-1 MIPs. Advances in Operations Research،Vol. 2015, no. 2015, pp.1-13.
https://search.emarefa.net/detail/BIM-1053799
Modern Language Association (MLA)
Ouzia, Hacene. Two New Reformulation Convexification Based Hierarchies for 0-1 MIPs. Advances in Operations Research No. 2015 (2015), pp.1-13.
https://search.emarefa.net/detail/BIM-1053799
American Medical Association (AMA)
Ouzia, Hacene. Two New Reformulation Convexification Based Hierarchies for 0-1 MIPs. Advances in Operations Research. 2015. Vol. 2015, no. 2015, pp.1-13.
https://search.emarefa.net/detail/BIM-1053799
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1053799