Competition assignment problem algorithm based on Hungarian method

Traditional Hungarian method can only solve standard assignment problems, while can not solve competition assignment problems. This article emphatically discussed the difference between standard assignment problems and competition assignment problems. The kinds of competition assignment problem algorithms based on Hungarian method and the solutions of them were studied.

Colony location algorithm for assignment problems

A novel algorithm called Colony Location Algorithm (CLA) is proposed. It mimics the phenomena in biotic community that colonies of species could be located in the places most suitable to their growth. The factors working on the species location such as the nutrient of soil, resource competition between species, growth and decline process, and effect on environment were considered in CLA via the nutrient function, growth and decline rates, environment evaluation and fertilization strategy. CLA was applied to solve the classical assignment problems. The computation results show that CLA can achieve the optimal solution with higher possibility and shorter running time.

Improved Hungarian algorithm for assignment problems of serial-parallel systems

In order to overcome the shortcoming of the classical Hungarian algorithm that it can only solve the problems where the total cost is the sum of that of each job, an improved Hungarian algorithm is proposed and used to solve the assignment problem of serial-parallel systems. First of all, by replacing parallel jobs with virtual jobs, the proposed algorithm converts the serial-parallel system into a pure serial system, where the classical Hungarian algorithm can be used to generate a temporal assignment plan via optimization. Afterwards, the assignment plan is validated by checking whether the virtual jobs can be realized by real jobs through local searching. If the assignment plan is not valid, the converted system will be adapted by adjusting the parameters of virtual jobs, and then be optimized again. Through iterative searching, the valid optimal assignment plan can eventually be obtained.To evaluate the proposed algorithm, the valid optimal assignment plan is applied to labor allocation of a manufacturing system which is a typical serial-parallel system.

Integrating Tabu Search in Particle Swarm Optimization for the Frequency Assignment Problem

In this paper, we address one of the issues in the frequency assignment problem for cellular mobile networks in which we intend to minimize the interference levels when assigning frequencies from a limited frequency spectrum. In order to satisfy the increasing demand in such cellular mobile networks, we use a hybrid approach consisting of a Particle Swarm Optimization(PSO) combined with a Tabu Search(TS) algorithm. This approach takes both advantages of PSO efficiency in global optimization and TS in avoiding the premature convergence that would lead PSO to stagnate in a local minimum. Moreover, we propose a new efficient, simple, and inexpensive model for storing and evaluating solution's assignment. The purpose of this model reduces the solution's storage volume as well as the computations required to evaluate thesesolutions in comparison with the classical model. Our simulation results on the most known benchmarking instances prove the effectiveness of our proposed algorithm in comparison with previous related works in terms of convergence rate, the number of iterations, the solution storage volume and the running time required to converge to the optimal solution.

Solving the Unbalanced Assignment Problem: Simpler Is Better

Recently, Yadaiah and Haragopal published in the American Journal of Operations Research a new approach to solving the unbalanced assignment problem. They also provide a numerical example which they solve with their approach and get a cost of 1550 which they claim is optimum. This approach might be of interest;however, their approach does not guarantee the optimal solution. In this short paper, we will show that solving this same example from the Yadaiah and Haragopal paper by using a simple textbook formulation to balance the problem and then solve it with the classic Hungarian method of Kuhn yields the true optimal solution with a cost of 1520.

Solution to the quadratic assignment problem usingsemi-Lagrangian relaxation

The semi-Lagrangian relaxation （SLR）, a new exactmethod for combinatorial optimization problems with equality constraints,is applied to the quadratic assignment problem （QAP）.A dual ascent algorithm with finite convergence is developed forsolving the semi-Lagrangian dual problem associated to the QAP.We perform computational experiments on 30 moderately difficultQAP instances by using the mixed integer programming solvers,Cplex, and SLR＋Cplex, respectively. The numerical results notonly further illustrate that the SLR and the developed dual ascentalgorithm can be used to solve the QAP reasonably, but also disclosean interesting fact： comparing with solving the unreducedproblem, the reduced oracle problem cannot be always effectivelysolved by using Cplex in terms of the CPU time.

Troubleshooting algorithm for solving assignment problem and its applications

A new troubleshooting algorithm for solving assignment problem based on existing algorithms is proposed, and an analysis on the related theory is given. By applying the new troubleshooting algorithm to the Lagrange relaxation algorithm of the multi-dimensional assignment problem of data association for multi-passive-sensor multi-target location systems, and comparing the simulation results with that of the Hungarian algorithm which is the classical optimal solving algorithm, and the multi-layer ordersearching algorithm which is a sub-optimal solving algorithm, the performance and applying conditions of the new algorithm are summarized. Theory analysis and simulation results prove the effectiveness and superiority of the new algorithm.

Generative Neural Network Based Spectrum Sharing Using Linear Sum Assignment Problems

Spectrum management and resource allocation(RA)problems are challenging and critical in a vast number of research areas such as wireless communications and computer networks.The traditional approaches for solving such problems usually consume time and memory,especially for large-size problems.Recently different machine learning approaches have been considered as potential promising techniques for combinatorial optimization problems,especially the generative model of the deep neural networks.In this work,we propose a resource allocation deep autoencoder network,as one of the promising generative models,for enabling spectrum sharing in underlay device-to-device(D2D)communication by solving linear sum assignment problems(LSAPs).Specifically,we investigate the performance of three different architectures for the conditional variational autoencoders(CVAE).The three proposed architecture are the convolutional neural network(CVAECNN)autoencoder,the feed-forward neural network(CVAE-FNN)autoencoder,and the hybrid(H-CVAE)autoencoder.The simulation results show that the proposed approach could be used as a replacement of the conventional RA techniques,such as the Hungarian algorithm,due to its ability to find solutions of LASPs of different sizes with high accuracy and very fast execution time.Moreover,the simulation results reveal that the accuracy of the proposed hybrid autoencoder architecture outperforms the other proposed architectures and the state-of-the-art DNN techniques.

Components Assignment Problem for Multi-Source Multi-Sink Flow Networks with Reliability and Budget Constraints

System reliability optimization problem of multi-source multi-sink flow network is defined by searching the optimal components that maximize the reliability and minimize the total assignment cost. Therefore, a genetic-based approach is proposed to solve the components assignment problem under budget constraint. The mathematical model of the optimization problem is presented and solved by the proposed genetic-based approach. The proposed approach is based on determining the optimal set of lower boundary points that maximize the system reliability such that the total assignment cost does not exceed the specified budget. Finally, to evaluate our approach, we applied it to various network examples with different numbers of available components;two-source two-sink network and three-source two-sink network.

Proposed Heuristic Method for Solving Assignment Problems

Assignment of jobs to workers, contract to contractors undergoing a bidding process, assigning nurses to duty post, or time tabling for teachers in school and many more have become a growing concern to both management and sector leaders alike. Hungarian algorithm has been the most successful tool for solving such problems. The authors have proposed a heuristic method for solving assignment problems with less computing time in comparison with Hungarian algorithm that gives comparable results with an added advantage of easy implementation. The proposed heuristic method is used to compute some bench mark problems.

A New Approach of Solving Single Objective Unbalanced Assignment Problem

In this paper, we discuss a new approach for solving an unbalanced assignment problem. A Lexi-search algorithm is used to assign all the jobs to machines optimally. The results of new approach are compared with existing approaches, and this approach outperforms other methods. Finally, numerical example (Table 1) has been given to show the efficiency of the proposed methodology.

An ADMM-based parallel algorithm for solving traffic assignment problem with elastic demand

Efficiently solving the user equilibrium traffic assignment problem with elastic demand(UE-TAPED)for transportation networks is a critical problem for transportation studies.Most existing UE-TAPED algorithms are designed using a sequential computing scheme,which cannot take advantage of advanced parallel computing power.Therefore,this study focuses on model decomposition and parallelization,proposing an origin-based formulation for UE-TAPED and proving an equivalent reformulation of the original problem.Furthermore,the alternative direction method of multipliers(ADMM)is employed to decompose the original problem into independent link-based subproblems,which can solve large-scale problems with small storage space.In addition,to enhance the efficiency of our algorithm,the parallel computing technology with optimal parallel computing schedule is implemented to solve the link-based subproblems.Numerical experiments are performed to validate the computation efficiency of the proposed parallel algorithm.

Backbone analysis and algorithm design for the quadratic assignment problem

As the hot line in NP-hard problems research in recent years, backbone analysis is crucial for phase transition, hardness, and algorithm design. Whereas theoretical analysis of backbone and its applications in algorithm design are still at a begin- ning state yet, this paper took the quadratic assignment problem （QAP） as a case study and proved by theoretical analysis that it is NP-hard to find the backbone, i.e., no algorithm exists to obtain the backbone of a QAP in polynomial time. Results of this paper showed that it is reasonable to acquire approximate backbone by inter- section of local optimal solutions. Furthermore, with the method of constructing biased instances, this paper proposed a new meta-heuristic -- biased instance based approximate backbone （BI-AB）, whose basic idea is as follows： firstly, construct a new biased instance for every QAP instance （the optimal solution of the new instance is also optimal for the original one）; secondly, the approximate backbone is obtained by intersection of multiple local optimal solutions computed by some existing algorithm; finally, search for the optimal solutions in the reduced space by fixing the approximate backbone. Work of the paper enhanced the research area of theoretical analysis of backbone. The meta-heuristic proposed in this paper provided a new way for general algorithm design of NP-hard problems as well.

Adaptive genetic algorithms guided by decomposition for PCSPs： application to frequency assignment problems

This paper proposes Adaptive Genetic Algorithms Guided by structural knowledges coming from decomposition methods, for solving PCSPs. The family of algorithms called AGAGD_x_y is designed to be doubly genetic, meaning that any decomposition method and different heuristics for the genetic operators can be considered. To validate the approach, the decomposition algorithm due to Newman was used and several crossover operators based on structural knowledge such as the cluster, separator and the cut were tested. The experimental results obtained on the most challenging Minimum Interference-FAP problems of CALMA instances are very promising and lead to interesting perspectives to be explored in the future.

Probabilistic Analysis and Multicriteria Decision for Machine Assignment Problem with General Service Times

In this paper we carried out a probabilistic analysis for a machine repair system with a general service-time distribution by means of generalized Markov renewal processes. Some formulas for the steady-state performance measures. such as the distribution of queue sizes, average queue length, degree of repairman utilization and so on. are then derived. Finally, the machine repair model and a multiple critcria decision-making method are applied to study machine assignment problem with a general service-time distribution to determine the optimum number of machines being serviced by one repairman.

An Efficient Algorithm for Obtaining the Optimum Solution of a Generalized Assignment Problem

This paper considers a generalized assignment problem. After intensively analyzing and researching, the generalizsed assignment problem is ingeniously reduced to a traditional assignment problem of which the optimum solution can be easily obtained by a famous method:Hungary algorithm. Finally, an illustrating example is given.

Competition Based Neural Networks for Assignment Problems

Competition based neural networks have been used to solve the generalized assignment problem andthe quadratic assignment problem.Both problems are very difficult and are ε approximation complete.Theneural network approach has yielded highly competitive performance and good performance for thequadratic assignment problem.These neural networks are guaranteed to produce feasible solutions.

Shuffled frog leaping algorithm with non-dominated sorting for dynamic weapon-target assignment

The dynamic weapon target assignment(DWTA)problem is of great significance in modern air combat.However,DWTA is a highly complex constrained multi-objective combinatorial optimization problem.An improved elitist non-dominated sorting genetic algorithm-II(NSGA-II)called the non-dominated shuffled frog leaping algorithm(NSFLA)is proposed to maximize damage to enemy targets and minimize the self-threat in air combat constraints.In NSFLA,the shuffled frog leaping algorithm(SFLA)is introduced to NSGA-II to replace the inside evolutionary scheme of the genetic algorithm(GA),displaying low optimization speed and heterogeneous space search defects.Two improvements have also been raised to promote the internal optimization performance of SFLA.Firstly,the local evolution scheme,a novel crossover mechanism,ensures that each individual participates in updating instead of only the worst ones,which can expand the diversity of the population.Secondly,a discrete adaptive mutation algorithm based on the function change rate is applied to balance the global and local search.Finally,the scheme is verified in various air combat scenarios.The results show that the proposed NSFLA has apparent advantages in solution quality and efficiency,especially in many aircraft and the dynamic air combat environment.

L(2,1)-labeling problem on distance graphs

L (2, 1)-labeling number, λ(G( Z , D)) , of distance graph G( Z , D) is studied. For general finite distance set D , it is shown that 2D+2≤λ(G( Z , D))≤D 2+3D. Furthermore, λ(G( Z , D)) ≤8 when D consists of two prime positive odd integers is proved. Finally, a new concept to study the upper bounds of λ(G) for some special D is introduced. For these sets, the upper bound is improved to 7.

Behaviours in a dynamical model of traffic assignment with elastic demand

This paper investigates the dynamical behaviour of network traffic flow. Assume that trip rates may be influenced by the level of service on the network and travellers are willing to take a faster route. A discrete dynamical model for the day-to-day adjustment process of route choice is presented. The model is then applied to a simple network for analysing the day-to-day behaviours of network flow. It finds that equilibrium is arrived if network flow consists of travellers not very sensitive to the differences of travel cost. Oscillations and chaos of network traffic flow are also found when travellers are sensitive to the travel cost and travel demand in a simple network.