Search

With the rapid development of new energy and smart technology, the demand for inter-device communication in medium–low-voltage smart distribution grids has sharply increased, leading to a surge in the variety and quantity of communication services. To meet the needs of diverse and massive communication services, deploying service function chains to flexibly combine virtual resources has become crucial. This paper proposes an optimization method based on fit entropy and network utility to address the limited communication network resources in medium–low-voltage smart distribution grids. This was conducted by modeling the distribution grid as a three-domain model consisting of a service domain, a logical domain, and a physical domain and transforming it into a hierarchical bipartite hypergraph-matching problem, which is a complex combinatorial optimization problem. This paper introduces two matching optimization algorithms: "business domain–logic domain–physical domain integration" and "service domain–logic domain, logic domain–physical domain two-stage", which effectively address this problem based on fit entropy and utility. The simulation results demonstrate that these algorithms significantly improve service success rates and resource utilization, enhancing overall network utility. [ABSTRACT FROM AUTHOR]

Aiming at the floorplanning problem with only hard modules, it is usually constructed as a combinatorial optimization model, but the time cost of solving process is high. In order to improve the solving efficiency, this paper proposed a floorplanning algorithm based on non-smooth analytic mathematical programming. Based on the coordinate representation of modules, this paper established a non-smooth mathematical programming model, which was a generalization of the optimization models corresponding to various optimization stages of different cases that were solved by the conjugate sub-gradient algorithm (CSA). Aiming at the fixed-outline floorplanning problem, this paper achieved wirelength optimization under fixed-outline constraint through the general framework consisted of three stages: global floorplanning, legalization and local optimization. To address the case without fixed-outline constraint, this paper proposed a conjugate sub-gradient algorithm with golden section strategy (CSA_GSS). The algorithm adopted golden section strategy to reduce the area of the fixed-outline and to achieve the dual effect of both area and wirelength optimization. Compared with floorplanning algorithm based on B-tree on GSRC test circuit, the proposed algorithm had advantages in terms of wirelength and time for large-scale circuits. Experimental results show that the algorithm can obtain better wirelength with lower time complexity. [ABSTRACT FROM AUTHOR]

In this paper, we study the minimum k-partition problem of submodular functions, i.e., given a finite set V and a submodular function f : 2 V → R , computing a k-partition { V 1 , ... , V k } of V with minimum ∑ i = 1 k f (V i) . The problem is a natural generalization of the minimum k-cut problem in graphs and hypergraphs. It is known that the problem is NP-hard for general k, and solvable in polynomial time for fixed k ≤ 3 . In this paper, we construct the first polynomial-time algorithm for the minimum 4-partition problem. [ABSTRACT FROM AUTHOR]

The durability is a key factor of fuel cell in large-scale application of automobiles. It is great important to real the lifetime and health status of fuel cells, especially in vehicle driving conditions. Based on the experimental data, this paper used the model-based method and data-driven method to predict the life of fuel cells, respectively. The model-based method established the equivalent circuit model according to the mapping law of electrochemical impedance spectroscopy (EIS) and the parameters of the equivalent circuit model were identified by newly considering the phenomenon of voltage recovery, revealing the strong linear correlation between impedance and voltage. The data-driven method selected a combinatorial optimization PSO-LSSVM algorithm and compared it with the prediction results of MATLAB's time series toolbox. The results show the mean square error (MSE), End of Life (EOL) of the model-based method, the time series toolbox and PSO-LSSVM algorithm are 0.019, 8.2 × 10−3 and 4.42 × 10−5, the 260h, 438h and 427h, respectively. Comparing with the real EOL of 421h, the error of PSO-LSSVM algorithm is only 6 h, which means the remaining useful life can be predicted with high accurately. Thus this study provides a reference for fault identification and life prediction of fuel cell health management. • The equivalent circuit model is established to realize the segmented voltage prediction and analysis of fuel cells. • The MSE of combinatorial optimized algorithms PSO-LSSVM to predict voltage is only 4.42 × 10−5. • The method in paper provides a reference for fault identification and life prediction of PEMFC's health management. [ABSTRACT FROM AUTHOR]

A recent study on the classical capacitated vehicle routing problem (CVRP) introduced an adaptive version of the widely used iterated local search paradigm, hybridized with a path-relinking (PR) strategy. The solution method, called adaptive iterated local search (AILS)-PR, outperformed existing meta-heuristics for the CVRP on benchmark instances. However, tests on large-scale instances suggest that PR is too slow, making AILS-PR less advantageous in this case. To overcome this challenge, this paper presents an AILS combined with mechanisms to handle large CVRP instances, called AILS-II. The computational cost of this implementation is reduced, whereas the algorithm also searches the solution space more efficiently. AILS-II is very competitive on smaller instances, outperforming the other methods from the literature with respect to the average gap to the best-known solutions. Moreover, AILS-II consistently outperforms the state of the art on larger instances with up to 30,000 vertices. History: Accepted by Ted Ralphs, Area Editor for Software Tools. This paper has been accepted for the INFORMS Journal on Computing Special Issue on Software Tools for Vehicle Routing. Funding: This work was supported by the Fundação de Amparo à Pesquisa do Estado de São Paulo [Grants 2013/07375-0, 2019/22067-6, and 2022/05803-3] and the Conselho Nacional de Desenvolvimento Científico e Tecnológico [Grants 309385/2021-0 and 403735/2021-1]. 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.2023.0106) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2023.0106). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

Civil aircraft represent intricate technical systems, and their flight test is a system engineering process. This process is essential for verifying their compliance with airworthiness regulations and operational requirements. In this process, planning flight test missions is a type of combinatorial optimization problem. The solution gives an optimal allocation plan adhering to operational constraints. Assigning flight test missions for civil aircraft involves numerous uncertainties and very often, requires unforeseen adjustments. The original missions need to be reassigned due to these adjustments in a scientific way. In this paper, considering the scenarios that emerged during real civil aircraft flight tests, a multi-objective flight test mission planning model is established based on the Flexible Job Shop Problem (FJSP) model. The model is specifically tailored to the flight text mission reassignment. Examples of flight test scenarios that require mission reassignments are addressed using the FJSP model proposed in this paper and optimized using the Particle Swarm Optimization algorithm. Two rounds of initial population updates were conducted to obtain overall extreme values. The results verify the feasibility of obtaining a viable solution for the flight test mission assignment problem under complex constraints derived from real engineering requirements. These solutions can be used to address similar types of engineering problems. [ABSTRACT FROM AUTHOR]

The problem of finding optimal block designs can be formulated as a combinatorial optimization, but its resolution is still a formidable challenge. This paper presents a general and user-friendly algorithm, namely Modified Particle Swarm Optimization (MPSO), to construct optimal or near-optimal block designs. It can be used for several classes of block designs such as binary, non-binary and test-control block designs with correlated or uncorrelated observations. In order to evaluate the algorithm, we compare our results with the optimal designs presented in some published papers. An advantage of our algorithm is its independency to the sizes of blocks and the structure of correlations. [ABSTRACT FROM AUTHOR]

Purpose: A fleet of mobile robots has been effectively used in various application domains such as industrial plant inspection. This paper proposes a solution to the combined problem of task allocation and motion planning problem for a fleet of mobile robots which are requested to operate in an intelligent industry. More specifically, the robots are requested to serve a set of inspection points within given service time windows. In comparison with the conventional time windows, our problem considers fuzzy time windows to express the decision maker's satisfaction for visiting an inspection point. Design/methodology/approach: The paper develops a unified approach to the combined problem of task allocation and motion planning for a fleet of mobile robots with three objectives: (a) minimizing the total travel cost considering all robots and tasks, (b) balancing fairly the workloads among robots and (c) maximizing the satisfaction grade of the decision maker for receiving the services. The optimization problem is solved by using a novel combination of a Genetic Algorithm with pareto solutions and fuzzy set theory. Findings: The computational results illustrate the efficiency and effectiveness of the proposed approach. The experimental analysis leverages the potential for using fuzzy time windows to reflect real situations and respond to demanding situations. Originality/value: This paper provides trade-off solutions to a realistic combinatorial multi-objective optimization problem considering concurrently the motion and path planning problem for a fleet of mobile robots with fuzzy time windows. [ABSTRACT FROM AUTHOR]

The problem of finding a maximum size matching in a graph (known as the maximum matching problem) is one of the most classical problems in computer science. Despite a significant body of work dedicated to the study of this problem in the data stream model, the state-of-the-art single-pass semi-streaming algorithm for it is still a simple greedy algorithm that computes a maximal matching, and this way obtains 1 / 2 -approximation. Some previous works described two/three-pass algorithms that improve over this approximation ratio by using their second and third passes to improve the above mentioned maximal matching. One contribution of this paper continues this line of work by presenting new three-pass semi-streaming algorithms that work along these lines and obtain improved approximation ratios of 0.6111 and 0.5694 for triangle-free and general graphs, respectively. Unfortunately, a recent work Konrad and Naidu (Approximation, randomization, and combinatorial optimization. Algorithms and techniques, APPROX/RANDOM 2021, August 16–18, 2021. LIPIcs, vol 207, pp 19:1–19:18, 2021. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.19) shows that the strategy of constructing a maximal matching in the first pass and then improving it in further passes has limitations. Additionally, this technique is unlikely to get us closer to single-pass semi-streaming algorithms obtaining a better than 1 / 2 -approximation. Therefore, it is interesting to come up with algorithms that do something else with their first pass (we term such algorithms non-maximal-matching-first algorithms). No such algorithms were previously known, and the main contribution of this paper is describing such algorithms that obtain approximation ratios of 0.5384 and 0.5555 in two and three passes, respectively, for general graphs. The main significance of our results is not in the numerical improvements, but in demonstrating the potential of non-maximal-matching-first algorithms. [ABSTRACT FROM AUTHOR]

This paper considers optimal pricing in a system with limited substitutable resources, such as certain goods or services. Prices for the different resources have to be set and then customers with heterogeneous preferences show up sequentially. Customers, of n types, select an item from the m available resources, depending on their valuations of the resources and the prices. The goal is to analyze this optimization problem, characterize a set of candidates to optimal solutions and provide methods for solving it. We prove that this problem is NP-hard to approximate within a factor O (n 1 - ε) for any fixed ε > 0 . Another important contribution is to prove that, the space of prices (which in principle is a continuous domain in R m ), can be reduced to a finite set of vectors of cardinality m m - 2 n m 2 m . For a deterministic version of the problem, where the customer types are known to the firm, we provide a mathematical program that chooses the best set of prices. We report extensive computational results showing the usefulness of our exact approach to solve medium size problems with up to 200 customers and different assortments of products and customer types. We then show how to approximate the stochastic model by a small number of solutions of deterministic scenarios solved using a mixed-integer linear program. [ABSTRACT FROM AUTHOR]

We determine the sensitivity of a current optimal solution to a combinatorial optimization problem to cost changes in a set of elements. In a recent study, the concept of regular set tolerances has been introduced for a combinatorial optimization problem and for three types of cost functions, namely sum, product, and bottleneck. A regular set tolerance is the supremum amount of cost changes that can be distributed in the most favorable way to multiple elements such as not to change the current optimal solution. In this paper, we introduce an alternative concept, namely the reverse set tolerance , which is a measure of the infimum amount of cost changes to multiple elements such that the current optimal solution becomes non-optimal. We characterize the specific cases in which reverse set upper and lower tolerances have positive values and in which they are infinite. We also show a criterion for the uniqueness of an optimal solution. Furthermore, we present bounds and exact formulas for reverse set upper and lower tolerances using the relation to their corresponding single tolerance counterparts. We discuss the similarities and differences in the results between regular and reverse set tolerances. Finally, we motivate this new concept by analyzing them for special combinatorial optimization problems with important practical applications. [ABSTRACT FROM AUTHOR]

In the path version of the Travelling Salesman Problem (Path-TSP), a salesman is looking for the shortest Hamiltonian path through a set of n cities. The salesman has to start his journey at a given city s , visit every city exactly once, and finally end his trip at another given city t. In this paper we show that a special case of the Path-TSP with a Demidenko distance matrix is solvable in polynomial time. Demidenko distance matrices fulfill a particular condition abstracted from the convex Euclidian special case by Demidenko (1979) as an extension of an earlier work of Kalmanson (1975). We identify a number of crucial combinatorial properties of the optimal solution and design a dynamic programming approach with time complexity O (n 6). [ABSTRACT FROM AUTHOR]

Terrain visibility analysis is vital in geospatial research, employing computer geometry and graphics principles for computing and visualizing visibility between observation and target points. The observation point setup problem is crucial for tasks like sentry point selection and signal base station placement. This problem involves choosing the minimum viewpoints on terrain for optimal joint view coverage, presenting a combinatorial optimization challenge. As technology advances, data can be acquired with increasing precision, the number of viewpoints that can be extracted from the same area is gradually increasing as well, obtaining candidate viewpoints and determining optimal combinations become challenging. This paper proposes a novel method, Stepwise Maximum Viewshed (SMV), addressing observation point setup by stepwise filtering the maximum viewshed and can customize the size of the observation point combination. In complex mountainous terrain, the SMV algorithm demonstrates superior joint view coverage compared to Candidate Viewpoints Filtering (CVF) and Simulated Annealing (SA) algorithms. Experimental results reveal up to 5.59% improvement over CVF and a maximum of 12.52% over SA in joint viewshed coverage. [ABSTRACT FROM AUTHOR]

Graph matching is a commonly used technique in computer vision and pattern recognition. Recent data-driven approaches have improved the graph matching accuracy remarkably, whereas some traditional algorithm-based methods are more robust to feature noises, outlier nodes, and global transformation (e.g. rotation). In this paper, we propose a graph neural network (GNN) based approach to combine the advantage of data-driven and traditional methods. In the GNN framework, we transform traditional graph matching solvers as single-channel GNNs on the association graph and extend the single-channel architecture to the multi-channel network. The proposed model can be seen as an ensemble method that fuses multiple algorithms at every iteration. Instead of averaging the estimates at the end of the ensemble, in our approach, the independent iterations of the ensembled algorithms exchange their information after each iteration via a 1 × 1 channel-wise convolution layer. Experiments show that our model improves the performance of traditional algorithms significantly. In addition, we propose a random sampling strategy to reduce the computational complexity and GPU memory usage, so that the model is applicable to matching graphs with thousands of nodes. We evaluate the performance of our method on three tasks: geometric graph matching, semantic feature matching, and few-shot 3D shape classification. The proposed model performs comparably or outperforms the best existing GNN-based methods. [ABSTRACT FROM AUTHOR]

Summary Oscillator‐based Ising machines (OIMs) particularly those realized in complementary metal oxide semiconductor (CMOS) have gained popularity for solving combinatorial optimization problems (COPs) in recent years due to its scalability, low‐power consumption, and room temperature operation. The implemented OIMs have thus far focused on solving optimization problems with a single global minima. However, real‐life optimization problems often have multiple solutions. In this paper, we propose a generalized approach to solve COPs with single (without contention), as well as multiple (with contention) solutions using frequency tunable CMOS ring oscillator (ROSC)‐based Ising machine. A capacitive frequency tunable CMOS ring‐oscillator coupled with an internal subharmonic injection locking (SHIL) generator realized using 14‐nm FinFET models works as Ising spin in the proposed approach. We demonstrate how frequency tuning can help in attaining good quality results and also determine all possible solutions of COP with contention. We also propose a generalized algorithm for monitoring the states of the oscillator network to indicate tuning necessity and extract solutions from the oscillator's output irrespective of the type of COP. [ABSTRACT FROM AUTHOR]

Unmanned aerial vehicles (UAVs) have been extensively researched and deployed in both military and civilian applications due to their tiny size, low cost, and great ease. Although UAVs working together on complicated jobs can significantly increase productivity and reduce costs, they can cause major issues with path planning. In complex environments, the path planning problem, which is a multiconstraint combinatorial optimization problem and hard to settle, requires considering numerous constraints and limitations and generates the best paths for each UAV to accomplish group tasks. In this paper, we study the path planning problem for multiple UAVs and propose a reinforcement learning algorithm: PERDE‐MADDPG based on prioritized experience replay (PER) and delayed update skills. First, we adopt a PER mechanism based on temporal difference (TD) error to enhance the efficiency of experience utilization and accelerate the convergence speed of the algorithm. Second, we use delayed updates in the process of updating network parameters to ensure stability in training multiple agents. Finally, we propose the PERDE‐MADDPG algorithm based on PER and delayed update skills, which is evaluated against the MATD3, MADDPG, and SAC methods in simulation scenarios to confirm its efficacy. [ABSTRACT FROM AUTHOR]

The bipartite polarization problem is an optimization problem where the goal is to find the highest polarized bipartition on a weighted and labeled graph that represents a debate developed through some social network, where nodes represent user's opinions and edges agreement or disagreement between users. This problem can be seen as a generalization of the maxcut problem, and in previous work, approximate solutions and exact solutions have been obtained for real instances obtained from Reddit discussions, showing that such real instances seem to be very easy to solve. In this paper, we further investigate the complexity of this problem by introducing an instance generation model where a single parameter controls the polarization of the instances in such a way that this correlates with the average complexity to solve those instances. The average complexity results we obtain are consistent with our hypothesis: the higher the polarization of the instance, the easier is to find the corresponding polarized bipartition. In view of the experimental results, it is computationally feasible to implement transparent mechanisms to monitor polarization on online discussions and to inform about solutions for creating healthier social media environments. [ABSTRACT FROM AUTHOR]

The gas-gathering pipeline network is a critical infrastructure for collecting and conveying natural gas from the extraction site to the processing facility. This paper introduces a design optimization model for a star–tree gas-gathering pipeline network within a discrete space, aimed at determining the optimal configuration of this infrastructure. The objective is to reduce the investment required to build the network. Key decision variables include the locations of stations, the plant location, the connections between wells and stations, and the interconnections between stations. Several equality and inequality constraints are formulated, primarily addressing the affiliation between wells and stations, the transmission radius, and the capacity of the stations. The design of a star–tree pipeline network represents a complex, non-deterministic polynomial (NP) hard combinatorial optimization problem. To tackle this challenge, a hierarchical optimization framework coupled with an improved genetic algorithm (IGA) is proposed. The efficacy of the genetic algorithm is validated through testing and comparison with other traditional algorithms. Subsequently, the optimization model and solution methodology are applied to the layout design of a pipeline network. The findings reveal that the optimized network configuration reduces investment costs by 16% compared to the original design. Furthermore, when comparing the optimal layout under a star–star topology, it is observed that the investment needed for the star–star topology is 4% higher than that needed for the star–tree topology. [ABSTRACT FROM AUTHOR]

The traveling salesman problem (TSP) is a well‐known NP‐hard combinatorial optimization problem. In TSP, the objective is to find the shortest distance to the most appropriate route to the starting city. Finding an optimal solution in a reasonable time becomes difficult as the number of cities increases. In recent years, metaheuristic methods obtained optimal or near‐optimal solutions in TSP in an acceptable time. This paper proposes a new hybrid metaheuristic method for solving the TSP. The proposed method is developed by combining the 3‐Opt method and the improved discrete cuckoo search algorithm. The performance of the proposed method is tested on 39 different benchmark problems in the TSPLIB library. For the 39 different benchmark problems with a size of less than 150 cities, the proposed hybrid method found optimal solutions. In addition, it was observed that as the problem size increases, the results obtained are closer to the optimum compared to other methods. When compared to studies in the literature using the same problem, similar or better results were obtained. For 500 iterations, the average best solution of the proposed method differed from the average optimal solution by 0.07%. In the results of the improved discrete cuckoo search algorithm (CSA), this rate was calculated to be 0.08%. In terms of processing time, the average time of the proposed algorithm was 11.46 seconds, while the average time of the improved discrete CSA was 92.86 seconds. For 1000 iterations, the deviation of the proposed method from the average optimal solution is 0.05%, and the average processing time is 23.72 seconds. The experimental results showed that the proposed new hybrid‐improved discrete CSA is effective for solving TSP. [ABSTRACT FROM AUTHOR]

Motivated by the strengths of unmanned aerial vehicle (UAV), the UAV–human collaboration route planning (UHCRP) for intelligent infrastructure inspection is a problem worthy of discussion to help reduce human costs and minimize the risk of noninspected infrastructures under limited resources. To facilitate UHCRP, this paper proposes a novel deep reinforcement learning (DRL)‐based approach to well handle multi‐source uncertain features and constraints at a fast speed. To begin with, UHCRP is mathematically described and reformulated as a dual interdependent deep reinforcement learning (diDRL) framework to reflect real‐world scenarios. Afterward, a novel policy network named the attention‐based deep neural network (A‐DNN) is introduced to learn the route planning decisions for the combinatorial optimization problem. In particular, A‐DNN is made up of an encoder and a dual decoder for UAV and human inspection, where the multi‐head attention mechanism is incorporated to generate richer representations for model performance improvement. Performance of the proposed dual multi‐head attention model (DAM) has been tested in simulations and a real‐world case study regarding wind farm inspection. Results indicate that DAM under the sampling decoding strategy can deliver a high‐quality path plan and show better generalizability for larger scale problem sizes compared to single‐head attention model (SAM), multi‐head attention model (AM), and two baseline models, namely OR‐Tools and genetic algorithm. Moreover, DAM trained by randomly generated data can be directly employed to solve the practical problem with standardization of inputs. Overall, DRL integrates decision‐making for inspection method selection and inspected infrastructure selection, providing adaptive and intelligent inspection path planning for UAV and human in complex and dynamic engineering environments. [ABSTRACT FROM AUTHOR]

As a leading economic center in China and an international metropolis, Shenzhen has great significance in promoting sustainable urban development. To predict its amount of domestic waste clearance, a new multivariable grey prediction model with combinatorial optimization of parameters is established in this paper. Firstly, the new model expands the value range of the order r of a grey accumulation generation operator from positive real numbers (R +) to all real numbers (R), which enlarges the optimization space of parameter and has positive significance for improving model performance. Secondly, the dynamic background-value coefficient λ is introduced into the new model to improve the smoothing effect of the nearest neighbor generated sequences. Thirdly, with the objective function of minimizing the mean absolute percentage error (MAPE), the particle swarm optimization (PSO) is employed to optimize parameters r and λ to improve the overall performance of the new model. The new model is used to simulate and predict the amount of domestic waste clearance in Shenzhen, and the MAPE of the new model is only 0.27%, which is far superior to several other similar models. Lastly, the new model is applied to predict the amount of domestic waste clearance in Shenzhen. The results indicate the amount of domestic waste clearance in 2028 could be 9.96 million tons, an increase of 20.58% compared to 2021.This highlights the significant challenge that Shenzhen faces in terms of urban domestic waste treatment. Therefore, some targeted countermeasures and suggestions have been proposed to ensure the sustainable development of Shenzhen's economy and society. [ABSTRACT FROM AUTHOR]

This paper aims to solve the multi-objective operating planning problem in the radioactive environment. First, a more complicated radiation dose model is constructed, considering difficulty levels at each operating point. Based on this model, the multi-objective operating planning problem is converted to a variant traveling salesman problem (VTSP). Second, with respect to this issue, a novel combinatorial algorithm framework, namely hyper-parameter adaptive genetic algorithm (HPAGA), integrating bio-inspired optimization with reinforcement learning, is proposed, which allows for adaptive adjustment of the hyperparameters of GA so as to obtain optimal solutions efficiently. Third, comparative studies demonstrate the superior performance of the proposed HPAGA against classical evolutionary algorithms for various TSP instances. Additionally, a case study in the simulated radioactive environment implies the potential application of HPAGA in the future. [ABSTRACT FROM AUTHOR]

We consider the weighted k-set packing problem, where, given a collection S of sets, each of cardinality at most k, and a positive weight function w : S → Q > 0 , the task is to find a sub-collection of S consisting of pairwise disjoint sets of maximum total weight. As this problem does not permit a polynomial-time o (k log k) -approximation unless P = N P (Hazan et al. in Comput Complex 15:20–39, 2006. https://doi.org/10.1007/s00037-006-0205-6), most previous approaches rely on local search. For twenty years, Berman's algorithm SquareImp (Berman, in: Scandinavian workshop on algorithm theory, Springer, 2000. https://doi.org/10.1007/3-540-44985-X%5f19), which yields a polynomial-time k + 1 2 + ϵ -approximation for any fixed ϵ > 0 , has remained unchallenged. Only recently, it could be improved to k + 1 2 - 1 63 , 700 , 993 by Neuwohner (38th International symposium on theoretical aspects of computer science (STACS 2021), Leibniz international proceedings in informatics (LIPIcs), 2021. https://doi.org/10.4230/LIPIcs.STACS.2021.53). In her paper, she showed that instances for which the analysis of SquareImp is almost tight are "close to unweighted" in a certain sense. But for the unit weight variant, the best known approximation guarantee is k + 1 3 + ϵ (Fürer and Yu in International symposium on combinatorial optimization, Springer, 2014. https://doi.org/10.1007/978-3-319-09174-7%5f35). Using this observation as a starting point, we conduct a more in-depth analysis of close-to-tight instances of SquareImp. This finally allows us to generalize techniques used in the unweighted case to the weighted setting. In doing so, we obtain approximation guarantees of k + ϵ k 2 , where lim k → ∞ ϵ k = 0 . On the other hand, we prove that this is asymptotically best possible in that local improvements of logarithmically bounded size cannot produce an approximation ratio below k 2 . [ABSTRACT FROM AUTHOR]

With the rise of e-commerce and increasing customer requirements, logistics service providers face a new complexity in their daily planning, mainly due to efficiently handling same-day deliveries. Existing multistage stochastic optimization approaches that allow solving the underlying dynamic vehicle routing problem either are computationally too expensive for an application in online settings or—in the case of reinforcement learning—struggle to perform well on high-dimensional combinatorial problems. To mitigate these drawbacks, we propose a novel machine learning pipeline that incorporates a combinatorial optimization layer. We apply this general pipeline to a dynamic vehicle routing problem with dispatching waves, which was recently promoted in the EURO Meets NeurIPS Vehicle Routing Competition at NeurIPS 2022. Our methodology ranked first in this competition, outperforming all other approaches in solving the proposed dynamic vehicle routing problem. With this work, we provide a comprehensive numerical study that further highlights the efficacy and benefits of the proposed pipeline beyond the results achieved in the competition, for example, by showcasing the robustness of the encoded policy against unseen instances and scenarios. History: This paper has been accepted for the Transportation Science special issue on DIMACS Implementation Challenge: Vehicle Routing Problems. Funding: This work was supported by Deutsche Forschungsgemeinschaft [Grant 449261765]. [ABSTRACT FROM AUTHOR]

A 2‐factor in a graph G $G$ is a subset of edges M $M$ such that every node of G $G$ is incident with exactly two edges of M $M$. Many results are known concerning 2‐factors including a polynomial‐time algorithm for finding 2‐factors and a characterization of those graphs that have a 2‐factor. The problem of finding a 2‐factor in a graph is a relaxation of the NP‐hard problem of finding a Hamilton cycle. A stronger relaxation is the problem of finding a triangle‐free 2‐factor, that is, a 2‐factor whose edges induce no cycle of length 3. In this paper, we present a polynomial‐time algorithm for the problem of finding a triangle‐free 2‐factor as well as a characterization of the graphs that have such a 2‐factor and related min–max and augmenting path theorems. [ABSTRACT FROM AUTHOR]

The quantum alternating operator ansatz (QAOA) and its predecessor, the quantum approximate optimization algorithm, are one of the most widely used quantum algorithms for solving combinatorial optimization problems. However, as there is yet no rigorous proof of convergence for the QAOA, we provide one in this paper. The proof involves retracing the connection between the quantum adiabatic algorithm and the QAOA, and naturally suggests a refined definition of the 'phase separator' and 'mixer' keywords. [ABSTRACT FROM AUTHOR]

An extension of the p-center problem, called the p-next center problem, is considered in this paper. In practice, it has been shown that centers can close suddenly due to a problem (accident, staff shortage, technical problem, etc.). In this case, customers should proceed to the backup center - the one closest to the closed center. Both the p-center problem and the p-next center problem are NP-hard, so approximation methods are suitable for solving them. In this paper, an efficient solution approach based on Skewed Variable Neighborhood Search (SVNS) is proposed for the p-next center problem. The performance of the proposed SVNS method is evaluated on a set of pmed instances with up to 900 nodes. The obtained computational results are presented and compared with the best results from the literature, confirming the efficiency and stability of the proposed method in solving the p-next center problem. [ABSTRACT FROM AUTHOR]

Operations in areas of importance to society are frequently modeled as mixed-integer linear programming (MILP) problems. While MILP problems suffer from combinatorial complexity, Lagrangian Relaxation has been a beacon of hope to resolve the associated difficulties through decomposition. Due to the non-smooth nature of Lagrangian dual functions, the coordination aspect of the method has posed serious challenges. This paper presents several significant historical milestones (beginning with Polyak's pioneering work in 1967) toward improving Lagrangian Relaxation coordination through improved optimization of non-smooth functionals. Finally, this paper presents the most recent developments in Lagrangian Relaxation for fast resolution of MILP problems. The paper also briefly discusses the opportunities that Lagrangian Relaxation can provide at this point in time. [ABSTRACT FROM AUTHOR]

The fixed fleet heterogeneous open vehicle routing problem (HFFOVRP) is one of the most practical versions of the vehicle routing problem (VRP) defined because the use of rental vehicles reduces the cost of purchasing and routing for shipping companies nowadays. Also, applying a heterogeneous fleet is recommended due to the physical limitations of the streets and efforts to reduce the running costs of these companies. In this paper, a mixed-integer linear programming is proposed for HFFOVRP. Because this problem, like VRP, is related to NP-hard issues, it is not possible to use exact methods to solve real-world problems. Therefore, in this paper, a hybrid algorithm based on the ant colony algorithm called MACO is presented. This algorithm uses only global updating pheromones for a more efficient search of feasible space and considers a minimum value for pheromones on the edges. Also, pheromones of some best solutions obtained so far are updated, based on the quality of the solutions at each iteration, and three local search algorithms are used for the intensification mechanism. This method was tested on several standard instances, and the results were compared with other algorithms. The computational results show that the proposed algorithm performs better than these methods in cost and CPU time. Besides, not only has the algorithm been able to improve the quality of the best-known solutions in nine cases but also the high-quality solutions are obtained for other instances. [ABSTRACT FROM AUTHOR]

This paper addresses the triangle width problem, which generalizes the classic two-machine flexible job-shop problem (FJSP) with tooling constraints. This new problem can be studied from three different angles: scheduling, matrix visualization, and vertex ordering in hypergraphs. We prove the equivalence of the different formulations of the problem and use them to establish the N P -Hardness and polynomiality of several of its subcases. This problem allows us to find more elegant (and probably shorter) proofs for several combinatorial problems in our analysis setting. Our study provides an elegant generalization of Johnson's argument for the two-machine flow shop. It also shows the relation between the question: "Is a matrix triangular?" and the "k-visit of a graph". [ABSTRACT FROM AUTHOR]

The traveling salesman problem (TSP) involves determining the shortest length (optimal tour) for a complete circuit through an arbitrary number of points. In the special case that the points to be visited are randomly distributed in the plane within a unit square, and travel costs correspond to the Euclidean distance between points, it is known that the length of the optimal tour divided by the square root of the number of points (n) asymptotically approaches a constant (βTSP) as n becomes large. If individual points are randomly drawn from a uniform distribution, the optimal lengths for a sufficiently large number of TSP instances of the same size (n) comprise a normal distribution whose mean approaches βTSP as n increases. Moreover, as n approaches infinity, this distribution gradually narrows such that its standard deviation asymptotically approaches zero. Although the precise value of βTSP is unknown, published studies indicate its magnitude is approximately 0.712. In this paper, possibly for the first time, precise formulae are proposed for the parameters of the underlying normal distribution and βTSP, based on intuition, mathematical reasoning, and empirical fits to both published and experimentally derived data. [ABSTRACT FROM AUTHOR]

We propose a heuristic method of using network centralities for constructing small-weight Steiner trees in this paper. The Steiner tree problem in graphs is one of the practical NP-hard combinatorial optimization problems. Given a graph and a set of vertices called terminals in the graph, the objective of the Steiner tree problem in graphs is to find a minimum weight Steiner tree that is a tree containing all the terminals. Conventional construction methods make a Steiner tree based on the shortest paths between terminals. If these shortest paths are overlapped as much as possible, we can obtain a small-weight Steiner tree. Therefore, we proposed to use network centralities to distinguish which edges should be included to make a small-weight Steiner tree. Experimental results revealed that using the vertex or the edge betweenness centralities contributes to making small-weight Steiner trees. [ABSTRACT FROM AUTHOR]

The dominating set problem (DSP) is one of the most famous problems in combinatorial optimization. It is defined as follows. For a given graph G = (V , E) , a dominating set of G is a subset S ⊆ V such that every vertex in V ∖ S is adjacent to at least one vertex in S. Furthermore, the DSP is the problem of finding a minimum-size dominating set and the corresponding minimum size, the domination number of G. In this, work we investigate a variant of the DSP, the super dominating set problem (SDSP), which has attracted much attention during the last years. A dominating set S is called a super dominating set of G , if for every vertex u ∈ S ¯ = V ∖ S , there exists a v ∈ S such that N (v) ∩ S ¯ = N (v) ∖ S = { u }. Analogously, the SDSP is to find a minimum-size super dominating set, and the corresponding minimum size, the super domination number of G. The decision variants of both the DSP and the SDSP have been shown to be NP -hard. In this paper, we present tight bounds for the super domination number of the neighbourhood corona product, r -clique sum, and the Hajós sum of two graphs. Additionally, we present infinite families of graphs attaining our bounds. Finally, we give the exact number of minimum size super dominating sets for some graph classes. In particular, the number of super dominating sets for cycles has quite surprising properties as it varies between values of the set { 4 , n , 2 n , 5 n 2 − 10 n 8 } based on n mod 4. [ABSTRACT FROM AUTHOR]

Solving combinatorial optimization problems (COPs) poses a significant challenge in various application domains. The NP-hardness of many COPs necessitates the integration of meta-heuristics to effectively tackle these problems by leveraging the strengths of each meta-heuristic. However, hybrid meta-heuristics lack a mechanism to determine when to activate specific techniques during the search process. To address these limitations and enhance the overall generality, this study proposes a novel agent-based hyper-heuristic framework, referred to as IAFCO, for solving COPs. The proposed framework imbues the search strategy with greater intelligence and information, resulting in improved performance. The proposed framework comprises 4 coalitions that leverage different search perspectives to enhance the search process: a global coalition, a local coalition, a learning coalition, and a perturbation coalition. Additionally, a control agent is introduced to coordinate the coalitions. Using a reinforcement learning mechanism, the control agent autonomously selects the most suitable coalition of agents based on the search state. The set of states employed in this study is problem-independent and encompasses all possible states that may arise during the search process. Furthermore, some agents adopt chaotic numbers instead of random numbers to maintain diversity. To showcase the effectiveness of the proposed framework, its performance is evaluated on the software modularization problem (SMP) -also known as software clustering- and community detection problem (CDP) in complex networks as 2 case studies. The experiments on SMP's software systems, including 10 applications and 10 folders of Mozilla Firefox, and comparison with 21 modularization algorithms and experiments on CDP's networks, including 9 real-world networks, and comparison with 22 state-of-the-art community detection algorithms, indicate that the proposed framework is comparable to other existing methods. The source codes and datasets of this paper are available at https://github.com/mahjoubeh-t/IAFCO. [ABSTRACT FROM AUTHOR]

In this paper, we study the knapsack problem with conflict pair constraints. After a thorough literature survey on the topic, our study focuses on the special case of bipartite conflict graphs. For complete bipartite (multipartite) conflict graphs, the problem is shown to be NP-hard but solvable in pseudo-polynomial time, and it admits an FPTAS. Extensions of these results to more general classes of graphs are also presented. Further, a class of integer programming models for the general knapsack problem with conflict pair constraints is presented, which generalizes and unifies the existing formulations. The strength of the LP relaxations of these formulations is analyzed, and we discuss different ways to tighten them. Experimental comparisons of these models are also presented to assess their relative strengths. This analysis disclosed various strong and weak points of different formulations of the problem and their relationships to different types of problem data. This information can be used in designing special purpose algorithms for KPCC involving a learning component. [ABSTRACT FROM AUTHOR]

Linear assignment problems hold a pivotal role in combinatorial optimization, offering a broad spectrum of applications within the field of data sciences. They consist of assigning "agents" to "tasks" in a way that leads to a minimum total cost associated with the assignment. The assignment is balanced when the number of agents equals the number of tasks, with a one-to-one correspondence between agents and tasks, and it is and unbalanced otherwise. Additional options and constraints may be imposed, such as allowing agents to perform multiple tasks or allowing tasks to be performed by multiple agents. In this paper, we propose a novel framework that can solve all these assignment problems employing methodologies derived from the field of statistical physics. We describe this formalism in detail and validate all its assertions. A major part of this framework is the definition of a concave effective free energy function that encapsulates the constraints of the assignment problem within a finite temperature context. We demonstrate that this free energy monotonically decreases as a function of a parameter β representing the inverse of temperature. As β increases, the free energy converges to the optimal assignment cost. Furthermore, we demonstrate that when β values are sufficiently large, the exact solution to the assignment problem can be derived by rounding off the elements of the computed assignment matrix to the nearest integer. We describe a computer implementation of our framework and illustrate its application to multi-task assignment problems for which the Hungarian algorithm is not applicable. [ABSTRACT FROM AUTHOR]

As a classical combinatorial optimization problem, the traveling salesman problem (TSP) has been extensively investigated in the fields of Artificial Intelligence and Operations Research. Due to being NP-complete, it is still rather challenging to solve both effectively and efficiently. Because of its high theoretical significance and wide practical applications, great effort has been undertaken to solve it from the point of view of intelligent search. In this paper, we propose a two-stage probe-based search optimization algorithm for solving both symmetric and asymmetric TSPs through the stages of route development and a self-escape mechanism. Specifically, in the first stage, a reasonable proportion threshold filter of potential basis probes or partial routes is set up at each step during the complete route development process. In this way, the poor basis probes with longer routes are filtered out automatically. Moreover, four local augmentation operators are further employed to improve these potential basis probes at each step. In the second stage, a self-escape mechanism or operation is further implemented on the obtained complete routes to prevent the probe-based search from being trapped in a locally optimal solution. The experimental results on a collection of benchmark TSP datasets demonstrate that our proposed algorithm is more effective than other state-of-the-art optimization algorithms. In fact, it achieves the best-known TSP benchmark solutions in many datasets, while, in certain cases, it even generates solutions that are better than the best-known TSP benchmark solutions. [ABSTRACT FROM AUTHOR]

Due to its high spectral efficiency and various other advantages, filter bank multicarrier/offset quadrate amplitude modulation (FBMC/OQAM) has long been considered as a candidate waveform for the fifth generation (5G) and beyond telecommunication technologies. On the other hand, it is possible to both increase the data rate and alleviate the channel fading effects by using the multiple-input multiple-output (MIMO) antenna structure in the FBMC/OQAM transceiver. However, since the symbol detection is an indispensable task to be fulfilled in wireless communication, it is crucial to employ an efficient symbol detector at the MIMO-FBMC/OQAM receiver. Maximum likelihood (ML) detector, which always finds the optimal symbols by trying all of the possible symbol combinations likely to be transmitted, is known for its extremely high computational complexity making it impractical to be used in any system. On the other hand, it is possible to both considerably reduce the ML complexity and achieve the near-ML performance by optimizing the symbol vectors instead of implementing an exhaustive search. Since searching for the optimal symbol combination in discrete space is a combinatorial optimization problem, we developed a novel discrete harmony search (disHS) algorithm to perform this operation. According to the simulation results, the newly developed disHS algorithm not only achieves near-ML performance with lower computational complexity, but also clearly leaves behind the other symbol detectors considered in this paper. [ABSTRACT FROM AUTHOR]

We consider the problem of designing lightweight, load-bearing planar frame structures for additive manufacturing, which can be formulated as a nonlinear, non-convex mathematical programming problems. Even using state-of-the-art commercial solvers, exact methods are only capable of solving small unrealistic instances (with very few variables). In this paper, we develop a heuristic method which is fast and capable of solving the design problem for larger-scale, weight-optimized, planar frame structures for additive manufacturing. The approach explicitly considers manufacturability constraints stemming from the use of additive manufacturing technology and leverages the problem structure imposed by these constraints. The proposed heuristic method is based on iteratively resolving a relaxed master problem on a reduced ground structure. The approach differs from the existing methods in two important aspects. First, we consider planar frame optimization master problem directly (instead of simpler but less relevant truss optimization). Secondly, we employ both element and node addition, which allows us to enforce additive manufacturability constraints without using binary variables (and hence, avoiding the need for computationally expensive integer programming). [ABSTRACT FROM AUTHOR]

In recent years, the development of graph neural network (GNN) and deep reinforcement learning provides new methods to solve combinatorial optimization problems. Currently, most of these methods do not consider the problem of algorithm parameter learning. This paper developed an intelligent optimization model based on graph attention networks to solve this problem. The model automatically learned neighborhood search operators and destructive sequence terminators according to a significant amount of problem data, and trained model parameters based on reinforcement learning. This article used standard examples to test the model and conducted three different groups of experiments. The experimental results show that the learned neighborhood search operator has a remarkable ability to optimize and converge, while significantly reducing the training memory occupation. It can solve CVRP problems containing hundreds of nodes in a short time and has the potential for expansion. [ABSTRACT FROM AUTHOR]

Network disintegration is a fundamental issue in the field of complex networks, with its core in identifying critical nodes or sets and removing them to weaken network functionality. The research on this problem has significant strategic value and has increasingly attracted attention, including in controlling the spread of diseases and dismantling terrorist organizations. In this paper, we focus on the problem of network disintegration with discrete entity resources from the attack view, that is, optimizing resource allocation to maximize the effect of network disintegration. Specifically, we model the network disintegration problem with limited entity resources as a nonlinear optimization problem and prove its NP-hardness. Then, we design a method based on deep reinforcement learning (DRL), Net-Cracker, which transforms the two-stage entity resource and network node selection task into a single-stage object selection problem. Extensive experiments demonstrate that compared with the benchmark algorithm, Net-Cracker can improve the solution quality by about 8∼62%, while enabling a 30-to-160-fold speed up. Net-Cracker also exhibits strong generalization ability and can find better results in a near real-time manner even when the network scale is much larger than that in training data. [ABSTRACT FROM AUTHOR]

In this paper, we study a robust two-stage concept for combinatorial optimization problems under discrete demand uncertainty. Combinatorial optimization problems are based on a finite set of elements for which we decide whether they are part of a solution. We divide the elements into two types, the so-called fixed and free elements. In a first stage, we irrecoverably decide whether some fixed elements are part of a solution despite uncertain demand. In a second stage, we decide whether some free elements complete a solution after a demand scenario is realized. The objective is to find a robust solution that minimizes the worst-case cost over a finite scenario set. We show the NP -hardness of this robust two-stage version of several specific combinatorial optimization problems under discrete demand uncertainty but provide a polynomial-time solvable special case. In particular, we apply this concept to three combinatorial optimization problems: the representative multi-selection, the shortest path, and the minimum weight perfect b -matching problem. We prove the NP -hardness and present special cases solvable in pseudo-polynomial and polynomial time. [ABSTRACT FROM AUTHOR]

Assigning patients to rooms is a fundamental task in hospitals and, especially, within wards. For this so-called patient-to-room assignment problem (PRA) many heuristics have been proposed with a large variety of different practical constraints. However, a thorough investigation of the problem's structure itself has been neglected so far. In this paper, we present insights about the basic, underlying combinatorial problem of PRA with a focus on minimizing the number of patient transfers which occur if patients have to change rooms during their stay. Particularly, we prove that in the case of double bedrooms, although minimizing the total number of transfers is NP -complete, each patient has to be transferred at most once, and provide upper bounds on the minimum total number of transfers. [ABSTRACT FROM AUTHOR]

Symmetry is an important principle and characteristic that is prevalent in nature and artificial environments. In the three-dimensional packing problem, leveraging the inherent symmetry of goods and the symmetry of the packing space can enhance packing efficiency and utilization.The three-dimensional packing problem is an NP-hard combinatorial optimization problem in the field of modern logistics, with high computational complexity. This paper proposes an improved genetic algorithm by incorporating a fusion tabu search strategy to address this problem. The algorithm employs a three-dimensional loading mathematical model and utilizes a wall-building method under residual space constraints for stacking goods. Furthermore, adaptation of fitness variation strategy, chromosome adjustment, and tabu search algorithm are introduced to balance the algorithm's global and local search capabilities, as well as to enhance population diversity and convergence speed. Through testing on benchmark cases such as Bischoff and Ratcliff, the improved algorithm demonstrates an average increase of over 3% in packing space utilization compared to traditional genetic algorithms and other heuristic algorithms, validating its feasibility and effectiveness. The proposed improved genetic algorithm provides new insights for solving three-dimensional packing problems and optimizing logistics loading schedules, offering promising prospects for various applications. [ABSTRACT FROM AUTHOR]

This paper presents a novel hybrid approach, fusing genetic algorithms (GA) and penguin search optimization (PSeOA), to address the flow shop scheduling problem (FSSP). GA utilizes selection, crossover, and mutation inspired by natural selection, while PSeOA emulates penguin foraging behavior for efficient exploration. The approach integrates GA's genetic diversity and solution space exploration with PSeOA's rapid convergence, further improved with FSSP-specific modifications. Extensive experiments validate its efficacy, outperforming pure GA, PSeOA, and other metaheuristics. [ABSTRACT FROM AUTHOR]

The development of information technology, wireless communications have become prevalent in every other field we can imagine. Sensor nodes are the fundamental element of wireless communication networks. When they are deployed, they gather environmental data from the surrounding area and send it to the base station for further analysis. This paper focused on creating a routing technique that improved wireless communication energy conservation through the use of fuzzy logic and ant colony optimisation in order to extend battery life. Ant colony optimisation algorithm (HFACO) and hybrid fuzzy logic were used in the construction of the routing protocol. Numerous derived techniques have been adapted to dynamic problems in real variables, stochastic problems, multi-targets, and parallel implementations. Ant colony optimisation algorithms have been applied to a wide range of combinatorial optimisation problems, from quadratic assignment to protein folding or routing vehicles. Several techniques that are based on how ant colonies forage have been used recently to solve challenging discrete optimisation problems.By taking into account the node's energy and traffic load, fuzzy logic was utilised to determine the total node cost to the gateway. Ant colony optimisation (ACO) was used to find the shortest path between the source and destination sensor nodes, and the path's value was determined by measuring its shortest distance. When compared to the ACO's performance in the same conditions, the Matlab simulation's results showed superior energy conservation performance. This improved routing technique can be applied to Wi-Fi sensor networks in industrial environments. [ABSTRACT FROM AUTHOR]

The object of research is the method and algorithm of arithmetic addition of binomial numbers generated by binary binomial counting systems. The lack of binomial arithmetic, in particular the operation of adding binary binomial numbers, in a certain way prevents their introduction into information systems and the construction of information and communication technologies based on them for combinatorial optimization, generation of combinatorial objects, data compression and encryption. In the framework of the proposed approach, instead of operating with binomial coefficients, only operations with their upper and lower parameters are carried out. At the same time, the weighting coefficients of binary binomial numbers, which are added to each other, are represented in the form of two-component tuples. Taking this into account, this paper presents an algorithm for binomial arithmetic addition using dynamic arrays. The main idea, which is included in the structure of the algorithm of binomial arithmetic addition based on dynamic arrays, is that the transition from a two-dimensional model of summation to a one-dimensional one is carried out. At the same time, only available, existing binomial coefficients are placed in the dynamic array. Accordingly, the search for binomial coefficients equal to or greater than the quantitative equivalent takes place in much smaller areas. In comparison with the algorithm based on matrix models, this quite significantly reduces the amount of time spent when performing the summation operation, and also reduces the requirements for the amount of memory required for placing two-component tuples of the assembly array. In the course of the research, a several-fold decrease in the number of machine cycles required to search for the necessary elements in the dynamic array was practically confirmed. This leads to an increase in the performance of the presented algorithm of binomial arithmetic addition based on dynamic arrays. In turn, this leads to the acceleration of solving information tasks of combinatorial optimization, generation of combinatorial objects, data compression and encryption, for the solution of which the operation of adding binary binomial numbers is used. [ABSTRACT FROM AUTHOR]

Among the distribution network planning problems, feeder routing is one of the most important and challenging issues. Feeder routing is defined as the optimal determination of the feeders' routes by minimizing the investment cost and satisfying the network constraints. To the best knowledge of the authors, solving feeder routing problem in multi-objective framework is rarely investigated in the previous literature. This paper develops a bi-objective modeling and optimization framework to efficiently solve the feeder routing problem of distribution network considering cost and power losses. Since feeder routing is a complex, high-dimensional and combinatorial optimization problem, a multi-objective differential crow search algorithm (MO-CSAdif) is proposed to obtain a well-distributed and widely spread Pareto front. On a real large distribution network, simulation results confirm the usefulness of the proposed optimization framework. It can be drawn that MO-CSAdif can be a promising method to optimally solve the feeder routing problem. [ABSTRACT FROM AUTHOR]

Prompt optimization is a crucial task for improving the performance of large language models for downstream tasks. In this paper, a prompt is a sequence of n-grams selected from a vocabulary. Consequently, the aim is to select the optimal prompt concerning a certain performance metric. Prompt optimization can be considered as a combinatorial optimization problem, with the number of possible prompts (i.e., the combinatorial search space) given by the size of the vocabulary (i.e., all the possible n-grams) raised to the power of the length of the prompt. Exhaustive search is impractical; thus, an efficient search strategy is needed. We propose a Bayesian Optimization method performed over a continuous relaxation of the combinatorial search space. Bayesian Optimization is the dominant approach in black-box optimization for its sample efficiency, along with its modular structure and versatility. We use BoTorch, a library for Bayesian Optimization research built on top of PyTorch. Specifically, we focus on Hard Prompt Tuning, which directly searches for an optimal prompt to be added to the text input without requiring access to the Large Language Model, using it as a black-box (such as for GPT-4 which is available as a Model as a Service). Albeit preliminary and based on "vanilla" Bayesian Optimization algorithms, our experiments with RoBERTa as a large language model, on six benchmark datasets, show good performances when compared against other state-of-the-art black-box prompt optimization methods and enable an analysis of the trade-off between the size of the search space, accuracy, and wall-clock time. [ABSTRACT FROM AUTHOR]