12,000

We have over 12,000 students, from over 100 countries, within one of the safest campuses in the UK

93%

93% of Lancaster students go into work or further study within six months of graduating

Home > Research > Publications & Outputs > Cover Inequalities
View graph of relations

« Back

Cover Inequalities

Research output: Contribution in Book/Report/ProceedingsEntry for encyclopedia/dictionary

Published

Publication date02/2011
Host publicationWiley Encyclopedia of Operations Research and Management Science
EditorsJames J. Cochran, Louis Anthony Cox, Pinar Keskinocak, Jeffrey P. Kharoufeh, J. Cole Smith
PublisherWiley
Number of pages0
ISBN (Print)978-0-470-40063-0
Original languageEnglish

Abstract

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, it
is often useful to have a class of cutting planes available. Cutting planes are linear
inequalities 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 of
MILPs.
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 have
been applied. Finally, at the end of the article, we give some pointers for further reading.