Search

Abstract: This paper investigates the skiving and cutting stock problem (SCSP) encountered in the paper and plastic film industries, in which a set of nonstandard reels generated from previous cutting processes are used to produce finished rolls through the skiving and cutting process. First, reels are skived together lengthwise to form a reel‐pyramid (a polygon), and then the reel‐pyramid is cut into finished rolls of small widths. Depending on if a reel can be divided lengthwise into subreels to form the reel‐pyramid, the problem can be classified into divisible SCSP (DSCSP) and indivisible SCSP (ISCSP). In this paper, two integer programming (IP) models are proposed for DSCSP and ISCSP, respectively. A sequential value correction procedure combined with the two IP models (SVCTIP) is developed to solve the two SCSPs. The effectiveness of the SVCTIP is demonstrated through extensive computational tests. [ABSTRACT FROM AUTHOR]

Focuses on the polyhedral technique for combinatorial optimization problems. Formulation of a mathematical programming model for difficult problems; Concept of the linear programming relaxation.

In this paper, we introduce, study and analyze several classes of compact formulations for the symmetric Hamiltonian p$$ p $$‐median problem (Hp$$ p $$MP). Given a positive integer p$$ p $$ and a weighted complete undirected graph G=(V,E)$$ G=\left(V,E\right) $$ with weights on the edges, the Hp$$ p $$MP on G$$ G $$ is to find a minimum weight set of p$$ p $$ elementary cycles partitioning the vertices of G$$ G $$. The advantage of developing compact formulations is that they can be readily used in combination with off‐the‐shelf optimization software, unlike other types of formulations possibly involving the use of exponentially sized sets of variables or constraints. The main part of the paper focuses on compact formulations for eliminating solutions with less than p$$ p $$ cycles. Such formulations are less well known and studied than formulations which prevent solutions with more than p$$ p $$ cycles. The proposed formulations are based on a common motivation, that is, the formulations contain variables that assign labels to nodes, and prevent less than p$$ p $$ cycles by stating that different depots must have different labels and that nodes in the same cycle must have the same label. We introduce and study aggregated formulations (which consider integer variables that represent the label of the node) and disaggregated formulations (which consider binary variables that assign each node to a given label). The aggregated models are new. The disaggregated formulations are not, although in all of them new enhancements have been included to make them more competitive with the aggregated models. The two main conclusions of this study are: (i) in the context of compact formulations, it is worth looking at the models with integer node variables, which have a smaller size. Despite their weaker LP relaxation bounds, the fewer variables and constraints lead to faster integer resolution, especially when solving instances with more than 50 nodes; (ii) the best of our compact models exhibit a performance that, overall, is comparable to that of the best methods known for the Hp$$ p $$MP (including branch‐and‐cut algorithms), solving to optimality instances with up to 226 nodes within 1 h. This corroborates our message that the knowledge of the inequalities for preventing less than p$$ p $$ cycles is much less well understood. [ABSTRACT FROM AUTHOR]

Feature selection is a fundamental pre‐processing step in machine learning that aims to reduce the dimensionality of a dataset by selecting the most effective features from the original features. This process is regarded as a combinatorial optimization problem, and the grey wolf optimizer (GWO), a novel meta‐heuristic algorithm, has gained popularity in feature selection due to its fast convergence speed and easy implementation. In this paper, an improved binary GWO algorithm incorporating a novel Population Adaptation strategy called PA‐BGWO is proposed. The PA‐BGWO takes into account the characteristics of the feature selection problem and designs three strategies. The proposed strategy includes an adaptive individual update procedure to enhance the exploitation ability and accelerate convergence speed, a head wolf fine‐tuned mechanism to exert the impact on each independent feature of the objective function, and a filter‐based method ReliefF for calculating feature weights with dynamically adjusted mutation probabilities based on the ranking features to effectively escape from local optima. Experimental comparisons with several state‐of‐the‐art feature selection methods on 15 classification problems demonstrate that the proposed approach can select a small feature subset with higher classification accuracy in most cases. [ABSTRACT FROM AUTHOR]

Metaheuristic algorithms are employed to solve complex and large‐scale optimization problems in many different fields, from transportation and smart cities to finance. This paper discusses how metaheuristic algorithms are being applied to solve different optimization problems in the area of bioinformatics. While the text provides references to many optimization problems in the area, it focuses on those that have attracted more interest from the optimization community. Among the problems analyzed, the paper discusses in more detail the molecular docking problem, the protein structure prediction, phylogenetic inference, and different string problems. In addition, references to other relevant optimization problems are also given, including those related to medical imaging or gene selection for classification. From the previous analysis, the paper generates insights on research opportunities for the Operations Research and Computer Science communities in the field of bioinformatics. [ABSTRACT FROM AUTHOR]

Since the late 70s, much research activity has taken place on the class of dynamic vehicle routing problems (DVRP), with the time period after year 2000 witnessing a real explosion in related papers. Our paper sheds more light into work in this area over more than 3 decades by developing a taxonomy of DVRP papers according to 11 criteria. These are (1) type of problem, (2) logistical context, (3) transportation mode, (4) objective function, (5) fleet size, (6) time constraints, (7) vehicle capacity constraints, (8) the ability to reject customers, (9) the nature of the dynamic element, (10) the nature of the stochasticity (if any), and (11) the solution method. We comment on technological vis-à-vis methodological advances for this class of problems and suggest directions for further research. The latter include alternative objective functions, vehicle speed as decision variable, more explicit linkages of methodology to technological advances and analysis of worst case or average case performance of heuristics. [ABSTRACT FROM AUTHOR]

Approximation of the optimal tour length in a Euclidean traveling salesman problem (TSP) has been studied by many researchers. In a previous study, we used the standard deviation in random tour lengths to approximate the optimal tour length in both Euclidean and non‐Euclidean TSPs and we obtained good estimates. In this paper, we show that the strong power‐law relationship between the standard deviation in random feasible solution values and the optimal solution value also holds for other Euclidean and near‐Euclidean combinatorial optimization problems like the minimum spanning tree (MST) and maximum weight matching (MWM) problems. We then enhance the estimation ability of the model by considering a second predictor: the mean in random feasible solution values. Experimental results show that by using the mean, standard deviation, and randomization, we can accurately predict the optimal solution values for the TSP, MST, MWM, and the capacitated vehicle routing problem (VRP). [ABSTRACT FROM AUTHOR]

Summary Oscillator‐based Ising machines (OIMs) particularly those realized in complementary metal oxide semiconductor (CMOS) have gained popularity for solving combinatorial optimization problems (COPs) in recent years due to its scalability, low‐power consumption, and room temperature operation. The implemented OIMs have thus far focused on solving optimization problems with a single global minima. However, real‐life optimization problems often have multiple solutions. In this paper, we propose a generalized approach to solve COPs with single (without contention), as well as multiple (with contention) solutions using frequency tunable CMOS ring oscillator (ROSC)‐based Ising machine. A capacitive frequency tunable CMOS ring‐oscillator coupled with an internal subharmonic injection locking (SHIL) generator realized using 14‐nm FinFET models works as Ising spin in the proposed approach. We demonstrate how frequency tuning can help in attaining good quality results and also determine all possible solutions of COP with contention. We also propose a generalized algorithm for monitoring the states of the oscillator network to indicate tuning necessity and extract solutions from the oscillator's output irrespective of the type of COP. [ABSTRACT FROM AUTHOR]

Summary: The wireless network resource allocation is a NP‐hard combinatorial optimization problem. This paper proposes a new optimization method using the manta ray foraging optimization (MRFO) based on spiral modeling to solve the wireless network resource problem. In order to reduce the computational complexity and ensure the optimal performance of the allocation scheme, a MRFO algorithm based on spiral modeling and mutation strategy is proposed. In the first stage, spiral modeling is introduced to narrow the exploration area, while the mutation strategy of the genetic algorithm enhances the ability of the algorithm to jump out of the local optimal. In the second stage, a binary MRFO algorithm for using different transfer functions is proposed to solve the mixed integer programming problem. The experimental results show that IMRFO and BIMRFO have high comprehensive performance advantages, achieve better effects than the other optimization algorithms, which lead to faster convergence, faster accuracy, and lower complexity. [ABSTRACT FROM AUTHOR]

Motivated by the strengths of unmanned aerial vehicle (UAV), the UAV–human collaboration route planning (UHCRP) for intelligent infrastructure inspection is a problem worthy of discussion to help reduce human costs and minimize the risk of noninspected infrastructures under limited resources. To facilitate UHCRP, this paper proposes a novel deep reinforcement learning (DRL)‐based approach to well handle multi‐source uncertain features and constraints at a fast speed. To begin with, UHCRP is mathematically described and reformulated as a dual interdependent deep reinforcement learning (diDRL) framework to reflect real‐world scenarios. Afterward, a novel policy network named the attention‐based deep neural network (A‐DNN) is introduced to learn the route planning decisions for the combinatorial optimization problem. In particular, A‐DNN is made up of an encoder and a dual decoder for UAV and human inspection, where the multi‐head attention mechanism is incorporated to generate richer representations for model performance improvement. Performance of the proposed dual multi‐head attention model (DAM) has been tested in simulations and a real‐world case study regarding wind farm inspection. Results indicate that DAM under the sampling decoding strategy can deliver a high‐quality path plan and show better generalizability for larger scale problem sizes compared to single‐head attention model (SAM), multi‐head attention model (AM), and two baseline models, namely OR‐Tools and genetic algorithm. Moreover, DAM trained by randomly generated data can be directly employed to solve the practical problem with standardization of inputs. Overall, DRL integrates decision‐making for inspection method selection and inspected infrastructure selection, providing adaptive and intelligent inspection path planning for UAV and human in complex and dynamic engineering environments. [ABSTRACT FROM AUTHOR]

A 2‐factor in a graph G $G$ is a subset of edges M $M$ such that every node of G $G$ is incident with exactly two edges of M $M$. Many results are known concerning 2‐factors including a polynomial‐time algorithm for finding 2‐factors and a characterization of those graphs that have a 2‐factor. The problem of finding a 2‐factor in a graph is a relaxation of the NP‐hard problem of finding a Hamilton cycle. A stronger relaxation is the problem of finding a triangle‐free 2‐factor, that is, a 2‐factor whose edges induce no cycle of length 3. In this paper, we present a polynomial‐time algorithm for the problem of finding a triangle‐free 2‐factor as well as a characterization of the graphs that have such a 2‐factor and related min–max and augmenting path theorems. [ABSTRACT FROM AUTHOR]

This paper deals with the problem of finding the optimal configuration of a network of land parcels connecting and protecting core areas through corridors and buffer areas within budget. We focus on polynomial‐sized integer linear programming formulations, building on previous research and borrowing some ideas from other authors. We establish the relationships between the proposed and past models in linear programming relaxation terms and test them on synthetic instances with up to 400 land parcels. [ABSTRACT FROM AUTHOR]

Abstract: In their paper “An improved Clarke and Wright savings algorithm for the capacitated vehicle routing problem,” published in ScienceAsia (38, 3, 307–318, 2012), Pichpibul and Kawtummachai developed a simple stochastic extension of the well‐known Clarke and Wright savings heuristic for the capacitated vehicle routing problem. Notwithstanding the simplicity of the heuristic, which they call the “improved Clarke and Wright savings algorithm” (ICW), the reported results are among the best heuristics ever developed for this problem. Through a careful reimplementation, we demonstrate that the results published in the paper could not have been produced by the ICW heuristic. Studying the reasons how this paper could have passed the peer review process to be published in an ISI‐ranked journal, we have to conclude that the necessary conditions for a thorough examination of a typical paper in the field of optimization are generally lacking. We investigate how this can be improved and come to the conclusion that disclosing source code to reviewers should become a prerequisite for publication. [ABSTRACT FROM AUTHOR]

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

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

In this paper, we present a novel methodology to solve the problem of delineating homogeneous site‐specific management zones (SSMZ) in agricultural fields. This problem consists of dividing the field into small regions for which a specific rate of inputs is required. The objective is to minimize the number of management zones, which must be homogeneous according to a specific soil property: physical or chemical. Furthermore, as opposed to oval zones, SSMZ with rectangular shapes are preferable since they are more practical for agricultural technologies. The methodology we propose is based on evolutionary computation, specifically on a class of the estimation of distribution algorithms (EDAs). One of the strongest contributions of this study is the representation used to model the management zones, which generates zones with orthogonal shapes, for example, L or T shapes, and minimizes the number of zones required to delineate the field. The experimental results show that our method is efficient to solve real field and randomly generated instances. The average improvement of our method consists in reducing the number of management zones in the agricultural fields concerning other operations research methods presented in the literature. The improvement depends on the size of the field and the level of homogeneity established for the resulting management zones. [ABSTRACT FROM AUTHOR]

An introduction to the periodical 1974 issue is presented in which the guest editors discuss vehicle routing problem.

Quantum computing shows promise for 6G networks due to its parallel computing capabilities. In the context of the Noisy Intermediate‐Scale Quantum era, the introduction of hybrid quantum‐classical algorithms like Quantum Approximate Optimization Algorithm (QAOA) offer powerful solutions to many combinatorial optimization problems in 6G. This paper focuses on Low‐Density Parity‐Check (LDPC) channel decoding and proposes an improved QAOA algorithm assisted by the learning‐to‐learn strategy. We also investigate the parameter concentration phenomenon in QAOA‐based LDPC decoding to assess the rationality. To evaluate effectiveness, a comprehensive numerical expression for the energy expectation of single‐layer QAOA and propose indicators for transfer performance evaluation is provided. Based on simulation results, the similarity in parameter distribution across specific LDPC configurations is investigated. This similarity facilitates the transfer of training outcomes from smaller to larger‐scale problems for optimization initialization, thereby avoiding the need for retraining. This approach offers insights and potential solutions for rapid, large‐scale channel decoding in 6G networks, despite the current limitations of quantum hardware. [ABSTRACT FROM AUTHOR]

In this paper, we introduce the quay partitioning problem (QPP), that is, a problem of partitioning quay length into berths for minimum ship waiting time. Such a problem arises when designing the terminal layout. Two schemes of quay layout are considered: with at most one ship in a berth and with at most two ships in a berth. Ship arrival times, service times, lengths, and weights are given. We show that QPP is NP‐hard. The two versions of QPP are formulated as mixed integer linear programs (MIPs). Scalability of solving QPPs as MIPs is studied. We investigate, analytically and in computational experiments, features of the QPP solutions such as (i) changes in solution quality when one long berth length is used versus choosing various berth lengths flexibly, (ii) what lengths of berths are chosen when ship lengths mixture is changing, (iii) what is the impact of congestion on the chosen berth lengths, and (iv) how much is one quay layout scheme better than the other. [ABSTRACT FROM AUTHOR]

In the last years, there has been a great interest in machine‐learning‐based heuristics for solving NP‐hard combinatorial optimization problems. The developed methods have shown potential on many optimization problems. In this paper, we present a learned heuristic for the reoptimization of a problem after a minor change in its data. We focus on the case of the capacited vehicle routing problem with static clients (i.e., same client locations) and changed demands. Given the edges of an original solution, the goal is to predict and fix the ones that have a high chance of remaining in an optimal solution after a change of client demands. This partial prediction of the solution reduces the complexity of the problem and speeds up its resolution, while yielding a good quality solution. The proposed approach resulted in solutions with an optimality gap ranging from 0% to 1.7% on different benchmark instances within a reasonable computing time. [ABSTRACT FROM AUTHOR]

Vehicle routing problem (VRP) is one of the classic combinatorial optimization problems where an optimal tour to visit customers is required with a minimum total cost in the presence of some constraints. Recently, VRP is being solved with the use of deep reinforcement learning (DRL), with node sets considered (represented) as a graph structure. Existing Transformer based DRL solutions for VRP rely only on node information ignoring the role of information on the edges between nodes in the graph structure. In this paper, we proposed an attention‐based end‐to‐end DRL model to solve VRP which embeds edge information between nodes for rich graph representation learning. We used Transformer based encoder‐decoder framework with an edge information embedded multi‐head attention (EEMHA) layer in the encoder. The EEMHA‐based encoder learns underlying structure of the graph and generates an expressive graph topology representation by merging node and edge information. We trained our model using proximal policy optimization (PPO) with some code‐level optimization techniques. We conducted an experiment on randomly generated instances and on a real‐world data generated from road networks to verify the performance of our proposed model. The result from all experiments show that our model performs better than the existing DRL methods and most of the conventional heuristics with good generalizability from random instance training to real‐world instance testing of different problem size. © 2023 Institute of Electrical Engineers of Japan. Published by Wiley Periodicals LLC. [ABSTRACT FROM AUTHOR]

Service composition is the process of combining a set of elementary or atomic services. The aim is to produce a new composite service to satisfy the user's request that cannot be satisfied by the atomic services. Combining multiple services is a complex problem that has been the subject of several research studies. The meta‐heuristic approaches are good techniques that have been used to solve several complex problems in various domains. These techniques are able to discover promising search regions and locate good quality solutions in reasonable time without exploring the whole solution space. In this paper, we deal with the problem of optimal web service composition by using meta‐heuristic approaches. Given a set of services and a set of tasks to be completed, the problem is to find the best set of services composition to complete all tasks where each service must be assigned to a given task. This problem can be modelled as a combinatorial optimization problem with a set of objective functions that need to be optimized. We search for a composite service that allows us to execute the considered tasks and offers the best quality of services (QoS). More precisely, we search for an execution plan that indicates for each task the assigned service. First, we propose a multi‐objective local search based meta‐heuristic (MO‐LS) and a multi‐objective genetic algorithm (MO‐GA) to handle our problem. Then we propose a multi‐objective memetic algorithm (MO‐MA) that combines the two methods LS and GA. The role of GA is to detect promising regions to be explored. The role of LS is to exploit efficiently the potential regions created by GA. Four objective functions are used to compute the Pareto optimal set of solutions. The main objective is to minimize cost and time and to maximize availability and reputation and produce a good composite service. The three proposed approaches namely MO‐LS, MO‐GA, and MO‐MA are evaluated on some datasets generated randomly and on the well‐known QWS dataset to select the best fit services in terms of maximum or minimum aggregated end‐to‐end QoS parameters. The numerical results are encouraging and demonstrate the effectiveness of the proposed MO‐MA for the web service composition. [ABSTRACT FROM AUTHOR]

The location routing problem (LRP) integrates operational decisions on vehicle routing operations with strategic decisions on the location of the facilities or depots from which the distribution will take place. In other words, it combines the well-known vehicle routing problem (VRP) with the facility location problem (FLP). Hence, the LRP is an NP-hard combinatorial optimization problem, which justifies the use of metaheuristic approaches whenever large-scale instances need to be solved. In this paper, we explore a realistic version of the LRP in which facilities of different capacities are considered, i.e., the manager has to consider not only the location but also the size of the facilities to open. In order to tackle this optimization problem, three mixed-integer linear formulations are proposed and compared. As expected, they have been proved to be cost- and time- inefficient. Hence, a biased-randomized iterated local search algorithm is proposed. Classical instances for the LRP with homogeneous facilities are naturally extended to test the performance of our approach. [ABSTRACT FROM AUTHOR]

This paper studies a districting problem arising in the collection of waste of electrical and electronic equipment. Given a set of collection bins, where users return end-of-life electronic goods, located across a region or country, the design problem involves assigning these bins to the companies responsible for the collection at a later stage. This assignment must meet specific planning and legal requirements such as a fair household distribution according to each company’s market share and a fair assignment based on the bin infrastructure quality. According to the current law, this assignment must be done in such a way to avoid, to the best possible extent, regional monopolies. This anti-monopoly requirement is achieved by maximizing a dispersion function. A tabu search metaheuristic with an advanced feature of strategic oscillation is proposed for this N P-hard combinatorial optimization problem. The particular components are designed to exploit the mathematical structure of the problem entirely. Besides, a few upper bounding schemes are developed and tested. The empirical work shows the tabu search’s effectiveness and its components over a broad set of instances from the literature. In particular, the strategic oscillation idea turned out to have a very positive impact. Overall, the proposed metaheuristic outperformed the best existing method for this problem. [ABSTRACT FROM AUTHOR]

Distributing points on a (possibly high‐dimensional) sphere with minimal energy is a long‐standing problem in and outside the field of mathematics. This paper considers a novel energy function that arises naturally from statistics and combinatorial optimization, and studies its theoretical properties. Our result solves both the exact optimal spherical point configurations in certain cases and the minimal energy asymptotics under general assumptions. Connections between our results and the L1‐principal component analysis and quasi‐Monte Carlo methods are also discussed. [ABSTRACT FROM AUTHOR]

This paper presents an improved version of the Vantage Point Bees Algorithm (VPBA‐II), which is implemented to solve the Travelling Salesman Problem. The Vantage Point Tree has been used to produce initial tour solutions and also as a global search operator of the proposed algorithm to find the minimal Hamiltonian tour of the Travelling Salesman Problem. VPBA‐II is tested on 15 different benchmark datasets from TSPLIB, particularly for the high dimensional combinatorial solution spaces, and it outperformed the basic Bees Algorithm. The composition of the local search operators combined with Vantage Point Tours perform better except one dataset and achieved optimum results according to best‐known solutions of Travelling Salesman Problem as a best‐case scenario. The experiments prove that Vantage Point Tour construction could be used as initialization and global search operator to improve the basic Bees Algorithm performance on the combinatorial domains. [ABSTRACT FROM AUTHOR]

Minimizing the amount of spill code is still an open problem in code generation and optimization. The amount of spill code depends on both the register allocation algorithm and the pre-allocation instruction scheduling algorithm that controls the register pressure. In this paper, we focus on the impact of pre-allocation instruction scheduling on the amount of spill code. Many heuristic techniques have been proposed to do instruction scheduling with the objective of minimizing register pressure and consequently the amount of spill code. However, the performance of these heuristic techniques has not been studied relative to optimality on real large-scale programs. In this paper, we present an experimental study that evaluates the performance of several pre-allocation scheduling heuristics. The evaluation involves computing an experimental lower bound on the size of gap between each heuristic's performance and optimal performance. We also propose a simple heuristic technique based on a specific permutation of two basic priority schemes and experimentally evaluate the performance of this technique compared with other heuristics, including the heuristics implemented in the LLVM open-source Compiler. The evaluation is carried out by running SPEC CPU2006 on real x86-64 hardware and measuring both the amount of spill code and the execution time. The results of our study show that the proposed heuristic technique gives better overall performance than LLVM's best heuristic on x86-64, although it produces slightly more spilling. The proposed heuristic has better overall performance, because it achieves a better balance between register pressure and instruction-level parallelism (ILP). This result shows the importance of ILP in pre-allocation scheduling even on out-of-order machines. Furthermore, the results of the study show that there is a large gap between the performance of any of the studied heuristics and optimal performance; even the best heuristic in the study produces significantly more spill code than the optimal amount. This experimental result quantifies the intuitive belief that it is unlikely to find a heuristic that works well in all cases, thus showing the need for more rigorous solutions using combinatorial approaches. The paper discusses the challenges and complexities that are involved in developing such rigorous solutions. Copyright © 2014 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Abstract: While monolithic satellite missions still pose significant advantages in terms of accuracy and operations, novel distributed architectures are promising improved flexibility, responsiveness, and adaptability to structural and functional changes. Large satellite swarms, opportunistic satellite networks or heterogeneous constellations hybridizing small‐spacecraft nodes with high‐performance satellites are becoming feasible and advantageous alternatives requiring the adoption of new operation paradigms that enhance their autonomy. While autonomy is a notion that is gaining acceptance in monolithic satellite missions, it can also be deemed an integral characteristic in Distributed Satellite Systems (DSS). In this context, this paper focuses on the motivations for system‐level autonomy in DSS and justifies its need as an enabler of system qualities. Autonomy is also presented as a necessary feature to bring new distributed Earth observation functions (which require coordination and collaboration mechanisms) and to allow for novel structural functions (e.g., opportunistic coalitions, exchange of resources, or in‐orbit data services). Mission Planning and Scheduling (MPS) frameworks are then presented as a key component to implement autonomous operations in satellite missions. An exhaustive knowledge classification explores the design aspects of MPS for DSS, and conceptually groups them into: components and organizational paradigms; problem modeling and representation; optimization techniques and metaheuristics; execution and runtime characteristics and the notions of tasks, resources, and constraints. This paper concludes by proposing future strands of work devoted to study the trade‐offs of autonomy in large‐scale, highly dynamic and heterogeneous networks through frameworks that consider some of the limitations of small spacecraft technologies. [ABSTRACT FROM AUTHOR]

Summary: The primary objective of our research work is to enhance the prediction of the quality of a component‐based software system and to develop an artificial neural network (ANN) model for the system reliability optimization problem. In this paper, we introduced the ANN‐supported Teaching‐Learning Optimization by transforming constraints to objective functions. Artificial neural network techniques are found to be powerful in the modeling software package quality metrics compared with the ancient statistical techniques. Therefore, by using the neural network, the quality characteristics of software components of the proposed work are predicted. A nonlinear differentiable transfer function of ANN used in the proposed approach is hyperbolic tangent sigmoid. A new efficient optimization methodology referred to as the Teaching‐Learning–based Optimization is proposed in this paper to optimize reliability and different cost functions. The weight values of the network are then adjusted consistent with a proposed optimization rule, therefore minimizing the network error. The proposed work is implemented in MATLAB by using the Neural Network Toolbox. The proposed work provides improved performance in terms of sensitivity, precision, specificity, negative predictive value, fall‐out or false positive rate, false discovery rate, accuracy, Matthews correlation coefficient, and rate of convergence. [ABSTRACT FROM AUTHOR]

When participating in demand response, the industrial adjustable load has the advantages of large capacity, high benefit, and easy management compared with commercial and residential loads. However, the stage of the production process is strongly coupled with the power consumption process, especially in the steel industry. Here, a multi‐objective optimization model for the optimal scheduling of hot rolling load considering the actual production operation conditions was proposed, the model was abstracted into a vehicle routing problem (VRP) ,which is a typical combinatorial optimization problem.To minimize the cost of electricity and the risk of delivery order default, this paper considered the jump penalty value between adjacent slabs simultaneously, constructed an integrated scheduling model of hot rolling shop scheduling and power demand response, and designed a multi‐objective production scheduling algorithm based on NSGA‐II to solve the problem. The results showed that the proposed method can realize the reasonable distribution of production load under the constraints of electricity price and production. [ABSTRACT FROM AUTHOR]

In recent years, the field of combinatorial optimization has witnessed a true tsunami of 'novel' metaheuristic methods, most of them based on a metaphor of some natural or man-made process. The behavior of virtually any species of insects, the flow of water, musicians playing together - it seems that no idea is too far-fetched to serve as inspiration to launch yet another metaheuristic. In this paper, we will argue that this line of research is threatening to lead the area of metaheuristics away from scientific rigor. We will examine the historical context that gave rise to the increasing use of metaphors as inspiration and justification for the development of new methods, discuss the reasons for the vulnerability of the metaheuristics field to this line of research, and point out its fallacies. At the same time, truly innovative research of high quality is being performed as well. We conclude the paper by discussing some of the properties of this research and by pointing out some of the most promising research avenues for the field of metaheuristics. [ABSTRACT FROM AUTHOR]

Video camera sensor networks (VCSN) has numerous applications in smart cities, including vehicular networks, environmental monitoring, and smart houses. Scheduling of video camera sensor networks (VCSN) can reduce the computational complexity, increase energy efficiency, and enhance throughput for the Internet of things (IoT) systems. In this paper, we apply the iterative low‐complexity probabilistic evolutionary method for scheduling video cameras to maximize throughput in VCSNs for IoT systems. Scheduling of video cameras in VCSNs to maximize throughput is a combinatorial optimization problem whose computational complexity increases exponentially with the increase in the number of video cameras. We propose an iterative probabilistic method named as cross‐entropy optimization (CEO), which is an evolutionary algorithm. The combinatorial optimization problems can be solved using the CEO which is a generalized Monte Carlo technique. The proposed method updates its selected population (video cameras) at each iteration based on the Kullback Leibler (KL) distance/divergence. The KL distance/divergence is minimized using the probability distribution obtained from the learned from the group of selected samples of better solutions found in the previous iterations. The effectiveness of the CEO is verified in terms of optimality and simplicity through simulations. In addition, the results of the CEO are better than the suboptimal algorithms (ie, best norm‐based algorithm, genetic algorithm, and capacity upper‐bound–based greedy algorithm) and maximum of 2%‐3% deviation from the exhaustive search (optimal) with less complexity. The trade‐off between CEO and optimal is the computational complexity. [ABSTRACT FROM AUTHOR]

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

We review recent literature pertaining to the maritime inventory routing problem (MIRP), a stimulating, albeit niche, subclass of vendor‐managed inventory problems. MIRPs deal with optimally distributing products with a (typically heterogeneous) vessel fleet between production and consumption ports with inventory tracking and inventory limits. We present two mixed‐integer linear programming models for the MIRP—one based on discrete time, the other based on continuous time—and we discuss the advantages and disadvantages of each of the two modeling approaches. In surveying more than 50 papers spanning the decade 2013–2023, we investigate MIRP variants from many different applications and discuss how these have been modeled and solved. Our purpose is to provide a comprehensive overview of state‐of‐the‐art MIRP research published in this period, collated along multiple dimensions. In addition to providing information about available test instances, we highlight recent trends and interesting avenues for future research. As such, we believe this survey will be useful to students, researchers, and practitioners in this domain. [ABSTRACT FROM AUTHOR]

Lead pipe remediation budgets are limited and ought to maximize public health impact. This goal implies a nontrivial optimization problem; lead service lines connect water mains to individual houses, but any realistic replacement strategy must batch replacements at a larger scale. Additionally, planners typically lack a principled method for comparing the relative public health value of potential interventions and often plan projects based on nonhealth factors. This paper describes a simple process for estimating child health impact at a parcel level by cleaning and synthesizing municipal datasets that are commonly available but seldom joined due to data quality issues. Using geocoding as the core record linkage mechanism, parcel‐level toxicity data can be combined with school enrollment records to indicate where young children and lead lines coexist. A harm metric of estimated exposure‐years is described at the parcel level, which can then be aggregated to the project level and minimized globally by posing project selection as a 0/1 knapsack problem. Simplifying for use by nonexperts, the implied linear programming relaxation is solved with the greedy algorithm; ordering projects by benefit cost ratio produces a priority list that planners can then consider holistically alongside harder to quantify factors. A case study demonstrates the successful application of this framework to a small U.S. city's existing data to prioritize federal infrastructure funding. [ABSTRACT FROM AUTHOR]

The Distance Geometry Problem (DGP) seeks to find positions for a set of points in geometric space when some distances between pairs of these points are known. The so‐called discretization assumptions allow us to discretize the search space of DGP instances. In this paper, we focus on a key subclass of DGP, namely the Discretizable Molecular DGP, and study its associated graph vertex ordering problem, the Contiguous Trilateration Ordering Problem (CTOP), which helps solve DGP. We propose the first constraint programming formulations for CTOP, as well as a set of checks for proving infeasibility, domain reduction techniques, symmetry breaking constraints, and valid inequalities. Our computational results on random and pseudo‐protein instances indicate that our formulations outperform the state‐of‐the‐art integer programming formulations. [ABSTRACT FROM AUTHOR]

We consider a coloring as a function that assigns a color to a vertex, regardless of the color of its neighbors. In this sense, a coloring is said to be convex if every set of all same colored vertices induces a connected subgraph. The Convex Recoloring Problem finds the minimum number of recolored vertices needed to turn a coloring convex. This problem is most commonly studied considering trees due to its origins in Computational Biology, but in this paper, we focus on general graphs. We propose a heuristic based on the Greedy Randomized Adaptive Search Procedure to solve the problem. We present computational experiments for our heuristic and compare it to an Integer Linear Programming (ILP) model from the literature. In these experiments, our heuristic recolored at most one vertex more than the ILP model, and it was also able to give better solutions when the ILP model was unable to find the optimal solution within the time limit. We also introduce a set of benchmark instances for the problem. [ABSTRACT FROM AUTHOR]

Reward-based scheduling of real-time systems of periodic, preemptable, and independent tasks with mandatory and optional parts in homogeneous multiprocessors with energy considerations is a problem that has not been analyzed before. The problem is NP-hard. In this paper, a restricted migration schedule is adopted in which different jobs of the same task may execute in different processors and at different power modes but no migration is allowed after the job has started its execution. An objective function to maximize the performance of the system considering the execution of optional parts, the benefits of slowing down the processor, and a penalty for changing the operation frequency is introduced together with a set of constraints that guarantee the real-time performance of the system. Different algorithms are proposed to find a feasible schedule maximizing the objective function and are compared using synthetic systems of tasks generated following guidelines proposed in previous papers. [ABSTRACT FROM AUTHOR]

To monitor electrical activity throughout the power grid and mitigate outages, sensors known as phasor measurement units can installed. Due to implementation costs, it is desirable to minimize the number of sensors deployed while ensuring that the grid can be effectively monitored. This optimization problem motivates the graph theoretic power dominating set problem. In this paper, we propose a method for computing minimum power dominating sets via a set cover IP formulation and a novel constraint generation procedure. The set cover problem's constraints correspond to neighborhoods of zero forcing forts; we study their structural properties and show they can be separated with delayed row generation. In addition, we offer several computation enhancements which be be applied to our methodology as well as existing methods. The proposed and existing methods are evaluated in several computational experiments. In many of the larger test instances considered, the proposed method exhibits an order of magnitude runtime performance improvement. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of multirobot search for a stationary object in an a priori known environment. Two variants of the problem are studied given the working environment represented by a graph. The first variant is an extension of the traveling deliveryman problem for multiple vehicles, while the second variant is a generalization of the graph search problem. A novel algorithm is presented to solve both problems, which is based on a combination of greedy randomized adaptive search procedure with variable neighborhood descent. A set of experimental evaluations were conducted over the benchmark instances derived from the TSPLIB library. For both problems, the results obtained show that the proposed approach is comparable to state‐of‐the‐art heuristics. Moreover, for problems of a few hundred vertices, the solution times suggest that the approach is suitable for online decision‐making in search and rescue. [ABSTRACT FROM AUTHOR]

In market basket analysis (MBA), the goal is to understand human behavior to maximize sales. A clear behavior is buying correlated items. As a consequence, the determination of a set of items with a high correlation with others is a valuable tool for MBA. In this work, we address a combinatorial optimization problem with valuable applications to MBA, especially in marketing and product placement. The focus will be on the combinatorial problem and not on specific applications. For any given undirected graph G=(V,E) (where the nodes are items and the edges represent correlation), we aim to find the clique C⊆V such that the number of edges shared between C and V−C is maximized. This problem is known in the literature as the max cut‐clique (MCC) problem. We can generalize this problem by considering the weights associated with each edge. In this context, we are interested in finding the clique C⊆V such that the weighted sum associated with each edge shared between C and V−C is maximized. The weighted version of the MCC problem is known as the maximum edge‐weight neighborhood clique (MEWNC) problem. The main contributions of this paper are threefold. First, the computational complexity of both the MCC and MEWNC problems is established. Specifically, we prove that the MCC and MEWNC problems belong to the class of NP‐complete problems. Second, an exact integer linear programming (ILP) formulation for the MEWNC problem is proposed. Third, a full greedy randomized adaptive search procedure/variable neighborhood descent methodology enriched with a tabu search is here developed, where the main components are novel neighborhood structures and a restricted candidate list that trade greediness for randomization in a multistart fashion. A dynamic tabu list considers a bounding technique based on the previous analysis. Finally, a fair comparison between our hybrid algorithm and a globally optimal solution using the ILP formulation confirms that a globally optimal solution is found by our heuristic for graphs with hundreds of nodes, but it is more efficient than the exact solution in terms of time and memory requirements. [ABSTRACT FROM AUTHOR]

In this paper a model‐based heuristic approach for a typical distribution problem is presented. In order to be cost‐effective, the distribution process for many customers, each of them with orders of considerable volume, should be dealt with like a combination of two well‐known problems: the vehicle routing problem (VRP) and the container loading problem (CLP). This paper studies a particular integration of these two problems called the vehicle routing and loading problem (VRLP). The VRLP is an operational problem that must be solved daily by many production and distribution companies. Like the two original problems (VRP and 3D‐CLP), the VRLP is NP‐hard. In this work, regardless of the complexity of this problem, a mixed integer linear programming (MILP) model that characterizes the VRLP with time windows is presented and it is also used to solve the problem optimally. Then, a model‐based heuristic that improves the computational time, when bigger instances need to be solved, is also presented. In order to prove the viability of the approach and the developed MILP model, tests with the benchmark instances of the VRLP were made and the results compared with other published works. Despite the long computational time needed to solve bigger instances, the VRLP model could be used to compute optimal solutions or at least good lower bounds, in order to have a base of comparison when nonexact methods are applied to the VRLP. [ABSTRACT FROM AUTHOR]

This paper considers the rectangular packing problem and investigates the effectiveness of the neighborhood cultivation genetic algorithm (NCGA). NCGA, which we proposed, is a new algorithm in which the unique mechanism of neighborhood crossover is combined with effective mechanisms for search in multi-objective GA proposed in the past. The effectiveness of the proposed method in typical test problems has already been investigated with satisfactory results in past studies. The rectangular packing problem, on the other hand, is applied to floor planning, such as chip area minimization in large-scale integrated circuits. It is a kind of discrete combinatorial problem in which it is known that the search is difficult and a very long time is required until the solution is obtained. This paper formulates the rectangular packing problem as a multi-objective problem with the vertical and horizontal lengths of the placement configuration as the objectives. The sequence-pair is used as the block placement representation, and PPEX is used as the crossover procedure. Using these processes, the effectiveness of NCGA is investigated. For comparison, three other methods—NSGA-II, SPEA2, and non-NCGA (NCGA without neighborhood crossover)—are investigated. © 2007 Wiley Periodicals, Inc. Electron Comm Jpn Pt 2, 90(12): 111–120, 2007; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecjb.20427 [ABSTRACT FROM AUTHOR]

Recently, simulations are increasingly important in the design and development of high-speed transmission circuits, and simulations of high-precision transmission lines based on actual measurements are essential. Therefore, in this paper, the authors propose a method of determining transmission line characteristics for implementing high-precision transmission simulations from transmission line measurement results. The authors had previously proposed a method of creating an equivalent circuit model from transmission line characteristics. Combining that method with the method proposed in this paper enables high-precision simulations based on actual measurements to be performed with a circuit simulator such as SPICE according to a procedure that (1) measures transmission lines, (2) determines transmission line characteristics, and (3) creates an equivalent circuit model. The method that is proposed in this paper for determining transmission line characteristics has two features: (1) fitting that simultaneously uses actually measured frequency characteristics and time-based response waveform and (2) fitting that uses multi-objective optimization. Specifically, the authors apply multi-objective optimization using a genetic algorithm to simultaneously fit multiple sets of frequency characteristics and time-based response waveforms. As a result, trial-and-error with weightings among the characteristics is unnecessary and fitting is automated. The results when the proposed method was actually verified by using micro-strip lines clearly showed that a high-precision simulation could be performed with respect to both the frequency and time axes. © 2007 Wiley Periodicals, Inc. Electron Comm Jpn Pt 2, 90(8): 8–17, 2007; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecjb.20343 [ABSTRACT FROM AUTHOR]

This paper examines electric field optimizations at the joint of power cables by using evolution strategy [(1+1)-ES, (µ+λ)-ES] and genetic algorithm which are so- called evolutionary calculation methods. The object of the paper is to minimize the electric field strength on the inner curved electrode under the constraint that the electric field strength along the interface between the two different insulators should be below the permissible value. The surface charge method that provides accurate solutions on the boundaries for the multilayer substances with a relatively small number of elements is employed for the calculation of the electric field distribution. Three evolutionary calculation methods are employed for the optimization method. Because these methods employ mutation and rearrangement (cross-over) processes, the shape design can be performed widely and locally. As a result, each method can reduce the electric field strength on the inner curved electrode while the electric field strength along the interface was kept below the permissible value. The search results of each optimization method were compared and (µ+λ)-ES was found to have the best performance of the three methods. © 2005 Wiley Periodicals, Inc. Electr Eng Jpn, 150(4): 44–53, 2005; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/eej.10287 [ABSTRACT FROM AUTHOR]

With an explosive growth of the datacenter research, virtual machines migration aiming at optimization of virtual machines placement is a major technology of improving power efficiency and resource utilization in the datacenter. While recent studies have primarily focused on maximizing resource utilization or minimizing migration cost separately, there has been little attention on jointly taking these two objectives into account. In this paper, we present the optimization model taking minimum migration cost and maximum resource utilization with multi-resources such as storage, bandwidth, CPU, and disk space into account. The optimization of our proposed model is non-deterministic polynomial-time hard. According to the model, we present an efficient approximate algorithm based on bin packing algorithm, called MinCost, to resolve our model and obtain a near-optimal solution. Finally, the simulation results in this paper show that our model and algorithm is efficient. Copyright © 2015 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Travelling salesman problem (TSP) is one of the most famous problems in graph theory, as well as one of the typical nondeterministic polynomial time (NP)‐hard problems in combinatorial optimization. Reinforcement learning (RL) has been widely regarded as an effective tool for solving combinatorial optimization problems. This paper attempts to solve the TSP problem using different reinforcement learning algorithms and evaluated the performance of three RL algorithms (Q‐Learning, SARSA, and Double Q‐Learning) under different reward functions, ε‐greedy decay strategies, and running times. A comprehensive analysis and comparison of the three algorithms mentioned above were conducted in the experiment. First, the experimental results indicate that the Double Q‐Learning algorithm is the best algorithm. Among the eight TSP instances, the Double Q‐Learning algorithm outperforms the other two algorithms in five instances. Additionally, it has shorter runtimes compared to the SARSA algorithm and similar runtimes to the Q‐Learning algorithm across all instances. Second, upon analysing the results, it was found that using the 1/dij$1/d_{ij}$ reward strategy contributes to obtaining the best results for all algorithms. Among the 24 combinations of 3 algorithms and 8 instances, 17 combinations achieved the best results when the reward strategy was set to 1/dij$1/d_{ij}$. [ABSTRACT FROM AUTHOR]

An effective way to improve distribution system reliability is to place switches and protective equipment in the optimal location. Commonly, in the placement problem, the use of equipment in the designated location is assumed to be possible. But in practice, to establish protection coordination between the equipment, it is necessary to remove or relocate some of the equipment. This paper aims to increase distribution companies' profits and reduce customer interruption costs through a feasible solution. A new hybrid method for equipment placement has been proposed that simultaneously solves the protection coordination problem. While determining the optimal number and location of reclosers and sectionalizers, the proposed method ensures protection coordination between equipment (new and existing devices). Furthermore, to achieve a more realistic and accurate model, factors such as equipment malfunction, fault types (transient and permanent), and the relationship between these faults have been carefully considered to formulate the proposed method. In this method, to solve the optimization problems related to equipment placement and protection coordination, genetic algorithm, and linear programming in MATLAB software have been used, respectively. A real‐life distribution network has been utilized to evaluate the proposed method, and the results show the capability and robustness of this method. [ABSTRACT FROM AUTHOR]

The paper describes the reliability‐based optimization of a TT‐shaped precast roof girder produced in Austria. An extensive experimental programme was performed using laboratory specimens to gain information on the mechanical fracture parameters of the utilized concrete. Subsequently, destructive shear tests were performed on scaled‐down and full‐scale girders under laboratory conditions. The experiments helped in the development of an accurate numerical model of the girder. The developed model was consequently used for the advanced stochastic analysis of structural response, followed by reliability‐based optimization, which was used to maximize the shear and bending capacities of the girder and minimize production cost under defined reliability constraints. The enormous computational requirements of the double‐loop optimization approach were significantly reduced by the utilization of an artificial neural network‐based surrogate model instead of the original nonlinear finite element model of the optimized structure. [ABSTRACT FROM AUTHOR]

Planning of location area (LA) in cellular networks plays a vital role in utilizing the resources efficiently and economically. Location update and paging costs directly affect the cost to the service provider. When the size of the Mobile Switching Centre (MSC) is large, the paging cost becomes maximum. Though, no location update is required for this case. On the contrary, paging cost shoots high if each cell forms individual LA, but in this case, location update cost shoots to the maximum value. Therefore, deducing the network to the optimal amount of LA's is an intractable combinatorial optimization problem. In this paper, we intend to optimize the partitions of the MSC service area into an optimal number of LA, to curtail the total location management cost. We propose a novel scheme bearing in mind cell attributes of the network to deduce an optimum number of location areas, leading to minimum cost per call. It is revealed by the results of this work, attained after simulating the scenario on MATLAB 2018a that Cell Attributes Based Algorithm is a very promising scheme for cellular networks, and it outperforms the existing algorithms in a practical scenario. [ABSTRACT FROM AUTHOR]