Configuring Mixed-Integer Programming Solvers for Large-Scale Instances

Kemminer, Robin; Lange, Jannick; Kempkes, Jens Peter; Tierney, Kevin; Weiß, Dimitri Article — Published Version Configuring Mixed-Integer Programming Solversfor Large-Scale Instances Operations Research Forum Provided in Cooperation with: Springer Nature Suggested Citation: Kemminer, Robin; Lange, Jannick; Kempkes, Jens Peter; Tierney, Kevin; Weiß, Dimitri (2024) : Configuring Mixed-Integer Programming Solversfor Large-Scale Instances, Operations Research Forum, ISSN 2662-2556, Springer International Publishing, Cham, Vol. 5, Iss. 2, https://doi.org/10.1007/s43069-024-00327-7 This Version is available at: https://hdl.handle.net/10419/316971 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. http://creativecommons.org/licenses/by/4.0/ https://doi.org/10.1007/s43069-024-00327-7 RESEARCH Configuring Mixed-Integer Programming Solvers for Large-Scale Instances Robin Kemminer1·Jannick Lange1·Jens Peter Kempkes1·Kevin Tierney2· Dimitri Weiß2 Received: 6 April 2023 / Accepted: 30 April 2024 / Published online: 30 May 2024 Abstract Algorithm configuration techniques automatically search for parameters of solvers and algorithms that provide minimal runtime or maximal solution quality on specified instance sets. Mixed-integer programming (MIP) solvers pose a particular challenge for algorithm configurators due to the difficulty of finding optimal, or even feasible, solutions on the large-scale problems commonly found in practice. We introduce the OPTANO Algorithm Tuner (OAT) to find configurations for MIP solvers and other optimization algorithms. We present and evaluate several critical components of OAT for solving MIPs in particular and show that OAT can find configurations that significantly improve the solution time of MIPs on two different datasets. Keywords Algorithm configuration ·Mixed-integer programming ·Large-scale problem instances BKevin Tierney ke[email protected] Robin Kemminer [email protected] Jannick Lange [email protected] Jens Peter Kempkes jens.peter[email protected] Dimitri Weiß [email protected] 1OPTANO GmbH, Technologiepark 18, Paderborn 33100, NRW, Germany 2Decision and Operation Technologies, Bielefeld University, Universitätsstraße 25, Bielefeld 33615, NRW, Germany 123 Operations Research Forum (2024) 5: 48 © The Author(s) 2024 1 Introduction The performance of algorithms and solvers varies greatly depending on the settings of the parameters controlling the behavior of the approach [1]. In particular, parameter settings that work well for a particular dataset of instances may work poorly on a different dataset, especially in terms of special problem structures or instance sizes. To ensure good performance of an algorithm, either in terms of runtime or solution quality, it is critical that algorithm parameters be configured or tuned for the types of instances the algorithm is expected to solve in practice. Searching for high-quality parameter settings by hand is a time-consuming endeavor, hence several tools have been developed to automatically determine good parameter settings for a solver or algorithm given a dataset of instances. These tools use a variety of methods ranging from fractional factorial design [2], local search [3, 4], genetic algorithms [5–7], Bayesian optimization [8,9], and racing [10] (see [1]for a full overview). Most algorithm configurators support configuring for one or both of the following settings: (1) minimization of target algorithm runtime or (2) maximization of solution quality. Some target algorithms, such as mixed-integer programming solvers, require a mixture of configuring for runtime and solution quality to find high quality solutions [6] to effectively tune their parameters for a given dataset. Mixed-integer programming (MIP) solvers can tackle a wide range of problem types and thus ought to be configured for the instance set they are meant to solve. Indeed, with this in mind, IBM CPLEX, Gurobi, and FICO Xpress, three of the most well-known general MIP solvers, have built in parameter tuning capabilities [11– 13]. Moreover, MIP solvers have been a focus of the algorithm configuration (AC) community for some time, with early results providing speed-ups of up to 52x on the CPLEX solver [14] and recent results showing there are still performance gains to be had in tuning these approaches [15,16]. Most of the successes of AC solvers on MIP have involved small-scale problems; however, in industry, problems with tens of thousands or even millions of variables must be solved on a regular basis. These extremely large problems post a challenge to configurators. On the one hand, when tuning for runtime, many instances will likely not finish in the given timeout, leading to wasted executions and poor performance of the configurator. On the other hand, when tuning for solution quality, many MIP runs may not find feasible solutions, meaning a mechanism for comparing these failed executions is required to provide the configurator with a search trajectory. This paper introduces the OPTANO Algorithm Tuner (OAT), a general algorithm configurator that has a special focus on addressing large-scale MIP instances. The contributions are as follows: •We describe OAT, an AC tool based on the GGA algorithm. •We investigate a dominance racing mechanism to shorten configuration times on MIP without sacrificing overall performance. •We further show on a real world problem that configuring smaller copies of large instances (i.e., instances of reduced size, but similar structures to large instances) is effective for finding good configurations for the large instances. 123 48 Page 2 of 14 Operations Research Forum (2024) 5: 48 We make OAT freely available under the MIT license at https://github.com/ OPTANO/optano.algorithm.tuner. This paper is organized as follows: We discuss the current state-of-the-art for configuring MIP solvers in Section2. In Section3, we describe OAT, which forms the experimental basis for this work followed by the extensions of OAT specifically for configuring MIP solvers. We evaluate the extensions computationally in Section4and show that OAT can find high-quality configurations for a large-scale, real-world MIP dataset. Finally, we discuss future work and conclude in Section 5. 2 Related Work and Background Information We provide a general overview of AC, including offline and realtime AC, and discuss its application to configure MIP solvers. For further details about AC and related problem settings, we refer interested readers to [1]. 2.1 Offline Automated AC We first formalize the offline AC problem and adopt the notation in [3]. The goal of AC is to optimize the performance of a parameterized algorithm A. To achieve this, the configurator searches for high-quality parameter configurations θin the space of all possible configurations of A. The quality of a configuration is measured by a performance metric mon a set of problem instances ⊆ˆ , where ˆ represents the full distribution of problem instances and the sample the AC approach is provided, such that m:ˆ ×→R. The general process of algorithm configuration is depicted in Fig.1. Offline AC aims at finding a high quality configuration θ∗that performs well over any possible set drawn from ˆ . To this end, a set of problem instances , called the training set, is drawn from ˆ is provided to the AC method that is representative of ˆ . The configuration space is searched for high quality configurations θion the training set, where the aim is to minimize π∈ˆ m(π, θ) in the runtime scenario, whereas in the solution quality scenario, this term is maximized. Fig. 1 The information flow of offline automated AC 123 Page 3 of 14 48Operations Research Forum (2024) 5: 48 Several well-known approaches have been developed for offline AC using both model-based (i.e., machine learned models to predict/evaluate configurations) and non-model-based approaches. ParamILS [3], a non-model-based approach, employs an iterated local search combined with an adaptive capping mechanism to avoid wasting CPU time on poorly performing configurations. The AC method on which our approach in this paper is based, GGA [5,7], uses a genetic algorithm with a tournamentbased racing mechanism, while irace [10] also uses racing, but in a statistical fashion. GPS [4] exploits parameter configuration landscape structures and examine sparameters in a semi-independent way. Model-based configurators include SMAC [8], which is based on a Bayesian optimization paradigm that uses a random forest to predict the performance metric of a given configuration, and GGA++ [6], which uses a random forest with a modified tree building mechanism to predict configuration performance. 2.2 Algorithm Configuration for MIP The AC community has long targeted the MIP setting due to the long runtimes of solving MIP instances and the industrial relevance of MIPs. Several commercial MIP solvers include configuration procedures, such as CPLEX [11], Gurobi [12], and FICO Xpress [13], although we note that these have not been shown to be more effective than any AC method in the literature. ParamILS is used to configure the solvers CPLEX, Gurobi, and LpSolve in [14], resulting in significant speedups on seven different instance sets. Several MIP settings are included in the AClib [17], allowing developers of AC methods to test on standard benchmarks. AC methods have also been used to configure MIPs in instancespecific settings, i.e., a specific configuration θis assigned to each instance in ˆ Pi, e.g., in [18] using the Hydra method [19] and in [20] using the instance-specific algorithm configuration (ISAC) approach. We further note that online/dynamic approaches for configuring MIP parameters exist, e.g., DASH [21] (see also dynamic AC (DAC), [22]). 3 OPTANO Algorithm Tuner OAT is a general algorithm configurator distributed as a.NET nuget package that can be used as a standalone configurator or integrated directly into solvers or algorithms written in.NET. The goal of OAT is to provide a configurator that has state-of-the-art performance combined with the reliability expected of software running in production. While OAT is originally based on GGA [5] and GGA++ [6], it has since been extended to include search strategies based on JADE [23] and active CMA-ES [24]. OAT is inherently distributed and can run its target algorithm in parallel across multiple machines to reduce the overall wall-clock time of the configuration process. In addition, OAT supports configuring in multiple sessions, allowing the configuration process to be restarted should it be interrupted by, e.g., a system failure or reaching a resource limit. Finally, OAT includes numerous ideas from the literature, including parameter tree customization (from GGA), non-numeric evaluation metrics (GGA++), and adaptive capping strategies (ParamILS). We first describe how OAT works and 123 48 Page 4 of 14 Operations Research Forum (2024) 5: 48 describe how it distributes jobs across cores, which differs from previous distributed versions of GGA. Then, we introduce its MIP-specific enhancements, namely the new evaluation metric and short-circuit domination rule. 3.1 OAT’s Configuration Process OAT is based on the genetic algorithm-based GGA and GGA++ configurators from a methodological standpoint, however not an engineering one. The function of OAT consists of three phases: (1) initialization, (2) the main loop, and (3) convergence/termination. The main loop iterates until OAT either reaches the maximum number of generations (as specified by the user), a maximum number of evaluations of the target algorithm, or runs out of time. Figure2provides an overview of the function of OAT, and we refer readers to [5] and [6] for further details. Fig. 2 Overview of the GGA approach [5]usedinOAT 123 Page 5 of 14 48Operations Research Forum (2024) 5: 48 Initialization Considering the previously introduced formalization of algorithm configuration, OAT needs the following four inputs to start its search. First, it needs a list of instances, I, that will be investigated, potentially associated with random seeds. Second, OAT must be told how to invoke the target algorithm, either on the command line or through an interface into other.NET code. Third, the target algorithm parameters to be configured must be specified. OAT takes a structured view of parameters as in GGA, accepting a parameter tree defining relations between parameters (see part 1(c) of Fig.2). For example, Gurobi [12] contains several parameters relating to the presolver that can be adjusted to change its behavior. Another parameter turns the presolver on and off, meaning that the parameters relating to the presolver depend on the parameter to turn it on and off. This information is used during search to generate new configurations. Thus, the dependent parameters are placed lower below the presolver on/off parameter, and the recombination procedure takes this into account when creating new individuals. Finally, OAT’s own internal parameters can be changed from their default values, relating to how its search strategy functions.1 Given the inputs outlined above, OAT initializes a population consisting of the default configuration(s) and randomly generated configurations, partitioned into two groups, representing the competitive (C) configurations that will be run on the target algorithm, and non-competitive (N) configurations, which act as a diversity store. Main Loop This phase consists of up to n generations, in which configurations from the C population are assessed in races and the winners are recombined with noncompetitive configurations. At the beginning of each generation, a subset of instances are sampled from the instance pool. This subset linearly increases with each generation until either all instances are used or a user-specified maximum value is reached. All configurations of the competitive population must be evaluated on the currently active subset of instances. We note that some configurations may have already been evaluated on some of the instances in previous generations; these configurations need not be evaluated on the same instances again. If the size of the competitive population is larger than the number of available CPUs,2the configurations are split into minitournaments equal to the number of available CPUs. In the pure runtime setting, mini-tournaments are executed until a fixed percentage of the configurations have solved all instances; in the case of Fig.2, only one configuration can win the race. The rest of the configurations are subsequently terminated when they have used the same amount of CPU time as the winning configuration(s). The mechanism by which OAT distributes mini-tournaments is described in more detail below. In the case of MIP, we slightly modify this procedure and describe this in Sections3.2 and 3.3. After all planned evaluations for the current generation are completed, the population is updated based on the performance of the configurations. Several options are available to do this, such as the GGA crossover mechanism in GGA, the genetic 1We note that “tuning the tuner” poses a significant challenge; thus, these parameters are set to values that have worked well for GGA and GGA++ in the past. 2We assume the target algorithm is single threaded in our descriptions; however, OAT also supports configuring multithreaded target algorithms. 123 48 Page 6 of 14 Operations Research Forum (2024) 5: 48 engineering algorithm of GGA++, as well as approaches based on JADE and active CMA-ES. Figure2shows the GGA crossover mechanism in which the winners of the mini-tournaments are recombined with randomly chosen members of the noncompetitive population. The crossover procedure constructs a new configuration by randomly choosing components from the two parents. We refer to [5] for the full details of this algorithm and of the subsequent mutation operator. A specified percentage of the population is replaced every generation (usually one third) through the recombination procedure in the hope of generating high-quality configurations. Model-based recombination is also possible in OAT using the GGA++ recombination strategy, see [6] for details. Termination The main loop of OAT runs until one of three conditions is reached. The first condition is whether the maximum number of generations is achieved (usually 75 or 100). The second condition is whether a maximum number of evaluations of the target algorithm is exceeded. Finally, the third condition is whether the maximum wall-clock time of the configurator is exceeded. Note that GGA supports a convergence criterion that checks whether the population is improving or not, but this is not implemented yet in OAT. Increasing Mini-Tournament CPU Utilization The mini-tournaments as described above must be efficiently distributed across the available CPU resources. A key engineering advancement of OAT over previous GGA configurators is that it attempts to maximally utilize available CPU resources. While OAT runs mini-tournaments to race competitive configurations, it distributes mini-tournaments across multiple nodes according to a priority queue of configuration-instance-seed tuples that must still be run, leading to less wasted CPU capacity than, e.g., GGA and GGA++. OAT prioritizes configurations that it believes are likely to finish first so that the finishing time can be used in the short-circuit evaluation of other configurations according to the formula priority(c)=100 timeouts(c) |Ig|+10 running(c) |Ig|+runtime(c) κ|Ig|, where cis a configuration being evaluated in the current generation, g,timeouts(c) provides the number of timeouts the configuration chas had in the current generation so far, Igis the instance subset being considered in the current generation, running(c) describes the number of instance-seed pairs cis currently running on, runtime(c) gives the total runtime of cso far in the current generation, and κis the timeout as previously defined. The proposed mechanism runs configuration-instance-seed tuples with a low value. The intuition is that a low priority score corresponds first to configurations with a low number of timeouts, following that configurations that have not yet seen much CPU time are favored, and finally, the total runtime expended should be a low percentage of the total CPU time allotment for the configuration. In this way, configurations are preferred that are likely to finish the mini-tournaments first, allowing us to dominate poor-performers before they waste CPU resources (see Section 3.3). 123 Page 7 of 14 48Operations Research Forum (2024) 5: 48 3.2 MIP Evaluation Metric The evaluation metric tells OAT how to interpret and aggregate the performance of the target algorithm on a subset of the training instances. One of the main considerations when developing a runtime evaluation metric is how to deal with timeouts. While many configurators simply use the average performance of a configuration over a set of instances, this does not significantly discourage timeouts from occurring. Hence, many configurators also support the so-called PAR10 score, which extends the average by multiplying timeouts by a factor of 10. While PAR10 effectively penalizes timeouts, when an instance set contains many difficult instances, it often does not offer effective search guidance. To improve on this, in the gray-box configuration schemes [25] and [16], we analyze intermediate output of the target algorithm to assist in ranking or otherwise scoring timeouts. In the case of CPPL, ties between configurations that do not finish are broken using the quality of the feasible solution found (if one was found). In contrast to realtime configuration, where only a single instance is solved per iteration, in offline configuration, breaking times is somewhat more complicated. Especially in the first few iterations of configuration, timeouts are very likely as the search process has not yet identified good configurations. Hence, it is critical to have an effective mechanism for comparing configurations even if none find optimal solutions to the instances being solved. Thus, to minimize the runtime of solving MIPs, we propose the following simple ranking scheme. Assume we are given two configurations Aand Bthat are run on ninstances and the following rules are applied in order: 1. If Afinds more feasible solutions than B,Ais better. 2. Otherwise, if Ahas less timeouts than B,Ais better. 3. Otherwise, if Ahas a lower average MIP gap over the timeout runs than B,A is better. 4. Otherwise, if Ahas a lower average runtime than B,Ais better. Since the runtime is a floating point value, and there is generally some noise in its measurement, this ranking is all but guaranteed to return a total order over the available configurations. Note that the focus of the ranking is on feasibility and not optimality. The reason for this is that companies solving MIPs in practice would much rather have feasible solutions for all of the instances they are investigating than optimal solutions on a few and no solution at all on the rest. However, while our motivation for these rule set is a practical one, we show later that there is also a computational benefit to the rules, as these rules help guide the configurator’s search towards areas of the search space with configurations effective at finding optimal solutions. 3.3 Dominance Racing Running MIPs is computationally expensive; thus, if we detect that a particular configuration is dominated, we can stop running it and use the available resources to run something else. GGA and GGA++ accomplish this in the average or PAR10 runtime setting through their racing mechanism, which ensures that configurations that are dominated are stopped before wasting CPU resources. However, when using a rank123 48 Page 8 of 14 Operations Research Forum (2024) 5: 48