Computational Aspects of Lifted Cover Inequalities for Knapsacks with Few Different Weights
Christopher Hojny, Cédric Roy · 2024
Read Computational Aspects of Lifted Cover Inequalities for Knapsacks with Few Different Weights by Christopher Hojny, Cédric Roy (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-14919.txt.
Introduction
Christopher Hojny and Cédric Roy sped up a cutting-plane method for packing problems in a 2024 paper. Integer programs model choices like loading a knapsack to the best value, and extra inequalities, called cuts, trim away useless fractional options. A prized family of cuts comes from minimal covers, but finding the best such cut is provably hard in general, so solvers settle for rough guesses.
Many real knapsacks, though, reuse only a few distinct weights. In that sparse case, covers fall into only modestly many structural types. Hojny and Roy exploit that with sorting tricks that handle whole types of cuts at once. Benchmark gains follow where few weights repeat often across big models.
Catalog record
| CREATOR | Christopher Hojny, Cédric Roy |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 91 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-14919
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Computational Aspects of Lifted Cover Inequalities for Knapsacks with Few Different Weights Christopher Hojny, Cédric Roy Abstract Cutting planes are frequently used for solving integer programs. A common strategy is to derive cutting planes from building blocks or a substructure of the integer program. In this paper, we focus on knapsack constraints that arise from single row relaxations. Among the most popular classes derived from knapsack constraints are lifted minimal cover inequalities. The separation problem for these inequalities is NP-hard though, and one usually separates them heuristically, therefore not fully exploiting their potential. For many benchmarking instances however, it turns out that many knapsack constraints only have few different coefficients. This motivates the concept of sparse knapsacks where the number of different coefficients is a small constant, independent of the number of variables present. For such knapsacks, we observe that there are only polynomially many different classes of structurally equivalent minimal covers. This opens the door to specialized techniques for using lifted minimal cover inequalities. In this article we will discuss two such techniques, which are based on specialized sorting methods. On the one hand, we present new separation routines that separate equivalence classes of inequalities rather than individual inequalities. On the other hand, we derive compact extended formulations that express all lifted minimal cover inequalities by means of a polynomial number of constraints. These extended formulations are based on tailored sorting networks that express our separation algorithm by linear inequalities. We conclude the article by a numerical investigation of the different techniques for popular benchmarking instances. This article is part of the project “Local Symmetries for Global Success” with project number OCENW.M.21.299, which is financed by the Dutch Research Council (NWO). 1 Introduction We consider binary programs \max\{{d}^{\top}{x}:Ax\leq b,\;x\in\{0,1\}^{n}\} , where A\in\mathds{R}^{m\times n} , b\in\mathds{R}^{m} , and d\in\mathds{R}^{n} . A standard technique to solve such problems is branch-and-bound [ 1 ] . Among the many techniques to enhance branch-and-bound, one popular class are cutting planes. These are inequalities {c}^{\top}{x}\leq\delta that are satisfied by each feasible solution of the binary program, but which exclude some points of the LP relaxation. Cutting planes turn out to be a crucial component of modern branch-and-bound solvers, since disabling them may degrade the performance drastically [ 2 ] . Many families of cutting planes are known in the literature. In this article, we focus on cutting planes arising from knapsack polytopes, which are among the most extensively studied [ 3 , 4 , 5 , 6 , 7 , 8 , 9 ] . A knapsack set is a set K^{a,\beta}=\left\{x\in\{0,1\}^{n}:{a}^{\top}{x}\leq\beta\right\} for some non-negative vector a\in\mathds{Z}^{n} and positive integer \beta ; the corresponding knapsack polytope is P^{a,\beta}=\conv(K^{a,\beta}) , where \conv(\cdot) denotes the convex hull operator. Note that any cutting plane derived from knapsack sets can be used for general binary programs by considering a single row of the inequality system Ax\leq b (after possibly complementing some variables). A popular class of knapsack-based cutting planes are derived from so-called covers. A cover is a set C\subseteq[n]\coloneqq\{1,\dots,n\} with \sum_{i\in C}a_{i}>\beta . The corresponding cover inequality [ 3 , 10 , 11 ] is \sum_{i\in C}x_{i}\leq\left\lvert C\right\rvert-1 , which implies that not all elements in C can simultaneously attain value 1. It is easy to show that, given two covers C,C^{\prime} , the cover inequality for C can be dominated by the inequality for C^{\prime} if C^{\prime}\subsetneq C . This motivates to consider covers C that are minimal , i.e., no proper subset of C is a cover. To strengthen these inequalities even further, so-called sequential lifting [ 12 ] can be used to turn a cover inequality for a minimal cover C into a facet-defining inequality \sum_{i\in C}x_{i}+\sum_{i\in[n]\setminus C}\alpha_{i}x_{i}\leq\left\lvert C\right\rvert-1 (1) for the knapsack polytope, i.e, the inequality cannot be dominated by other inequalities. To use lifted cover inequalities (LCIs) as cutting planes, one could, in principle, fully enumerate and add them to the binary program. However, since there might be exponentially many covers, this is practically infeasible. Alternatively, one could add violated LCIs dynamically during the solving process. Deciding whether a violated LCI exists, is NP-complete [ 13 ] though. In practice, one therefore usually adds violated LCIs heuristically [ 14 ] . For many knapsacks arising from the MIPLIB 2017 [ 15 ] test set, however, we made an important observation: they only have very few different coefficients, say less than five. Indeed, as illustrated by Figure 1 , approximately 41\text{\,}\mathrm{\%} of all knapsacks have at most 4 different coefficients 1 1 1 In A , we provide details on how these numbers have been found. . Moreover, although the number of different coefficients can be small, the knapsacks still can contain hundreds or thousands of variables, e.g., 40\text{\,}\mathrm{\%} of knapsacks with only four different coefficients contain more than 120 variables, see Figure 2 . To the best of our knowledge, this structure is not exploited in integer programming solvers. (a) Absolute frequency. (b) Cumulative frequency in percent. Figure 1: Illustration of the frequencies at which sparse knapsacks arise in MIPLIB 2017. The horizontal axis shows the sparsity and the vertical axis plots the (cumulative) frequency of the respective sparsity level. (a) Sparsity 3. (b) Sparsity 4. Figure 2: For fixed sparsity of 3 and 4, illustration of the cumulative frequency at which knapsacks of a specific size arise in MIPLIB 2017. The horizontal axis shows the size of the knapsack (number of variables) and the vertical axis plots the cumulative frequency of knapsacks of this size. We therefore investigate so-called sparse knapsacks in this article. A knapsack with inequality \sum_{i=1}^{n}a_{i}x_{i}\leq\beta is called \sigma -sparse if the number of different coefficients is at most \sigma . After introducing some notation, in Section 2 we show how the simplified structure of sparse knapsacks allows for solving the separation problem for LCIs in polynomial time (Theorem 1 ). In Section 3 we propose a polyhedral model for this the separation procedure, using sorting networks. We have implemented our techniques for sparse knapsacks in the academic solver SCIP [ 16 ] and give an overview of it in Section 4 . In Section 5 , we report on numerical experience, showing, among others, that exactly separating LCIs for sparse knapsacks can substantially improve the performance of SCIP . Related Literature In the following we provide an overview of cutting planes derived from knapsack polytopes. We refer the reader to the survey [ 8 ] for a more detailed discussion. Deriving inequalities from covers [ 3 , 10 , 11 ] is a well-known topic in the domain of integer programming. These cover inequalities can be strengthened by lifting all the coefficients for variables not in C . There exist facet-defining lifting sequences [ 12 , 17 ] , so-called down-lifting sequences [ 18 , 9 ] , or even simultaneous lifting procedures [ 19 , 7 , 20 , 21 , 22 , 23 ] . Additionally, there also exist lifting techniques for variations of the original problem, such as liftings for non-minimal covers [ 20 ] or liftings for 0/1-coefficient polytopes [ 24 ] . Balas and Zemel [ 10 ] gave a complete description of the facet-defining inequalities arising from lifted cover inequalities. Deciding whether