This volume of Mathematical Programming, Series B (MPB) contains 23 high-quality articles in the area of integer programming and combinatorial optimization. Extended abstracts of these articles have previously appeared in the proceedings of the 23rd Conference on Integer Programming and Combinatorial Optimization (IPCO), held June 27–29, 2022, in Eindhoven, The Netherlands. The proceedings volume, also published by Springer in the Lecture Notes in Computer Science series, volume 13,265, comprises 33 extended abstracts, out of 93 submissions, that were selected and presented at IPCO 2022.

The IPCO conference is under the auspices of the Mathematical Optimization Society and is held every year. Until 2018, years divisible by three (in which the International Symposium on Mathematical Programming took place) were skipped. The conference is a forum for researchers and practitioners working on various aspects of integer programming and combinatorial optimization. The aim is to present recent developments in theory, computation, and applications in these areas. The first IPCO conference took place at the University of Waterloo in May 1990. More information on IPCO and its history can be found at www.mathopt.org/?nav=ipco

All authors of extended abstracts that were accepted for IPCO 2022 were invited to submit full journal papers to be considered for publication in this special volume of MPB. As compared to the IPCO extended abstracts, the full journal papers are roughly twice as long, containing full proofs, extensions of the preliminary results, etc. The submitted papers underwent a fully-rigorous refereeing process, and this volume contains the papers that were accepted after possible revisions. These papers that now appear represent a snapshot of the very best of an exciting and vibrant domain within mathematical programming.

We thank all authors and in particular the referees who reviewed the papers thoroughly and in a timely manner, helping us to complete this special issue. We also thank Andrea Lodi, the Editor-in-Chief of MPB, for his excellent cooperation.@en

The resource constrained project scheduling problem with a flexible project structure and consumption and production of resources, involves making a selection of activities and scheduling these activities in order to minimize the makespan, subject to precedence and resource constraints. Since finding a feasible selection of activities is NP-hard, we introduce the concept of group graphs and restrict ourselves to instances with an acyclic group graph. For these instances, which represent many practical cases, we show how to make a feasible selection of activities in polynomial time and use this concept to schedule the selected activities using a hybrid differential evolution algorithm. We compare this algorithm with an algorithm from the literature on special cases of instances without consumption and production of resources, and show that our algorithm creates solutions of higher quality. Furthermore, to compare general instances, we develop an ant colony optimization algorithm that performs slightly better on special cases than the algorithm from literature and show that the hybrid differential evolution algorithm outperforms the ant colony optimization algorithm on general instances.

@en

Branch-and-bound for integer optimization typically uses single-variable disjunctions. Enumerative methods for integer optimization with theoretical guarantees use a non-binary search tree with general disjunctions based on lattice structure. These disjunctions are expensive to compute and challenging to implement. Here we compare two lattice reformulations that can be used to heuristically obtain general disjunctions in the original space, we develop a new lattice-based variant, and compare the derived disjunctions computationally with those produced by the algorithm of Lovász and Scarf.

@en

The Resource Constrained Project Scheduling Problem with a flexible Project Structure (RCPSP-PS) is a generalization of the Resource Constrained Project Scheduling Problem (RCPSP). The objective of the RCPSP-PS is to find a minimal makespan schedule subject to precedence and resource constraints, while only having to execute a subset of all activities. We present a general model, which is based on a precedence graph and a task selection graph. Furthermore, we introduce an exact solution method including procedures for generating cutting planes and variable reduction. It is shown that both the lower bound obtained from the linear relaxation, and the computation time needed to obtain integer solutions are improved using these procedures.@en

Background Ambulance services play a crucial role in providing pre-hospital emergency care. In order to ensure quick responses, the location of the bases, and the distribution of available ambulances among these bases, should be optimized. In mixed urban-rural areas, this optimization typically involves a trade-off between backup coverage in high-demand urban areas and single coverage in rural low-demand areas. The aim of this study was to find the optimal distribution of bases and ambulances in the Vestfold region of Norway in order to optimize ambulance coverage. Method The optimal location of bases and distribution of ambulances was estimated using the Maximum Expected Covering Location Model. A wide range of parameter settings were fitted, with the number of ambulances ranging from 1 to 15, and an average ambulance utilization of 0, 15, 35 and 50%, corresponding to the empirical numbers for night, afternoon and day, respectively. We performed the analysis both conditioned on the current base structure, and in a fully greenfield scenario. Results Four of the five current bases are located close to the mathematical optimum, with the exception of the northernmost base, in the rural part of the region. Moving this base, along with minor changes to the location of the four other bases, coverage can be increased from 93.46% to 97.51%. While the location of the bases is insensitive to the workload of the system, the distribution of the ambulances is not. The northernmost base should only be used if enough ambulances are available, and this required minimum number increases significantly with increasing system workload. Conclusion As the load of the system increases, focus of the model shifts from providing single coverage in low-demand areas to backup coverage in high-demand areas. The classification rule for urban and rural areas significantly affects results and must be evaluated accordingly.

@en

The primary drivers for buying a ship from a certain yard are price, delivery time and quality. In order to decrease construction time and costs, shipbuilding companies are exploring the development of product-families to include family wide modularity and cross family standardization. Standardization is the use of identical components across multiple products, while modularity combines parts to create 'building-blocks'. This creates an opportunity for less inventory, a more efficient supply chain and shorter delivery times. Considering a network of suppliers and shipyards, the shipbuilder has to answer the following question: Which components and pre-assembled modules should be available in which inventory? Since the exact ship orders are not known, this can be seen as an optimization problem with uncertainty. To solve it, it is formulated as an integer linear program (ILP), and to handle the uncertainty, the Sampling Average Approximation (SAA) method is used. Several smaller instances are solved to optimality by Gurobi optimization software and the performance of this approach is evaluated along with the convergence of the SAA method. The results show convergence of the SAA method although only relatively small instances can be solved to optimality by the ILP.@en

Development in vehicle automation and the shared economy contribute to a growing interest in introducing flexible services. This paper investigates how archived passenger data can be used in the form of demand forecasts to improve routing of vehicles in a Dail-a-Ride problem. Two improvements to the Dail-a-Ride problem are investigated. Empty vehicle rerouting deals with the relocation of idle vehicles. We also introduce a new type of online dynamic insertion algorithm with demand forecasts, which can be incorporate demand forecasts in determining which vehicle serves which passenger. The performance of these algorithms is tested in a simulation model for a case study network in the Netherlands. The inclusion of empty vehicle rerouting reduces passenger rejections by 98% and reduces passenger travel and waiting times by 5 and 16% respectively. This induces an increase in vehicle distance driven per passenger by 25%. The insertion algorithm with demand forecasts reduces travel and waiting times by 6 and 30% respectively, with only a very minor increase in vehicle distance driven. The main conclusion of this paper is that if both measures are applied simultaneously, the strength of both are combined. Passenger rejections are all but eliminated, while travel and waiting time are reduced by up to 10 and 50% respectively. This causes a 25% increase in vehicle distance driven per passenger. A sensitivity analysis tested the robustness of the proposed routing measures to variations in operational and demand conditions. Demand forecasts proved to be a very strong instrument in improving the solution to Dail-a-Ride problems.@en

Background: Helicopter emergency medical services are important in many health care systems. Norway has a nationwide physician manned air ambulance service servicing a country with large geographical variations in population density and incident frequencies. The aim of the study was to compare optimal air ambulance base locations using both population and incident data. Methods: We used municipality population and incident data for Norway from 2015. The 428 municipalities had a median (5-95 percentile) of 4675 (940-36,264) inhabitants and 10 (2-38) incidents. Optimal helicopter base locations were estimated using the Maximal Covering Location Problem (MCLP) optimization model, exploring the number and location of bases needed to cover various fractions of the population for time thresholds 30 and 45 min, in green field scenarios and conditioned on the existing base structure. Results: The existing bases covered 96.90% of the population and 91.86% of the incidents for time threshold 45 min. Correlation between municipality population and incident frequencies was -0.0027, and optimal base locations varied markedly between the two data types, particularly when lowering the target time. The optimal solution using population density data put focus on the greater Oslo area, where one third of Norwegians live, while using incident data put focus on low population high incident areas, such as northern Norway and winter sport resorts. Conclusion: Using population density data as a proxy for incident frequency is not recommended, as the two data types lead to different optimal base locations. Lowering the target time increases the sensitivity to choice of data.

@en

Developments in vehicle automation and the shared economy call for new developments in routing flexible transport services. We propose a new type of insertion algorithm: an online dynamic insertion algorithm with demand forecasts. The performance of this algorithm is tested in a simulation model for a case study network in the Netherlands. When combining the new insertion algorithm with empty vehicle rerouting, 98% of passenger rejections are eliminated and travel and waiting times are reduced by up to 10 and 46% respectively, compared to traditional insertion algorithms. A sensitivity analysis tested performance robustness to variations in operational and demand conditions.@en

We consider the Maximum Weighted Coverage problem (MCP). We can relate the MCP to optimisation problems using submodular functions. Performance guarantees of the Swap Local Search algorithm are known for these problems, but can be improved for the MCP. Our main contribution is a constructive proof of tight performance guarantees for Swap Local Search applied to the MCP, which provides insight into the structure of worst-case MCP instances, and has the potential to be applicable to other optimisation problems.@en

Background Helicopter emergency medical services are an important part of many healthcare systems. Norway has a nationwide physician staffed air ambulance service with 12 bases servicing a country with large geographical variations in population density. The aim of the study was to estimate optimal air ambulance base locations. Methods We used high resolution population data for Norway from 2015, dividing Norway into >300 000 1 km×1 km cells. Inhabited cells had a median (5–95 percentile) of 13 (1–391) inhabitants. Optimal helicopter base locations were estimated using the maximal covering location problem facility location optimisation model, exploring the number of bases needed to cover various fractions of the population for time thresholds 30 and 45 min, both in green field scenarios and conditioning on the current base structure. We reanalysed on municipality level data to explore the potential information loss using coarser population data. Results For a 45 min threshold, 90% of the population could be covered using four bases, and 100% using nine bases. Given the existing bases, the calculations imply the need for two more bases to achieve full coverage. Decreasing the threshold to 30 min approximately doubles the number of bases needed. Results using municipality level data were remarkably similar to those using fine grid information. Conclusions The whole population could be reached in 45 min or less using nine optimally placed bases. The current base structure could be improved by moving or adding one or two select bases. Municipality level data appears sufficient for proper analysis. @en

In this paper we introduce a time-dependent probabilistic location model for Emergency Medical Service (EMS) vehicles. The goal is to maximize the expected coverage throughout the day and at the same time minimize the number of opened facilities and the number of relocations. We apply our model to both a randomly generated test instance and to data from the city of Amsterdam, the Netherlands. We see that time-dependent models can result in better solutions than time-independent models. Furthermore, we see that the current set of base locations in Amsterdam is not optimal. We can obtain higher coverage with even less base locations.@en

We study the capacitated k-facility location problem, in which we are given a set of clients with demands, a set of facilities with capacities and a positive integer k. It costs fi to open facility i, and cij for facility i to serve one unit of demand from client j. The objective is to open at most k facilities serving all the demands and satisfying the capacity constraints while minimizing the sum of service and opening costs. In this paper, we give the first fully polynomial time approximation scheme (FPTAS) for the single-sink (single-client) capacitated k-facility location problem. Then, we show that the capacitated k-facility location problem with uniform capacities is solvable in polynomial time if the number of clients is fixed by reducing it to a collection of transportation problems. Third, we analyze the structure of extreme point solutions, and examine the efficiency of this structure in designing approximation algorithms for capacitated k-facility location problems. Finally, we extend our results to obtain an improved approximation algorithm for the capacitated facility location problem with uniform opening costs.@en

Given facilities with capacities and clients with penalties and demands, the transportation problem with market choice consists in finding the minimum-cost way to partition the clients into unserved clients, paying the penalties, and into served clients, paying the transportation cost to serve them. We give polynomial-time reductions from this problem and variants to the (un)capacitated facility location problem, directly yielding approximation algorithms, two with constant factors in the metric case, one with a logarithmic factor in the general case.@en

Lattice-based reformulation techniques have been used successfully both theoretically and computationally. One such refor-mulation is obtained from the kernel lattice associated with an input matrix. Some of the hard instances in the literature thathave been successfully tackled by lattice-based techniques have randomly generated input. Since the considered instances arevery hard even in low dimension, less experience is available for larger instances. Recently, we have studied larger instancesand observed that the LLL-reduced basis of the kernel lattice has a specific sparse structure. In particular, this translates intoa map in which some of the original variables get a “rich”’ translation into a new variable space, whereas some variables areonly substituted in the new space. If an original variable is important in the sense of branching or cutting planes, this variableshould be translated in a nontrivial way. In this paper we partially explain, through a probabilistic analysis, the obtainedstructure of the LLL-reduced basis in the case that the input matrix consists of one row. The key ingredient is a bound onthe probability that the LLL-algorithm will interchange two subsequent basis vectors@en

Lattice-based reformulation techniques have been used successfully both theoretically and computationally. One such reformulation is obtained from the lattice kerℤ(A) = {x ∈ ℤ n |Ax = 0}. Some of the hard instances in the literature that have been successfully tackled by lattice-based techniques, such as market split and certain classes of knapsack instances, have randomly generated input A. These instances have been posed to stimulate algorithmic research. Since the considered instances are very hard even in low dimension, less experience is available for larger instances. Recently we have studied larger instances and observed that the LLL-reduced basis of kerℤ(A) has a specific sparse structure. In particular, this translates into a map in which some of the original variables get a “rich” translation into a new variable space, whereas some variables are only substituted in the new space. If an original variable is important in the sense of branching or cutting planes, this variable should be translated in a non-trivial way. In this paper we partially explain the obtained structure of the LLL-reduced basis in the case that the input matrix A consists of one row a. Since the input is randomly generated our analysis will be probabilistic. The key ingredient is a bound on the probability that the LLL algorithm will interchange two subsequent basis vectors. It is worth noticing that computational experiments indicate that the results of this analysis seem to apply in the same way also in the general case that A consists of multiple rows. Our analysis has yet to be extended to this general case. Along with our analysis we also present some computational indications that illustrate that the probabilistic analysis conforms well with the practical behavior.@en