Statistical bound of genetic solutions to quadratic assignment problems

Quadratic assignment problems (QAPs) are commonly solved by heuristic methods, where the optimum is sought iteratively. Heuristics are known to provide good solutions but the quality of the solutions, i.e., the confidence interval of the solution is unknown. This paper uses statistical optimum estimation techniques (SOETs) to assess the quality of Genetic algorithm solutions for QAPs. We examine the functioning of different SOETs regarding biasness, coverage rate and length of interval, and then we compare the SOET lower bound with deterministic ones. The commonly used deterministic bounds are confined to only a few algorithms. We show that, the Jackknife estimators have better performance than Weibull estimators, and when the number of heuristic solutions is as large as 100, higher order JK-estimators perform better than lower order ones. Compared with the deterministic bounds, the SOET lower bound performs significantly better than most deterministic lower bounds and is comparable with the best deterministic ones. 

A Lagrangian bound for many-to-many assignment problems

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Lagrangian heuristic for a class of the generalized assignment problems

A Lagrangian based heuristic is proposed for many-to-many assignment problems taking into account capacity limits for task and agents. A modified Lagrangian bound studied earlier by the authors is presented and a greedy heuristic is then applied to get a feasible Lagrangian-based solution. The latter is also used to speed up the subgradient scheme to solve the modified Lagrangian dual problem. A numerical study is presented to demonstrate the efficiency of the proposed approach. (C) 2010 Elsevier Ltd. All rights reserved.

Studying properties of Lagrangian bounds for many-to-many assignment problems

Classical and modified Lagrangian bounds for the optimal value of optimization problems with a double decomposable structure are studied. For the class of many-to-many assignment problems, this property of constraints is used to design a subgradient algorithm for solving the modified dual problem. Numerical results are presented to compare the quality of classical and modified bounds, as well as the properties of the corresponding Lagrangian solutions.

Comparison of Lagrangian Bounds for One Class of Generalized Assignment Problems

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Functional tests of solutions of personnel assignment problems.

Mode of access: Internet.

The moving targets algorithm for difficult temporal credit assignment problems

The 'moving targets' algorithm for training recurrent networks is reviewed and applied to a task which demonstrates the ability of this algorithm to use distant contextual information. Some practical difficulties are discussed, especially with regard to the minimization process. Results on performance and computational requirements of several different 2nd-order minimization algorithms are presented for moving target problems.

Optimization heuristic solutions, how good can they be? : With empirical applications in location problems

Combinatorial optimization problems, are one of the most important types of problems in operational research. Heuristic and metaheuristics algorithms are widely applied to find a good solution. However, a common problem is that these algorithms do not guarantee that the solution will coincide with the optimum and, hence, many solutions to real world OR-problems are afflicted with an uncertainty about the quality of the solution. The main aim of this thesis is to investigate the usability of statistical bounds to evaluate the quality of heuristic solutions applied to large combinatorial problems. The contributions of this thesis are both methodological and empirical. From a methodological point of view, the usefulness of statistical bounds on p-median problems is thoroughly investigated. The statistical bounds have good performance in providing informative quality assessment under appropriate parameter settings. Also, they outperform the commonly used Lagrangian bounds. It is demonstrated that the statistical bounds are shown to be comparable with the deterministic bounds in quadratic assignment problems. As to empirical research, environment pollution has become a worldwide problem, and transportation can cause a great amount of pollution. A new method for calculating and comparing the CO2-emissions of online and brick-and-mortar retailing is proposed. It leads to the conclusion that online retailing has significantly lesser CO2-emissions. Another problem is that the Swedish regional division is under revision and the border effect to public service accessibility is concerned of both residents and politicians. After analysis, it is shown that borders hinder the optimal location of public services and consequently the highest achievable economic and social utility may not be attained.

Problem of assignment cells to switches in a cellular mobile network via beam search method

The problem of assigning cells to switches in a cellular mobile network is an NP-hard optimization problem. So, real size mobile networks could not be solved by using exact methods. The alternative is the use of the heuristic methods, because they allow us to find a good quality solution in a quite satisfactory computational time. This paper proposes a Beam Search method to solve the problem of assignment cell in cellular mobile networks. Some modifications in this algorithm are also presented, which allows its parallel application. Computational results obtained from several tests confirm the effectiveness of this approach to provide good solutions for medium- and large-sized cellular mobile network.

A heuristic algorithm based on multi-assignment procedures for nurse scheduling

This paper tackles a Nurse Scheduling Problem which consists of generating work schedules for a set of nurses while considering their shift preferences and other requirements. The objective is to maximize the satisfaction of nurses' preferences and minimize the violation of soft constraints. This paper presents a new deterministic heuristic algorithm, called MAPA (multi-assignment problem-based algorithm), which is based on successive resolutions of the assignment problem. The algorithm has two phases: a constructive phase and an improvement phase. The constructive phase builds a full schedule by solving successive assignment problems, one for each day in the planning period. The improvement phase uses a couple of procedures that re-solve assignment problems to produce a better schedule. Given the deterministic nature of this algorithm, the same schedule is obtained each time that the algorithm is applied to the same problem instance. The performance of MAPA is benchmarked against published results for almost 250,000 instances from the NSPLib dataset. In most cases, particularly on large instances of the problem, the results produced by MAPA are better when compared to best-known solutions from the literature. The experiments reported here also show that the MAPA algorithm finds more feasible solutions compared with other algorithms in the literature, which suggest that this proposed approach is effective and robust. © 2013 Springer Science+Business Media New York.

An alternative formulation for the fuzzy assignment problem

The existing assignment problems for assigning n jobs to n individuals are limited to the considerations of cost or profit measured as crisp. However, in many real applications, costs are not deterministic numbers. This paper develops a procedure based on Data Envelopment Analysis method to solve the assignment problems with fuzzy costs or fuzzy profits for each possible assignment. It aims to obtain the points with maximum membership values for the fuzzy parameters while maximizing the profit or minimizing the assignment cost. In this method, a discrete approach is presented to rank the fuzzy numbers first. Then, corresponding to each fuzzy number, we introduce a crisp number using the efficiency concept. A numerical example is used to illustrate the usefulness of this new method. © 2012 Operational Research Society Ltd. All rights reserved.