Comparison of Lagrangian Bounds for One Class of Generalized 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.

Aggregation in the generalized transportation problem

Aggregation disaggregation is used to reduce the analysis of a large generalized transportation problem to a smaller one. Bounds for the actual difference between the aggregated objective and the original optimal value are used to quantify the error due to aggregation and estimate the quality of the aggregation. The bounds can be calculated either before optimization of the aggregated problem (a priori) or after (a posteriori). Both types of the bounds are derived and numerically compared. A computational experiment was designed to (a) study the correlation between the bounds and the actual error and (b) quantify the difference of the error bounds from the actual error. The experiment shows a significant correlation between some a priori bounds, the a posteriori bounds and the actual error. These preliminary results indicate that calculating the a priori error bound is a useful strategy to select the appropriate aggregation level, since the a priori bound varies in the same way that the actual error does. After the aggregated problem has been selected and optimized, the a posteriori bound provides a good quantitative measure for the error due to aggregation.

Métodos de geração de colunas para problemas de atribuição

Este trabalho apresenta métodos de geração de colunas para dois importantes problemas de atribuição: o Problema Generalizado de Atribuição (PGA) e o Problema de Atribuição de Antenas a Comutadores (PAAC). O PGA é um dos mais representativos problemas de Otimização Combinatória e consiste em otimizar a atribuição de n tarefas a m agentes, de forma que cada tarefa seja atribuída a exatamente um agente e a capacidade de cada agente seja respeitada. O PAAC consiste em atribuir n antenas a m comutadores em uma rede de telefonia celular, de forma a minimizar os custos de cabeamento entre antenas e comutadores e os custos de transferência de chamadas entre comutadores. A abordagem tradicional de geração de colunas é comparada com as propostas neste trabalho, que utilizam a relaxação lagrangeana/surrogate. São apresentados testes computacionais que demonstram a efetividade dos algoritmos propostos.

A Beam Search Method to Solve the Problem of Assignment Cells to Switches in a Cellular Mobile Network

Assigning cells to switches in a cellular mobile network is known as an NP-hard optimization problem. This means that the alternative for the solution of this type of problem is the use of heuristic methods, because they allow the discovery of a good solution in a very 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 and provide good solutions for large scale problems.

A Lagrangian bound for many-to-many assignment problems

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

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.

Using error bounds to compare aggregated generalized transportation models

A comparative study of aggregation error bounds for the generalized transportation problem is presented. A priori and a posteriori error bounds were derived and a computational study was performed to (a) test the correlation between the a priori, the a posteriori, and the actual error and (b) quantify the difference of the error bounds from the actual error. Based on the results we conclude that calculating the a priori error bound can be considered as a useful strategy to select the appropriate aggregation level. The a posteriori error bound provides a good quantitative measure of the actual error.

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.

Relax and cut: limitantes duais para o problema do caixeiro viajante

Pós-graduação em Matemática - IBILCE

Simple heuristics for the assembly line worker assignment and balancing problem

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

On the resolution of the generalized nonlinear complementarity problem

Minimization of a differentiable function subject to box constraints is proposed as a strategy to solve the generalized nonlinear complementarity problem (GNCP) defined on a polyhedral cone. It is not necessary to calculate projections that complicate and sometimes even disable the implementation of algorithms for solving these kinds of problems. Theoretical results that relate stationary points of the function that is minimized to the solutions of the GNCP are presented. Perturbations of the GNCP are also considered, and results are obtained related to the resolution of GNCPs with very general assumptions on the data. These theoretical results show that local methods for box-constrained optimization applied to the associated problem are efficient tools for solving the GNCP. Numerical experiments are presented that encourage the use of this approach.

On partial derivative-Neumann's problem in generalized functions framework

In this paper, we show that the equation delta u/delta (z) over bar + Gu = f, where the elements involved are in generalized functions context, has a local solution in the generalized functions context.

The canonical structure of Podolsky's generalized electrodynamics on the null-plane

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

A generalized alternating-direction implicit scheme for incompressible magnetohydrodynamic viscous flows at low magnetic Reynolds number

This paper presents numerical simulations of incompressible fluid flows in the presence of a magnetic field at low magnetic Reynolds number. The equations governing the flow are the Navier-Stokes equations of fluid motion coupled with Maxwell's equations of electromagnetics. The study of fluid flows under the influence of a magnetic field and with no free electric charges or electric fields is known as magnetohydrodynamics. The magnetohydrodynamics approximation is considered for the formulation of the non-dimensional problem and for the characterization of similarity parameters. A finite-difference technique is used to discretize the equations. In particular, an extension of the generalized Peaceman and Rachford alternating-direction implicit (ADI) scheme for simulating two-dimensional fluid flows is presented. The discretized conservation equations are solved in stream function-vorticity formulation. We compare the ADI and generalized ADI schemes, and show that the latter is more efficient in simulating low Reynolds number and magnetic Reynolds number problems. Numerical results demonstrating the applicability of this technique are also presented. The simulation of incompressible magneto hydrodynamic fluid flows is illustrated by numerical solution for two-dimensional cases. (c) 2007 Elsevier B.V. All rights reserved.