Search

We study the quadratic cycle cover problem (QCCP), which aims to find a node-disjoint cycle cover in a directed graph with minimum interaction cost between successive arcs. We derive several semidefinite programming (SDP) relaxations and use facial reduction to make these strictly feasible. We investigate a nontrivial relationship between the transformation matrix used in the reduction and the structure of the graph, which is exploited in an efficient algorithm that constructs this matrix for any instance of the problem. To solve our relaxations, we propose an algorithm that incorporates an augmented Lagrangian method into a cutting-plane framework by utilizing Dykstra's projection algorithm. Our algorithm is suitable for solving SDP relaxations with a large number of cutting-planes. Computational results show that our SDP bounds and efficient cutting-plane algorithm outperform other QCCP bounding approaches from the literature. Finally, we provide several SDP-based upper bounding techniques, among which is a sequential Q-learning method that exploits a solution of our SDP relaxation within a reinforcement learning environment. Summary of Contribution: The quadratic cycle cover problem (QCCP) is the problem of finding a set of node-disjoint cycles covering all the nodes in a graph such that the total interaction cost between successive arcs is minimized. The QCCP has applications in many fields, among which are robotics, transportation, energy distribution networks, and automatic inspection. Besides this, the problem has a high theoretical relevance because of its close connection to the quadratic traveling salesman problem (QTSP). The QTSP has several applications, for example, in bioinformatics, and is considered to be among the most difficult combinatorial optimization problems nowadays. After removing the subtour elimination constraints, the QTSP boils down to the QCCP. Hence, an in-depth study of the QCCP also contributes to the construction of strong bounds for the QTSP. In this paper, we study the application of semidefinite programming (SDP) to obtain strong bounds for the QCCP. Our strongest SDP relaxation is very hard to solve by any SDP solver because of the large number of involved cutting-planes. Because of that, we propose a new approach in which an augmented Lagrangian method is incorporated into a cutting-plane framework by utilizing Dykstra's projection algorithm. We emphasize an efficient implementation of the method and perform an extensive computational study. This study shows that our method is able to handle a large number of cuts and that the resulting bounds are currently the best QCCP bounds in the literature. We also introduce several upper bounding techniques, among which is a distributed reinforcement learning algorithm that exploits our SDP relaxations. [ABSTRACT FROM AUTHOR]

Coherent Ising Machine (CIM) is a network of optical parametric oscillators that solve combinatorial optimization problems by finding the ground state of an Ising Hamiltonian. In CIMs, a problem arises when attempting to realize the Zeeman term because of the mismatch in size between interaction and Zeeman terms due to the variable amplitude of the optical parametric oscillator pulses corresponding to spins. There have been three approaches proposed so far to address this problem for CIM, including the absolute mean amplitude method, the auxiliary spin method, and the chaotic amplitude control (CAC) method. This paper focuses on the efficient implementation of Zeeman terms within the mean-field CIM model, which is a physics-inspired heuristic solver without quantum noise. With the mean-field model, computation is easier than with more physically accurate models, which makes it suitable for implementation in field programmable gate arrays and large-scale simulations. First, we examined the performance of the mean-field CIM model for realizing the Zeeman term with the CAC method, as well as their performance when compared to a more physically accurate model. Next, we compared the CAC method to other Zeeman term realization techniques on the mean-field model and a more physically accurate model. In both models, the CAC method outperformed the other methods while retaining similar performance. [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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

Order-picking optimization in a business sustainable competitiveness context is challenging due to prior studies focusing on theoretical model development with unrealistic assumptions in their algorithms and methodological validation, often neglecting practical concerns. This paper improves order-picking operations by employing combinatorial optimization as a travelling salesman problem and class-based dedicated storage models for the ATP company. The paper's originality and novelty lie in bridging the gap between academia and management, presenting an effort to connect theoretical concepts with practical optimization in order-picking warehouse operations in an environment of competitiveness. Realistic data and LINGO software were employed, revealing substantial improvements in the ATP warehouse operations through optimized pick path decisions embedded in warehouse layouts. This paper provides managerial tools for distance traveled optimization in the warehouse that yield competitive edges, enhanced supply chain efficiency and effectiveness, as well as other positive impacts on social, and environmental concerns such as labor safety, customer satisfaction, energy consumption, and CO2 emission. The paper also outlines future research directions to advance warehouse management and address sustainable competitiveness challenges, adding a new dimension to the original research. [ABSTRACT FROM AUTHOR]

In this paper, we focus on Hitting-Set , a fundamental problem in combinatorial optimization, through the lens of sublinear time algorithms. Given access to the hypergraph through a subset query oracle in the query model, we give sublinear time algorithms for Hitting-Set with almost tight parameterized query complexity. In parameterized query complexity , we estimate the number of queries to the oracle based on the parameter k , the size of the Hitting-Set. The subset query oracle we use in this paper is called Generalized d -partite Independent Set query oracle (GPIS) and it was introduced by Bishnu et al. (ISAAC'18). GPIS is a generalization to hypergraphs of the Bipartite Independent Set query oracle (BIS) introduced by Beame et al. (ITCS'18 and TALG'20) for estimating the number of edges in graphs. Since its introduction GPIS query oracle has been used for estimating the number of hyperedges independently by Dell et al. (SODA'20 and SICOMP'22) and Bhattacharya et al. (STACS'22), and for estimating the number of triangles in a graph by Bhattacharya et al. (ISAAC'19 and TOCS'21). Formally, GPIS is defined as follows: GPIS oracle for a d-uniform hypergraph H takes as input d pairwise disjoint non-empty subsets A 1 , ... , A d of vertices in H and answers whether there is a hyperedge in H that intersects each set A i , where i ∈ { 1 , 2 , ... , d }. For d = 2 , the GPIS oracle is nothing but BIS oracle. We show that d - Hitting-Set , the hitting set problem for d -uniform hypergraphs, can be solved using O ˜ d (k d log ⁡ n) GPIS queries. Additionally, we also showed that d - Decision-Hitting-Set , the decision version of d - Hitting-Set can be solved with O ˜ d (min ⁡ { k d log ⁡ n , k 2 d 2 }) GPIS queries. We complement these parameterized upper bounds with an almost matching parameterized lower bound that states that any algorithm that solves d - Decision-Hitting-Set requires Ω (( k + d d )) GPIS queries. [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]

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]

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]

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]

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]

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]

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]

• A graph neural network is proposed for learning multi-satellite scheduling policy. • It analyzes the differential impact of various constraints in scheduling. • It models the multi-satellite scheduling problem as a heterogeneous graph. • It designs a variant transformer to learn various relations within graph. • It designs a two-stage model to learn a multi-satellite scheduling policy. In this paper, we investigate the multi-satellite scheduling (MSS) problem, a combinatorial optimization problem (COP) that aims to enhance satellite utilization. Numerous scholars have conducted in-depth studies on this matter. Handcrafted policies are commonly employed in various algorithms. Despite the use of graphical representations, designing policies manually becomes increasingly difficult, particularly as the number of satellites and tasks grows. Consequently, we propose a novel approach for automatically summarizing graph structures and learning policies for MSS problem. The proposed approach is developed based on graph neural network, Transformer, and sequence to sequence framework. First, MSS problem is modeled as a heterogeneous graph following various constraints. Next, the encoder, which is based on GNN and Transformer, is designed to summarize crucial information from the aforementioned graph. Finally, a two-stage decoder is proposed taking into account dynamic information in stepwise solution generation. Since obtaining optimal solutions in practical applications is challenging, we train the model using reinforcement learning. The results of the experiment demonstrate that our proposed method performs effectively in various scenarios. The quality of the solutions generated through this method transcends that of conventional construction methods. Additionally, the method generates solutions quickly, which are comparable in quality to those produced by meta-heuristic algorithms. [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]

The mathematical side of applied problems in multiple subject areas (biology, pattern recognition, etc.) is reduced to the problem of discrete optimization in the following mathematical method. We were provided a network and graphs in its leaves, for which we needed to find a rearrangement of graphs by non-leaf nodes, in which the given functional reached its minimum. Such a problem, even in the simplest case, is NP-hard, which means unavoidable restrictions on the network, on graphs, or on the functional. In this publication, this problem is addressed in the case of all graphs being so-called "structures", meaning directed-loaded graphs consisting of paths and cycles, and the functional as the sum (over all edges in the network) of distances between structures at the endpoints of every edge. The distance itself is equal to the minimal length of sequence from the fixed list of operations, the composition of which transforms the structure at one endpoint of the edge into the structure at its other endpoint. The list of operations (and their costs) on such a graph is fixed. Under these conditions, the given discrete optimization problem is called the reconstruction problem. This paper presents novel algorithms for solving the reconstruction problem, along with full proofs of their low error and low polynomial complexity. For example, for the network, the problem is solved with a zero error algorithm that has a linear polynomial computational complexity; and for the tree the problem is solved using an algorithm with a multiplicative error of at most two, which has a second order polynomial computational complexity. [ABSTRACT FROM AUTHOR]

Combinatorial optimization problems are ubiquitous and computationally hard to solve in general. Quantum approximate optimization algorithm (QAOA), one of the most representative quantum-classical hybrid algorithms, is designed to solve combinatorial optimization problems by transforming the discrete optimization problem into a classical optimization problem over continuous circuit parameters. QAOA objective landscape is notorious for pervasive local minima, and its viability significantly relies on the efficacy of the classical optimizer. In this work, we design double adaptive-region Bayesian optimization (DARBO) for QAOA. Our numerical results demonstrate that the algorithm greatly outperforms conventional optimizers in terms of speed, accuracy, and stability. We also address the issues of measurement efficiency and the suppression of quantum noise by conducting the full optimization loop on a superconducting quantum processor as a proof of concept. This work helps to unlock the full power of QAOA and paves the way toward achieving quantum advantage in practical classical tasks. There is no universal way of optimizing the variation quantum circuits used in Noisy Intermediate-Scale Quantum (NISQ) applications. In this paper the authors introduce a new classical Bayesian optimizer, which converges much more quickly than conventional approaches, and test it for solving the Quantum Approximate Optimization Algorithm (QAOA) problem. [ABSTRACT FROM AUTHOR]

S-boxes, the key nonlinear component in numerous cryptographic systems, play a crucial role in ensuring security. The quest for random highly nonlinear S-boxes, a desirable attribute for better diffusion and confusion properties, is, therefore, a critical endeavor in cryptographic research. However, generating such nonlinear S-boxes often involves significant computational effort, presenting a major challenge for researchers. This paper addresses this gap by proposing an optimized version of the Simulated Annealing (SA) algorithm specifically tailored for efficient generation of highly nonlinear S-boxes. Our work introduces a multithreaded implementation of the SA algorithm, a heuristic search method known for its proficiency in combinatorial optimization. The multithreading feature enhances computational efficiency, making our approach more suitable for large-scale cryptographic applications. We further optimize the algorithm by incorporating additional exit criteria for both internal and external loops, which significantly reduces the computational complexity associated with the nonlinear substitution generation process. Furthermore, we undertake comprehensive experiments to identify the optimal parameters of the SA algorithm, aiming to maximize the probability of generating target S-boxes while minimizing the number of iterations. This optimization step provides a clear pathway to improve the success rate of the generation process. The results of our study demonstrate a significant improvement over previous works, showing a 30–40% enhancement in the generation of nonlinear S-boxes. [ABSTRACT FROM AUTHOR]

Rooted and ranked phylogenetic trees are mathematical objects that are useful in modelling hierarchical data and evolutionary relationships with applications to many fields such as evolutionary biology and genetic epidemiology. Bayesian phylogenetic inference usually explores the posterior distribution of trees via Markov chain Monte Carlo methods. However, assessing uncertainty and summarizing distributions remains challenging for these types of structures. While labelled phylogenetic trees have been extensively studied, relatively less literature exists for unlabelled trees that are increasingly useful, for example when one seeks to summarize samples of trees obtained with different methods, or from different samples and environments, and wishes to assess the stability and generalizability of these summaries. In our paper, we exploit recently proposed distance metrics of unlabelled ranked binary trees and unlabelled ranked genealogies, or trees equipped with branch lengths, to define the Fréchet mean, variance and interquartile sets as summaries of these tree distributions. We provide an efficient combinatorial optimization algorithm for computing the Fréchet mean of a sample or of distributions on unlabelled ranked tree shapes and unlabelled ranked genealogies. We show the applicability of our summary statistics for studying popular tree distributions and for comparing the SARS-CoV-2 evolutionary trees across different locations during the COVID-19 epidemic in 2020. Our current implementations are publicly available at https://github.com/RSamyak/fmatrix. [ABSTRACT FROM AUTHOR]

Cost is the foremost factor in decision-making for profit-driven organizations. However, hybrid flow shop scheduling (HFSS) research rarely prioritizes cost as its optimization objective. Existing studies primarily focus on electricity costs linked to machine utilization. This paper introduces a comprehensive cost-based HFSS model, encompassing electricity, labor, maintenance, and penalty costs. Next, the Tiki-Taka Algorithm (TTA) is improved by increasing the exploration capability to optimize the problem. The cost-based HFSS model and TTA algorithm have been tested using benchmark and case study problems. The results indicated that the TTA consistently outperforms other algorithms. It delivers the best mean fitness and better solution distribution. In industrial contexts, the TTA able to reduces costs by 2.8% to 12.0% compared to other approaches. This holistic cost-based HFSS model empowers production planners to make more informed decisions. Furthermore, the improved TTA shows promise for broader applicability in various combinatorial optimization domains. [ABSTRACT FROM AUTHOR]

Word Sense Disambiguation (WSD) is a key step for many natural language processing tasks such as information search, automatic translation, and sentiment analysis. WSD is the process that identifies appropriate senses of ambiguous words in the text. With the increasing number of words to be disambiguated in large amount of text data, WSD becomes very challenging and that is why an exhaustive search for the best set of senses may be unpractical. Recently, several metaheuristic approaches have been proposed for different complex optimization problems and have achieved good results. Therefore, in order to improve the WSD process, in this paper, the WSD problem is modeled as a combinatorial optimization problem, and the Discrete Student Psychology-Based Optimization (DSPBO) metaheuristic is proposed and used to selecting appropriate senses. A DSPBO-based WSD is proposed to disambiguate more ambiguous words together in function to their contexts in the target text, and a Lesk-based fitness function is used to guide the DSPBO metaheuristic to optimize the general semantic similarity of selected senses. The proposed approach is evaluated and compared to several recent WSD approaches on the well-known corpuses SensEval-2, SensEval-3, SemEval-2007, SemEval-13, and SemEval-15. The comparison is made in terms of F-Measure, precision, and recall. Experiments show a significant improvement both over existing knowledge lexicon-based approaches and metaheuristic-based approaches, with a higher F-measure of 84.21%, 83.33%, 87.5%, 77.58%, and 81.08% on SensEval-2, SensEval-3, SemEval-2007, SemEval-13, and SemEval-15, respectively. [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]

Selecting or adjusting attribute-levels (e.g. components, equipments, flavors, ingredients, prices, tastes) for multiple new and/or status quo products is an important task for a focal firm in a dynamic market. Usually, the goal is to maximize expected overall buyers' welfare based on consumers' partworths or expected revenue, market share, and profit under given assumptions. However, in general, these so-called product-line design problems cannot be solved exactly in acceptable computing time. Therefore, heuristics have been proposed: Two-stage heuristics select promising candidates for single products and evaluate sets of them as product-lines. One-stage heuristics directly search for multiple attribute-level combinations. In this paper, Ant Colony Optimization, Genetic Algorithms, Particle Swarm Optimization, Simulated Annealing and, firstly, Cluster-based Genetic Algorithm and Max-Min Ant Systems are applied to 78 small- to large-size product-line design problem instances. In contrast to former comparisons, data is generated according to a large sample of commercial conjoint analysis applications (n = 2,089). The results are promising: The firstly applied heuristics outperform the established ones. [ABSTRACT FROM AUTHOR]

Product Portfolio Planning (PPP) is one of the most critical decisions for companies to gain an edge in the competitive market. It seeks for the optimal combination of products and attribute levels offered for customers in the target market, which is a NP-hard combinatorial optimization problem. In this paper, a Probability-based Discrete Particle Swarm Optimization (PDPSO) algorithm is proposed to solve the PPP problem. In PDPSO, the particle is encoded as discrete values, which can be straightforwardly used to represent the product portfolio with discrete attributes. PDPSO adopts a probability-based mechanism to update particles. Specifically, a probability vector is used to decide the probability of three search behaviors, i.e., learning from the personal best position, global best position, or random search. In experiments, the search performance of PDPSO has been compared with that of a Genetic Algorithm (GA) and a Simulated Annealing (SA) algorithm on generated PPP problem cases with different sizes. The results indicate that PDPSO obtains significantly better optimization results than GA and SA in most cases and obtains desirable/near-optimal solutions on various PPP problem cases. A case study of notebook computer portfolio planning is also presented to illustrate the efficiency and effectiveness of PDPSO. [ABSTRACT FROM AUTHOR]

In this paper, the generalized widest path problem (or generalized maximum capacity problem) is studied. This problem is denoted by the GWPP. The classical widest path problem is to find a path from a source (s) to a sink (t) with the highest capacity among all possible s-t paths. The GWPP takes into account the presence of loss/gain factors on arcs as well. The GWPP aims to find an s-t path considering the loss/gain factors while satisfying the capacity constraints. For solving the GWPP, three strongly polynomial time algorithms are presented. Two algorithms only work in the case of losses. The first one is less efficient than the second one on a CPU, but it proves to be more efficient on large networks if it parallelized on GPUs. The third algorithm is able to deal with the more general case of losses/gains on arcs. An example is considered to illustrate how each algorithm works. Experiments on large networks are conducted to compare the efficiency of the algorithms proposed. [ABSTRACT FROM AUTHOR]

Reinforcement learning is an important technique in various fields, particularly in automated machine learning for reinforcement learning (AutoRL). The integration of transfer learning (TL) with AutoRL in combinatorial optimization is an area that requires further research. This paper employs both AutoRL and TL to effectively tackle combinatorial optimization challenges, specifically the asymmetric traveling salesman problem (ATSP) and the sequential ordering problem (SOP). A statistical analysis was conducted to assess the impact of TL on the aforementioned problems. Furthermore, the Auto_TL_RL algorithm was introduced as a novel contribution, combining the AutoRL and TL methodologies. Empirical findings strongly support the effectiveness of this integration, resulting in solutions that were significantly more efficient than conventional techniques, with an 85.7% improvement in the preliminary analysis results. Additionally, the computational time was reduced in 13 instances (i.e., in 92.8% of the simulated problems). The TL-integrated model outperformed the optimal benchmarks, demonstrating its superior convergence. The Auto_TL_RL algorithm design allows for smooth transitions between the ATSP and SOP domains. In a comprehensive evaluation, Auto_TL_RL significantly outperformed traditional methodologies in 78% of the instances analyzed. [ABSTRACT FROM AUTHOR]

In this paper, we study the following robust optimization problem. Given a set family representing feasibility and candidate objective functions, we choose a feasible set, and then an adversary chooses one objective function, knowing our choice. The goal is to find a randomized strategy (i.e., a probability distribution over the feasible sets) that maximizes the expected objective value in the worst case. This problem is fundamental in wide areas such as artificial intelligence, machine learning, game theory, and optimization. To solve the problem, we provide a general framework based on the dual linear programming problem. In the framework, we utilize the ellipsoid algorithm with the approximate separation algorithm. We prove that there exists an α -approximation algorithm for our robust optimization problem if there exists an α -approximation algorithm for finding a (deterministic) feasible set that maximizes a nonnegative linear combination of the candidate objective functions. Using our result, we provide approximation algorithms for the max–min fair randomized allocation problem and the maximum cardinality robustness problem with a knapsack constraint. [ABSTRACT FROM AUTHOR]

This paper expands the research around a recently proposed method to reduce the search space region for thermal unit commitment problems. The importance of such techniques comes from the combinatorial explosion regarding the variables of the problem when there are a large quantity of generating units in the system. The proposed heuristic approach utilizes sensitivity indices to gather information about the system and fix many of the binary decision variables over the planning horizon. This work further explores the method by demonstrating its effectiveness in large-scale systems subjected to ramp constraints. Despite the significantly increased complexity, the results of this paper indicate that the method can achieve high quality solutions notably faster than other approaches from the literature. [ABSTRACT FROM AUTHOR]

This paper presents an application of a novel quadratic unconstrained binary optimization (QUBO) formulation to the minimum loss problem in distribution networks. The proposed QUBO formulation was conceived to be employed in quantum annealing—a quantum computing paradigm useful for solving combinatorial optimization problems. Quantum annealing is expected to provide better and/or faster solutions to optimization problems when compared to the ones provided by classical computers. With the problem at stake, better solutions result in lower energy losses, and faster solutions contribute to the same outcome given the future need for frequent reconfiguration of distribution networks to accommodate highly volatile demand, as anticipated by recent low-carbon solutions. The paper presents the results obtained through a hybrid quantum-classical solver for a standard 33-node test network and compares them with the ones obtained from classical solvers. Our main conclusion is that quantum annealing has potential to show advantage in the near future in terms of solution quality and time-to-solution, as quantum annealers and hybrid solvers continue to improve their performance. [ABSTRACT FROM AUTHOR]

This paper introduces a new variant of the Bees Algorithm (BA) called Bees Algorithm with 2-parameter (BA2), which is a population-based metaheuristic algorithm designed to solve continuous and combinatorial optimisation problems. The proposed algorithm simplified the BA's parameters by combining exploration and exploitation strategies while preserving the algorithm's core principles to efficiently search for optimal solutions. The paper provides a detailed description of the algorithm's core principles and its application to two engineering problems, the air-cooling system design (ACSD) and the printed circuit board assembly sequence optimisation (PASO). The results show that BA2 outperforms previous versions of the basic BA in terms of convergence speed and solution quality. However, the authors acknowledge that further research is needed to test the scalability and generalisability of the algorithm to larger and more diverse optimisation problems. Overall, this paper provides valuable insights into the potential of metaheuristics for solving real-world optimisation problems. [ABSTRACT FROM AUTHOR]

The set-based particle swarm optimisation algorithm is a swarm-based meta-heuristic that has gained popularity in recent years. In contrast to the original particle swarm optimisation algorithm, the set-based particle swarm optimisation algorithm is used to solve discrete and combinatorial optimisation problems. The main objective of this paper is to review the set-based particle swarm optimisation algorithm and to provide an overview of the problems to which the algorithm has been applied. This paper starts with an examination of previous attempts to create a set-based particle swarm optimisation algorithm and discusses the shortcomings of the existing attempts. The set-based particle swarm optimisation algorithm is established as the only suitable particle swarm variant that is both based on true set theory and does not require problem-specific modifications. In-depth explanations are given regarding the general position and velocity update equations, the mechanisms used to control the exploration–exploitation trade-off, and the quantifiers of swarm diversity. After the various existing applications of set-based particle swarm optimisation are presented, this paper concludes with a discussion on potential future research. [ABSTRACT FROM AUTHOR]

This paper presents a new hybrid algorithm that combines genetic algorithms (GAs) and the optimizing spotted hyena algorithm (SHOA) to solve the production shop scheduling problem. The proposed GA-SHOA algorithm incorporates genetic operators, such as uniform crossover and mutation, into the SHOA algorithm to improve its performance. We evaluated the algorithm on a set of OR library instances and compared it to other state-of-the-art optimization algorithms, including SSO, SCE-OBL, CLS-BFO and ACGA. The experimental results show that the GA-SHOA algorithm consistently finds optimal or near-optimal solutions for all tested instances, outperforming the other algorithms. Our paper contributes to the field in several ways. First, we propose a hybrid algorithm that effectively combines the exploration and exploitation capabilities of SHO and GA, resulting in a balanced and efficient search process for finding near-optimal solutions for the FSSP. Second, we tailor the SHO and GA methods to the specific requirements of the FSSP, including encoding schemes, objective function evaluation and constraint handling, which ensures that the hybrid algorithm is well suited to address the challenges posed by the FSSP. Third, we perform a comprehensive performance evaluation of the proposed hybrid algorithm, demonstrating its effectiveness in terms of solution quality and computational efficiency. Finally, we provide an in-depth analysis of the behavior of the hybrid algorithm, discussing the roles of the SHO and GA components and their interactions during the search process, which can help understand the factors contributing to the success of the algorithm and provide insight into potential improvements or adaptations to other combinatorial optimization problems. [ABSTRACT FROM AUTHOR]