Search

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]

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.)

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]

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 article focuses on the Computational Optimization and Applications (COAP) 2008 Best Paper Award-winning work of Peter Hahn, Bum-Jin Kim, Monique Guignard-Spielberg and Yi-Rong Zhu at the University of Pennsylvania and J. MacGregor Smith at the University of Massachusetts. It notes that the interest of authors in the subject of the award paper has began in December 2003, in which they had learned important facts about the Quadratic Assignment Problem (QAP).

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]

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]

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]

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

The minimum connected dominating set problem is widely studied due to its applicability to mobile ad-hoc networks and sensor grids. Its variant the minimum 2-connected dominating set (M-2CDS) problem has become increasingly important because its critical role in designing fault-tolerant network. This paper presents a connected dominating degree-based local search (CDD-LS) tailored for solving the M-2CDS. The proposed algorithm implements an improved swap-based neighborhood structure as well as the corresponding fast neighborhood evaluation method using connected dominating degree data structure. The diversification techniques including tabu strategy and perturbaistion help the search jump out of the local optima improving the efficiency. This study investigates the performance of the CDD-LS algorithm on 38 publicly available benchmark datasets. The results demonstrate that the CDD-LS algorithm significantly improves the best runtime in 19 instances, while providing the equivalent performance in 8 instances. Furthermore, the CDD-LS is tested on 18 newly generated instances to check its capability on large-scale scenarios. To gain a deeper understanding of the algorithm’s effectiveness, an investigation into the key components of the CDD-LS algorithm is conducted. [ABSTRACT FROM AUTHOR]

Combinatorial optimization (CO) on graphs is a classic topic that has been extensively studied across many scientific and industrial fields. Recently, solving CO problems on graphs through learning methods has attracted great attention. Advanced deep learning methods, e.g., graph neural networks (GNNs), have been used to effectively assist the process of solving COs. However, current frameworks based on GNNs are mainly designed for certain CO problems, thereby failing to consider their transferable and generalizable abilities among different COs on graphs. Moreover, simply using original graphs to model COs only captures the direct correlations among objects, which does not consider the mathematical logicality and properties of COs. In this paper, we propose a unified pre-training and adaptation framework for COs on graphs with the help of the maximum satisfiability (Max-SAT) problem. We first use Max-SAT to bridge different COs on graphs since they can be converted to Max-SAT problems represented by standard formulas and clauses with logical information. Then we further design a pre-training and domain adaptation framework to extract the transferable and generalizable features so that different COs can benefit from them. In the pre-training stage, Max-SAT instances are generated to initialize the parameters of the model. In the fine-tuning stage, instances from CO and Max-SAT problems are used for adaptation so that the transferable ability can be further improved. Numerical experiments on several datasets show that features extracted by our framework exhibit superior transferability and Max-SAT can boost the ability to solve COs on graphs. [ABSTRACT FROM AUTHOR]

Container transportation is pivotal in global supply chains, facilitating the exchange of goods between companies across different countries. Given the exceedingly high operational costs of transporting containers, optimizing itinerary schedules can yield significant benefits for logistics companies. In this paper, we delve into a real-world container transportation routing issue where trucks are scheduled to haul trailers, subsequently transporting containers amongst container depots, ports, and warehouses. Our research bridges the existing gap between academic literature and industrial practice by examining the versatile role of trailers. We specifically focus on factors like trailer capacity restrictions and the ability to detach. To encapsulate these intricacies, we introduce a mixed-integer linear programming model, incorporating new variables, invariants, and constraints pertinent to these requirements. We follow this with the proposition of an Approximate Adapted Large Neighborhood Search algorithm (A-ALNS) aimed at solving the model. Within this algorithm, six innovative operators and elimination strategies have been integrated to amplify the efficiency of solution searches and sidestep local optima. Moreover, we've established an adaptive scoring mechanism to expedite operator selection and deliver feasible solutions within constrained timeframes. Our empirical tests on 25 data sets underscore the efficacy of our algorithms; they serve between 90.9% to 100% of total requests across all instances. Impressively, our proposed framework can attain feasible solutions within an hour - a task that often spanned days with preceding methodologies. [ABSTRACT FROM AUTHOR]

In recent years, swarm intelligence optimization algorithms have been proven to have significant effects in solving combinatorial optimization problems. Introducing the concept of evolutionary computing, which is currently a hot research topic, into swarm intelligence optimization algorithms to form novel swarm intelligence optimization algorithms has proposed a new research direction for better solving combinatorial optimization problems. The longhorn beetle whisker search algorithm is an emerging heuristic algorithm, which originates from the simulation of longhorn beetle foraging behavior. This algorithm simulates the touch strategy required by longhorn beetles during foraging, and achieves efficient search in complex problem spaces through bioheuristic methods. This article reviews the research progress on the search algorithm for longhorn beetles from 2017 to present. Firstly, the basic principle and model structure of the beetle whisker search algorithm were introduced, and its differences and connections with other heuristic algorithms were analyzed. Secondly, this paper summarizes the research achievements of scholars in recent years on the improvement of longhorn whisker search algorithms. Then, the application of the beetle whisker search algorithm in various fields was explored, including function optimization, engineering design, and path planning. Finally, this paper summarizes the research achievements of scholars in recent years on the improvement of the longhorn whisker search algorithm, and proposes future research directions, including algorithm deep learning fusion, processing of multimodal problems, etc. Through this review, readers will have a comprehensive understanding of the research status and prospects of the longhorn whisker search algorithm, providing useful guidance for its application in practical problems. [ABSTRACT FROM AUTHOR]

The uncapacitated facility location problem (UFLP) is a well-known combinatorial optimization problem that finds practical applications in several fields, such as logistics and telecommunication networks. While the existing literature primarily focuses on the deterministic version of the problem, real-life scenarios often involve uncertainties like fluctuating customer demands or service costs. This paper presents a novel algorithm for addressing the UFLP under uncertainty. Our approach combines a tabu search metaheuristic with path-relinking to obtain near-optimal solutions in short computational times for the determinisitic version of the problem. The algorithm is further enhanced by integrating it with simulation techniques to solve the UFLP with random service costs. A set of computational experiments is run to illustrate the effectiveness of the solving method. [ABSTRACT FROM AUTHOR]

Most existing deep learning methods for graph matching tasks tend to focus on affinity learning in a feedforward fashion to assist the neural network solver. However, the potential benefits of a direct feedback from the neural network solver to the affinity learning are usually underestimated and overlooked. In this paper, we propose a bidirectional learning method to tackle the above issues. Our method leverages the output of a neural network solver to perform feature fusion on the input of affinity learning. Such direct feedback helps augment the input feature maps of the raw images according to the current solution. A feature fusion procedure is proposed to enhance the raw features with pseudo features that contain deviation information of the current solution from the ground-truth one. As a result, the bidrectional alternation enables the learning component to benefit from the feedback, while keeping the strengths of learning affinity models. According to the results of experiments conducted on five benchmark datasets, our methods outperform the corresponding state-of-the-art feedforward methods. [ABSTRACT FROM AUTHOR]

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

In recent years, combinatorial optimization has been widely studied. The existing optimization solutions are prone to fall into local optimal solutions and have a lower probability of obtaining global optimal solutions. Quantum approximate optimization algorithm (QAOA) is an effective algorithm that can obtain the optimal solution with high probability. In this paper, the problem Hamiltonian is obtained by summing the problem function and the deformed constraints. Through theoretical formula derivation, the problem Hamiltonian is transformed into the Ising model. The performance of the experimental result under different optimizers and asynchronous lengths is verified on pyQPanda. The experimental results show that when using the problem Hamiltonian method set in this paper, the probability of obtaining the optimal solution is 99.59%. Compared with other methods, the proposed method can alleviate the risk of falling into local optimal solutions and obtain the global optimal solution with a higher probability. [ABSTRACT FROM AUTHOR]

In this paper, we study the Multi-Start Team Orienteering Problem (MSTOP), a mission re-planning problem where vehicles are initially located away from the depot and have different amounts of fuel. We consider/assume the goal of multiple vehicles is to travel to maximize the sum of collected profits under resource (e.g., time, fuel) consumption constraints. Such re-planning problems occur in a wide range of intelligent UAS applications where changes in the mission environment force the operation of multiple vehicles to change from the original plan. To solve this problem with deep reinforcement learning (RL), we develop a policy network with self-attention on each partial tour and encoder-decoder attention between the partial tour and the remaining nodes. We propose a modified REINFORCE algorithm where the greedy rollout baseline is replaced by a local mini-batch baseline based on multiple, possibly non-duplicate sample rollouts. By drawing multiple samples per training instance, we can learn faster and obtain a stable policy gradient estimator with significantly fewer instances. The proposed training algorithm outperforms the conventional greedy rollout baseline, even when combined with the maximum entropy objective. The efficiency of our method is further demonstrated in two classical problems – the Traveling Salesman Problem (TSP) and the Capacitated Vehicle Routing Problem (CVRP). The experimental results show that our method enables models to develop more effective heuristics and performs competitively with the state-of-the-art deep reinforcement learning methods. [ABSTRACT FROM AUTHOR]

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

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

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

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

Submodular function maximization is an attractive optimization model and also a well-studied problem with a variety of algorithms available. Constraint generation (CG) approaches are appealing techniques to tackle the problem with, as the mixed-integer programming formulation of the problem suffers from the exponential size of the number of constraints. Most of the problems in these topics are of combinatorial nature and involve graphs on which the maximization is defined. Inspired by the recent work of Uematsu et al. (J Oper Res Soc Jpn 63:41–59, 2020), in this paper we introduce variants of the CG algorithm which take into account certain properties of the input graph aiming at informed selection of the constraints. Benchmarking results are shown to demonstrate the efficiency of the proposed methods. [ABSTRACT FROM AUTHOR]

The paper proposes a methodology for mathematical modeling of the phased development of nodes and transport routes in a hierarchical network with multicommodity discrete flows of correspondences based on solving the problems of optimizing its structure and distribution of flows. As a rule, such networks consist of a decentralized mainline network and networks in the internal service areas of mainline nodes. In a multicommodity network, each node can exchange correspondence (products, goods, cargo, messages) with the other nodes. Correspondence is characterized by a source node, a sink node, and a quantity, which for data transmission networks is given by the number of bytes, kilobytes, etc., and for transport networks by the number of cargo units in a package of uniform size. In the mainline network, all correspondences are transmitted via communication channels or transported by vehicles in transport units of a given size (capacity, volume). The authors considered the main postulates of generating a mathematical model of the perspective development of mainline network. They presented a method of mathematical modeling of the phased development of nodes and transport routes, which includes, for each stage of development, the forecasting of data and network parameters, solving the problem of packing correspondence and choosing the structure of the network, and solving the problem of distribution and routing of transport unit flows. [ABSTRACT FROM AUTHOR]

The Capacitated Vehicle Routing Problem (CVRP) is a classical combinatorial optimization problem, which objective is to minimize the vehicle travel distance. In this paper a hybrid ant colony optimization based on Fireworks Algorithm (FWA) is proposed to solve the CVRP. The main work of hybrid algorithm is reflected in three aspects: firstly, FWA is introduced on the basis of Ant Colony Optimization (ACO) algorithm to increase the diversity of algorithms and avoid falling into local optimum too early in the search process; secondly, the elite ant strategy is added to increase the attractiveness of the local optimal path to the ants; thirdly, the Max-Min Ant System (MMAS) is added to limit the pheromone value within a range to prevent the pheromone from increasing too fast on the path. In this paper, the proposed hybrid algorithm is tested in 71 instances and compared with other intelligent algorithms. Experimental results show that the proposed hybrid algorithm finds new best solutions and is competitive with other algorithms. [ABSTRACT FROM AUTHOR]

The estimation of distribution algorithm (EDA) has recently emerged as a promising alternative to the traditional evolutionary algorithms for solving combinatorial optimization problems. In this paper, an estimation of distribution algorithm with multiple intensification strategies (EDA-MIS) is proposed to solve a typical kind of hybrid flow-shop scheduling problem. The two-stage heterogeneous hybrid flow-shop scheduling problem is investigated. The sequence-dependent setup time at the first stage is also considered. In the proposed EDA-MIS, the initial population is constructed through the heuristic method and random strategy. An order matrix is established to estimate the probabilistic model of promising solutions. Then the solutions of the algorithm are evolved through the processes of selection, recombination, sampling, and local search. The obtained results indicate that the EDA-MIS provides good solutions in the aspects of solution quality and computational efficiency. [ABSTRACT FROM AUTHOR]

Tower cranes are a key factor for both the operational and the economic success of large-scale construction projects. Cranes not only constitute a major position on the books, their role as the primary lifting equipment makes them a centerpiece of activities on the site as well. However, in contradiction to this and the considerable complexities of crane operations, decision support tools in the scientific literature are mostly limited to simulation-based sandbox tools or rather simplistic mathematical models. We address this issue by focusing on a crane selection and location planning problem which has been developed in a previous paper in cooperation with a partner from the construction industry. Loosely speaking, we consider a polygonal construction site with polygonal supply and demand areas located on it. Demand and supply areas have to be connected by selecting and locating cranes on-site. In doing so, both the areas' specific lifting requirements and the cranes' specifications such as lifting weight-dependent operating radius and operating height have to be respected. The goal is to minimize total crane-related costs while accounting for the cranes' operating characteristics as well as interdependencies between cranes and on-site structures. In a previous paper, we have proven this problem to be NP-hard and have provided four mixed-integer programming formulations which have been computationally studied with standard solver CPLEX. In the current paper, we develop a simple, but competitive exact branch and bound approach that overcomes the limitations we encountered when employing CPLEX on our mixed-integer programs. [ABSTRACT FROM AUTHOR]

Influence maximization (IM) is a challenging combinatorial optimization problem on (social) networks given a diffusion model and limited choice for initial seed nodes. In a recent paper by Keskin and Güler (Turkish J of Electrical Eng & Comput Sci 26:3383–3396, 2018) an integer programming formalization of IM using the so-called deterministic linear threshold diffusion model was proposed. In fact, it is a special 0-1 linear program in which the objective is to maximize influence while minimizing the diffusion time. In this paper, by rigorous analysis, we show that the proposed algorithm can get stuck in locally optimal solution or cannot even start on certain input graphs. The identified problems are resolved by introducing further constraints which then leads to a correct algorithmic solution. Benchmarking results are shown to demonstrate the efficiency of the proposed method. [ABSTRACT FROM AUTHOR]

Over the years, there have been many variations of the Vehicle Routing Problem created to fit the actual needs of society, one of which is the Electric Vehicle Routing Problem (EVRP). EVRP is a more complex and challenging combinatorial optimization than the conventional vehicle routing problem. This paper considers a specific model for the tram routing problem and proposes a clustering-inspired greedy search algorithm GS. GS algorithm aims to cluster charging routes and greedily search charging stations for the optimal route output. In this paper, we purposely implement GS into a meta-heuristic genetic algorithm GA to utilize GA's finding a globally optimal, leading to the formulation of the GSGA algorithm. To evaluate performance, we use a benchmark dataset found in the CEC-12 Tram Routing Problem CEC-12 Competition at the World Congress on Computational Intelligence (WCCI) 2020. The experiment evaluates GS's effectiveness when applied to other algorithms such as genetic algorithms and simulated annealing. The experiments results show that our proposed algorithm has better solution quality than previous algorithms. [ABSTRACT FROM AUTHOR]

Resource optimization is becoming a prime factor in the progress of Internet-based technology, Cloud Computing. A resource management model is highly required in cloud data center paradigms to utilize available resources effectively. Bin-Packing problem is an applicable combinatorial optimization for Virtual Machine (VM) to Physical Machine (PM) allocation to minimize the required PMs. In this paper, we have proposed an efficient resource allocation and management algorithm in two phases. During the first phase, a Load Balanced Multi-Dimensional Bin-Packing (LBMBP) heuristic for Virtual Machine (VM) to Physical Machine (PMs or host) allocation is introduced, considering multidimensional resources: CPU, RAM, and Network Bandwidth. In the Second Phase, to perform VM migration, a mechanism to detect overloaded and underloaded hosts based on outliers has been described. The proposed work illustrated the simulation results using CloudSim Plus Simulator and observed a reduction in the number of active PMs. Energy consumption and the number of migrations with improved resource utilization. [ABSTRACT FROM AUTHOR]

In this paper, we consider the heterogeneous Chinese postman problem (the HCPP), which generalizes the k-Chinese postman problem. Specifically, given a weighted graph G = (V , E ; w ; r) with length function w : E → R + satisfying the triangle inequality, a fixed depot r ∈ V , and k vehicles having k nonuniform speeds λ 1 , λ 2 , … , λ k , respectively, it is asked to find k tours in G for these k vehicles, each starting at the same depot r, and collectively traversing each edge in E at least once. The objective is to minimize the maximum completion time of vehicles, where the completion time of a vehicle is its total travel length divided by its speed. The main contribution of our paper is to show the following two results. (1) Given any small constant δ > 0 , we design a 20.8765 (1 + δ) -approximation algorithm to solve the HCPP, where the running time required is bounded by a polynomial in the input size and 1 δ . (2) We present a (1 + Δ - 1 / k) -approximation algorithm to solve the HCPP in cubic time, where Δ is the ratio of the largest vehicle speed to the smallest one. [ABSTRACT FROM AUTHOR]

Hepatitis B (HB) is a deadly disease that has a severe impact on infected individuals. In China, not only are the incidence and infection rates of HB very high, but also many HB patients suffer from mental illness associated with anxiety and fear because of HB-associated symptoms. This exacerbates the patients' condition, potentially increasing the risk of mortality. In this paper, we propose a new treatment mode to improve the therapeutic efficiency and patients' satisfaction with their healthcare. In a single process of this new treatment, several patients with similar disease symptoms are treated by one doctor at the same time. This new treatment mode can not only relieve the anxiety and fear of HB patients, and improve patients' cognition rate of HB, but also reduce the HB infection rate, slow down the progression of disease symptoms, and shorten the course. If patients with similar disease symptoms are to be grouped together, there is a need to determine the optimal patient batch combination, which can be solved in the new mode, called patient combined problem (PCP). We also constructed a mathematical model of PCP, and present the ant colony (AC) algorithm and Enhanced AC with a P-3-exchange operator for PCP in the new treatment mode in this paper. We also performed an experiment that showed that our proposed algorithms are very fast and effective for solving this problem. [ABSTRACT FROM AUTHOR]

With the slowdown of improvement in conventional von Neumann systems, increasing attention is paid to novel paradigms such as Ising machines. They have very different approach to solving combinatorial optimization problems. Ising machines have shown great potential in solving binary optimization problems like MaxCut. In this paper, we present an analysis of these systems in boolean satisfiability (SAT) problems. We demonstrate that, in the case of 3-SAT, a basic architecture fails to produce meaningful acceleration, largely due to the relentless progress made in conventional SAT solvers. Nevertheless, careful analysis attributes part of the failure to the lack of two important components: cubic interactions and efficient randomization heuristics. To overcome these limitations, we add proper architectural support for cubic interaction on a state-of-the-art Ising machine. More importantly, we propose a novel semantic-aware annealing schedule that makes the search-space navigation much more efficient than existing annealing heuristics. Using numerical simulations, we show that such an "Augmented" Ising Machine for SAT is projected to outperform state-of-the-art software-based, GPU-based and conventional hardware SAT solvers by orders of magnitude. [ABSTRACT FROM AUTHOR]

An automatic alpha factor mining method is proposed in this paper to assist expert traders in finding profitable alpha factors efficiently. Unlike finding qualified alpha factors by directly enumerating all possible combinations, the mining task is formulated as an iterative convolution kernel learning problem. Each kernel to be learned is associated with a unique alpha factor. To better solve the learning problem, the sparsity is introduced at the mutation step of the learning process to find simple and interpretable solutions efficiently and relieve the overfitting risks in real-world trading. A theorem is proposed to prove that the designed learning process can complete automatically in finite iterations as all convolution kernel vectors converge to zero vectors. In addition, a score function based on win rate, expected return and trade frequency is designed to evaluate the performance of market entry signals generated by the alpha factors practically. The convolution kernels with high score values are recorded and exported as the mined alpha factors. The experiment results show that the proposed method can achieve superior performance on both the China government bond dataset and the gold dataset. [ABSTRACT FROM AUTHOR]

Evolutionary multitasking optimization, which concentrates on solving multiple tasks simultaneously, has been a core area of interest for researchers in recent years. Existing Multifactorial Evolutionary Algorithms (MFEA) are quite dependent on the synergy among the tasks. Consequently, solving multiple tasks is prone to fall into local traps when the optimization enters a certain stage. The objective of this paper is to investigate these problems in more detail and provide corresponding solutions. Specifically, we propose a three-stage analysis method that divides the multitasking optimization problem into three stages and explain the MFEA features according to the individual distribution in each stage, based on which we further develop a Parametric Segmented Multifactorial Evolutionary Algorithm (PS-MFEA) and apply a precise search strategy in the algorithm. Additionally, we propose both a reinitialization mechanism and a backtracking mechanism to avoid local optima. We conduct a comprehensive experiment on two test sets of benchmark problems with different similarity levels and the discrete combinatorial optimization tasks of the traveling salesman problem. The results demonstrate that using PS-MFEA can obtain better performances in both test sets and solve practical problems. [ABSTRACT FROM AUTHOR]

Vehicle routing (VRP) and traveling salesman problems (TSP) are classical and interesting NP-hard routing combinatorial optimization (CO) with practical significance. While moving forward with artificial intelligence, researchers are paying more and more attention to applying machine learning to classical CO problems. However, traditional reinforcement learning faces challenges like reward sparsity and unstable training, so it is necessary to assist agents in finding high-quality routings in the initial model training stage to obtain more positive feedback. This paper proposes a novel Monte Carlo Tree Search (MCTS)-based two-stage multi-agent reinforcement learning training pipeline (MCRL) in which we also design a multifunctional reward function, improving efficiency, accuracy, and diversity to guide agents to learn the routings over graphs better. Besides, previous approaches are frequently too sluggish in runtime to be useful in contexts with sparsely connected networks and uncertain traffic. As an alternative, we design a model based on graph neural networks that can execute multi-agent routing in a sparsely connected graph with constantly changing traffic circumstances. Also, the agents are better equipped to collaborate online and adjust to changes thanks to our learned communication module. [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]

In this paper, we address the constrained knapsack problem with divisible item sizes and penalties (the CK-DSP problem, for short), which is modelled as follows. Given a set A = { a 1 , a 2 , ... , a n } of n items and a knapsack K with capacity L, where each item a i ∈ A has a size s i ∈ Z + , a profit c i ∈ R + , a penalty p i ∈ R + , and these n item sizes are divisible, i.e., either s i | s j or s j | s i for any two distinct items a i and a j in A, each item a i ∈ A must be either put into K under the constraint that the summation of sizes of items in K does not exceed L, or rejected with its penalty p i that we must pay for, it is asked to find a subset X ⊆ A to satisfy the constraint s (X) = ∑ a i ∈ X s i ≤ L . We consider three versions of the CK-DSP problem, respectively. (1) The constrained knapsack problem with divisible item sizes and total penalties (the CK-DSTP problem, for short) is asked to find a subset X ⊆ A to satisfy the constraint s (X) ≤ L , the objective is to maximize the value of total profits of the items in X minus total penalties paid for the rejected items not in X; (2) The constrained knapsack problem with divisible item sizes and maximum penalty (the CK-DSMP problem, for short) is asked to find a subset X ⊆ A to satisfy the constraint s (X) ≤ L , the objective is to maximize the value of total profits of the items in X minus maximum penalty paid for the rejected items not in X; (3) The penalized knapsack problem with divisible item sizes (the PK-DS problem, for short) is asked to find a subset X ⊆ A to satisfy the constraint s (X) ≤ L , the objective is to maximize the value of total profits of the items in X minus maximum penalty paid for the items in X. As our contributions, we design three exact combinatorial algorithms to solve the CK-DSTP problem, the CK-DSMP problem and the PK-DS problem, and these three algorithms run in time O (n log n) , O (n 2 log n) and O (n 2 log n) , respectively, where n is the number of items with divisible sizes. [ABSTRACT FROM AUTHOR]

Motivated by cutting-edge applications like cryo-electron microscopy (cryo-EM), the Multi-Reference Alignment (MRA) model entails the learning of an unknown signal from repeated measurements of its images under the latent action of a group of isometries and additive noise of magnitude σ . Despite significant interest, a clear picture for understanding rates of estimation in this model has emerged only recently, particularly in the high-noise regime σ ≫ 1 that is highly relevant in applications. Recent investigations have revealed a remarkable asymptotic sample complexity of order σ 6 for certain signals whose Fourier transforms have full support, in stark contrast to the traditional σ 2 that arise in regular models. Often prohibitively large in practice, these results have prompted the investigation of variations around the MRA model where better sample complexity may be achieved. In this paper, we show that sparse signals exhibit an intermediate σ 4 sample complexity even in the classical MRA model. Further, we characterize the dependence of the estimation rate on the support size s as O p (1) and O p (s 3.5) in the dilute and moderate regimes of sparsity respectively. Our techniques have implications for the problem of crystallographic phase retrieval, indicating a certain local uniqueness for the recovery of sparse signals from their power spectrum. Our results explore and exploit connections of the MRA estimation problem with two classical topics in applied mathematics: the beltway problem from combinatorial optimization, and uniform uncertainty principles from harmonic analysis. Our techniques include a certain enhanced form of the probabilistic method, which might be of general interest in its own right. [ABSTRACT FROM AUTHOR]

Task scheduling (TS) and multi-agent-path-finding (MAPF) are two cruxes of pickup-and-delivery in automated warehouses. In this paper, the two cruxes are optimized simultaneously. Firstly, the system model, task model, and path model are established, respectively. Then, a task scheduling algorithm based on enhanced HEFT, a heuristic MAPF algorithm and a TS- MAPF algorithm are proposed to solve this combinatorial optimization problem. In EHEFT, a novel rank priority rule is used to determine task sequencing and task allocation. In MAPF algorithm, a CBS algorithm with priority rules is designed for path search. Subsequently, the TS-MAPF algorithm which combines EHEFT and MAPF is proposed. Finally, the proposed algorithms are tested separately against relevant typical algorithms at different scales. The experimental results indicate that the proposed algorithms exhibited good performance. [ABSTRACT FROM AUTHOR]

The beetle antennae search (BAS) algorithm is a memetic meta-heuristic optimization algorithm capable of solving combinatorial optimization problems. In this paper, the binary version of BAS (BBAS) is modified by adding a V-shaped transfer function. In this way, we introduce the V-shaped transfer function-based binary BAS (VSBAS) algorithm, which is a more effective and efficient version of BBAS in the case of large input data. Applications using real-world data sets on a binary Markowitz-based portfolio selection (BMPS) problem validate the excellent performance of VSBAS on large input data and demonstrate that it is a marvelous alternative against other ordinary memetic meta-heuristic optimization algorithms. Note that, because the meta-heuristic algorithms compared in this paper are directly applicable only to unconstrained optimization, the penalty function method was used to keep their solutions in the feasible district. In order to support and promote the findings of this work, we have constructed a complete MATLAB package for the interested user, which is freely available through GitHub. [ABSTRACT FROM AUTHOR]

Mining high-utility itemsets (HUIs) is one of the most important research topics in data mining because HUIs consider non-binary frequency values of items in transactions and different profit values for each item. However, setting appropriate minimum utility thresholds by trial and error is a tedious process for users. Thus, mining the top-k HUIs without setting a utility threshold is becoming an alternative to determine all the HUIs. In this paper, we propose two algorithms, called the top-k high-utility itemset mining based on cross-entropy method (TKU-CE) and TKU-CE+, for mining the top-k HUIs heuristically. The TKU-CE algorithm is based on cross-entropy, and implements top-k HUI mining using combinatorial optimization. The main idea of TKU-CE is to generate the top-k HUIs by gradually updating the probabilities of itemsets with high-utility values. TKU-CE+ optimizes TKU-CE in three respects. First, unpromising items are filtered by critical utility value, to reduce the computational burden in the initial stage. Second, a sample refinement strategy is used in each iteration, to reduce the computational burden in the iterative stage. Finally, smoothing mutation is proposed, to randomly generate some new itemsets in addition to those from previous iterations. Consequently, diversity of samples is improved, so that more actual top-k HUIs can be discovered with fewer iterations. Compared with state-of-the-art algorithms, TKU-CE and TKU-CE+ are easy to implement and avoid the computational costs that would be incurred by additional data structures and threshold-raising strategies. Extensive experimental results show that both algorithms are efficient, memory-saving, scalable, and can discover the most actual top-k HUIs. [ABSTRACT FROM AUTHOR]

This paper proposes to combine the method of conditional expectations (MOCE, also known as Johnson's Algorithm) with the state-of-the-art heuristic configuration checking local search (CCLS), to solve maximum satisfiability (Max Sat) instances. First, MOCE is used to find an outstanding assignment, and then CCLS explores the solution space, starting at this assignment. This combined heuristic, which we call MOCE–CCLS, is shown to provide a significant improvement over each of its parts: MOCE and CCLS. An additional contribution of this paper is the results of a comprehensive comparative evaluation of MOCE–CCLS versus CCLS on various benchmarks. On random benchmarks, the combined heuristic reduces the number of unsatisfied clauses by up to tens of percents. On Max Sat 2016 and 2021 public competition benchmarks, which include crafted and industrial instances also, MOCE–CCLS outperforms CCLS as well. To provide an empirical basis to the above result, this work further explores the correlation between the quality of initial assignments provided to CCLS and that of the corresponding final assignments. Empirical results show that the correlation is significant and long-lasting. Thus, under practical time constraints, the quality of the initial assignment is crucial to the performance of local search heuristics. [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]

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

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]

Double Roman domination (DRD) is a combinatorial optimization problem posed on undirected graphs. It can be interpreted as allocating certain service providers (e.g., military formations, fire brigades or ambulances) to chosen locations within a certain area. Thereby the whole service (i.e., response to enemy attacks, fire or medical urgencies) should be established in a least expensive way, while still assuring a required "double Roman" level of availability and redundancy of providers. The standard version of DRD treated in the literature identifies the total expense of service with the total number of needed providers. In this paper a new "minimum-cost" version of DRD is considered, which is more general and more realistic than the standard version. It takes into account the fact that the actual expenses of providing service can differ from one location to another. Thus, formally speaking, each vertex in our graph is given a cost that is intepreted as the cost of keeping one service provider at the corresponding location. First, it is noted that the considered minimum-cost DRD problem is NP-hard, not only for general graphs but also for many special graph classes. Next, a dynamic programming algorithm is constructed, which shows that the problem can still be solved in linear time if the involved graph is a tree. Finally, as a solution for general graphs, a heuristic is proposed based on greedy construction and local search. Performance of both algorithms is evaluated by experiments. [ABSTRACT FROM AUTHOR]