Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Entry for encyclopedia/dictionary
Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Entry for encyclopedia/dictionary
}
TY - CHAP
T1 - Cover Inequalities
AU - Kaparis, Konstantinos
AU - Letchford, A N
PY - 2011/2
Y1 - 2011/2
N2 - Many problems arising in OR/MS can be formulated as mixed-integer linear programs (MILPs): see the article titled Formulating Good MILP Models in this encyclopedia.If one wishes to solve a class of MILPs to proven optimality, or near optimality, itis often useful to have a class of cutting planes available. Cutting planes are linearinequalities that are satisfied by all feasible solutions to the MILP, but may be violated by solutions to its continuous relaxation (see Branch and Cut).This article is concerned with one particular class of cutting planes—the cover inequalities—along with some variants of them.Cover inequalities were originally defined in the context of the 0–1 Knapsack problem (0–1 KP), but can be applied to any 0–1 linear program (0–1 LP). Moreover, the idea underlying the cover inequalities has been extended to yield cutting planes for other knapsack-type problems and other kinds ofMILPs.The article is structured as follows. In the section titled ‘‘Theory,’’ we recall the theory underlying the inequalities. In the section titled ‘‘Algorithmic Aspects,’’ we discuss some algorithmic questions that must be addressed if one wishes to actually use cover inequalities in a cutting-plane algorithm. In the section titled ‘‘Applications,’’ we list some of the problems to which cover inequalities havebeen applied. Finally, at the end of the article, we give some pointers for further reading.
AB - Many problems arising in OR/MS can be formulated as mixed-integer linear programs (MILPs): see the article titled Formulating Good MILP Models in this encyclopedia.If one wishes to solve a class of MILPs to proven optimality, or near optimality, itis often useful to have a class of cutting planes available. Cutting planes are linearinequalities that are satisfied by all feasible solutions to the MILP, but may be violated by solutions to its continuous relaxation (see Branch and Cut).This article is concerned with one particular class of cutting planes—the cover inequalities—along with some variants of them.Cover inequalities were originally defined in the context of the 0–1 Knapsack problem (0–1 KP), but can be applied to any 0–1 linear program (0–1 LP). Moreover, the idea underlying the cover inequalities has been extended to yield cutting planes for other knapsack-type problems and other kinds ofMILPs.The article is structured as follows. In the section titled ‘‘Theory,’’ we recall the theory underlying the inequalities. In the section titled ‘‘Algorithmic Aspects,’’ we discuss some algorithmic questions that must be addressed if one wishes to actually use cover inequalities in a cutting-plane algorithm. In the section titled ‘‘Applications,’’ we list some of the problems to which cover inequalities havebeen applied. Finally, at the end of the article, we give some pointers for further reading.
U2 - 10.1002/9780470400531
DO - 10.1002/9780470400531
M3 - Entry for encyclopedia/dictionary
SN - 978-0-470-40063-0
BT - Wiley Encyclopedia of Operations Research and Management Science
A2 - Cochran, James J.
A2 - Cox, Louis Anthony
A2 - Keskinocak, Pinar
A2 - Kharoufeh, Jeffrey P.
A2 - Smith, J. Cole
PB - Wiley
ER -