Search

We consider the incremental subgradient algorithm employing dynamic step sizes for minimizing the sum of a large number of component convex functions. The dynamic step size rule was firstly introduced by Goffin and Kiwiel [Math. Program., 1999, 85(1): 207-211] for the subgradient algorithm, soon later, for the incremental subgradient algorithm by Nedic and Bertsekas in [SIAM J. Optim., 2001, 12(1): 109-138]. It was observed experimentally that the incremental approach has been very successful in solving large separable optimizations, and that the dynamic step sizes generally have better computational performance than others in the literature. In the present paper, we propose two modified dynamic step size rules for the incremental subgradient algorithm and analyse the convergence properties of them. At last, the assignment problem is considered and the incremental subgradient algorithms employing different kinds of dynamic step sizes are applied to solve the problem. The computational experiments show that the two modified ones converges dramatically faster and stabler than the corresponding one in [SIAM J. Optim., 2001, 12(1): 109-138]. Particularly, for solving large separable convex optimizations, we strongly recommend the second one (see Algorithm 3.3 in the paper) since it has interesting computational performance and is the simplest one.

Multi-target tracking (MTT) is an important component of situation-awareness based on the Internet of Things (IoT). Existing algorithms mainly focus on tracking based on conventional measurements, e.g., bearings or ranges. However, measurement parameter estimations are considered in isolation, limiting the accuracy and resolution of MTT, and the related data association is an NP-hard multi-dimensional assignment problem. In this paper, we develop a new one-step MTT algorithm based on a novel dynamic Bayesian network (DBN), i.e, DBNMTT. The new MTT algorithm directly infers target states from the raw measurement data by fusing the array signal model, the signal propagation model, and the motion model. In this new DBNMTT framework, we treat target states and conventional measurements such as bearings and target energies as hidden random variables. The posterior joint probability optimization problem is translated into the problem of graphical model learning. In this way, we can improve the accuracy and resolution of MTT and convert the NP-hard data association problem to a hidden variable learning problem. For non-conjugate models in the DBNMTT, we develop a novel reparameterized approximation variational inference (ReAVI) approach to solve the learning problem. The ReAVI converts non-conjugate models to conjugate models with new parameters and reuses the mean-field algorithm. The performance of our proposed new MTT method, namely DBNMTT-ReAVI, is analyzed on extensive simulations in challenging scenarios. The simulation results show that the DBNMTT-ReAVI algorithm is superior to conventional measurement based MTT algorithms in several aspects including the success probability, the convergence, the resolution, and the accuracy.

The gate assignment problem (GAP) aims at assigning gates to aircraft considering operational efficiency of airport and satisfaction of passengers. Unlike the existing works, we model the GAP as a bi-objective constrained optimization problem. The total walking distance of passengers and the total robust cost of the gate assignment are the two objectives to be optimized, while satisfying the constraints regarding the limited number of flights assigned to apron, as well as three types of compatibility. A set of real instances is then constructed based on the data obtained from the Baiyun airport (CAN) in Guangzhou, China. A two-phase large neighborhood search (2PLNS) is proposed, which accommodates a greedy and stochastic strategy (GSS) for the large neighborhood search; both to speed up its convergence and to avoid local optima. The empirical analysis and results on both the synthetic instances and the constructed real-world instances show a better performance for the proposed 2PLNS as compared to many state-of-the-art algorithms in literature. An efficient way of choosing the tradeoff from a large number of nondominated solutions is also discussed in this article. WOS:000696078900016 31899446 Q1

First, we give a detailed review of two algorithms that solve the minimization case of the assignment problem, the Bertsekas auction algorithm and the Goldberg & Kennedy algorithm. It was previously alluded that both algorithms are equivalent. We give a detailed proof that these algorithms are equivalent. Also, we perform experimental results comparing the performance of three algorithms for the assignment problem: the $$\epsilon $$ -scaling auction algorithm, the Hungarian algorithm and the FlowAssign algorithm. The experiment shows that the auction algorithm still performs and scales better in practice than the other algorithms which are harder to implement and have better theoretical time complexity.

Multidetection (MD) systems are characterized by multiple observation modes (OMs), and hence, simultaneously produce multiple measurements for each target. The key challenge in exploiting MD systems for multitarget tracking (MTT), compared to single-detection (SD) systems, is the significant amount of extra computational burden involved in order to solve the resulting multidimensional assignment problem among measurements, targets, and OMs. This article presents a novel computationally efficient MTT framework for MD systems, wherein the multitarget state is modeled as a random finite set (RFS), and a bank of OM-dependent MTT RFS filters with SD model are employed to recursively provide OM-dependent posteriors. The latter, which contain both real and false targets, are then suitably fused so as to enhance consensus on the true targets while weakening trust on the existence of the false ones. In this way, the computational complexity is significantly reduced compared to existing MTT algorithms with the MD model. Two representative RFS filters, i.e., unlabeled probability hypothesis density (PHD) and labeled multi-Bernoulli (LMB), are considered in the proposed framework and the computational complexity of the resulting MD MTT algorithms is analyzed. Performance of the proposed approach is assessed by simulation experiments in both over-the-horizon-radar (OTHR) and single-frequency-network passive radar (SFN-PR) MTT applications.

An improved parallel block coordinate descent (iPBCD) algorithm for solving the user equilibrium traffic assignment problem is proposed. The iPBCD algorithm is developed based on the parallel block...

Step size determination (also known as line search) is an important component in effective algorithmic development for solving the traffic assignment problem. In this paper, we explore a novel step size determination scheme, the Barzilai-Borwein (BB) step size, and adapt it for solving the stochastic user equilibrium (SUE) problem. The BB step size is a special step size determination scheme incorporated into the gradient method to enhance its computational efficiency. It is motivated by the Newton-type methods, but it does not need to explicitly compute the second-order derivative. We apply the BB step size in a path-based traffic assignment algorithm to solve two well-known SUE models: the multinomial logit (MNL) and cross-nested logit (CNL) SUE models. Numerical experiments are conducted on two real transportation networks to demonstrate the computational efficiency and robustness of the BB step size. The results show that the BB step size outperforms the current step size strategies, i.e., the Armijo rule and the self-regulated averaging scheme.

We present a new algorithm for solving the dense linear (sum) assignment problem and an efficient, parallel implementation that is based on the successive shortest path algorithm. More specifically, we introduce the well-known epsilon scaling approach used in the Auction algorithm to approximate the dual variables of the successive shortest path algorithm prior to solving the assignment problem to limit the complexity of the path search. This improves the runtime by several orders of magnitude for hard-to-solve real-world problems, making the runtime virtually independent of how hard the assignment is to find. In addition, our approach allows for using accelerators and/or external compute resources to calculate individual rows of the cost matrix. This enables us to solve problems that are larger than what has been reported in the past, including the ability to efficiently solve problems whose cost matrix exceeds the available systems memory. To our knowledge, this is the first implementation that is able to solve problems with more than one trillion arcs in less than 100 hours on a single machine.

Although integrated process planning and scheduling (IPPS) problem is studied extensively as scheduling with due-date assignment problem (SWDDA) in the literature, there are only a few studies on integration of these three manufacturing functions which are process planning, scheduling, and due-date assignment. Since outputs of upper stream functions effect downstream functions and higher integration gives a better global performance, it is better to integrate these three functions. In this study integration of process planning and earliest due-date scheduling (EDD) with due-date assignment is studied using hybrid evolutionary strategies (RS/ES) and hybrid simulated annealing algorithms (RS/SA). Ordinary solutions (OS), random search (RS) solutions, evolutionary strategies (ES) solutions, and simulated annealing (SA) solutions are compared with each other and hybrid solutions of ES and SA, with RS. According to the results, higher integration found better and best results are obtained with the highest integration level. ES and SA methods gave better results compared to the RS and OS, and RS/ES and RS/SA techniques were found promising search techniques.

The intensive deployment of cells in a wireless communication system may significantly increase the network capacity, but it may cause more complex and severe inter-cell interference. In order to effectively coordinate the interference, terminals in different cells are matched with the purpose of avoiding severe interference, called terminal matching, and a fast method is proposed in this article for multi-cell scenarios. By constructing a fully weighted graph of all the base stations with interferences as the weights, the minimum spanning tree method in graph theory is used to identify the coordination relationship among all the cells, and multiple coordination pairs can be obtained. For each coordination pair, terminal matching is modeled as a two-dimensional assignment problem between the coefficients after wavelet decomposition and Hungarian algorithm is applied to obtain their optimal match. Wavelet transform is used to extract the scale transformation coefficients describing the terminal features in each single cell, so that the optimization process can be accelerated because the amount of these coefficients is dramatically reduced after several layers of wavelet decomposition. The minimum Hamilton path method in graph theory is used to rank the terminals in each cell based on their key features, so that the coefficients lose as minimum useful information as possible during wavelet decomposition. Simulation results show that the performance of the proposed method reaches approximately the optimal matching obtained by traversing all the coordination possibilities among all the cells. Compared with the simulated annealing algorithm, the performance loss in terms of system spectral efficiency is only about 2%, but the proposed method requires only less than one thousandth of its computational time.

In this paper, we explore the problem of routing, modulation and spectrum assignment (RMSA) for advance reservation (AR) requests in elastic optical networks (EONs), with the objective to further reduce the blocking probability and improve the spectrum utilization. On the one hand, we propose a minimum resource consumption routing policy (MRC) for leaving more free resources for future requests. On the other hand, we introduce a two-dimensional (2D) path resource model, in which each AR request can be transformed into a rectangle block whose length and width are related to request bandwidth and request duration respectively. Therefore, the spectrum assignment problem of AR requests is simplified to the two-dimensional rectangle packing problem. Furthermore, we design several factors to evaluate the two-dimensional fragmentation caused by a rectangle packing operation, where we consider the fragmentation situation in the rectangle block neighborhood for the first time. Based on these factors, we propose a two-dimensional fragmentation-aware spectrum assignment strategy (2D-FA). Through the combination of MRC and 2D-FA, we propose a novel RMSA algorithm named MRC-2D-FA for dynamically provisioning AR requests in EONs. Simulation results show that MRC-2D-FA can achieve lower bandwidth blocking probability and higher spectrum utilization compared with several well-performed benchmark algorithms.

This research proposes a Multi-swarm and Discrete Firefly Algorithm (MDFA) to deal with the component sequencing problem (CSP) and feeder assignment problem (FAP) simultaneously for a multi-head gantry surface-mounted technology (SMT) machine. The MDFA is an improved version of standard Firefly Algorithm (FA) which is a kind of nature-inspired and population-based metaheuristic. To our best knowledge, the FA has never been used to deal with the CSP and FAP simultaneously for the multi-head gantry SMT machine. Empowered by novel features such as multiple swarms as well as adaptive and discrete moving step, in addition to using an exploration-to-exploitation strategy, the MDFA is found capable of searching a solution space effectively. To investigate its effectiveness, the MDFA has been compared to the standard FA, particle swarm optimization (PSO), and genetic algorithm (GA). The experimental results show that the MDFA outperforms the others in terms of assembly time.

Assigning commercial flights to available airport gates can have a major impact on the efficiency of flight schedules as well as on the level of passenger satisfaction with the service. These assignments also depend on the service requirements of flights and the capacity of stand facilities. Unexpected changes also called perturbations, like those due to air traffic delays, severe weather conditions, or equipment failures, may disrupt the initial assignments and increase the difficulty of maintaining smooth operations, which will detrimentally affect customer satisfaction. The provision of solutions which reduce the potential detrimental effect of perturbations in the stands already assigned on the day of operation is desirable and some approaches are presented here, and compare between them to help identify their performance and trends.

State assignment is the most critical step in the synthesis and optimization of sequential circuits as it significantly impacts sequential circuits area and power. Due to the high complexity of the state assignment problem and the ineffectiveness of existing deterministic algorithms in generating good solutions, evolutionary algorithms can be employed to obtain more effective state assignment solutions. In this paper, we propose a probabilistic tabu search (PTS) state assignment algorithm that is employed for the optimization of area and power of sequential circuits. The proposed algorithm is based on tabu search with the addition of exploiting code swap probabilities to prune the search space more effectively. Code swap probabilities are updated dynamically during the execution of the algorithm in such a way that code swaps that result in relatively inferior solutions will be assigned lower probabilities while those that result in good solutions will be assigned higher probabilities. In addition, tabu list size is changed dynamically during execution to help the algorithm get out of local minima. Based on experimental results, we show that the proposed PTS state assignment algorithm is more effective than all existing state assignment algorithms as it generates state assignment solutions with significantly lower area and power.

Mobile crowdsensing has become a new way to perceive and collect information due to the widespread of smart devices. In this paper, we study the task assignment problem in mobile crowdsensing systems, which is aimed to reducing the average and largest makespan of all tasks. We consider scenarios where task requester needs the help of mobile users for task completion when they encounter directly or through AP cloud (i.e., several APs connected via wired/wireless links) in an opportunistic manner. We describe the mobile crowdsensing system and formulate the problems under study. We first derive the conditional expected encountering time between requester and different users by jointly considering the opportunities via direct encountering and indirect encountering via AP cloud. Then we propose an AP-assisted average makespan sensitive online task assignment (AP-AOTA) algorithm and an AP-assisted largest makespan sensitive online task assignment (AP-LOTA) algorithm. We present detailed design for both algorithms. We deduce the computational complexities of both algorithms to be O(mn2), where m represents the number of tasks and n represent the number of users. We conduct simulations on a real trace data set and a synthetic trace data set and the results show that our proposed algorithms significantly outperform existing work.

The Routing and Spectrum Assignment (RSA) problem is NP-Hard so searching the entire problem space is not applicable. Many decomposition algorithms rely on reducing the search space in the routing space and applying heuristics algorithm in the spectrum assignment sub-problem. This is not necessarily a right solution as the ignored routing tables may lead to a better solution when they are used later as input to the Spectrum Assignment sub-problem. In this paper, we develop a new recursive decomposition approach for the RSA problem in optical networks. At the core of our approach is a new recursive branch and-bound procedure for carrying out an exhaustive search of the routing space in a scalable manner. This recursion effectively decouples the routing from the spectrum assignment part of the problem. Sequential generation of the full set of routing tables requires huge memory and very large processing time. Alternatively, our approach deploys multi-core architectures to generate the routing tables in parallel using OpenMP. Experimental results indicate that our recursive algorithm is quite efficient in searching the entire routing space for topologies representing large-scale wide area networks. Importantly, the decomposition may be more generally applied to any network design problem whose solution involves a search over both a routing and a resource allocation space. The main contributions for this paper are that we are able to generate all the search space in parallel in less than 1 min for 32-nodes network. Secondly, we are able to investigate all the routing tables, eliminate most of the search space, and select the promising routing tables that are proven to lead to a better solution in the Spectrum Assignment Sub-Problem

Blood and its products, in some cases, are the only vital and sanative medicine for the patients. Each donated blood unit is a valuable asset to protect the patients’ lives, and it should be avoided waste and non-optimal consumption. The assignment of blood and its products to hospitals is one of assignment problems, in which finding the optimal solution can lead to a reduction in mortality and waste of expenditure. In this research, a new model for the assignment of blood products in a stochastic environment is presented. The goal of the model is to minimize the preparation, deficiency and waste cost of blood products, while considering the constraints of the problem. The stochastic model is implemented in a real case and is solved by the Monte Carlo simulation method. Then, a random model is settled in a real problem in Yazd city and it is solved via a Monte Carlo based Particle Swarm Optimization algorithm. The results reveal that the solution of the hybrid algorithm can significantly reduce the costs of preparation, deficiency and waste of blood products.

An efficient storage strategy for retail e-commerce warehousing is important for minimizing the order retrieval time to improve the warehouse-output efficiency. In this paper, we consider a model and algorithm to solve the cargo location problem in a retail e-commerce warehouse. The problem is abstracted into storing cargo on three-dimensional shelves, and the mathematical model is built considering three objectives: efficiency, stability, and classification. An artificial swarm algorithm is designed to solve the proposed models. Computational experiments performed on a warehouse show that the proposed approach is effective at solving the cargo location assignment problem and is significant for the operation and organization of a retail e-commerce warehouse.

Controller area network (CAN) is a widely used protocol that allows communication among electronic control units (ECUs) in automotive electronics. It was extended to CAN with flexible data-rate (CAN-FD) to meet the increasing demand for bandwidth generated by the growing number of features in modern automobiles. The signal-to-frame packing problem has been studied in the literature for both CAN and CAN-FD. In this paper, we propose and formulate the signal offset assignment problem (SOAP) in CAN-FD to improve the bus utilization during frame packing. We propose two algorithmic themes to solve SOAP and establish their worst case performance guarantees. The first is a general approximation framework (GAF) which can use any approximation algorithm for the makespan minimization problem (MMP) in multiprocessor systems. Its performance guarantee is the product of the performance guarantee of the MMP algorithm and the number of distinct periods in the frame. The second is a 2-D strip packing-based framework (2DSPF) which uses the bottom left fill algorithm for 2-D strip packing. The performance guarantee is $2{G}$ , where ${G}$ is the minimum number of groups into which the set of signals can be partitioned so that the periods of the signals in the same group form a geometric series. The experimental results for GAF and 2DSPF indicate that by carefully assigning offsets for signals in frame packing schemes, one can achieve about 10.83% improvement in bus utilization in CAN-FD systems.

A cooperative mapping and target-search algorithm is presented for detecting a single moving ground target in an urban environment that is initially unknown to a team of autonomous quadrotors equipped with noisy, range-limited sensors. The target moves according to a biased random-walk model, and search agents (quadrotors) build a target state graph that encodes past and present target positions. A track-before-detect algorithm assimilates target measurements into the log-likelihood ratio and anisotropic kriging interpolation predicts the location of occupancy nodes in unexplored regions. Mutual information evaluated at each location in the search area defines a sampling-priority surface that is partitioned by a weighted Voronoi algorithm into candidate waypoint tasks. Tasks are assigned to each agent by iteratively solving a utility-maximizing assignment problem. Numerical simulations show that the proposed approach compares favorably to non-adaptive lawnmower and random coverage strategies. The proposed strategy is also demonstrated experimentally through an outdoor flight test using two real and two virtual quadrotors.

Background/objectives: Patients of kidney failure sometimes have incompatible donors. This study proposes an application to get the best matchings based on scoring data. Methods: For pairwise matching, we created a new graph from the original scoring matrix. This graph ensures pairwise matchings. To find an optimal matching, we used the Blossom algorithm. For multiway matching, we interpreted the scoring matrix as an assignment problem. For this, we used the Hungarian algorithm. The application was created using Python, NetworkX, NumPy, and PySimpleGUI. The app uses CSV files as input. Findings: Both algorithms made for polynomial run times. Matching is fast and is guaranteed to be optimal. The application itself gets instantaneous results even for large donor-patient matrices. Application/improvement: Hospitals or organizations can use this application for their kidney matching programs. Keywords: Blossom Algorithm, Hungarian Algorithm, Kidney Failure, Donor Matching.

To deal with the multi-objective optimization problems (MOPs), this study proposes a new Multi-Objective Multi-Agent Complex Network Optimization Algorithm called MOMCNA based on the idea of Cellular genetic algorithm (CGA) and the Multi-agent complex network. Compared with the traditional CGA for multi objective problem, the individuals in the population of MOMCNA have more features of intelligent agent, the new form of neighborhood for the population, private archive for individuals, the new strategy of “local-global” genetic operator and the chaotic mutation are proposed in the new algorithm to balance the convergence and diversity of the algorithm. Seventeen unconstrained multi-objective optimization problems and seven many-objective problems are introduced and tested to evaluate the new algorithm, in addition, the classical traffic assignment problem based on different system optimum principle is also established to evaluate the new algorithm. The comparison between MOMCNA and other classical algorithms shows that the proposed MOMCNA proves to be competitive in dealing with multi-objective and many-objective optimization problems and the structure of the complex network made up of population also has effect on algorithm’s performance.

This work proposes a marginal distribution multi-target Bayes filter with assignment of measurements to track multiple targets in the presence of an unknown and variable number of targets, clutter, and missed detections. Mathematically, the association of the measurements with either a target or clutter may be established by maximizing the joint likelihood function of the measurement partition, which leads to a two-dimensional assignment problem. By the introduction of detecting label, a handling approach for missed detections is also developed and is applied to the proposed filter. This filter greatly reduces the number of hypothesized targets or Gaussian terms by selecting the predicted probability density of a target or one of its multiple updated probability densities as its state distribution at each time step. Experimental results indicate that the proposed filter requires a less computational load than the existing filters and performs better than the efficient implementations of the δ-generalized labeled multi-Bernoulli filter for multi-target tracking at low and moderate clutter densities.

Machine-to-Machine (M2M) communications have been introduced to improve the communication capacity in dense wireless networks. One of the most important concerns for network designers is maintaining the high performance of the network when the quality of connections between sources and their destinations is poor. Thus the careful selection of relays between data sources and their destinations is a very important issue. The possibility of simultaneous use of different Radio Frequency (RF) interfaces for transmitting data, which communication devices are equipped with them, can increase the capacity of data transmission over the network. In this paper, two novel M2M relay selection algorithms are proposed, named as Optimal Relay Selection Algorithm (ORSA) and Matching based Relay Selection Algorithm (MRSA). ORSA is a centralized algorithm for the optimal selection of relays by transforming the main problem to a k-cardinality assignment problem that can be solved using the Hungarian algorithm. MRSA is a distributed algorithm that leverages concepts from matching theory to provide a stable solution for the relay selection problem. In both proposed algorithms static RF interfaces usage is applied to enable simultaneous use of different interfaces for data transmission. The simulations show that ORSA is optimally solving the relay selection problem. MRSA has an optimal stable result, that when there is no restriction on the number of channels, is only about 1% lower than ORSA. Besides, MRSA provides better results than direct transmission Without any Relay Selection Algorithm (WRSA) and Random Relay Selection Algorithm (RRSA), about 15% and 98%, respectively., 51 pages, 17 figures

This article addresses the periodic home health care (HHC) server assignment problem in HHC companies. This problem is a variant of the periodic vehicle routing problem with specific constraints for customers and servers (e.g., customers’ requirements for multiple medical skills and continuous care offered by a given number of servers and servers’ requirements for workload balance). Solving large-scale problems from practical applications of HHC companies within an acceptable computation time is challenging. Consequently, we develop an efficient region-partition-based algorithm to solve these large-scale problems. First, the algorithms assign customers and servers to many independent regions. Second, four different tabu search (TS) algorithms are designed to solve the optimization problem of each region. Finally, the algorithms iteratively adjust the assignment of customers and servers to regions and solve the problems of each region. The performances of different TS algorithms are discussed. The effectiveness of the proposed region-partition-based algorithm for large-scale problems is validated. Note to Practitioners —This article is motivated by our collaboration with an HHC company in Shanghai, China. The company delivers medical, paramedical, and social services to customers in their homes to help them improve their clinical and psychological conditions without hospital stays. In practice, customers require long-term and periodic service (e.g., weekly), which may last many months or even years. HHC companies have to assign a combination of service days and at least one server to each customer. Due to specific constraints in practical operations and the large scale of the practical problems (e.g., 1000–2000 customers) of the HHC in this article, the server assignment problem is challenging to the HHC company. The algorithm presented in this article takes into account the special constraints of the HHC and is able to solve the large-scale problem in a reasonable time span. The algorithm can be used to help decision-makers assign combinations of service days and servers to customers with the objective of balancing the workloads among servers.

In this paper, we address the multiple sound source localization problem by associating and fusing the direction of arrival DOA estimates from multiple microphone arrays. For multi-source scenarios especially in indoor environments, a critical issue is to tell the correspondence among DOA estimates across different arrays, which is known as the data association problem. We propose a multi-dimensional assignment-based data association approach to find the optimal associations of DOA estimates from the same source. First, in the sense of maximum likelihood, the data association problem is formulated by finding the most likely partition of the measurement set into the source-originated and false alarm-originated subsets. Next, by defining the association costs appropriately, the problem of finding the most likely measurement partition is transformed into a generalized multi-dimensional assignment problem which can be solved efficiently by a Lagrangian relaxation algorithm. After the optimal associations of DOA estimates across different arrays are obtained, the locations of sources can be estimated by fusing the same source-originated DOA estimates. In the presence of missed detections, false alarms and the unknown number of sources, the proposed method achieves high accuracy in data association and localization, and outperforms the competing method in reverberant and noisy environments. In addition, since our method does not require additional features and uses DOA estimates only, it is more computationally efficient than the competing method.

This paper presents a new approach to accurately and efficiently identifying a large number of wireless devices blindly installed to known three-dimensional installation/fitting points, based on received signal strengths (RSSs) between the devices. The approach is non-trivial because of the factorial, mapping nature of the considered problem, the multiplicative ranging errors of the RSS measurements (with standard deviation of 5–7 dB), and the requirement of high mapping accuracy in many internet-of-things (IoT) applications, e.g., industrial IoT and aircraft. The consideration of a structured environment where the set of candidate node positions is known beforehand shifts the problem of interest from a pure position estimation problem to a position assignment problem. The key idea of the proposed approach is that we interpret the position mapping problem with a probabilistic graphical model, where the factorial nature of mapping (more specifically, the mutual exclusiveness of devices at every installation point) is fully captured. A max-product belief propagation is designed against the probabilistic graph, to estimate the max-marginal position distribution of each device. The Kuhn-Munkres algorithm is applied to preserve the mutual exclusiveness of devices throughout the belief propagation and to decide device locations based on the estimated position distributions. Large-scale simulations and field tests are carried out, showing that the new approach achieves close-to-100% accuracy in simulations with hundreds of blindfolded devices under RSS measurement errors with standard deviation of 5–7 dB. Our approach also achieves 100% accuracy in all field trials with 76 devices inside the cabin of a Fokker 100 airplane, dramatically outperforming baseline techniques.

In a periodic examination and a general entrance examination of a university, examination proctors are needed in order to smoothly and rigorously carry out the examination. Since such an examination is typically executed at many sites at the same time, many examination proctors are required and they must be assigned appropriately. When assigning proctors, there are a wide range of constraints to be considered. When all the constraints are not satisfied, it is necessary to obtain a solution that satisfies the constraints as much as possible by minimizing the total of the penalties for the soft constraints. In this way, the examination proctors assignment problem can be formulated as an optimization problem. We formulate the problem of assigning proctors as an integer programming problem. Furthermore, we design an algorithm based on the 2-opt method of local search which is one of the meta-heuristic algorithms. The performance of the proposed algorithm is evaluated by applying it to some periodic examination assignment with actual sizes. As a result, the proposed algorithm can output a feasible solution of a local minimum, even if the size of an instance of the problem is large and the optimization solver cannot solve it.

The multistate sliding window system (SWS) comprises [Formula: see text] multistate components arranged in a line; each group of [Formula: see text] consecutive multistate components is considered as a window. If the total performance rate in a window does not meet the predetermined demand [Formula: see text], then that window is regarded as a failure. The SWS fails if and only if there exists at least one failed window. Several researchers have considered the component assignment problem for the SWS with the aim of finding an appropriate component arrangement that maximizes system reliability. Such an arrangement is called the optimal arrangement. Although several metaheuristic and heuristic algorithms have been proposed, an exact algorithm for solving the component assignment problem of the SWS has not been developed thus far. Therefore, in this study, a branch-and-bound-based algorithm is developed to determine the optimal arrangement of the SWS efficiently. Furthermore, a recursive method is proposed to compute the system reliability. Combining the branch-and-bound-based algorithm with the recursive method enables reduction of the complexity of the reliability computations for determining the optimal arrangement. To investigate the efficiency of the branch-and-bound-based algorithm, numerical experiments were conducted; it was observed that the parameters [Formula: see text] and [Formula: see text] have the maximum effect on computation time, whereas parameter [Formula: see text] has minimal effect. The proposed algorithm is useful for improving the reliability of a practical system that can be expressed as an SWS. In addition, the optimal arrangements can be used to measure the heuristic and metaheuristic performances because they guarantee global optimality.

The Assignment Problem is a basic combinatorial optimization problem. In a weighted bipartite graph, the Assignment Problem is to find the largest sum of weights matching. The Hungarian method is a well-known algorithm, which is combinatorial optimization. Adding a new row and a new column to a weighted bipartite graph is called the Incremental Assignment Problem (IAP). The algorithm of the Incremental Assignment Problem utilizes the given optimal solution (the maximum weighted matching) and the dual variables to solve the matrix after extending the bipartite graph. This paper proposes an improvement of the Incremental Assignment Algorithm (IAA), named the Improved Incremental Assignment Algorithm (IIAA). The improved algorithm will save the operation time and operation space to find the optimal solution (the maximum weighted matching) of the bipartite graph.

With the rapid development of civil aviation transportation, the airport gate assignment problem (AGAP) has become an important issue for improving the operation efficiency of airport. By now, there has been a lot of algorithm research on the AGAP. However, the dynamic of flight schedule and the huge amount of large hub airport has not been well considered. For the convenient of advanced algorithm study and evaluation, a demo system for the AGAP is designed and built providing the function of data input, animation display of gate assignment result and the AGAP algorithm module. The user interface and the animation are implemented using the HTML and CSS, the AGAP algorithm functions are called through JavaScript, and the PHP is responsible for accessing the MySQL database. The test result show that the system can process data properly and the animation is smooth. The monitoring data of system running environment show that the system works stably.

This paper treats the partial eigenstructure assignment problem for multi-variable linear systems by state feedback. Both the open-loop and the closed-loop eigenvalues are allowed to have arbitrary geometric and algebraic multiplicities. Based on a previously proposed result on partial eigenstructure assignment, a new complete parametric solution is derived, which gives a complete general parameterization of the feedback gain and also provides the general parametric expression for all the admissible eigenvector matrices. The solution involves, instead of a matrix inverse of full-dimension, the inverse of a matrix with a much smaller dimension. By using this new solution repeatedly, a circulation algorithm is proposed, which is simple and dramatically reduces the computational load in the case of large scale systems. Furthermore, two important special cases are especially examined, and simple and direct solutions are proposed, which no longer needs computation of matrix inverses, and suits best in the proposed circulation algorithm. The approach provides all the design degrees of freedom which can be further utilized to achieve additional closed-loop system performance. An illustrative example is thoroughly examined, which demonstrates the procedure and the advantages of the proposed parametric approach.

The dynamics of individual water molecules has a strong effect on the energetics of biochemical interactions, such as peptide–protein binding. Existing software are able to predict the location of water molecules at the interface between a macromolecule and a ligand in a single state or at a particular time point. The program described in this article compares explicit solvent molecules from two different states within a given volume of space; for example between a free protein vs. the same protein with a ligand bound. This comparison creates a unique one-to-one matching between waters from the two states utilizing the Jonker and Volgenant algorithm for linear assignment. Matchings are deterministic and minimize the sum of the distance between matched pairs. Explicit solvent ligand docking can utilize this matching to understand how ligand binding affects the energy of interface waters. This algorithm can also be used to compare predicted water molecules to those seen in X-ray crystallography, or to compare two different methods of solvent prediction. Program summary Program title: WaterAlignment Program files doi: http://dx.doi.org/10.17632/pk6fnvwgg7.1 Licensing provisions: GNU Lesser General Public License Programming language: Python Nature of problem: Comparison of the location of solvent water molecules present in the same volume under two conditions in order to ‘match’ waters between the two conditions; that is, to define matched waters that represent the same molecule. The algorithm was developed to compare waters present in the binding pocket of a protein with and without a bound ligand, in order to determine the effect of ligand binding on the energy of waters in the binding pocket. Solution method: The task is treated as a linear assignment problem solved by the Jonker and Volgenant algorithm. A bipartite graph is constructed with each part of the graph consisting of nodes representing one of the two set of waters. Edges facing from the first set of nodes to the second set are added with cost equal to the distance between the waters that the nodes represent. This data structure is then used to create propositional matches, with each new match able to replace prior matches when beneficial to the overall result.

The multi-dimensional assignment problem is universal for data association analysis such as data association-based visual multi-object tracking and multi-graph matching. In this paper, multi-dimensional assignment is formulated as a rank-1 tensor approximation problem. A dual L1-normalized context/hyper-context aware tensor power iteration optimization method is proposed. The method is applied to multi-object tracking and multi-graph matching. In the optimization method, tensor power iteration with the dual unit norm enables the capture of information across multiple sample sets. Interactions between sample associations are modeled as contexts or hyper-contexts which are combined with the global affinity into a unified optimization. The optimization is flexible for accommodating various types of contextual models. In multi-object tracking, the global affinity is defined according to the appearance similarity between objects detected in different frames. Interactions between objects are modeled as motion contexts which are encoded into the global association optimization. The tracking method integrates high order motion information and high order appearance variation. The multi-graph matching method carries out matching over graph vertices and structure matching over graph edges simultaneously. The matching consistency across multi-graphs is based on the high-order tensor optimization. Various types of vertex affinities and edge/hyper-edge affinities are flexibly integrated. Experiments on several public datasets, such as the MOT16 challenge benchmark, validate the effectiveness of the proposed methods.

This paper discusses efficient parallel algorithms for obtaining strong lower bounds and exact solutions for large instances of the quadratic assignment problem (QAP). Our parallel architecture is comprised of both multicore processors and compute unified device architecture–enabled NVIDIA graphics processing units (GPUs) on the Blue Waters Supercomputing Facility at the University of Illinois at Urbana–Champaign. We propose novel parallelization of the Lagrangian dual ascent algorithm on the GPUs, which is used for solving a QAP formulation based on the level-2 reformulation linearization technique. The linear assignment subproblems in this procedure are solved using our accelerated Hungarian algorithm [Date K, Rakesh N (2016) GPU-accelerated Hungarian algorithms for the linear assignment problem. Parallel Computing 57:52–72.]. We embed this accelerated dual-ascent algorithm in a parallel branch-and-bound scheme and conduct extensive computational experiments on single and multiple GPUs, using problem instances with up to 42 facilities from the quadratic assignment problem library (QAPLIB). The experiments suggest that our GPU-based approach is scalable, and it can be used to obtain tight lower bounds on large QAP instances. Our accelerated branch-and-bound scheme is able to comfortably solve Nugent and Taillard instances (up to 30 facilities) from the QAPLIB, using a modest number of GPUs.

Cross-docks serve as distribution centers where shipments from different vendors are first consolidated according to their destinations, and then delivered to the retailers directly, with little or no storage in between. A critical problem encountered in the operation of cross-docks is the assignment of receiving and shipping doors, which greatly influences the labor or machinery cost of transferring the shipments between inbound and outbound transports. We show that the cross-dock door assignment problem (CDAP) is strictly non-deterministic polynomial-time complete. Although some deterministic algorithms have been reported to handle small-scale problems, the solutions to the middle- and large-scale CDAPs progressed at a slow pace. In this paper, we develop a nature-inspired dual-colony ant algorithm for CDAP, in which the two colonies of ants cooperatively search the optimal assignments of receiving and shipping doors to minimize the transferring costs of shipments. A collaborative local search strategy is designed and incorporated into the algorithm to enhance the search efficiency. Experiments have been conducted on a number of problem instances with different cross-dock sizes and freight flow patterns. The results show that the proposed algorithm is very competitive and can provide better solutions than the state-of-the-art heuristic algorithms.

In this paper, a combined model of auto-transit assignment is introduced based on two complementarity formulations in the literature. The model accounts for interactions between the auto and transit modes through non-separable asymmetric demand and cost functions. A path-based solution algorithm is presented based on the three ideas of decomposition, column generation, and linearization, which have proved to be effective in tackling large-size networks. Numerical results over the Chicago sketch network suggest that the algorithm converges quickly within the first iterations, but is less effective as the solution gets closer to the neighborhood of the equilibrium solution. The sluggish convergence behavior is attributed to the difficulty of searching the space of strategy-based transit assignment model.

During multi-robot exploration, the calculation cost of the target assignment increases significantly with an increase in the map size and number of robots. In this study, a target elimination method is proposed to overcome this challenge. The benefit of the proposed method increases as the map size and number of robots increase, which is demonstrated both empirically and theoretically. Moreover, it is established that the proposed method does not rely on a specific map representation or robot–target assignment method.

We consider the assignment problem with a special structure with a general form value function and constraints prohibiting certain matchings. In this case, the matching cost may be undefined until some permutation is found. We formulate the problem in terms of graph theory and reduce it to finding a minimal cost path in a graph with nonlocal edge weights. The proposed method for solving the problem is a modification of the Dijkstra’s shortest path algorithm in a weighted directed graph. This research is motivated by well drilling applications. We also show the analysis of our numerical experiments.

This paper addresses multi-agent multi-object tracking with labeled random finite sets via Generalized Covariance Intersection (GCI) fusion. While standard GCI fusion of Labeled Multi-Object (LMO) densities is labelwise and hence fully parallelizable, previous work unfortunately revealed that its fusion performance is highly sensitive to the unavoidable label inconsistencies among different agents. In order to overcome the label inconsistency sensitivity problem, we present a novel approach for the GCI fusion of LMO densities that is both robust to label inconsistencies and computationally efficient. The novel approach consists of, first, finding the best matching between labels of different agents by minimization of a suitable label inconsistency indicator, and, then, performing GCI fusion labelwise according to the obtained label matching. Furthermore, it is shown how the label matching problem, which is at the core of the proposed method, can be formulated as a linear assignment problem of finite length (efficiently solvable in polynomial time by the Hungarian algorithm), exactly for Labeled Multi-Bernoulli densities and approximately for arbitrary LMO densities. Simulation experiments are carried out to demonstrate the robustness and effectiveness of the proposed approach in challenging tracking scenarios.

This paper presents a new optimization method for printed circuit board assembly (PCBA) process based on improved spider monkey optimization (SMO) algorithm, and a production model for PCBA is created. The proposed method proves to be suitable for product-service system(PSS). PCBA process mainly consists of three parts. First is the assignment of PCB, second is the assignment of machines, the last is the component assignment problem. In this research, the SMO algorithm is applied on optimization of component assignment which is divided into two stages: local leader phase (LLP) and global leader phase (GLP). In the first stage, the electronic components are assigned to the feeders by GLP. In the second stage, the component placement sequence, which is apparently known as a travelling salesman problem (TSP), is determined by LLP. Numerical experiments are performed to compare the performance of SMO algorithm with others under various experimental settings, the results show that the proposed method is more effective than other traditional methods. A production model is created with the proposed method, which is calimed to be able to increase the efficiency of the product services.

In this paper, an improved ant colony optimization (ICMPACO) algorithm based on the multi-population strategy, co-evolution mechanism, pheromone updating strategy, and pheromone diffusion mechanism is proposed to balance the convergence speed and solution diversity, and improve the optimization performance in solving the large-scale optimization problem. In the proposed ICMPACO algorithm, the optimization problem is divided into several sub-problems and the ants in the population are divided into elite ants and common ants in order to improve the convergence rate, and avoid to fall into the local optimum value. The pheromone updating strategy is used to improve optimization ability. The pheromone diffusion mechanism is used to make the pheromone released by ants at a certain point, which gradually affects a certain range of adjacent regions. The co-evolution mechanism is used to interchange information among different sub-populations in order to implement information sharing. In order to verify the optimization performance of the ICMPACO algorithm, the traveling salesmen problem (TSP) and the actual gate assignment problem are selected here. The experiment results show that the proposed ICMPACO algorithm can effectively obtain the best optimization value in solving TSP and effectively solve the gate assignment problem, obtain better assignment result, and it takes on better optimization ability and stability.

This paper studies the use of Electric Vehicles (EVs) in a Mobility-on-Demand (MoD) scheme. In this scheme, customers that act as cooperative agents request a set of alternative trips, where each trip provides a utility to the agent. The EVs are distributed across a number of stations. We propose congestion management algorithms which take as input the trip requests and calculate the EV-to-customer assignment, considering the number of executed trips and the utility obtained by the agents. Initially, we solve the problem offline and optimally using Mixed-Integer-Programming (MIP) techniques and then we solve it online using an equivalent greedy algorithm. The online algorithm uses three alternative heuristic functions to decide on the execution of a customer request: (a) The sum of squares of all EVs in all stations, (b) the percentage of trips’ destination location fullness and (c) a random choice of trip execution. To further improve the performance of the online algorithms, we also propose an agent-based negotiation scheme where alternative offers in terms of trip starting time are made to the agents when the initial EV assignment problem is unsolvable due to insufficient resources. Through a detailed evaluation, we observe that (a) provides an increase of up to $$3.2\%$$ compared to (b) and up to $$3.7\%$$ compared to (c) in terms of average trip execution, while giving the higher utility to the agents. All variations achieve close to the optimal performance. At the same time, the negotiation scheme improves the performance of the algorithms by up to $$15.7\%$$ .

Multi-UAVs task assignment is regarded as an important problem in the UAV research domain. To assign multi-UAVs tasks efficiently and accurately, a common method of assigning tasks is needed with resource constraints and precedence constraint. Then, we apply fully adaptive cross-entropy (FACE) algorithm to multi-UAVs task assignment, and the resources and the sequence required for three tasks are also taken into account. Through emphasizing the iterative principle of FACE algorithm and utilizing it to handle the multi-UAVs task assignment problem with constraints, the simulations validate that compared with the cross-entropy method and the particle swarm optimization algorithm, the FACE algorithm has fast convergence speed and the strength to solve large-scale allocation problems.

The maximum flow and minimum cost-maximum flow problems are both concerned with determining flows through a network between a source and a destination. Maximum flow applies to any problem where the objective is move as many as possible goods/objects/people between two locations via intermediate locations. Maximum flow-minimum cost applies to flow problems where both capacities and costs are involved. When given information about a network (network flow diagram, capacities, costs), computing enables one to arrive at a solution to the problem. Once the solution becomes available, it has to be applied to a real world problem. The use of the following computer software in solving these problems will be discussed: R (several packages and functions), specially written Pascal programs and Excel SOLVER. The minimum cost-maximum flow solutions to the following problems will also be discussed: maximum flow, minimum cost-maximum flow, transportation problem, assignment problem, shortest path problem, caterer problem.

Radar jamming task assignment is one of the most important functions of EW simulation system. The result of radar jamming task assignment has great influence on the EW effect. At present, the existing optimization algorithm has difficulty in meeting the demand of simulation for its complexity and long computing time. In view of this problem, a new evolution algorithm, particle swarm optimization, is adopted to solve radar jamming task assignment problem on the basis of studying the problem and the algorithm is compared with the Genetic algorithm. The simulation result shows that the algorithm has faster computing speed and not many parameters to adjust in the same condition compared with the Genetic algorithm, so it is more suitable to solve radar jamming task assignment problem.

This paper focuses on identifying an algorithm that can be utilized in grocery cost reduction within the consumer space. The algorithm produces the combination of grocery products to stores that net the lowest overall grocery cost for the consumer. This is often referred to as a combinatorial optimization problem, and is commonly used by many industries for resource or task assignment. To identify a solution for grocery cost reduction, the Kuhn-Munkres algorithm (often referred to as the Hungarian algorithm) and the Deepest Hole algorithm are explored in depth. After comparing the algorithms based on their implementation and performance, a third solution combining ideas from the Kuhn-Munkres algorithm and Deepest Hole algorithm was created to solve for the specific needs of this problem. This solution will be referred to as the KMDH Hybrid algorithm. Modifications include the ability for users to select the number of stores they wish to shop at, the ability to use a rectangular grid, and allowing for one-to-many assignments. All three algorithms were developed in Python, and tested on a dataset with a predefined list of stores, products, and prices. It is apparent that the proposed hybrid algorithm can be applied to the assignment problem, and has the potential to be applied to other similar applications.