Search

The problem of finding optimal block designs can be formulated as a combinatorial optimization, but its resolution is still a formidable challenge. This paper presents a general and user-friendly algorithm, namely Modified Particle Swarm Optimization (MPSO), to construct optimal or near-optimal block designs. It can be used for several classes of block designs such as binary, non-binary and test-control block designs with correlated or uncorrelated observations. In order to evaluate the algorithm, we compare our results with the optimal designs presented in some published papers. An advantage of our algorithm is its independency to the sizes of blocks and the structure of correlations. [ABSTRACT FROM AUTHOR]

The problem of finding a maximum size matching in a graph (known as the maximum matching problem) is one of the most classical problems in computer science. Despite a significant body of work dedicated to the study of this problem in the data stream model, the state-of-the-art single-pass semi-streaming algorithm for it is still a simple greedy algorithm that computes a maximal matching, and this way obtains 1 / 2 -approximation. Some previous works described two/three-pass algorithms that improve over this approximation ratio by using their second and third passes to improve the above mentioned maximal matching. One contribution of this paper continues this line of work by presenting new three-pass semi-streaming algorithms that work along these lines and obtain improved approximation ratios of 0.6111 and 0.5694 for triangle-free and general graphs, respectively. Unfortunately, a recent work Konrad and Naidu (Approximation, randomization, and combinatorial optimization. Algorithms and techniques, APPROX/RANDOM 2021, August 16–18, 2021. LIPIcs, vol 207, pp 19:1–19:18, 2021. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.19) shows that the strategy of constructing a maximal matching in the first pass and then improving it in further passes has limitations. Additionally, this technique is unlikely to get us closer to single-pass semi-streaming algorithms obtaining a better than 1 / 2 -approximation. Therefore, it is interesting to come up with algorithms that do something else with their first pass (we term such algorithms non-maximal-matching-first algorithms). No such algorithms were previously known, and the main contribution of this paper is describing such algorithms that obtain approximation ratios of 0.5384 and 0.5555 in two and three passes, respectively, for general graphs. The main significance of our results is not in the numerical improvements, but in demonstrating the potential of non-maximal-matching-first algorithms. [ABSTRACT FROM AUTHOR]

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]

This paper addresses the triangle width problem, which generalizes the classic two-machine flexible job-shop problem (FJSP) with tooling constraints. This new problem can be studied from three different angles: scheduling, matrix visualization, and vertex ordering in hypergraphs. We prove the equivalence of the different formulations of the problem and use them to establish the N P -Hardness and polynomiality of several of its subcases. This problem allows us to find more elegant (and probably shorter) proofs for several combinatorial problems in our analysis setting. Our study provides an elegant generalization of Johnson's argument for the two-machine flow shop. It also shows the relation between the question: "Is a matrix triangular?" and the "k-visit of a graph". [ABSTRACT FROM AUTHOR]

Solving combinatorial optimization problems (COPs) poses a significant challenge in various application domains. The NP-hardness of many COPs necessitates the integration of meta-heuristics to effectively tackle these problems by leveraging the strengths of each meta-heuristic. However, hybrid meta-heuristics lack a mechanism to determine when to activate specific techniques during the search process. To address these limitations and enhance the overall generality, this study proposes a novel agent-based hyper-heuristic framework, referred to as IAFCO, for solving COPs. The proposed framework imbues the search strategy with greater intelligence and information, resulting in improved performance. The proposed framework comprises 4 coalitions that leverage different search perspectives to enhance the search process: a global coalition, a local coalition, a learning coalition, and a perturbation coalition. Additionally, a control agent is introduced to coordinate the coalitions. Using a reinforcement learning mechanism, the control agent autonomously selects the most suitable coalition of agents based on the search state. The set of states employed in this study is problem-independent and encompasses all possible states that may arise during the search process. Furthermore, some agents adopt chaotic numbers instead of random numbers to maintain diversity. To showcase the effectiveness of the proposed framework, its performance is evaluated on the software modularization problem (SMP) -also known as software clustering- and community detection problem (CDP) in complex networks as 2 case studies. The experiments on SMP's software systems, including 10 applications and 10 folders of Mozilla Firefox, and comparison with 21 modularization algorithms and experiments on CDP's networks, including 9 real-world networks, and comparison with 22 state-of-the-art community detection algorithms, indicate that the proposed framework is comparable to other existing methods. The source codes and datasets of this paper are available at https://github.com/mahjoubeh-t/IAFCO. [ABSTRACT FROM AUTHOR]

We consider the problem of designing lightweight, load-bearing planar frame structures for additive manufacturing, which can be formulated as a nonlinear, non-convex mathematical programming problems. Even using state-of-the-art commercial solvers, exact methods are only capable of solving small unrealistic instances (with very few variables). In this paper, we develop a heuristic method which is fast and capable of solving the design problem for larger-scale, weight-optimized, planar frame structures for additive manufacturing. The approach explicitly considers manufacturability constraints stemming from the use of additive manufacturing technology and leverages the problem structure imposed by these constraints. The proposed heuristic method is based on iteratively resolving a relaxed master problem on a reduced ground structure. The approach differs from the existing methods in two important aspects. First, we consider planar frame optimization master problem directly (instead of simpler but less relevant truss optimization). Secondly, we employ both element and node addition, which allows us to enforce additive manufacturability constraints without using binary variables (and hence, avoiding the need for computationally expensive integer programming). [ABSTRACT FROM AUTHOR]

Due to its high spectral efficiency and various other advantages, filter bank multicarrier/offset quadrate amplitude modulation (FBMC/OQAM) has long been considered as a candidate waveform for the fifth generation (5G) and beyond telecommunication technologies. On the other hand, it is possible to both increase the data rate and alleviate the channel fading effects by using the multiple-input multiple-output (MIMO) antenna structure in the FBMC/OQAM transceiver. However, since the symbol detection is an indispensable task to be fulfilled in wireless communication, it is crucial to employ an efficient symbol detector at the MIMO-FBMC/OQAM receiver. Maximum likelihood (ML) detector, which always finds the optimal symbols by trying all of the possible symbol combinations likely to be transmitted, is known for its extremely high computational complexity making it impractical to be used in any system. On the other hand, it is possible to both considerably reduce the ML complexity and achieve the near-ML performance by optimizing the symbol vectors instead of implementing an exhaustive search. Since searching for the optimal symbol combination in discrete space is a combinatorial optimization problem, we developed a novel discrete harmony search (disHS) algorithm to perform this operation. According to the simulation results, the newly developed disHS algorithm not only achieves near-ML performance with lower computational complexity, but also clearly leaves behind the other symbol detectors considered in this paper. [ABSTRACT FROM AUTHOR]

The development of information technology, wireless communications have become prevalent in every other field we can imagine. Sensor nodes are the fundamental element of wireless communication networks. When they are deployed, they gather environmental data from the surrounding area and send it to the base station for further analysis. This paper focused on creating a routing technique that improved wireless communication energy conservation through the use of fuzzy logic and ant colony optimisation in order to extend battery life. Ant colony optimisation algorithm (HFACO) and hybrid fuzzy logic were used in the construction of the routing protocol. Numerous derived techniques have been adapted to dynamic problems in real variables, stochastic problems, multi-targets, and parallel implementations. Ant colony optimisation algorithms have been applied to a wide range of combinatorial optimisation problems, from quadratic assignment to protein folding or routing vehicles. Several techniques that are based on how ant colonies forage have been used recently to solve challenging discrete optimisation problems.By taking into account the node's energy and traffic load, fuzzy logic was utilised to determine the total node cost to the gateway. Ant colony optimisation (ACO) was used to find the shortest path between the source and destination sensor nodes, and the path's value was determined by measuring its shortest distance. When compared to the ACO's performance in the same conditions, the Matlab simulation's results showed superior energy conservation performance. This improved routing technique can be applied to Wi-Fi sensor networks in industrial environments. [ABSTRACT FROM AUTHOR]

Among the distribution network planning problems, feeder routing is one of the most important and challenging issues. Feeder routing is defined as the optimal determination of the feeders' routes by minimizing the investment cost and satisfying the network constraints. To the best knowledge of the authors, solving feeder routing problem in multi-objective framework is rarely investigated in the previous literature. This paper develops a bi-objective modeling and optimization framework to efficiently solve the feeder routing problem of distribution network considering cost and power losses. Since feeder routing is a complex, high-dimensional and combinatorial optimization problem, a multi-objective differential crow search algorithm (MO-CSAdif) is proposed to obtain a well-distributed and widely spread Pareto front. On a real large distribution network, simulation results confirm the usefulness of the proposed optimization framework. It can be drawn that MO-CSAdif can be a promising method to optimally solve the feeder routing problem. [ABSTRACT FROM AUTHOR]

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

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

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]

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

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

This paper 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]

Production scheduling is a critical factor to enhancing productivity in manufacturing engineering and combinatorial optimization research. The complexity and dynamic nature of production systems necessitates innovative solutions. The Job Shop Flexible Programming Problem (FJSP) provides a realistic environment for production, where processing times are variable and uncertain, and multiple objectives need optimization. To solve the Multi-Objective Flexible Fuzzy Job Shop problem with partial flexibility (P-MOFfJSP), this paper proposes a hybrid metaheuristic approach that combines the Teaching–Learning-based Optimization (TLBO) algorithm with a Genetic Algorithm. The proposed algorithm of Adaptive TLBO (TLBO-A) uses two genetic operators (mutation and crossover) with an adaptive population reconfiguration strategy, ensuring solution space exploration and preventing premature convergence. We have evaluated the TLBO-A algorithm's performance on benchmark instances commonly used in programming problems with fuzzy variables. The experimental analysis indicates significant results, demonstrating that the adaptive strategy improves the search for suitable solutions. The proposed algorithm (TLBO-A) exhibits low variations (around 11%) compared to the best mono-objective heuristic for the fuzzy makespan problem, indicating its robustness. Moreover, compared with other heuristics like traditional TLBO, the variations decrease to around 1%. However, TLBO-A stands out as it aims to solve a multi-objective problem, improving the fuzzy makespan, and identifying good results on the Pareto frontier for the fuzzy average flow time, all within this low variation margin. Our contribution addresses the challenges of production scheduling in fuzzy time environments and proposes a practical hybrid metaheuristic approach. The TLBO-A algorithm shows promising results in solving the P-MOFfJSP, highlighting the potential of our proposed methodology for solving real-world production scheduling problems. [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]

Submodular maximization is a NP-hard combinatorial optimization problem regularly used in machine learning and data mining with large-scale data sets. To quantify the running time of approximation algorithms, the query complexity and adaptive complexity are two important measures, where the adaptivity of an algorithm is the number of sequential rounds it makes when each round can execute polynomially many function evaluations in parallel. These two concepts reasonably quantify the efficiency and practicability of parallel computation. In this paper, we consider the problem of maximizing a nonnegative monotone DR-submodular function over a bounded integer lattice with a cardinality constraint in a value oracle model. Prior to our work, Soma and Yoshida (Math Program 172:539–563, 2018) have studied this problem and present an approximation algorithm with almost optimal approximate ratio and the same adaptivity and query complexity. We develop two novel algorithms, called low query algorithm and low adaptivity algorithm, which have approximation ratios equal to Soma and Yoshida (2018), but reach a new record of query complexity and adaptivity. As for methods, compared with the threshold greedy in Soma and Yoshida (2018), the low query algorithm reduces the number of possible thresholds and improves both the adaptivity and query complexity. The low adaptivity algorithm further integrates a vector sequencing technique to accelerate adaptive complexity in an exponential manner while only making logarithmic sacrifices on oracle queries. [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]

We consider the block relocation problem (BRP), a combinatorial optimization problem that may arise in storage systems where items are organized in stacks. The objective is to retrieve all items in a predefined order with a minimal number of relocations. It can be distinguished between a restricted and an unrestricted version of the BRP. While in the restricted BRP (R-BRP) only relocations of items located above the item to be retrieved next are permitted, in the unrestricted BRP (U-BRP) all possible relocations are allowed. Existing exact methods concerning the BRP are frequently search-based methods which appear to be very effective. Nevertheless, recent literature concerning the R-BRP has shown that model-based methods can be competitive and therefore should also be taken into consideration. In this paper, we propose a new model-based approach for the U-BRP. It eliminates the fact that the number of variables is increasing with the number of necessary relocations; a disadvantage most mathematical models for the U-BRP have in common. [ABSTRACT FROM AUTHOR]

The Digital Annealer is a CMOS hardware designed by Fujitsu Laboratories for high-speed solving of Quadratic Unconstrained Binary Optimization (QUBO) problems that could be difficult to solve by means of existing general-purpose computers. In this paper, we present a mathematical description of the first-generation Digital Annealer's Algorithm from the Markov chain theory perspective, establish a relationship between its stationary distribution with the Gibbs-Boltzmann distribution, and provide a necessary and sufficient condition on its cooling schedule that ensures asymptotic convergence to the ground states. [ABSTRACT FROM AUTHOR]

The Inventory Routing Problem (IRP) is a combinatorial optimization problem that combines routing decisions with inventory management. In this paper, an approach to solving the IRP is studied, which aims at using an external knowledge source (a known good solution or user interaction) to improve the results attained by an evolutionary algorithm solving an IRP instance. The proposed method improves the best solution found by the evolutionary algorithm by modifying schedules for some of the retailers according to those present in the known good solution or to schedules provided by a domain expert. The experiments shown that to improve the optimization results it suffices to perform a few repetitions of the knowledge import procedure. This observation motivates further research on user-interactive optimization algorithms for the IRP, because the number of interactions needed to improve the results can easily be handled by the user. [ABSTRACT FROM AUTHOR]

The minimum weighted vertex cover (MWVC) problem is to find a subset of vertices that can cover all the edges of the network and minimize the sum of the vertex weights in the vertex subset. MWVC is a generalization of the minimum vertex cover (MVC) problem and can be regarded as a combinatorial optimization problem. This paper proposes an evolutionary algorithm based on the snowdrift game to solve the MWVC problem. We use the evolutionary algorithm framework, and the snowdrift game is combined to construct and improve the initial solution. First, the network's vertex is regarded as an intelligent agent, and each vertex and its neighbors play a snowdrift game to form an initial solution. Then local search and global search are used to improve the initial solution. The solution is improved according to the proposed score function in the local search stage to obtain a better MWVC solution. The evolutionary algorithm is used in the global search stage to escape the local optimum. Experiments on different networks show that the proposed algorithm are effective on weighted networks. [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]

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]

Disasters are large-scale disruptions for the society that cause damage to human lives, infrastructure, and the ecosystem. Multiple emergencies emerge, which need to be handled and resolved efficiently to minimize the impact of the disaster. Therefore, the need for an effective and efficient emergency response system that optimally allocates resources and emergency services is essential. This paper proposes a methodology to model this situation as an optimization problem that can be solved using meta-heuristic algorithms. In the proposed model, four meta-heuristics, namely Particle Swarm Optimization, Cuckoo Search, Grey Wolf Optimizer, and iLSHADE-RSP algorithm, have been used to allocate resources and services. A benchmark dataset consisting of 16 situations is prepared to analyze the proposed model. The conducted empirical analysis demonstrates the applicability of the meta-heuristic algorithms in locating near-optimum solutions for the considered situations. The convergence analysis and statistical tests have been performed to test the validity and significance of the conducted experiments. [ABSTRACT FROM AUTHOR]

The graph coloring problem is an NP-hard problem. Currently, one of the most effective methods to solve this problem is a hybrid evolutionary algorithm. This paper proposes a hybrid evolutionary algorithm NERS_HEAD with a new elite replacement strategy. In NERS_HEAD, a method to detect the local optimal state is proposed so that the evolutionary process can jump out of the local optimal state by introducing diversity on time; a new elite structure and a replacement strategy are designed to increase the diversity of the evolutionary population so that the evolution process can not only converge quickly but also jump out of the local optimal state in time. The comparison experiments with current excellent graph coloring algorithms on 59 DIMACS benchmark instances show that NERS_HEAD can effectively improve the efficiency and success rate of solving graph coloring problems. [ABSTRACT FROM AUTHOR]

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

This paper considers the planning of logistics missions of hybrid transport systems, which include a car or other vehicle that can move from a base to other locations along a designated route, carrying one unmanned aerial vehicle (UAV). A meaningful formulation and mathematical models of optimization problems of distributing objects to bases, selecting bases, and generating UAV routes during the inspection of maintenance of a given set of objects in the presence of flight resource constraints are proposed. We have developed an algorithm based on ant colony optimization to solve the resulting combinatorial optimization problems. We present the results of a computational experiment. [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]

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]

This document is a preface to a special issue of Mathematical Programming, Series B (MPB) focused on integer programming and combinatorial optimization. The issue contains 23 high-quality articles that were previously presented at the 23rd Conference on Integer Programming and Combinatorial Optimization (IPCO) in 2022. The IPCO conference is an annual event that brings together researchers and practitioners in the field. The full journal papers in this special issue are longer and more comprehensive than the extended abstracts presented at IPCO. The papers underwent a rigorous refereeing process before being accepted for publication. The authors express their gratitude to the referees and the Editor-in-Chief of MPB for their contributions to this special issue. [Extracted from the article]

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

Facility location is a prominent optimization problem that has inspired a large quantity of both theoretical and practical studies in combinatorial optimization. Although the problem has been investigated under various settings reflecting typical structures within the optimization problems of practical interest, little is known on how the problem behaves in conjunction with parity constraints. This shortfall of understanding was rather discouraging when we consider the central role of parity in the field of combinatorics. In this paper, we present the first constant-factor approximation algorithm for the facility location problem with parity constraints. We are given as the input a metric on a set of facilities and clients, the opening cost of each facility, and the parity requirement– odd , even , or unconstrained –of every facility in this problem. The objective is to open a subset of facilities and assign every client to an open facility so as to minimize the sum of the total opening costs and the assignment distances, but subject to the condition that the number of clients assigned to each open facility must have the same parity as its requirement. Although the unconstrained facility location problem as a relaxation for this parity-constrained generalization has unbounded gap, we demonstrate that it yields a structured solution whose parity violation can be corrected at small cost. This correction is prescribed by a T-join on an auxiliary graph constructed by the algorithm. This auxiliary graph does not satisfy the triangle inequality, but we show that a carefully chosen set of shortcutting operations leads to a cheap and sparseT-join. Finally, we bound the correction cost by exhibiting a combinatorial multi-step construction of an upper bound. We also consider the parity-constrained k-center problem, the bottleneck optimization variant of parity-constrained facility location. We present the first constant-factor approximation algorithm also for this problem. [ABSTRACT FROM AUTHOR]

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

Community detection is a prominent research topic in Complex Network Analysis, and it constitutes an important research field on all those areas where complex networks represent a powerful interpretation tool for describing and understanding systems involved in neuroscience, biology, social science, economy, and many others. A challenging approach to uncover the community structure in complex network, and then revealing the internal organization of nodes, is Modularity optimization. In this research paper, we present an immune optimization algorithm (opt-IA) developed to detect community structures, with the main aim to maximize the modularity produced by the discovered communities. In order to assess the performance of opt-IA, we compared it with an overall of 20 heuristics and metaheuristics, among which one Hyper-Heuristic method, using social and biological complex networks as data set. Unlike these algorithms, opt-IA is entirely based on a fully random search process, which in turn is combined with purely stochastic operators. According to the obtained outcomes, opt-IA shows strictly better performances than almost all heuristics and metaheuristics to which it was compared; whilst it turns out to be comparable with the Hyper-Heuristic method. Overall, it can be claimed that opt-IA, even if driven by a purely random process, proves to be reliable and with efficient performance. Furthermore, to prove the latter claim, a sensitivity analysis of the functionality was conducted, using the classic metrics NMI, ARI and NVI. [ABSTRACT FROM AUTHOR]

This paper deals with an interesting facility location problem known as the bi-objective p-Median and p-Dispersion problem (BpMD problem). The BpMD problem seeks to locate p facilities to service a set of n demand points, and the goal is to minimize the total distance between facilities and demand points and, simultaneously, maximize the minimum distance between all pairs of hosted facilities. The problem is addressed with a novel path relinking approach, called reactive path relinking, which hybridizes two of the most extended path relinking variants: interior path relinking and exterior path relinking. Additionally, the proposal is adapted to a multi-objective perspective for finding a good approximation of the Pareto front. Computational results prove the superiority of the proposed algorithm over the best procedures found in the literature. [ABSTRACT FROM AUTHOR]

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

Sensitivity analysis in general deals with the question of how changes in input data of a model affect its output data. In the context of optimization problems, such an analysis could, for instance, address how changes in capacity constraints affect the optimal solution value. Although well established in the domain of linear programming, sensitivity analysis approaches for combinatorial optimization problems are model-specific, limited in scope and not applicable to practical optimization problems. To overcome these limitations, Schulte et al. developed the concept of bilevel innovization. By using evolutionary bilevel optimization in combination with data mining and visualization techniques, bilevel innovization provides decision-makers with deeper insights into the behavior of the optimization model and supports decision-making related to model building and configuration. Originally introduced in the field of evolutionary computation, most recently bilevel innovization has been proposed as an approach to sensitivity analysis for combinatorial problems in general. Based on previous work on bilevel innovization, our paper illustrates this concept as a tool for sensitivity analysis by providing a comprehensive analysis of the generalized assignment problem. Furthermore, it is investigated how different algorithms for solving the combinatorial problem affect the insights gained by the sensitivity analysis, thus evaluating the robustness and reliability of the sensitivity analysis results. [ABSTRACT FROM AUTHOR]

Considering the complex structure and large size of multiple axes rotary spindle heads and the small workspace of parallel modules, a 5-degree of freedom (DOF) hybrid robot is proposed, which is a symmetrical 4-limb parallel module in series with a single axis rotary spindle head. Screw theory was used to analyze the mobility and kinematics of the hybrid mechanism. The singularity of the symmetrical 4-limb parallel module was studied, and the analysis results were verified by the Grassmann linear geometry principle. According to the singularity analysis results, the kinematic pairs' positions of the robot were determined, so the hybrid robot model was constructed. Considering the workspace volume, and optimizing the Latin hypercube sample algorithm, a combinatorial numerical optimization algorithm is proposed to optimize dimension parameters of this hybrid robot, which combines non-linear programming by quadratic Lagrangian (NLPQL) algorithm with the optimized Latin hypercube sampling (Opt LHS) algorithm. Through this optimization algorithm, the workspace volume of the robot is increased by 1.93 times. The research method in this paper is also suitable for the analysis and optimization of other hybrid robots. [ABSTRACT FROM AUTHOR]

Ensuring fairness in computational problems has emerged as a key topic during recent years, buoyed by considerations for equitable resource distributions and social justice. It is possible to incorporate fairness in computational problems from several perspectives, such as using optimization, game-theoretic or machine learning frameworks. In this paper we address the problem of incorporation of fairness from a combinatorial optimization perspective. We formulate a combinatorial optimization framework, suitable for analysis by researchers in approximation algorithms and related areas, that incorporates fairness in maximum coverage problems as an interplay between two conflicting objectives. Fairness is imposed in coverage by using coloring constraints that minimizes the discrepancies between number of elements of different colors covered by selected sets; this is in contrast to the usual discrepancy minimization problems studied extensively in the literature where (usually two) colors are not given a priori but need to be selected to minimize the maximum color discrepancy of each individual set. Our main results are a set of randomized and deterministic approximation algorithms that attempts to simultaneously approximate both fairness and coverage in this framework. [ABSTRACT FROM AUTHOR]

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

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

This non-conventional paper represents the first attempt to uncover a possible vulnerability in some proposals for optical network designs and performance comparisons. While optical network designs and planning lie at the heart of achieving fiber capacity efficiency and/or operational efficiency, its combinatorial nature makes it computationally hard to reach optimal solutions for realistic scenarios. As a consequence, the well-established way that have been taken for granted by not-so-small number of research papers is that an optimization model based on mixed integer linear programming (MILP) formulation is first proposed and then due to the intractability of such combinatorial optimization model, a heuristic algorithm is offered as an approximation. The solution-quality comparison between the MILP and heuristic is then carried out on small-scale instances including topologies and traffic tests to verify the efficacy of the proposed heuristic. Next such allegedly verified heuristic are used for optical network designs of realistic scenarios. This approach may nevertheless leave a critical vulnerability as there is no guarantee that one performs well in small tests will generalize adequately for large-scale cases, a common pitfall widely referred as the peril of extrapolation and/or overfitting. Besides, it is not uncommon that in some research works, for benchmarking purpose, the comparison between a new design proposal whose performance is obtained from on one heuristic and a reference design based on another heuristic is carried out. As the consequence of lacking solution quality check, such performance comparison relied merely on heuristic solutions may be equally vulnerable, resulting to possibly unreliable conclusions. In this work, we pinpoint those issues and provide a realistic case study to highlight and demonstrate the impact of such vulnerabilities. [ABSTRACT FROM AUTHOR]

In this paper, we explore the theory and expand upon the practice of fitness landscape analysis for optimization problems over the space of permutations. Many of the computational and analytical tools for fitness landscape analysis, such as fitness distance correlation, require identifying a distance metric for measuring the similarity of different solutions to the problem. We begin with a survey of the available distance metrics for permutations, and then use principal component analysis to classify these metrics. The result of this analysis aligns with existing classifications of permutation problem types produced through less formal means, including the A-permutation, R-permutation, and P-permutation types, which classifies problems by whether absolute position of permutation elements, relative positions of elements, or general precedence of pairs of elements, is the dominant influence over solution fitness. Additionally, the formal analysis identifies subtypes within these problem categories. We see that the classification can assist in identifying appropriate metrics based on optimization problem feature for use in fitness landscape analysis. Using optimization problems of each class, we also demonstrate how the classification scheme can subsequently inform the choice of mutation operator within an evolutionary algorithm. From this, we present a classification of a variety of mutation operators as a counterpart to that of the metrics. Our implementations of the permutation metrics, permutation mutation operators, and associated evolutionary algorithm, are available in a pair of open source Java libraries. All of the code necessary to recreate our analysis and experimental results are also available as open source. [ABSTRACT FROM AUTHOR]

In recent years, convolutional neural networks (CNNs) have demonstrated their ability to solve problems in many fields and with accuracy that was not possible before. However, this comes with extensive computational requirements, which made general central processing units (CPUs) unable to deliver the desired real-time performance. At the same time, field-programmable gate arrays (FPGAs) have seen a surge in interest for accelerating CNN inference. This is due to their ability to create custom designs with different levels of parallelism. Furthermore, FPGAs provide better performance per watt compared to other computing technologies such as graphics processing units (GPUs). The current trend in FPGA-based CNN accelerators is to implement multiple convolutional layer processors (CLPs), each of which is tailored for a subset of layers. However, the growing complexity of CNN architectures makes optimizing the resources available on the target FPGA device to deliver the optimal performance more challenging. This is because of the exponential increase in the design variables that must be considered when implementing a Multi-CLP accelerator as CNN's complexity increases. In this paper, we present a CNN accelerator and an accompanying automated design methodology that employs metaheuristics for partitioning available FPGA resources to design a Multi-CLP accelerator. Specifically, the proposed design tool adopts simulated annealing (SA) and tabu search (TS) algorithms to find the number of CLPs required and their respective configurations to achieve optimal performance on a given target FPGA device. Here, the focus is on the key specifications and hardware resources, including digital signal processors (DSPs), block random access memories (BRAMs), and off-chip memory bandwidth. Experimental results and comparisons using four well-known benchmark CNNs are presented demonstrating that the proposed acceleration framework is both encouraging and promising. The SA-/TS-based Multi-CLP achieves 1.31 × - 2.37 × higher throughput than the state-of-the-art Single-/Multi-CLP approaches in accelerating AlexNet, SqueezeNet 1.1, VGGNet, and GoogLeNet architectures on the Xilinx VC707 and VC709 FPGA boards. [ABSTRACT FROM AUTHOR]

This paper studies a shuffled linear regression problem. As a variant of ordinary linear regression, it requires estimating not only the regression variable, but also permutational correspondences between the covariates and responses. While existing formulations require the underlying ground-truth correspondences to be an ideal bijection such that all pieces of data should match, such a requirement barely holds in real-world applications due to either missing data or outliers. In this work, we generalize the formulation of shuffled linear regression to a broader range of conditions where only a part of the data should correspond. To this end, the effective recovery condition and NP-hardness of the proposed formulation are also studied. Moreover, we present a simple yet effective algorithm for deriving the solution. Its global convergence property and convergence rate are also analyzed in detail. Distinct tasks validate the effectiveness of our proposed formulation and the solution method. [ABSTRACT FROM AUTHOR]

Learning heuristics without expert experience to construct solutions automatically has always been a critical challenge of combinatorial optimization. It is also the pursuit of artificial intelligence to construct an agent with the planning ability to solve multiple problems simultaneously. Nonetheless, most current learning-based methods for combinatorial optimization still rely on artificially designed heuristics. In real-world problems, the environment's dynamics are often unknown and complex, making it challenging to generalize and implement current methods. Inspired by AlphaGo Zero, we propose a novel self-play reinforcement learning algorithm (CH-Zero) based on the Monte Carlo tree search (MCTS) for routing optimization problems in this paper. Like AlphaGo Zero, CH-Zero does not require expert experience but some necessary rules. However, unlike other self-play algorithms based on MCTS, we have designed offline training and online reasoning. Specifically, we apply self-play reinforcement learning without MCTS to train offline policy and value networks. Then, we apply the learned heuristics and neural network combined with an MCTS to make inferences on unknown instances. Since we did not incorporate MCTS during training, this is equivalent to training a lightweight self-playing framework whose learning efficiency is much higher than the existing self-play-based methods for combinatorial optimization. We can employ the learned heuristics to guide MCTS to improve policies and take better actions at runtime. [ABSTRACT FROM AUTHOR]

Optical Ising machines promise to solve complex optimization problems with an optical hardware acceleration advantage. Here we study the ground state properties of a nonlinear optical Ising machine realized by spatial light modulator, Fourier optics, and second-harmonic generation in a nonlinear crystal. By tuning the ratio of the light intensities at the fundamental and second-harmonic frequencies, we experimentally observe two distinct ferromagnetic-to-paramagnetic phase transitions: a second-order phase transition where the magnetization changes to zero continuously and a first-order phase transition where the magnetization drops to zero abruptly as the effective temperature increases. Our experimental results are corroborated by a numerical simulation based on the Monte Carlo Metropolis-Hastings algorithm, and the physical mechanism for the distinct phase transitions can be understood with a mean-field theory. Our results showcase the flexibility of the nonlinear optical Ising machine, which may find potential applications in solving combinatorial optimization problems. Optical Ising machines provide a promising approach to solve complex optimization problems and hence are of broad interest in physics society. This paper constructs a nonlinear optical Ising machine with spatial light modulators to find distinct phase transitions, which demonstrates a platform for solving optimization problem in more efficient way. [ABSTRACT FROM AUTHOR]