Search

Bin packing problem (BPP) is one of the fastest-growing research issues within the field of combinatorial optimization. Over the last years, several studies carried out various BPP variants, mathematical models, and proposed methods to the BPPs. The classical BPP consists of packing a set of rectangular items in a minimum number of rectangular bins while respecting some constraints.Throughout the years, an improved typology was introduced by Wäscher et al. (2007), providing an excellent instrument for the organization and categorization criteria that defined the problem categories different from those of Dyckhoff (1990). Several early literature reviews have been conducted on various aspects of related packing problem variants.The contribution of this paper is to provide a comprehensive and refined taxonomy intended for BPPs. In addition to that, it is an up-to-date review based on a chronological taxonomy of the literature and depicts further research horizons.This systematic review allowed us to identify other characteristics and constraints, based on Wäscher's original ideas, mainly distinguished according to real cases studies. The detailed analysis provides a valuable framework for understanding the research gaps for future studies that should be acknowledged while proposing and solving new extensions. Note: The addresses of second and third authors have been corrected online. [ABSTRACT FROM AUTHOR]

Hyper-heuristics have arisen as methods that increase the generality of existing solvers. They have proven helpful for dealing with complex problems, particularly those related to combinatorial optimization. Their recent growth in popularity has increased the daily amount of text in the related literature. This information is primarily unstructured, mainly text that traditional computer data systems cannot process. Traditional systematic literature review studies exhibit multiple limitations, including high time consumption, lack of replicability, and subjectivity of the results. For this reason, text mining has become essential for researchers in recent years. Therefore, efficient text mining techniques are needed to extract meaningful information, patterns, and relationships. This study adopts a literature review of 963 journal and conference papers on hyper-heuristic-related works. We first describe the essential text mining techniques, including text preprocessing, word clouds, clustering, and frequent association rule learning in hyper-heuristic publications. With that information, we implement visualization tools to understand the most frequent relations and topics in the hyper-heuristic domain. The main findings highlight the most dominant topics in the literature. We use text mining analysis to find widespread manifestations, representing the significance of the different areas of hyper-heuristics. Furthermore, we apply clustering to provide seven categories showing the associations between the topics related to hyper-heuristic literature. The vast amount of data available that we find opens up a new opportunity for researchers to analyze the status of hyper-heuristics and help create strategic plans regarding the scope of hyper-heuristics. Lastly, we remark that future work will address the limitations of collecting information from multiple data sources and analyze book chapters related to hyper-heuristics. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Shanghai Jiaotong University (Science) is the property of Springer Nature and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

This paper combines the digital twin system modeling method to conduct an in-depth study and analysis of graph-theoretic combinatorial optimization. This paper provides new ideas and approaches for optimal numerical analysis work by studying the digital twin modeling method that integrates digital modeling and graph theory combination, provides theoretical support for safe, stable, and economic operation of the system, proposes a solution for digital twin model based on big data platform, focuses on the nearest neighbor propagation (AP) and graph theory combination, solves the digital twin real-time monitoring data asynchronous, incomplete problem, and applies the algorithm to the digital twin model based on the big data platform for data preprocessing to achieve better results. This paper also presents a web-based digital twin system based on intelligent practical needs, analysis, and comparison of existing models, combined with digital twin technology, detailing the differences and connections between the various levels of numerical analysis and the implementation of this data in various fields, such as user management, equipment health management, product quality management, and workshop 3D navigation and detailed modeling of the digital twin system based on this numerical analysis to realize remote online monitoring, analysis, and management. In this paper, for the numerical analysis process, firstly, the key technologies of modeling and simulation operation control of production line based on digital twin are studied, and the rapid response manufacturing system based on a digital twin is designed and validated. Secondly, a scheduling technology framework for capacity simulation evaluation and optimization is established, and batching optimization, outsourcing decision, and rolling scheduling techniques are thus proposed to form a batching optimization algorithm based on priority rules, which realizes batching processing, outsourcing decision, and rolling scheduling of production orders to optimize equipment utilization and capacity. Finally, digital twin-based modeling is designed, and the validation results demonstrate the system's superior performance in achieving information interaction between physical and virtual production lines, optimization of numerical analysis, and display of results. [ABSTRACT FROM AUTHOR]

In recent years, sensor technology has been widely used in the defense and control of sensitive areas in cities, or in various scenarios such as early warning of forest fires, monitoring of forest pests and diseases, and protection of endangered animals. Deploying sensors to collect data and then utilizing unmanned aerial vehicle (UAV) to collect the data stored in the sensors has replaced traditional manual data collection as the dominant method. The current strategies for efficient data collection in above scenarios are still imperfect, and the low quality of the collected data and the excessive energy consumed by UAV flights are still the main problems faced in data collection. With regards this, this paper proposes a multi-UAV mission planning method for self-organized sensor data acquisition by comprehensively utilizing the techniques of self-organized sensor clustering, multi-UAV mission area allocation, and sub-area data acquisition scheme optimization. The improved α-hop clustering method utilizes the average transmission distance to reduce the size of the collection sensors, and the K-Dimensional method is used to form a multi-UAV cooperative workspace, and then, the genetic algorithm is used to trade-off the speed with the age of information (AoI) of the collected information and the energy consumption to form the multi-UAV data collection operation scheme. The combined optimization scheme in paper improves the performance by 95.56% and 58.21%, respectively, compared to the traditional baseline model. In order to verify the excellent generalization and applicability of the proposed method in real scenarios, the simulation test is conducted by introducing the digital elevation model data of the real terrain, and the results show that the relative error values of the proposed method and the performance test of the actual flight of the UAV are within the error interval of ±10%. Then, the advantages and disadvantages of the present method with the existing mainstream schemes are tested, and the results show that the present method has a huge advantage in terms of space and time complexity, and at the same time, the accuracy for data extraction is relatively improved by 10.46% and 12.71%. Finally, by eliminating the clustering process and the subtask assignment process, the AoI performance decreases by 3.46× and 4.45×, and the energy performance decreases by 3.52× and 4.47×. This paper presents a comprehensive and detailed proactive optimization of the existing challenges faced in the field of data acquisition by means of a series of combinatorial optimizations. [ABSTRACT FROM AUTHOR]

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

The split delivery vehicle routing problem (SDVRP) is a classic combinatorial optimization problem, which is usually solved using a heuristic algorithm. The ant colony optimization algorithm is an excellent heuristic algorithm that has been successfully applied to solve various practical problems, and it has achieved good results. However, in the existing ant colony optimization algorithms, there are issues with weak targeting of different customer selection strategies, difficulty in balancing convergence speed and global search ability, and a predisposition to become trapped in local optima. To solve these problems, this paper proposes an improved ant colony algorithm (IACA). First, in terms of customer point selection, the initial customer and noninitial customer selection strategies are proposed for different customers, and the adaptive selection threshold is designed. Second, in terms of pheromone processing, an initial pheromone distribution method based on a greedy strategy, a pheromone backtracking mechanism, and an adaptive pheromone volatile factor are proposed. Finally, based on the 2-opt local search method, vehicle path self-search and intervehicle path search are proposed to further improve the quality of the solution. This paper tests the performance of the IACA on datasets of different scales. The experimental results show that compared with the clustering algorithm, artificial bee colony algorithm, particle swarm optimization algorithm, traditional ant colony algorithm, and other algorithms, the IACA can achieve more competitive results. Specifically, compared to the path length calculated by other algorithms, the path length calculated by IACA decreased by an average of 1.58%, 4.28%, and 3.64% in small, medium, and large-scale tests, respectively. [ABSTRACT FROM AUTHOR]

Dynamic task scheduling problem in cloud manufacturing (CMfg) is always challenging because of changing manufacturing requirements and services. To make instant decisions for task requirements, deep reinforcement learning-based (DRL-based) methods have been broadly applied to learn the scheduling policies of service providers. However, the current DRL-based scheduling methods struggle to fine-tune a pre-trained policy effectively. The resulting training from scratch takes more time and may easily overfit the environment. Additionally, most DRL-based methods with uneven action distribution and inefficient output masks largely reduce the training efficiency, thus degrading the solution quality. To this end, this paper proposes an improved DRL-based approach for dynamic task scheduling in CMfg. First, the paper uncovers the causes behind the inadequate fine-tuning ability and low training efficiency observed in existing DRL-based scheduling methods. Subsequently, a novel approach is proposed to address these issues by updating the scheduling policy while considering the distribution distance between the pre-training dataset and the in-training policy. Uncertainty weights are introduced to the loss function, and the output mask is extended to the updating procedures. Numerical experiments on thirty actual scheduling instances validate that the solution quality and generalization of the proposed approach surpass other DRL-based methods at most by 32.8% and 28.6%, respectively. Additionally, our method can effectively fine-tune a pre-trained scheduling policy, resulting in an average reward increase of up to 23.8%. [ABSTRACT FROM AUTHOR]

Based on the project portfolio selection and scheduling problem (PPSS), the development of a systematic and scientific project scheduling plan necessitates comprehensive consideration of individual preferences and multiple realistic constraints, rendering it an NP-hard problem. Simultaneously, accurately and swiftly evaluating the value of projects as a complex entity poses a challenging issue that requires urgent attention. This paper introduces a novel qualitative evaluation-based project value assessment process that significantly reduces the cost and complexity of project value assessment, upon which a preference-based deep reinforcement learning method is presented for computing and solving project subsets and time scheduling plans. This paper first determines the key parameter values of the algorithm through specific examples. Then, using the method of controlling variables, it explores the sensitivity of the algorithm to changes in problem size and dimensionality. Finally, the proposed algorithm is compared with two classical algorithms and two heuristic algorithms across different instances. The experimental results demonstrate that the proposed algorithm exhibits higher effectiveness and accuracy. [ABSTRACT FROM AUTHOR]

Let D = (V , A) be a digraph. For an integer k ≥ 1 , a k-arc-connected flip is an arc subset of D such that after reversing the arcs in it the digraph becomes (strongly) k-arc-connected. The first main result of this paper introduces a sufficient condition for the existence of a k-arc-connected flip that is also a submodular flow for a crossing submodular function. More specifically, given some integer τ ≥ 1 , suppose d A + (U) + (τ k - 1) d A - (U) ≥ τ for all U ⊊ V , U ≠ ∅ , where d A + (U) and d A - (U) denote the number of arcs in A leaving and entering U, respectively. Let C be a crossing family over ground set V, and let f : C → Z be a crossing submodular function such that f (U) ≥ k τ (d A + (U) - d A - (U)) for all U ∈ C . Then D has a k-arc-connected flip J such that f (U) ≥ d J + (U) - d J - (U) for all U ∈ C . The result has several applications to Graph Orientations and Combinatorial Optimization. In particular, it strengthens Nash-Williams' so-called weak orientation theorem, and proves a weaker variant of Woodall's conjecture on digraphs whose underlying undirected graph is τ -edge-connected. The second main result of this paper is even more general. It introduces a sufficient condition for the existence of capacitated integral solutions to the intersection of two submodular flow systems. This sufficient condition implies the classic result of Edmonds and Giles on the box-total dual integrality of a submodular flow system. It also has the consequence that in a weakly connected digraph, the intersection of two submodular flow systems is totally dual integral. [ABSTRACT FROM AUTHOR]

This paper proposes a proximal policy optimization (PPO) algorithm for coupling matrix synthesis of microwave filters. With the improvement of filter design requirement, the limitations of traditional methods such as limited applicability are becoming more and more obvious. In order to improve the filter synthesis efficiency, this paper constructs a reinforcement learning algorithm based on Actor-Critic network architecture, and designs a unique filter coupling matrix synthesis reward function and action function, which can solve combinatorial optimization problems stably. [ABSTRACT FROM AUTHOR]

Job shop scheduling problem (JSP) is a widely studied NP-complete combinatorial optimisation problem. Neighbourhood structures play a critical role in solving JSP. At present, there are three state-of-the-art neighbourhood structures, i.e. N5, N6, and N7. Improving the upper bounds of some famous benchmarks is inseparable from the role of these neighbourhood structures. However, these existing neighbourhood structures only consider the movement of critical operations within a critical block. According to our experiments, it is also possible to improve the makespan of a scheduling scheme by moving a critical operation outside its critical block. According to the above finding, this paper proposes a new N8 neighbourhood structure considering the movement of critical operations within a critical block and the movement of critical operations outside the critical block. Besides, a neighbourhood clipping method is designed to avoid invalid movement, discarding non-improving moves. Tabu search (TS) is a commonly used algorithm framework combined with neighbourhood structures. This paper uses this framework to compare the N8 neighbourhood structure with N5, N6, and N7 neighbourhood structures on four famous benchmarks. The experimental results verify that the N8 neighbourhood structure is more effective and efficient in solving JSP than the other state-of-the-art neighbourhood structures. [ABSTRACT FROM AUTHOR]

Cooperative multi-agent systems make it possible to employ miniature robots in order to perform different experiments for data collection in wide open areas to physical interactions with test subjects in confined environments such as a hive. This paper proposes a new multi-agent path-planning approach to determine a set of trajectories where the agents do not collide with each other or any obstacle. The proposed algorithm leverages a risk-aware probabilistic roadmap algorithm to generate a map, employs node classification to delineate exploration regions, and incorporates a customized genetic framework to address the combinatorial optimization, with the ultimate goal of computing safe trajectories for the team. Furthermore, the proposed planning algorithm makes the agents explore all subdomains in the workspace together as a formation to allow the team to perform different tasks or collect multiple datasets for reliable localization or hazard detection. The objective function for minimization includes two major parts, the traveling distance of all the agents in the entire mission and the probability of collisions between the agents or agents with obstacles. A sampling method is used to determine the objective function considering the agents' dynamic behavior influenced by environmental disturbances and uncertainties. The algorithm's performance is evaluated for different group sizes by using a simulation environment, and two different benchmark scenarios are introduced to compare the exploration behavior. The proposed optimization method establishes stable and convergent properties regardless of the group size. [ABSTRACT FROM AUTHOR]

The Vehicle Routing Problem (VRP) is a classic combinatorial optimization problem commonly encountered in the fields of transportation and logistics. This paper focuses on a variant of the VRP, namely the Vehicle Routing Problem with Stochastic Travel Cost (VRP-STC). In VRP-STC, the introduction of stochastic travel costs increases the complexity of the problem, rendering traditional algorithms unsuitable for solving it. In this paper, the GAT-AM model combining Graph Attention Networks (GAT) and multi-head Attention Mechanism (AM) is employed. The GAT-AM model uses an encoder–decoder architecture and employs a deep reinforcement learning algorithm. The GAT in the encoder learns feature representations of nodes in different subspaces, while the decoder uses multi-head AM to construct policies through both greedy and sampling decoding methods. This increases solution diversity, thereby finding high-quality solutions. The REINFORCE with Rollout Baseline algorithm is used to train the learnable parameters within the neural network. Test results show that the advantages of GAT-AM become greater as problem complexity increases, with the optimal solution generally unattainable through traditional algorithms within an acceptable timeframe. [ABSTRACT FROM AUTHOR]

As potent approaches for addressing computationally expensive optimization problems, surrogate-assisted evolutionary algorithms (SAEAs) have garnered increasing attention. Prevailing endeavors in evolutionary computation predominantly concentrate on expensive continuous optimization problems, with a notable scarcity of investigations directed toward expensive combinatorial optimization problems (ECOPs). Nevertheless, numerous ECOPs persist in practical applications. The widespread prevalence of such problems starkly contrasts the limited development of relevant research. Motivated by this disparity, this paper conducts a comprehensive survey on SAEAs tailored to address ECOPs. This survey comprises two primary segments. The first segment synthesizes prevalent global, local, hybrid, and learning search strategies, elucidating their respective strengths and weaknesses. Subsequently, the second segment furnishes an overview of surrogate-based evaluation technologies, delving into three pivotal facets: model selection, construction, and management. The paper also discusses several potential future directions for SAEAs with a focus towards expensive combinatorial optimization. [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 flexible job-shop scheduling problem (FJSP) with parallel batch processing machine (PBM) is one of those long-standing issues that needs cutting-edge approaches. It is a recent extension of standard flexible job shop scheduling problems. Despite their wide application and prevalence in practical production, it seems that current research on these types of combinatorial optimization problems remains limited and uninvestigated. More specifically, existing research mainly concentrates on the flow shop scenarios in parallel batch machines for job shop scheduling but few literature emphasis on the flexible job shop integration in these contexts. To directly address the above mentioned problems, this paper establishes an optimization model considering parallel batch processing machines, aiming to minimize the maximum completion time in operating and production environments. The proposed solution merges variable neighborhood search with multi-population genetic algorithms, conducting a neighborhood search on the elite population to reduce the likelihood of falling into local optima. Subsequently, its applicability was evaluated in computational experiments using real production scenarios from a partnering enterprise and extended datasets. The findings from the analyses indicate that the enhanced algorithm can decrease the objective value by as much as 15% compared to other standard algorithms. Importantly, the proposed approach effectively resolves flexible job shop scheduling problems involving parallel batch processing machines. The contribution of the research is providing substantial theoretical support for enterprise production scheduling. [ABSTRACT FROM AUTHOR]

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

Replacing traditional manual sweeping with unmanned sweepers in closed parks can not only greatly reduce labor costs, but also improve sweeping efficiency. Efficient path planning is the key technology for unmanned sweepers to complete the sweeping task. Existing unmanned sweepers are often based on fixed path sweeping or completely traversing the sweeping mode, this mode does not have the environmental adaptability, in the actual sweeping is often high energy cost, and sweeping is not complete. In this paper, an environment-adaptive sweeping path planning method is proposed to improve the sweeping intelligence and environmental adaptability of unmanned sweepers, reduce the energy consumption of sweeping and improve the efficiency of sweeping. Specifically, in this paper, we first use YOLOv5 to complete the accurate identification of individual garbage and obstacles in the road, and then work with LIDAR and Gaussian Mixture Model(GMM) to remove redundant targets. We also propose a Permutation Entropy(PE) value-based discrimination method to complete the target distribution posture analysis of each complex garbage pile. Finally, the traditional path planning problem is transformed into a combinatorial optimization problem of garbage areas, and a sweeping path accurate method based on Simulated Annealing(SA) algorithm is proposed. Through comprehensive theoretical analysis and simulation study, the optimality and effectiveness of the proposed method are proved by comparing A star and Coverage Path Planning(CPP) algorithms in a variety of experimental scenarios. [ABSTRACT FROM AUTHOR]

Simultaneous allocation of service times and buffer capacities in manufacturing systems in a random environment is a NP-hard combinatorial optimisation problem. This paper presents a sophisticated simulation-based optimisation approach for the design of unreliable production lines to maximise the production rate. The proposed method allows for a global search using a Genetic Algorithm (GA), which is coupled with Finite Perturbation Analysis (FPA) as a local search technique. Traditional techniques based on perturbation analysis optimise decision variables of the same nature (e.g. service time only, buffer capacity only), whereas the proposed technique simultaneously provides an allocation of service times and buffer capacities. One of the main focuses of this paper is the investigation of the persistence or absence of the buffer and service rate allocation patterns which are among the most essential insights that come from designing production lines. The results show the superiority of the combined GA-FPA approach regarding GA and FPA in terms of solution quality and convergence behaviour. Moreover, considering instances ranging from 3 to 100 machines, our numerical experiments are in line with the literature for small instances (as similar allocation patterns are identified in our work), but important differences are highlighted for medium/large instances. [ABSTRACT FROM AUTHOR]

Cutting and packing problems are hard combinatorial optimization problems that arise in several manufacturing and process industries or in their supply chains. The solution of these problems is not only a scientific challenge but also has a large economic impact, as it contributes to the reduction of one of the major cost factors for many production sectors, namely raw materials, together with a positive environmental impact. The explicit consideration of uncertainty when solving cutting and packing problems with optimization techniques is crucial for a wider adoption of research results by companies. However, current research has paid little attention to the role of uncertainty in these problems. In this paper, we review the existing literature on uncertainty in cutting and packing problems, propose a classification framework, and highlight the many research gaps and opportunities for scientific contributions. [ABSTRACT FROM AUTHOR]

The gradient descent is one of the most common methods to modify the gradient parameters of the neural network, however, it may fall into the local optimum in the training process. As we all know, genetic algorithm can find the global optimal solution through global search, but it may not be efficient, always takes a lot of running time. These two methods are complementary in the running time and the cost, which inspired us to consider the combination of gradient descent and genetic algorithm. In this paper, a multi-start combinatorial optimization method based on the genetic algorithm and the gradient descent is proposed. First, the initial point is selected through the genetic algorithm. Then the combination of multi-start and gradient descent is used, which can quickly achieve the global search and improve the performance with relatively less running time and cost. Compared with the traditional genetic algorithm and gradient descent method, this proposed algorithm has a better performance in computing the global optimum efficiently. [ABSTRACT FROM AUTHOR]

This paper introduces the Cyclic Production Routing Problem (CPRP). The CPRP is an extension of the well-known NP-hard Production Routing Problem (PRP), which is a hard-to-solve combinatorial optimisation problem with numerous practical applications in the field of freight transportation, logistics and supply chain management. Under the PRP setting, a manufacturer is responsible for determining production decisions, as well as the timing and quantity of replenishment services offered to a set of geographically dispersed customers over a multi-period time horizon. The problem calls for jointly optimising the production, inventory, distribution and routing decisions. In this paper, the basic PRP model is modified to generate repeatable cyclic production and delivery schedules. A two-commodity flow formulation is proposed along with valid inequalities. Extensive comparisons between the basic PRP and the proposed cyclic variant on well-known benchmark instances are provided. The new variant is significantly harder to solve, especially when the vehicle fleet is limited. From a managerial perspective, the generation of cyclic production-routing schedules significantly increases all costs, whereas the number of vehicle routes required to implement a cyclic schedule is higher. [ABSTRACT FROM AUTHOR]

When a system of one-sided max-plus linear equations is inconsistent, the approximate solutions within an admissible error bound may be desired instead, particularly with some sparsity property. It is demonstrated in this paper that obtaining the sparsest approximate solution within a given L8 error bound may be transformed in polynomial time into the set covering problem, which is known to be NP-hard. Besides, the problem of obtaining the sparsest approximate solution within a given L1 error bound may be reformulated as a polynomial-sized mixed integer linear programming problem, which may be regarded as a special scenario of the facility location-allocation problem. By this reformulation approach, this paper reveals some interesting connections between the sparsest approximate solution problems in max-plus algebra and some well known problems in discrete and combinatorial optimization. [ABSTRACT FROM AUTHOR]

The study presents theHalfMax InsertionHeuristic (HMIH) as a novel approach to solving the Travelling Salesman Problem (TSP). The goal is to outperform existing techniques such as the Farthest Insertion Heuristic (FIH) and Nearest Neighbour Heuristic (NNH). The paper discusses the limitations of current construction tour heuristics, focusing particularly on the significant margin of error in FIH. It then proposes HMIH as an alternative that minimizes the increase in tour distance and includes more nodes. HMIH improves tour quality by starting with an initial tour consisting of a 'minimum' polygon and iteratively adding nodes using our novel Half Max routine. The paper thoroughly examines and compares HMIH with FIH and NNH via rigorous testing on standard TSP benchmarks. The results indicate that HMIH consistently delivers superior performance, particularly with respect to tour cost and computational efficiency. HMIH's tours were sometimes 16% shorter than those generated by FIH and NNH, showcasing its potential and value as a novel benchmark for TSP solutions. The study used statistical methods, including Friedman's Non-parametric Test, to validate the performance of HMIH over FIH and NNH. This guarantees that the identified advantages are statistically significant and consistent in various situations. This comprehensive analysis emphasizes the reliability and efficiency of the heuristic, making a compelling case for its use in solving TSP issues. The research shows that, in general, HMIH fared better than FIH in all cases studied, except for a few instances (pr439, eil51, and eil101) where FIH either performed equally or slightly better than HMIH. HMIH's efficiency is shown by its improvements in error percentage (d) and goodness values (g) compared to FIH and NNH. In the att48 instance, HMIH had an error rate of 6.3%, whereas FIH had 14.6% and NNH had 20.9%, indicating that HMIH was closer to the optimal solution. HMIH consistently showed superior performance across many benchmarks, with lower percentage error and higher goodness values, suggesting a closer match to the optimal tour costs. This study substantially contributes to combinatorial optimization by enhancing current insertion algorithms and presenting a more efficient solution for the Travelling Salesman Problem. It also creates new possibilities for progress in heuristic design and optimization methodologies. [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]

Scheduling is an important technique being used widely in numerous applications especially in industry. Flexible Job Shop Scheduling Problem (FJSP) is an extension of job scheduling which has several practical applications, (FJSP) is NPhard combinatorial optimization problem. Owing to its importance and intricacy a lot of attention has been paid to this topic. Many swarm intelligent algorithms have drawn inspiration from nature; one particularly notable example is Ant Colony Optimization (ACO), which has shown to be incredibly successful and productive when applied to highcomplexity (NP-hard) combinatorial optimization tasks. The paper presents a literature survey on ACO variants types and applications in Scheduling. [ABSTRACT FROM AUTHOR]