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]

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]

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 job shop scheduling problem is a classical combinatorial optimization challenge frequently encountered in manufacturing systems. It involves determining the optimal execution sequences for a set of jobs on various machines to maximize production efficiency and meet multiple objectives. The Non-dominated Sorting Genetic Algorithm III (NSGA-III) is an effective approach for solving the multi-objective job shop scheduling problem. Nevertheless, it has some limitations in solving scheduling problems, including inadequate global search capability, susceptibility to premature convergence, and challenges in balancing convergence and diversity. To enhance its performance, this paper introduces a strengthened dominance relation NSGA-III algorithm based on differential evolution (NSGA-III-SD). By incorporating constrained differential evolution and simulated binary crossover genetic operators, this algorithm effectively improves NSGA-III's global search capability while mitigating premature convergence issues. Furthermore, it introduces a reinforced dominance relation to address the tradeoff between convergence and diversity in NSGA-III. Additionally, effective encoding and decoding methods for discrete job shop scheduling are proposed, which can improve the overall performance of the algorithm without complex computation. To validate the algorithm's effectiveness, NSGA-III-SD is extensively compared with other advanced multi-objective optimization algorithms using 20 job shop scheduling test instances. The experimental results demonstrate that NSGA-III-SD achieves better solution quality and diversity, proving its effectiveness in solving the multi-objective job shop scheduling problem. [ABSTRACT FROM AUTHOR]

The ant system (AS) and scheduling problem are well-known concepts in literature. Ant algorithms have been known to be an effective tool for solving combinatorial optimization problems. Elitist AS (EAS), rank-based AS (RAS), ant colony system (ACS), and max-min AS (MMAS) are the variants of the AS algorithm; they are triggered by the different ways of updating the pheromone trail τ, computing the visibility η, and/or other parameters in the basic AS model. The main contribution of this article is twofold. First, the basic AS and its controlled parameters are presented, the key variants of the ant algorithms are explained, and major changes of each variant from the basic model are tracked. Second, sixty papers are collected between 2015 and 2020 based on a search strategy for tracking the implementation of different AS variants in solving scheduling problems. Numerous findings based on a statistical analysis of the collected papers are reported and discussed. This study will allow the researcher to understand the essence of the ant algorithm, recognize the fundamental differences in its five systems, and determine how each of them can be implemented. Tracking a sample of articles that apply an ant algorithm for a specific case study gives researchers new ideas on how to adjust the original model to fit their problem. [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]

In real-world applications, feature selection is crucial for enhancing the performance of data science and machine learning models. Typically, feature selection is a complex combinatorial optimization problem and a multi-objective optimization problem. Its primary goals are to reduce the dimensionality of the dataset and enhance the performance of machine learning algorithms. The selection of features in high-dimensional datasets is challenging due to the intricate relationships between features, which pose significant challenges to the performance and computational efficiency of algorithms. This paper introduces a Knowledge-Guided Competitive Co-Evolutionary Algorithm (KCCEA) for feature selection, especially for high-dimensional features. In the proposed algorithm, we make improvements to the foundational dominance-based multi-objective evolutionary algorithm in two aspects. First, the use of feature correlation as knowledge to guide evolution enhances the search speed and quality of traditional multi-objective evolutionary algorithm solutions. Second, a dynamically allocated competitive–cooperative evolutionary mechanism is proposed, integrating the improved knowledge-guided evolution with traditional evolutionary algorithms, further enhancing the search efficiency and diversity of solutions. Through rigorous empirical testing on various datasets, the KCCEA demonstrates superior performance compared to basic multi-objective evolutionary algorithms, providing effective solutions to multi-objective feature selection problems while enhancing the interpretability and effectiveness of prediction models. [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]

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]

Heterogeneous architecture-based systems-on-chip enable the development of flexible and powerful multifunctional RF systems. In complex and dynamic environments where applications arrive continuously and stochastically, real-time scheduling of multiple applications to appropriate processor resources is crucial for fully utilizing the heterogeneous SoC's resource potential. However, heterogeneous resource-scheduling algorithms still face many problems in practical situations, including generalized abstraction of applications and heterogeneous resources, resource allocation, efficient scheduling of multiple applications in complex mission scenarios, and how to ensure the effectiveness combining with real-world applications of scheduling algorithms. Therefore, in this paper, we design the Multi-Application Scheduling Algorithm, named MASA, which is a two-phase scheduler architecture based on Deep Reinforcement Learning. The algorithm is made up of neural network scheduler-based task prioritization for dynamic encoding of applications and heuristic scheduler-based task mapping for solving the processor resource allocation problem. In order to achieve stable and fast training of the network scheduler based on the actor–critic strategy, we propose optimization methods for the training of MASA: reward dynamic alignment (RDA), earlier termination of the initial episodes, and asynchronous multi-agent training. The performance of the MASA is tested with classic directed acyclic graph and six real-world application datasets, respectively. Experimental results show that MASA outperforms other neural scheduling algorithms and heuristics, and ablation experiments illustrate how these training optimizations improve the network's capacity. [ABSTRACT FROM AUTHOR]

The introduction of 5G technologies has enabled the possibility of designing and building several new classes of networked information systems that were previously impossible to implement due to limitations on data throughput or the reliability of transmission channels. Among them, one of the most interesting and successful examples with a highly positive impact in terms of the quality of urban environments and societal and economical welfare is a system of semi-autonomous connected vehicles, where IoT devices, data centers, and fleets of smart vehicles equipped with communication and computational resources are combined into a heterogeneous and distributed infrastructure, unifying hardware, networks, and software. In order to efficiently provide various services (e.g., patrolling, pickup and delivery, monitoring), these systems typically rely on collecting and broadcasting large amounts of data (e.g., sensor data, GPS traces, or maps), which need to be properly collected and processed in a timely manner. As is well documented in the literature, one of the most effective ways to achieve this purpose, especially in a real-time context, is to adopt a graph model of the data (e.g., to model communication networks, roads, or interactions between vehicles) and to employ suitable graph algorithms to solve properly defined computational problems of interest (e.g., shortest paths or distributed consensus). While research in this context has been extensive from a theoretical perspective, works that have focused on the implementation, deployment, and evaluation of the practical performance of graph algorithms for real-world systems of autonomous vehicles have been much rarer. In this paper, we present a study of this kind. Specifically, we first describe the main features of a real-world information system employing semi-autonomous connected vehicles that is currently being tested in the city of L'Aquila (Italy). Then, we present an overview of the computational challenges arising in the considered application domain and provide a systematic survey of known algorithmic results for one of the most relevant classes of computational problems that have to be addressed in said domain, namely, pickup and delivery problems. Finally, we discuss implementation issues, adopted software tools, and the deployment and testing phases concerning one of the algorithmic components of the mentioned real-world system dedicated to handling a specific problem of the above class, namely, the pickup and delivery multi-vehicle problem with time windows. [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]

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]

Outlier detection is of great significance in the domain of data mining. Its task is to find those target points that are not identical to most of the object generation mechanisms. The existing algorithms are mainly divided into density-based algorithms and distance-based algorithms. However, both approaches have some drawbacks. The former struggles to handle low-density modes, while the latter cannot detect local outliers. Moreover, the outlier detection algorithm is very sensitive to parameter settings. This paper proposes a new two-parameter outlier detection (TPOD) algorithm. The method proposed in this paper does not need to manually define the number of neighbors, and the introduction of relative distance can also solve the problem of low density and further accurately detect outliers. This is a combinatorial optimization problem. Firstly, the number of natural neighbors is iteratively calculated, and then the local density of the target object is calculated by adaptive kernel density estimation. Secondly, the relative distance of the target points is computed through natural neighbors. Finally, these two parameters are combined to obtain the outlier factor. This eliminates the influence of parameters that require users to determine the number of outliers themselves, namely, the top-n effect. Two synthetic datasets and 17 real datasets were used to test the effectiveness of this method; a comparison with another five algorithms is also provided. The AUC value and F1 score on multiple datasets are higher than other algorithms, indicating that outliers can be found accurately, which proves that the algorithm is effective. [ABSTRACT FROM AUTHOR]

This paper investigates the use of Oracle PL/SQL and Genetic Algorithms for performing bulk resource scheduling tasks. To achieve this current theory and information from literature were examined, in order to select a suitable set of methods and algorithms. The findings of this paper are that PL/SQL and Genetic Algorithms when combined with knowledge bases provides an acceptable level of accuracy and speed when scheduling multiple of constrained resources. [ABSTRACT FROM AUTHOR]

Covering problems find applications in many areas of computer science and engineering, such that numerous combinatorial problems can be formulated as covering problems. Combinatorial optimization problems are generally NPhard problems that require an extensive search to find the optimal solution. Exploiting the benefits of quantum computing, we present a quantum oracle design for covering problems, taking advantage of Grover’s search algorithm to achieve quadratic speedup. This paper also discusses applications of the quantum counter in unate covering problems and binate covering problems with some important practical applications, such as finding prime implicants of a Boolean function, implication graphs, and minimization of incompletely specified Finite State Machines. [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]

Nodes localization has been a critical subject in wireless sensor network (WSN) field. As far as existing localization algorithms are concerned, distance vector hop (DV-Hop) has the advantages of no extra hardware and implementation simplicity, however its localization accuracy cannot meet some specific requirements. In order to enhance the accuracy of WSN nodes localization, a DV-Hop based localization algorithm based on nodes negotiation and multi communication radii (NNMCR DV-Hop) is proposed in this paper. Firstly, the hop counts between WSN nodes is modified from an integer to a decimal by changing communication radius of anchor nodes through nodes negotiation. By refining the hop counts, the accuracy of the estimated distance from the unknown to the anchor nodes is improved. Secondly, the calculation of the average hop size of the anchor node is abstracted into a combinatorial optimization problem which is solved by using binary particle swarm optimization (BPSO) to improve the accuracy of the estimated distance which is between the anchor and the unknown node. Finally, when calculating the coordinates of unknown nodes, only the anchor nodes with smaller hop counts are selected to participate in the calculation. Simulation experiments show that compared with the original DV-Hop as well as other improved algorithms based on DV-Hop, NNMCR DV-Hop greatly improves the localization accuracy of unknown nodes without additional hardware. [ABSTRACT FROM AUTHOR]

Recently, substantial progress has been made in developing efficient algorithms for solving combinatorial optimization problems. In this paper, following this direction, the problem of designing supply chains which is an important combinatorial optimization problem is considered. The structural properties of supply chain models are investigated to transform such models into a generalized network optimization model. The transformation to a generalized network optimization model reduces the algorithms' solution time. Moreover, this paper proposes a new efficient hybrid algorithm based on tabu search and generalized network simplex algorithm (GN-TSA) for designing multi-objectives supply chain models. The developed algorithm's parameters are tuned properly, validated, and evaluated. The algorithm's performance is then compared to an exact algorithm embedded in the General Algebraic Modeling System (GAMS) and two metaheuristic algorithms, namely a linear programming simplex algorithm integrated with the tabu search approach (LP-TSA) and simulated annealing. The findings indicated that the GN-TSA obtains solutions very close to the exact algorithm with less computation time. In addition, the proposed algorithm outperforms the LP-TSA and simulated annealing in terms of computation time, while the quality of the solutions is the same as solutions obtained by LP-TSA and better than simulated annealing. On average, the results revealed that the reduction in computational time is more than 26.30% using GN-TSA compared to LP-TSA and simulated annealing. [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]

We consider an optimization problem arising when a set of items must be selected and picked up from given locations in an automated storage and retrieval system by a crane of given capacity, minimizing the overall distance traveled. The problem has been classified as open in a recent taxonomy of optimal picking problems in automated warehouses. In this paper, we analyze some non-trivial properties of the problem and we describe a polynomial-time dynamic programming algorithm to solve it to proven optimality. [ABSTRACT FROM AUTHOR]

Fog radio access network (Fog-RAN), which pushes caching and computing capabilities to the network edge, is capable of efficiently delivering content to users by using carefully designed caching placement and content replacement algorithms. In this paper, the transmission scheme design and coding parameter optimization will be considered for coded caching in Fog-RAN, where the reliability of content delivery, i.e., content outage probability, is used as the performance metric. The problem will be formulated as a complicated multi-objective probabilistic combinatorial optimization. A novel maximum $b$ -matching approach will then be proposed to obtain the Pareto optimal solution with fairness constraint. Based on the fast message passing approach, a distributed algorithm with a low memory usage of $O(M+N)$ is also proposed, where $M$ is the number of users and $N$ is the number of fog access points (Fog-APs). Although it is usually very difficult to derive the closed-form formulas for the optimal solution, the approximation formulas of the content outage probability will also be obtained as a function of coding parameters. The asymptotic optimal coding parameters can then be obtained by defining and deriving the outage exponent region and diversity-multiplexing region. Simulation results will illustrate the accuracy of the theoretical derivations, and verify the outage performance of the proposed approach. Therefore, this paper not only proposes a practical distributed Fog-AP selection algorithm for coded caching but also provides a systematic way to evaluate and optimize the performance of Fog-RANs. [ABSTRACT FROM AUTHOR]

A greedy randomized adaptive search procedure (GRASP) is a metaheuristic for combinatorial optimization. It is a multi-start or iterative process, in which each GRASP iteration consists of two phases, a construction phase, in which a feasible solution is produced, and a local search phase, in which a local optimum in the neighborhood of the constructed solution is sought. Since 1989, numerous papers on the basic aspects of GRASP, as well as enhancements to the basic metaheuristic, have appeared in the literature. GRASP has been applied to a wide range of combinatorial optimization problems, ranging from scheduling and routing to drawing and turbine balancing. This is the second of two papers with an annotated bibliography of the GRASP literature from 1989 to 2008. In the companion paper, algorithmic aspects of GRASP are surveyed. In this paper, we cover the literature where GRASP is applied to scheduling, routing, logic, partitioning, location, graph theory, assignment, manufacturing, transportation, telecommunications, biology and related fields, automatic drawing, power systems, and VLSI design. [ABSTRACT FROM AUTHOR]

This paper deals with the integer inverse obnoxious p-median location problem on tree networks in which the aim is to modify the edge lengths by integer amounts at the minimum overall cost within certain modification bounds so that a given set of p vertices, defining the predetermined facility locations, becomes an obnoxious p-median location of the perturbed network. We develop exact combinatorial approaches for obtaining the optimal solutions of the problem under the weighted Chebyshev and the weighted bottleneck-type combining cost norms. Moreover, the optimal solution algorithms with linear time complexities are proposed for the problem under the weighted bottleneck-type Hamming and the weighted extended bottleneck-type Hamming cost norms. [ABSTRACT FROM AUTHOR]

The unit commitment problem (UCP), which includes the unit schedule and power dispatch, is a nonlinear high-dimensional and highly constrained mixed-integer combinatorial optimization problem. One challenge herein is to obtain high-quality solutions considering various constraints. Developing a competitive hybrid method is a mainstream study goal in this field, which has focused on the unit schedule optimization but less on power dispatch. Inspired by the advantage of genetic algorithms (GAs) in solving combinational optimization problems and the characteristic of grey prediction evolution algorithm (GPE) with strong exploration ability, this paper proposes a novel hybrid GA and GPE method, termed hGAGPE, to solve the UCP. In hGAGPE, GPE, as a novel real parameter stochastic search algorithm based on the grey prediction theory for data mining, is first employed to solve the power dispatch of the UCP. Meanwhile, the unit schedule is performed by the popular GA. Additionally, some heuristic repair mechanisms based on the priority list and an elite selection mechanism are incorporated to enhance the performance of hGAGPE. The proposed hGAGPE is evaluated on six test systems with generating units in the range of 10 to 100 during a 24-h scheduling period. The numerical results demonstrate the feasibility and effectiveness of hGAGPE in comparison with other existing approaches. [ABSTRACT FROM AUTHOR]

In this paper, we have done a rapid and very simple algorithm that resolves the multiple objective combinatorial optimization problem. This, by determining a basic optimal solution, which is a strong spanning tree constructed, according to a well-chosen criterion. Consequently, our algorithm uses notions of Bellman's algorithm to determine the best path of the network, and Ford Fulkerson's algorithm to maximise the flow value. The Simplex Network Method that permits to reach the optimality conditions manipulates the two algorithms. In short, the interest of our work is the optimization of many criteria taking into account the strong spanning tree, which represents the central angular stone of the network. To illustrate that, we propose to optimize a bi-objective distribution problem. [ABSTRACT FROM AUTHOR]

Quantum approximate optimization algorithm (QAOA) is a promising variational quantum algorithm for combinatorial optimization problems. However, the implementation of QAOA is limited due to the requirement that the problems be mapped to Ising Hamiltonians and the nonconvex optimization landscapes. Although the Ising Hamiltonians for many NP hard problems have been obtained, a general method to obtain the Ising Hamiltonians for constrained combinatorial optimization problems (CCOPs) has not yet been investigated. In this paper, a general method is introduced to obtain the Ising Hamiltonians for CCOPs and the Metropolis‐Hastings warm‐starting algorithm for QAOA is presented which can provably converge to the global optimal solutions. The effectiveness of this method is demonstrated by tackling the minimum weight vertex cover (MWVC) problem, the minimum vertex cover (MVC) problem, and the maximal independent set problem as examples. The Ising Hamiltonian for the MWVC problem is obtained first time by using this method. The advantages of the Metropolis‐Hastings warm‐starting algorithm presented here is numerically analyzed through solving 30 randomly generated MVC cases with 1‐depth QAOA. [ABSTRACT FROM AUTHOR]

This paper presents a Q-learning-based algorithm for sequence and orientation optimization toward the 2D rectangular strip packing problem. The width-filled skyline is used to represent the interior packing state, and a constructive rectangular packing algorithm with the commonly adopted fitness evaluation for placement is designed. Then, the consecutive item packing is simulated as Markov Decision Process, where the state is defined as the set of already packed items, and the action is defined as the rectangle selected to be packed along with its orientation. We propose the reverse updating of Q-value in the paradigm of Q-learning and use the algorithm to optimize the sequence and orientation of the rectangles. The decreasing-size-choice mechanism in Q-learning is studied on randomly generated problems to optimize the setting of ε-greedy policy. We also test the Q-learning-based algorithm on the benchmark instances of C21, N13, N-series from NT, Cgcut and Beng. Compared with a few state-of-the-art algorithms, the computational results show that the proposed algorithm can produce good packing quality when adequate execution time allowed. [ABSTRACT FROM AUTHOR]

The two-dimension strip packing problem (2DSPP) is an NP-hard combinatorial optimization problem, and it has a wide range of applications. The order in which the rectangles are placed in the strip is the key to solving the 2DSPP. In this paper, the corner increment multi-level scoring strategy and the two-step selection strategy are proposed to make the selection of rectangles more reasonable. The hierarchical construction strategy is used to improve the constructive heuristic algorithm to expand the search space of the rectangle selection. Based on this, this paper proposes a multi-strategy rectangle selection algorithm TSMSA for solving 2DSPP. Comparing experiments with 7 excellent algorithms for solving 2DSPP on 737 instances of the benchmark dataset shows that the instance number of the optimal solution obtained by TSMSA is 1.05~2.9 times that of the other 7 algorithms. [ABSTRACT FROM AUTHOR]

Online social networks have become major battlegrounds for political campaigns, viral marketing, and the dissemination of news. As a consequence, “bad actors” are increasingly exploiting these platforms, which is a key challenge for their administrators, businesses and society in general. The spread of fake news is a classical example of the abuse of social networks by these bad actors. While some have advocated for stricter policies to control the spread of misinformation in social networks, this often happens in detriment of their democratic and organic structure. In this paper, we aim to limit the influence of a target group in a social network via the removal of a few users/links. We formulate the influence limitation problem in a data-driven fashion, by taking into account past propagation traces. More specifically, our algorithms find critical edges to be removed in order to decrease the influence of a target group based on past data. The idea is to control the diffusion processes while minimizing the amount of disturbance in the network structure. Moreover, we consider two types of constraints over edge removals, a budget constraint and also a, more general, set of matroid constraints. These problems lead to interesting challenges in terms of algorithm design. For instance, we are able to show that influence limitation is APX-hard and propose deterministic and probabilistic approximation algorithms for the budgeted and the matroid version of the problem, respectively. Experiments show that the proposed approaches outperform several baselines. [ABSTRACT FROM AUTHOR]

The maximum internal spanning tree (MIST) problem is to find a spanning tree with maximum number of internal node for an undirected graph. It is a variation of the well-known minimum spanning tree problem and is NP-hard. Evolutionary algorithms (EAs) have been successfully applied to solve many NP-hard combinatorial optimization problems in numerical empirical studies. However, researchers know little about their performance guarantees from theory aspect. This paper designs a valid fitness function to guide the well-studied evolutionary algorithm, (1 + 1) EA , to optimize the MIST problem, and presents theoretical analysis to show that it can obtain a performance guarantee of 2 and 5/3 in expected runtime O (n m 2) and O (n m 4) , respectively. Moreover, this paper proves that the (1+1) EA can achieve a performance guarantee of 3 for a variation of the MIST problem, where each vertex is associated with a weight. In addition, comparison analyses on two family instance graphs are presented to show that (1 + 1) EA is better than two local search algorithms. This theoretical study provides insight into the process of (1 + 1) EA constructing a performance guarantee solution for the MIST problem. [ABSTRACT FROM AUTHOR]

The Quantum Approximate Optimization Algorithm (QAOA) is an algorithmic framework for finding approximate solutions to combinatorial optimization problems. It consists of interleaved unitary transformations induced by two operators labelled the mixing and problem Hamiltonians. To fit this framework, one needs to transform the original problem into a suitable form and embed it into these two Hamiltonians. In this paper, for the well-known NP-hard Traveling Salesman Problem (TSP), we encode its constraints into the mixing Hamiltonian rather than the conventional approach of adding penalty terms to the problem Hamiltonian. Moreover, we map edges (routes) connecting each pair of cities to qubits, which decreases the search space significantly in comparison to other approaches. As a result, our method can achieve a higher probability for the shortest round-trip route with only half the number of qubits consumed compared to IBM Q's approach. We argue the formalization approach presented in this paper would lead to a generalized framework for finding, in the context of QAOA, high-quality approximate solutions to NP optimization problems. [ABSTRACT FROM AUTHOR]

This paper focuses on developing an appropriate combinatorial optimization technique for solving the optimal sizing problem of hybrid ac–dc microgrids. A novel two-stage iterative approach is proposed. In the first stage, a meta-heuristic technique based on a tailor-made genetic algorithm is used to tackle the optimal sizing problem, while, in the second, a non-linear solver is deployed to solve the operational problem subject to the obtained design/investment decisions. The proposed approach, being able to capture technical characteristics such as voltage and frequency through a detailed power flow algorithm, provides accurate solutions and, therefore, can address operational challenges of microgrids. Its capability to additionally capture contingencies ensures that the proposed sizing solutions are suitable both during normal operation and transient states. Finally, the genetic algorithm provides convergence of the model with relative computational simplicity. The proposed model is applied to a generalizable microgrid comprising of ac and dc generators and loads, as well as various types of storage technologies in order to demonstrate the benefits. The load and natural resources data correspond to real data. [ABSTRACT FROM AUTHOR]

Packing and covering semidefinite programs (SDPs) appear in natural relaxations of many combinatorial optimization problems as well as a number of other applications. Recently, several techniques were proposed, which utilize the particular structure of this class of problems, to obtain more efficient algorithms than those offered by general SDP solvers. For certain applications, such as those described in this paper, it may be desirable to obtain sparse dual solutions, i.e., those with support size (almost) independent of the number of primal constraints. In this paper, we give an algorithm that finds such solutions, which is an extension of a logarithmic-potential based algorithm of Grigoriadis et al. [SIAM J. Optim. 11 (2001), pp. 1081-1091] for packing/covering linear programs. [ABSTRACT FROM AUTHOR]

Accelerating product flow, improving service level, lowering logistics costs, reducing the possibility of product losses in circulation, and thus optimizing the logistics distribution system are the issues that enterprise managers should consider in logistics distribution. Traditional algorithms can only solve simple problems, while intelligent algorithms can solve the most complex combinatorial optimization problems. The optimization problem of logistics vehicle scheduling path with different constraints is studied in this paper using the SVM algorithm, and the improved algorithm is simulated to verify its effectiveness. The simulation results show that the logistics distribution path optimization method based on the SVM algorithm has good global searching ability, effectively avoids the algorithm falling into local optimum, and reduces total distribution cost, proving the algorithm's effectiveness. This scheme can optimize vehicle routes, increase distribution efficiency, and reduce logistics costs, and it can be used in a wide range of logistics distribution route optimization applications. [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]

This paper introduces a parallel implementation of an exact two-phase method for solving the bi-objective knapsack problem on a CPU-GPU system. We utilize the Branch-and-Bound procedure in both phases, along with a highly efficient reduction technique to generate all efficient solutions. However, in the first phase, we focus on identifying all supported extreme efficient solutions, followed by reducing the dimension of the problem using an object efficiency reduction algorithm. The second phase is responsible for generating all unsupported efficient solutions. We develop a combined algorithm incorporating both phases, which is implemented in the CUDA language. Our study investigates the impact of parallel computing performance on various numerical instances compared to other exact methods in the literature. Additionally, we confirm the effectiveness of our proposed parallel-solving method by testing uncorrelated instances. [ABSTRACT FROM AUTHOR]

We propose an efficient primal-dual interior-point relaxation algorithm based on a smoothing barrier augmented Lagrangian, called IPRSDP, for solving semidefinite programming problems in this paper. The IPRSDP algorithm has three advantages over classical interior-point methods. Firstly, IPRSDP does not require the iterative points to be positive definite. Consequently, it can easily be combined with the warm-start technique used for solving many combinatorial optimization problems, which require the solutions of a series of semidefinite programming problems. Secondly, the search direction of IPRSDP is symmetric in itself, and hence the symmetrization procedure is not required any more. Thirdly, with the introduction of the smoothing barrier augmented Lagrangian function, IPRSDP can provide the explicit form of the Schur complement matrix. This enables the complexity of forming this matrix in IPRSDP to be comparable to or lower than that of many existing search directions. The global convergence of IPRSDP is established under suitable assumptions. Numerical experiments are made on the SDPLIB set, which demonstrate the efficiency of IPRSDP. [ABSTRACT FROM AUTHOR]

Recently, graph neural network (GNN)-based algorithms were proposed to solve a variety of combinatorial optimization problems [M. J. Schuetz, J. K. Brubaker, H. G. Katzgraber, Nat. Mach. Intell. 4, 367-377 (2022)].GNNwas tested in particular on randomly generated instances of these problems. The publication [M. J. Schuetz, J. K. Brubaker, H. G. Katzgraber, Nat. Mach. Intell. 4, 367-377 (2022)] stirred a debate whether the GNN-based method was adequately benchmarked against best prior methods. In particular, critical commentaries [M. C. Angelini, F. Ricci-Tersenghi, Nat. Mach. Intell. 5, 29-31 (2023)] and [S. Boettcher, Nat. Mach. Intell. 5, 24-25 (2023)] point out that a simple greedy algorithm performs better than the GNN. We do not intend to discuss the merits of arguments and counterarguments in these papers. Rather, in this note, we establish a fundamental limitation for running GNN on random instances considered in these references, for a broad range of choices of GNN architecture. Specifically, these barriers hold when the depth of GNN does not scale with graph size (we note that depth 2 was used in experiments in [M. J. Schuetz, J. K. Brubaker, H. G. Katzgraber, Nat. Mach. Intell. 4, 367-377 (2022)]), and importantly, these barriers hold regardless of any other parameters of GNN architecture. These limitations arise from the presence of the overlap gap property (OGP) phase transition, which is a barrier for many algorithms, including importantly local algorithms, of which GNN is an example. At the same time, some algorithms known prior to the introduction of GNN provide best results for these problems up to the OGP phase transition. This leaves very little space for GNN to outperform the known algorithms, and based on this, we side with the conclusions made in [M. C. Angelini, F. Ricci-Tersenghi, Nat. Mach. Intell. 5, 29-31 (2023)] and [S. Boettcher, Nat. Mach. Intell. 5, 24-25 (2023)]. [ABSTRACT FROM AUTHOR]

Over the last decade, there has been a rapid growth of the use of genetic algorithms in the various areas of production and operations management. This paper provides a review of genetic algorithms research published in twenty-one major production and operations management journals from 1990–2001. More specifically, it identifies research trends and publication outlets of genetic algorithms applications. Our findings show that there are only a handful of production and operations management areas to which genetic algorithms have been applied as the solution approach. Furthermore, we recognize and discuss potential research areas and outlets in which researchers may target their work as well as the need for top ranked POM journals to consider publishing genetic algorithms related papers. [ABSTRACT FROM AUTHOR]

As a meta-heuristic algorithm, the ant colony algorithm has been successfully used to solve various combinatorial optimization problems. However, the existing algorithm that takes the power of ants to solve distributed constraint optimization problems (ACO_DCOP) is easy to fall into local optima. To deal with this issue, this paper presents an adaptive ant colony algorithm based on local information entropy to solve distributed constraint optimization problems, named LIEAD. In LIEAD, the local information entropy is introduced to help agents adaptively select the pheromone update strategy and value selection strategy, which improves the convergence speed and the quality of the solution. Moreover, a restart mechanism is designed to break the accumulation state of pheromone, which increases the population diversity and helps the algorithm jump out of the local optima. The extensive experimental results indicate that LIEAD can significantly outperform ACO_DCOP and is competitive with the state-of-the-art DCOPs algorithms. [ABSTRACT FROM AUTHOR]

In the scenario of device-free localization under multiple effects, the accuracy of localization based on compressed sensing theory is severely affected. Most existing localization techniques directly ignore multiple path effects. However, it is not practical to ignore the multiple path effect due to its high signal strength, which can provide localization information. In this paper, we formulate the sensing matrix optimization problem in compressed sensing for device-free localization scenarios based on multiple reflections. To solve this problem, we model it as a constrained combinatorial optimization problem and propose a hybrid meta-heuristic algorithm. First, smart reflection surfaces and virtual node models are used to construct the desired communication links. Second, we iteratively improve the properties of the measurement matrix by using K-means clustering to obtain reasonable thresholds, and use a meta-heuristic algorithm to optimize the sensing matrix. Finally, the simulation results show that the proposed method efficiently optimizes the sensing matrix and achieves fast and high-precision localization while conserving communication resources. [ABSTRACT FROM AUTHOR]

A hybrid algorithm combines two or more individual algorithms in order to integrate the advantages of these individual algorithms. In recent years, a huge number of hybrid algorithms have been proposed, and their efficiencies have been demonstrated by experimental studies. However, few theoretical results that support the experimental conclusions are available. In this paper, we focus on theoretical investigation about the efficiency of hybrid algorithms for combinatorial optimization problems. We first analyze the runtime of three specific hybrid algorithms and their component algorithms on two instances. One is a well-known pseudo-Boolean function, and the other is an instance of a classical combinatorial optimization problem. We then theoretically investigate the relationship between the upper bounds of the expected runtime of three kinds of general hybrid algorithms and their component algorithms. [ABSTRACT FROM AUTHOR]

Combinatorial metaheuristic optimization algorithms have newly become a remarkable domain for handling real-world and engineering design optimization problems. In this paper, the Whale Optimization Algorithm (WOA) and the Woodpecker Mating Algorithm (WMA) are combined as HWMWOA. WOA is an effective algorithm with the advantage of global searching ability, where the control parameters are very less. But WOA is more probable to get trapped in the local optimum points and miss diversity of population, therefore suffering from premature convergence. The fundamental goal of the HWMWOA algorithm is to overcome the drawbacks of WOA. This betterment includes three basic mechanisms. First, a modified position update equation of WMA by efficient exploration ability is embedded into HWMWOA. Second, a new self-regulation Cauchy mutation operator is allocated to the proposed hybrid method. Finally, an arithmetic spiral movement with a novel search guide pattern is used in the suggested HWMWOA algorithm. The efficiency of the suggested algorithm is appraised over 48 test functions, and the optimal outcomes are compared with 15 most popular and newest metaheuristic optimization algorithms. Moreover, the HWMWOA algorithm is applied for simultaneously optimizing the parameters of SVM (Support Vector Machine) and feature weighting to handle the data classification problem on several real-world datasets from the UCI database. The outcomes prove the superiority of the suggested hybrid algorithm compared to both WOA and WMA. In addition, the results represent that the HWMWOA algorithm outperforms other efficient techniques impressively. [ABSTRACT FROM AUTHOR]

The knapsack problem (KP) is a discrete combinatorial optimization problem that has different utilities in many fields. It is described as a non-polynomial time (NP) problem and has several applications in many fields. The differential evolution (DE) algorithm has been successful in solving continuous optimization problems, but it needs further work to solve discrete and binary optimization problems and avoid local optima. According to the literature, no DE search operator or algorithm is optimal for all optimization tasks. As a result, using more than one search operator in a single algorithm architecture, called multi-operator-based algorithms, is a solution to address this problem. These methods outperformed single-based methods for continuous optimization problems. Thus, in this paper, a binary multi-operator differential evolution (BMODE) approach is presented to tackle the 0–1 KP. The presented methodology utilizes multiple differential evolution (DE) mutation strategies with complementary characteristics, with the best mutation operator being asserted utilizing the produced solutions' quality and the population's diversity. In BMODE, two types of transfer functions (TFs) (S-shaped and V-shaped) are used to transfer the continuous solutions to binary ones to be able to calculate the fitness function value. To handle the capacity constraints, a feasibility rule is utilized and some of the infeasible solutions are repaired. The performance of BMODE is tested by solving 40 instances with multiple dimensions, i.e., low, medium, and high. Experimental results of the proposed BMODE are compared with well-known state-of-the-art 0–1 knapsack algorithms. Based on Wilcoxon's nonparametric statistical test ( α = 0.05 ), the proposed BMODE can obtain the best results against the rival algorithms in most cases, and can work well on stability and computational accuracy. [ABSTRACT FROM AUTHOR]

In recent years, metaheuristic methods have shown remarkable efficacy in resolving complex combinatorial challenges across a broad spectrum of fields. Nevertheless, the escalating complexity of these problems necessitates the continuous development of innovative techniques to enhance the performance and reliability of these methods. This paper aims to contribute to this endeavor by examining the impact of solution initialization methods on the performance of a hybrid algorithm applied to the set union knapsack problem (SUKP). Three distinct solution initialization methods, random, greedy, and weighted, have been proposed and evaluated. These have been integrated within a sine cosine algorithm employing k-means as a binarization procedure. Through testing on medium- and large-sized SUKP instances, the study reveals that the solution initialization strategy influences the algorithm's performance, with the weighted method consistently outperforming the other two. Additionally, the obtained results were benchmarked against various metaheuristics that have previously solved SUKP, showing favorable performance in this comparison. [ABSTRACT FROM AUTHOR]

The discounted {0-1} knapsack problem (DKP) is an NP-hard problem that is more challenging than the classical knapsack problem. In this paper, an enhanced version of the sine-cosine algorithm (SCA) called TMHSCA is proposed to solve the DKP. The SCA is a novel metaheuristic algorithm based on sine-cosine theory. Three effective improvements are proposed for the SCA to enhance the convergence speed and exploitation capability of the algorithm. First, by dividing the initial population into three subpopulations using random, greedy and opposition-based learning (OBL) strategies, the diversity of the population can be effectively enhanced. Furthermore, a forward-inverse sine-cosine search that expands the search space by utilizing the worst solution as another target is proposed. The proposed forward-inverse sine-cosine search strategy facilitates the algorithm to explore the easily ignored solution space. The last improvement includes the use of an OBL mutation and the mutation operator of differential evolution at a two-stage mutation, which increases the algorithm's convergence speed and fitness. In our proposed two-stage mutation, the number of mutations can be adaptively adjusted based on the optimization capabilities of the optimal individual. Additionally, a reshuffling repair strategy for repairing infeasible solutions by sorting items into groups to obtain the weight-to-value ratio is proposed. Extensive experiments are conducted on 40 publicly available datasets and are compared to the greedy algorithm, 3 SCAs and 8 competitive baseline methods. The experimental results demonstrate that our method achieves a state-of-the-art performance. [ABSTRACT FROM AUTHOR]