Given a set of items, each requiring a set of elements, the set-union bin packing problem (SUBP) consists of grouping all items into a minimum number of bins such that each item is assigned to exactly one bin and the total weight of all distinct elements required in a bin does not exceed its capacity. The SUBP is a generalization of the well-known bin-packing problem, where items can share one or more elements in a nonadditive fashion. In the literature, it has been addressed by various names such as pagination problem, job grouping problem, tool switching problem, or bin packing problem with overlapping items. We propose a branch-and-price (B&P) algorithm for solving the SUBP. For the column-generation pricing problem, which is a set-union knapsack problem (SUKP), we present and explore alternative solution methods, namely the direct solution of an integer program with a general-purpose MIP solver and two labeling algorithms on ad hoc defined graphs. The overall best B&P variant combines an upfront greedy pricing heuristic and an item-based labeling approach without the application of any dominance. The latter is based on the representation of the pricing problem as a shortest path problem with resource constraints and relies on strong completion bounds as acceleration technique. Ryan-and-Foster branching is applied to ensure integer solutions. Extensive computational results demonstrate the effectiveness of the proposed method. Our B&P significantly outperforms the state-of-the-art IP formulations. It solves to optimality more than 10,000 instances from the literature that have only been solved heuristically before, improving the best known solutions for more than half of the benchmark. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This work was supported by Deutsche Forschungsgemeinschaft [Grant GS 83/1-1 Project No. 418727865]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0791 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0791 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

ABSTRACT This work considers branch‐price‐and‐cut algorithms for variants of the vehicle‐routing problem in which subset‐row inequalities (SRIs) are used to strengthen the linear relaxation. SRIs often help to substantially reduce the size of the branch‐and‐bound search tree. However, their use is computationally costly because SRIs modify the structure of the respective column‐generation subproblem, which is a shortest‐path problem with resource constraints (SPPRC). Each active SRI requires the addition of a resource to the labeling algorithm that is invoked for solving the SPPRC in every iteration. In the context of time‐window constraints, the concept of unreachable customers has been used for preprocessing (time‐window reduction, arc elimination, precedence identification) as well as for improving the dominance between labels in the elementary SPPRC and its relaxations. We show that the identification of unreachable customers can also help to improve the dominance due to a modified comparison of SRI‐related resources. Computational experiments with a fully fledged branch‐price‐and‐cut algorithm for the (standard and electric) vehicle‐routing problem with time windows demonstrate the effectiveness of the approach: Overall computation times decrease; for some difficult instances, they may even be cut in half, while the required modifications of a computer implementation for combining SRIs with unreachable customers are minor.

Many routing and scheduling problems are modeled through variables that represent paths (routes, schedules, etc.). For such extensive formulations, branch-price-and-cut (BPC) algorithms nowadays constitute the leading exact solution technique, and most of the time, the pricing problem is a shortest-path problem with resource constraints that can be solved by a dynamic-programming labeling algorithm. For this setting, variable fixing techniques based on the reduced costs of the paths have been proposed with the aim of eliminating arcs from the underlying network and speeding up the solution process of the pricing problem as well as of the overall BPC algorithm. For an efficient variable fixation, bidirectional labeling must be possible. We move one step forward and show how the reduced costs of paths can also be exploited to reduce the resource windows for many types of resources, including the time resource and a load-related resource. This can be achieved without modifying the pricing problem network and altering the structure of the pricing problem itself. Moreover, different resources can be considered simultaneously. A straightforward reduction of the resource windows associated with the vertices of the network can tighten them, but this reduction does not translate into savings in computation times. On the contrary, the reduction of the resource windows is effective when distinct forward and backward resource windows are defined for each arc and reduced independently based on the traversal direction of the arc itself. Moreover, an arc can be eliminated when one of its arc-specific resource windows becomes empty, and the explicit use of variable fixing techniques can be avoided. Computational results obtained for benchmark instances of the vehicle-routing problem with time windows show that the overall computation times of the BPC algorithm can be significantly reduced compared with a fully fledged BPC algorithm using variable fixing techniques. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms – Discrete. Funding: This research was supported by the Deutsche Forschungsgemeinschaft (DFG) [Grants GS 83/1-1 and IR 122/10-1] of Project 418727865. This support is gratefully acknowledged.

We study the family of problems of partitioning and covering a graph into/with a minimum number of relaxed cliques. Relaxed cliques are subsets of vertices of a graph for which a clique-defining property—for example, the degree of the vertices, the distance between the vertices, the density of the edges, or the connectivity between the vertices—is relaxed. These graph partitioning and covering problems have important applications in many areas such as social network analysis, biology, and disease-spread prevention. We propose a unified framework based on branch-and-price techniques to compute optimal decompositions. For this purpose, new, effective pricing algorithms are developed, and new branching schemes are invented. In extensive computational studies, we compare several algorithmic designs, such as structure-preserving versus dichotomous branching, and their interplay with different pricing algorithms. The final chosen branch-and-price setup produces results that demonstrate the effectiveness of all components of the newly developed framework and the validity of our approach when applied to social network instances.

Column generation (CG) models have several advantages over compact formulations: they provide better linear program bounds, may eliminate symmetry, and can hide nonlinearities in their subproblems. However, users also encounter drawbacks in the form of slow convergence, also known as the tailing-off effect, and the oscillation of the dual variables. Among different alternatives for stabilizing the CG process, Ben Amor et al. [Ben Amor H, Desrosiers J, Valério de Carvalho JM (2006) Dual-optimal inequalities for stabilized column generation. Oper. Res. 54(3):454–463] suggest the use of dual-optimal inequalities (DOIs) in the context of cutting stock and bin packing problems. We generalize their results, provide new classes of (deep) DOIs, and show the applicability to other problems (vector packing, vertex coloring, bin packing with conflicts). We also suggest the dynamic addition of violated dual inequalities in a cutting-plane fashion and the use of dual inequalities that are not necessarily (deep) DOIs. In the latter case, a recovery procedure is needed to restore primal feasibility. Computational results proving the usefulness of the methods are presented.