Search

One of the main issues in a paper mill is the minimization of trim loss when cutting master reels and stocked reels into reels of smaller required widths. The losses produced in trimming at a paper mill are reprocessed by using different chemicals which contributes to significant discharge of effluent to surface water and causes environmental damage. This paper presents a real-world industrial problem of production planning and cutting optimization of reels at a paper mill and differs from other cutting stock problems by considering production and cutting of master reels of flexible widths and cutting already stocked over-produced and useable leftover reels of smaller widths. The cutting process of reels is performed with a limited number of cutting knives at the winder. The problem is formulated as a linear programming model where the generation of all feasible cutting patterns determines the columns of the constraint matrix. The model is solved optimally using simplex algorithm with the objective of trim loss minimization while satisfying a set of constraints. The solution obtained is rounded in a post-optimization procedure in order to satisfy integer constraints. When tested on data from the paper mill, the results of the proposed model showed a significant reduction in trim loss and outperformed traditional exact approaches. The cutting optimization resulted in minimum losses in paper trimming and a lesser amount of paper is reprocessed to make new reels which reduced the discharge of effluent to the environment. [ABSTRACT FROM AUTHOR]

One of the main issues in a paper mill is the minimization of trim loss when cutting master reels and stocked reels into reels of smaller required widths. The losses produced in trimming at a paper mill are reprocessed by using different chemicals which contributes to significant discharge of effluent to surface water and causes environmental damage. This paper presents a real-world industrial problem of production planning and cutting optimization of reels at a paper mill and differs from other cutting stock problems by considering production and cutting of master reels of flexible widths and cutting already stocked over-produced and useable leftover reels of smaller widths. The cutting process of reels is performed with a limited number of cutting knives at the winder. The problem is formulated as a linear programming model where the generation of all feasible cutting patterns determines the columns of the constraint matrix. The model is solved optimally using simplex algorithm with the objective of trim loss minimization while satisfying a set of constraints. The solution obtained is rounded in a post-optimization procedure in order to satisfy integer constraints. When tested on data from the paper mill, the results of the proposed model showed a significant reduction in trim loss and outperformed traditional exact approaches. The cutting optimization resulted in minimum losses in paper trimming and a lesser amount of paper is reprocessed to make new reels which reduced the discharge of effluent to the environment.

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]

Abstract: The conversion of ethanol from paper sludge using the separate hydrolysis and fermentation (SHF) process with cellulase and Saccharomyces cerevisiae GIM-2 were investigated in this paper. Optimization strategy based on statistical experimental designs was employed to enhance degree of saccharification by enzymatic hydrolysis of paper sludge. Based on the Plackett–Burman design, hydrolysis time, substrate concentration and cellulase dosage were selected as the most significant variable on the degree of saccharification. Subsequently, the optimum combination of the selected factors was investigated by a Box-Behnken approach. A mathematical model was developed to show the effects of each factor and their combinatorial interactions on the degree of saccharification. The optimal conditions were hydrolysis time 82.7 h, substrate concentration 40.8 g L−1 and cellulase dosage 18.1 FPU g−1 substrate, and a degree of saccharification of 82.1% can be achieved. When hydrolysate was further fermented with S. cerevisiae GIM-2, the conversion rate of sugar to ethanol was 34.2% and the ethanol yield was 190 g kg−1 of dry paper sludge, corresponding to an overall conversion yield of 56.3% of the available carbohydrates on the initial substrate. The results derived from this study indicate that the response surface methodology is a useful tool for optimizing the hydrolysis conditions to converse paper sludge to ethanol. [Copyright &y& Elsevier]

Abstract: The continuation education is very important for people who have left school to work to increase their competence and skills. To avoid the disadvantages of the common test paper generating methods, genetic algorithm is used to generate the test paper automatically. The concrete design process of test paper generating based on genetic algorithm is discussed in this paper, and some corresponding parameters setting have been compared and defined. The application results demonstrated that the genetic algorithm was an effective tool in the test paper generating. [Copyright &y& Elsevier]

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]

The one-dimensional cutting stock problem (1D-CSP) is one of the representative combinatorial optimization problems which arises in many industrial applications. Although the primary objective of 1D-CSP is to minimize the total length of used stock rolls, the efficiency of cutting processes has become more important in recent years. The crucial bottleneck of the cutting process often occurs at handling operations in semiautomated manufacturers such as those in the paper tube industry. To reduce interruptions and errors at handling operations in the paper tube industry, we consider a variant of 1D-CSP that minimizes the total length of used stock rolls while constraining (C1) the number of setups of each stock roll type, (C2) the combination of piece lengths occurring in open stacks simultaneously, and (C3) the number of open stacks. For this problem, we propose a generalization of the cutting pattern called the 'cutting group,' which is a sequence of cutting patterns that satisfies the given upper bounds of setups of each stock roll type and open stacks. To generate good cutting groups, we decompose the 1D-CSP into a number of auxiliary bin packing problems. We develop a tabu search algorithm based on a shift neighborhood that solves the auxiliary bin packing problems by the first-fit decreasing heuristic algorithm. Experimental results show that our algorithm improves the quality of solutions compared to the existing algorithm used in a paper tube factory. [ABSTRACT FROM AUTHOR]

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]

The buffer allocation problem is an NP-hard combinatorial optimization problem, and it is an important design problem in manufacturing systems. The research proposed in this paper concerns a product line consisting of n unreliable machines with n − 1 buffers and a preventive maintenance policy. The focus of the research is to obtain a better trade-off between the buffer level and the preventive maintenance actions. This paper proposes a dynamic control of the buffers' level and the interval between two consecutive preventive actions. The set of the parameter of the proposed policy allows choosing the reduction in the costs or the increment of the throughput rate. A simulation model is developed to test the proposed model to the solution proposed in the literature. The proposed policy leads to better results in terms of total costs reduction keeping high production rate, while the design of a fixed level of buffer works better for lower production rates required. [ABSTRACT FROM AUTHOR]

The importance of linear programming, and especially mixed-integer linear programming, has increased over time as computers have gotten more capable, algorithms have improved and more software solutions have become available. This approach has been successfully applied for solving hard problems in operations research (like traveling salesman problem, routing problems and telecommunications network design problems). In the eighteenth paper, "Exact method for the two-machine flow-shop problem with time delays" Mkadem, Moukrim and Serairi propose an exact method for solving the two-machine flow-shop problem with time delays. [Extracted from the article]

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]

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]

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]

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]

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]

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]

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]

The Assignment Problem (AP) can be stated as n activities to be assigned to n resources in such a way that the overall cost of assignment is minimized and each activity is assigned to one and only one resource. In real-life, the parameters of the AP are presented as uncertain numbers due to the lack of knowledge, experiences or any other (internal or external) factor. In this paper, the AP is considered under intuitionistic triangular fuzzy number and solved by the novel constructive heuristic Dhouib-Matrix-AP1 (DM-AP1) with a time complexity of O(n). Actually, this paper presents the first enhancement of the novel heuristic DM-AP1 to solve the AP under intuitionistic triangular fuzzy environment. DM-AP1 is composed of three simple steps: computing the total cost, selecting the highest value and finding the minimal element. These steps are repeated in n iterations with the use of a standard deviation statistical metric. Two case studies of AP under intuitionistic triangular fuzzy set are taken from the literature and a step-by-step application of the novel DM-AP1 heuristic is presented for more clarification. [ABSTRACT FROM AUTHOR]

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

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

With the rapid development of intelligent manufacturing, the application of virtual reality technology to the optimization of workshop facility layout has become one of the development trends in the manufacturing industry. Virtual reality technology has put forward engineering requirements for real-time solutions to the Workshop Facility Layout Optimization Problem (WFLOP). However, few scholars have researched such solutions. Deep reinforcement learning (DRL) is effective in solving combinatorial optimization problems in real time. The WFLOP is also a combinatorial optimization problem, making it possible for DRL to solve the WFLOP in real time. Therefore, this paper proposes the application of DRL to solve the dual-objective WFLOP. First, this paper constructs a dual-objective WFLOP mathematical model and proposes a novel dual-objective DRL framework. Then, the DRL framework decomposes the WFLOP dual-objective problem into multiple sub-problems and then models each sub-problem. In order to reduce computational workload, a neighborhood parameter transfer strategy is adopted. A chain rule is constructed for the appealed sub-problem, and an improved pointer network is used to solve the bi-objective WFLOP of the sub-problem. Finally, the effectiveness of this method is verified by using the facility layout of a chip production workshop as a case study. [ABSTRACT FROM AUTHOR]

Data mining has achieved great success in air traffic management as a technology for learning knowledge from historical data that benefits people. However, data mining can rarely be embedded into the trajectory optimization process since regular optimization algorithms cannot utilize the functional and implicit knowledge extracted from historical data in a general paradigm. To tackle this issue, this research proposes a novel data mining-based trajectory generation method that is compatible with existing optimization algorithms. Firstly, the proposed method generates trajectories by combining various maneuvers learned from operation data instead of reconstructing trajectories with generative models. In such a manner, data mining-based trajectory optimization can be achieved by solving a combinatorial optimization problem. Secondly, the proposed method introduces a majorization–minimization-based adversarial training paradigm to train the generation model with more general loss functions, including non-differentiable flight performance constraints. A case study on Guangzhou Baiyun International Airport was conducted to validate the proposed method. The results illustrate that the trajectory generation model can generate trajectories with high fidelity, diversity, and flyability. [ABSTRACT FROM AUTHOR]

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

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

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

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

The 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]

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

This paper presents a new variant of Travelling Salesman Problem (TSP) and its first resolution. In literature there is not any research work that has presented the TSP under pentagonal fuzzy neutrosophic environment yet. TSP is a critical issue for manufacturing companies where all cities need to be visited only once except the starting city with a minimal cost. In real life, information provided (cost, time ... etc.) are generally uncertain, indeterminate or inconsistent that's why in this paper parameters of the TSP are presented as neutrosophic pentagonal fuzzy numbers. To solve this problem, the novel heuristic Dhouib-Matrix-TSP1 (DM-TSP1) is applied using a ranking function in order to transform the fuzzy set to crisp data and range function to select cities. To prove the efficiency of the proposed DM-TSP1 in solving the new variant of TSP, we create novel benchmark instances. Then, a stepwise application of DM-TSP1 is illustrated in details. [ABSTRACT FROM AUTHOR]

Intelligent manufacturing automation is a future trend, and optimizing production resource control using blockchain technology is a meaningful research topic. Existing studies have limitations, such as varying PSCO-PC models and insufficient flexibility in simulation models. This paper proposes a novel blockchain-based PSCO-PC strategy for intelligent manufacturing. It details the PSCO-PC model, improving the matching rationality and applicability of simulation system functions. The adaptive difficulty concept is introduced to address data throughput and consensus mechanism issues. Calculation steps for solving the optimal package revenue of PSCO matching records are provided. Experimental results confirm the effectiveness of the proposed simulation model and PSCO-PC strategy. [ABSTRACT FROM AUTHOR]

The Ising model is defined by an objective function using a quadratic formula of qubit variables. The problem of an Ising model aims to determine the qubit values of the variables that minimize the objective function, and many optimization problems can be reduced to this problem. In this paper, we focus on optimization problems related to permutations, where the goal is to find the optimal permutation out of the  n !  possible permutations of n elements. To represent these problems as Ising models, a commonly employed approach is to use a kernel that applies one-hot encoding to find any one of the  n !  permutations as the optimal solution. However, this kernel contains a large number of quadratic terms and high absolute coefficient values. The main contribution of this paper is the introduction of a novel permutation encoding technique called the dual-matrix domain wall, which significantly reduces the number of quadratic terms and the maximum absolute coefficient values in the kernel. Surprisingly, our dual-matrix domain-wall encoding reduces the quadratic term count and maximum absolute coefficient values from  n 3 − n 2  and  2 n − 4  to  6 n 2 − 12 n + 4  and 2, respectively. We also demonstrate the applicability of our encoding technique to partial permutations and Quadratic Unconstrained Binary Optimization (QUBO) models. Furthermore, we discuss a family of permutation problems that can be efficiently implemented using Ising/QUBO models with our dual-matrix domain-wall encoding. [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 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]

It has been proven that developing urban rail transit (URT) is the key to solving the traffic problems in big cities, and transport efficiency is essential for scientific line planning and construction, operation management and sustainable development of urban rail transit. This paper focuses on the transport efficiency of the URT network and adopts shadow efficiency theory creatively to combine factors of passengers, capacity, and efficiency effectively. A quantitative calculation method of system utility based on "double time penalty" is proposed. According to the characteristics of Beijing URT, this paper puts forward a single optimization strategy and combinatorial optimization strategy and analyzes the results with DEA. The simulation of Beijing subway network proves the availability of the method and its optimization effects. [ABSTRACT FROM AUTHOR]

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

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]