Approximate and exact merging of knapsack constraints with cover inequalities. (1st February 2021)

• Record Type: Journal Article
• Authors: Vitor, Fabio; Easton, Todd
• Is Part Of: Optimization. Volume 70:Number 2(2021)
• Page Start: 437
• Page End: 460
• Publication Date: 2021-02-01
• Subjects: Integer programming -- cover inequalities -- knapsack constraints -- cutting planes -- inequality merging; MSC 90C10 -- MSC 90C27 -- MSC 90C39 -- MSC90C57; Mathematical optimization -- Periodicals; 519.7
• DOI: 10.1080/02331934.2020.1719492
• Languages: English
• ISSNs: 0233-1934

Abstract

ABSTRACT: This paper presents both approximate and exact merged knapsack cover inequalities, a class of cutting planes for knapsack and multiple knapsack integer programs. These inequalities combine the information from knapsack constraints and cover inequalities. Approximate merged knapsack cover inequalities can be generated through a O ( n log ⁡ n ) algorithm, where n is the number of variables. This class of inequalities can be strengthened to an exact version with a pseudo-polynomial time algorithm. Computational experiments demonstrate an average improvement of approximately 8 % in solution time and 5 % in the number of ticks from CPLEX when approximate merged knapsack cover inequalities are implemented as preprocessing cuts to solve some benchmark multiple knapsack problems. Furthermore, exact merged knapsack cover inequalities improve the solution time and number of ticks of some random multiple knapsack instances by 15 % and 5 %, respectively.