The Experts below are selected from a list of 360 Experts worldwide ranked by ideXlab platform
Luiz Antonio Nogueira Lorena - One of the best experts on this subject based on the ideXlab platform.
-
Lagrangean relaxation with clusters and column generation for the manufacturer s pallet loading problem
Computers & Operations Research, 2007Co-Authors: Glaydston Mattos Ribeiro, Luiz Antonio Nogueira LorenaAbstract:We consider in this paper a new Lagrangean relaxation with clusters for the Manufacturer's Pallet Loading Problem (MPLP). The relaxation is based on the MPLP formulated as a Maximum Independent Set Problem (MISP) and represented in a conflict graph that can be partitioned in clusters. The edges inter clusters are relaxed in a Lagrangean fashion. Computational tests attain the optimality for some instances considered difficult for a Lagrangean relaxation. Our results show that this relaxation can be a successful approach for hard combinatorial problems modeled in conflict graphs. Moreover, we propose a column generation approach for the MPLP derived from the idea behind the Lagrangean relaxation proposed.
-
stabilizing column generation using Lagrangean surrogate relaxation an application to p median location problems
2003Co-Authors: Edson Luiz Franca Senne, Luiz Antonio Nogueira LorenaAbstract:The Lagrangean/surrogate relaxation was explored recently as a faster computational alternative to traditional Lagrangean heuristics. We combine the Lagrangean/surrogate and the traditional column generation approaches to accelerate and stabilize primal and dual bounds obtained using the reduced cost selection. The Lagrangean/surrogate multiplier modifies the reduced cost criterion, providing the selection of new productive columns. The p-median problem is the problem of locating p facilities (medians) on a network such as the sum of all the distances from each demand point to its nearest facility is minimized. Computational tests running p-median instances taken from the literature are presented.
-
Lagrangean surrogate heuristics for p median problems
2000Co-Authors: Edson Luiz Franca Senne, Luiz Antonio Nogueira LorenaAbstract:The p-median problem is the problem of locating p facilities (medians) on a network so as to minimize the sum of all the distances from each demand point to its nearest facility. A successful approach to approximately solve this problem is the use of Lagrangean heuristics, based upon Lagrangean relaxation and subgradient optimization. The Lagrangean/surrogate is an alternative relaxation proposed recently to correct the erratic behavior of subgradient like methods employed to solve the Lagrangean dual. We propose in this paper Lagrangean/surrogate heuristics to p-median problems. Lagrangean and surrogate relaxations are combined relaxing in the surrogate way the assignment constraints in the p-median formulation. Then, the Lagrangean relaxation of the surrogate constraint is obtained and approximately optimized (one-dimensional dual). Lagrangean/surrogate relaxations are very stable (low oscillating) and reach the same good results of Lagrangean (alone) heuristics in less computational times. Two primal heuristics was tested, an interchange heuristic and a location-allocation based heuristic. The paper presents several computational tests which have been conducted with problems from the literature, a set of instances presenting large duality gaps, a set of time consuming instances and a large scale instance.
-
Lagrangean surrogate relaxation for generalized assignment problems
European Journal of Operational Research, 1999Co-Authors: Marcelo Goncalves Narciso, Luiz Antonio Nogueira LorenaAbstract:Abstract This work presents Lagrangean/surrogate relaxation to the problem of maximum profit assignment of n tasks to m agents ( n > m ), such that each task is assigned to only one agent subject to capacity constraints on the agents. The Lagrangean/surrogate relaxation combines usual Lagrangean and surrogate relaxations relaxing first a set of constraints in the surrogate way. Then, the Lagrangean relaxation of the surrogate constraint is obtained and approximately optimized (one-dimensional dual). The Lagrangean/surrogate is compared with the usual Lagrangean relaxation on a computational study using a large set of instances. The dual bounds are the same for both relaxations, but the Lagrangean/surrogate can give improved local bounds at the application of a subgradient method, resulting in less computational times. Three relaxations are derived for the problem. The first relaxation considers a vector of multipliers for the capacity constraints, the second for the assignment constraints and the other for the Lagrangean decomposition constraints. Relaxation multipliers are used with efficient constructive heuristics to find good feasible solutions. The application of a Lagrangean/surrogate approach seems very promising for large scale problems.
Monique Guignard - One of the best experts on this subject based on the ideXlab platform.
-
strong rlt1 bounds from decomposable Lagrangean relaxation for some quadratic 0 1 optimization problems with linear constraints
Annals of Operations Research, 2020Co-Authors: Monique GuignardAbstract:The Reformulation Linearization Technique (RLT) of Sherali and Adams (Manag Sci 32(10):1274–1290, 1986; SIAM J Discrete Math 3(3):411–430, 1990), when applied to a pure 0–1 quadratic optimization problem with linear constraints (P), constructs a hierarchy of LP (i.e., continuous and linear) models of increasing sizes. These provide monotonically improving continuous bounds on the optimal value of (P) as the level, i.e., the stage in the process, increases. When the level reaches the dimension of the original solution space, the last model provides an LP bound equal to the IP optimum. In practice, unfortunately, the problem size increases so rapidly that for large instances, even computing bounds for RLT models of level k (called RLTk) for small k may be challenging. Their size and their complexity increase drastically with k. To our knowledge, only results for bounds of levels 1, 2, and 3 have been reported in the literature. We are proposing, for certain quadratic problem types, a way of producing stronger bounds than continuous RLT1 bounds in a fraction of the time it would take to compute continuous RLT2 bounds. The approach consists in applying a specific decomposable Lagrangean relaxation to a specially constructed RLT1-type linear 0–1 model. If the overall Lagrangean problem does not have the integrality property, and if it can be solved as a 0–1 rather than a continuous problem, one may be able to obtain 0–1 RLT1 bounds of roughly the same quality as standard continuous RLT2 bounds, but in a fraction of the time and with much smaller storage requirements. If one actually decomposes the Lagrangean relaxation model, this two-step procedure, reformulation plus decomposed Lagrangean relaxation, will produce linear 0–1 Lagrangean subproblems with a dimension no larger than that of the original model. We first present numerical results for the Crossdock Door Assignment Problem, a special case of the Generalized Quadratic Assignment Problem. These show that just solving one Lagrangean relaxation problem in 0–1 variables produces a bound close to or better than the standard continuous RLT2 bound (when available) but much faster, especially for larger instances, even if one does not actually decompose the Lagrangean problem. We then present numerical results for the 0–1 quadratic knapsack problem, for which no RLT2 bounds are available to our knowledge, but we show that solving an initial Lagrangean relaxation of a specific 0–1 RLT1 decomposable model drastically improves the quality of the bounds. In both cases, solving the fully decomposed rather than the decomposable Lagrangean problem to optimality will make it feasible to compute such bounds for instances much too large for computing the standard continuous RLT2 bounds.
-
efficient cuts in Lagrangean relax and cut schemes
European Journal of Operational Research, 1998Co-Authors: Monique GuignardAbstract:Abstract Lagrangean relaxation produces bounds on the optimal value of (mixed) integer programming problems. These bounds, together with integer feasible solution values, provide intervals bracketing the optimal value of the original problem. When the residual gap, i.e., the relative size of the interval, is too large for the approximations to be deemed satisfactory, it is desirable to ‘strengthen’ the Lagrangean bounds. One possible strengthening technique consists of identifying cuts which are violated by the current Lagrangean solution, and dualizing them. Unfortunately not every valid inequality that is currently violated will improve the Lagrangean relaxation bound when dualized. This paper investigates what makes a violated cut ‘efficient’ in improving bounds. It also provides examples of efficient cuts for several (mixed) integer programming problems.
-
a hybrid bounding procedure for the workload allocation problem on parallel unrelated machines with setups
Journal of the Operational Research Society, 1996Co-Authors: Hochang Lee, Monique GuignardAbstract:A nonpreemptive single stage manufacturing process with parallel, unrelated machines and multiple job types with setups (PUMS) is considered. We propose a hybrid approximation procedure where a Lagrangean relaxation dual and a Lagrangean decomposition dual are solved one after the other to generate a good lower bound on the optimal makespan value. Computational results are reported.
Brian Boffey - One of the best experts on this subject based on the ideXlab platform.
-
a comparison of Lagrangean and surrogate relaxations for the maximal covering location problem
European Journal of Operational Research, 2000Co-Authors: Roberto D Galvao, Luis Gonzalo Acosta Espejo, Brian BoffeyAbstract:Abstract We compare heuristics based on Lagrangean and surrogate relaxations of the Maximal Covering Location Problem (MCLP). The Lagrangean relaxation of MCLP used in this paper has the integrality property and the surrogate relaxed problem we solve is the LP relaxation of the original 0−1 knapsack problem. The heuristics were compared using 331 test problems available in the literature, corresponding to networks ranging from 55 to 900 vertices. The gaps obtained with both heuristics were very low and did not differ substantially among themselves for the several problem sets used, in accordance with theoretical results reviewed in the paper. When the initial set of multipliers was determined using a valid bound for MCLP the computing times did not differ significantly between the Lagrangean and surrogate heuristics.
Louis Veilleux - One of the best experts on this subject based on the ideXlab platform.
-
Lagrangean methods for the 0 1 quadratic knapsack problem
European Journal of Operational Research, 1996Co-Authors: Philippe Michelon, Louis VeilleuxAbstract:Abstract It is well known that the Lagrangean decomposition provides better bounds than the Lagrangean relaxation does. Nevertheless, the Lagrangean decomposition bound is harder to compute than the Lagrangean relaxation bound. Thus, one might wonder what is the best Lagrangean method to use in a branch-and-bound algorithm. In this paper, we give an answer to such a question for the 0–1 Quadratic Knapsack Problem. We first study the Lagrangean decomposition for this problem and give new necessary optimality conditions for the dual problem which allow us to elaborate a heuristic method for solving the Lagrangean decomposition dual problem. We then introduce this method in Chaillou-Hansen-Mahieu's branch-and-bound algorithm where upper bounds were computed by Lagrangean relaxation.
Kurt Jörnsten - One of the best experts on this subject based on the ideXlab platform.
-
a new semi Lagrangean relaxation for the p median problem
Journal of Information and Optimization Sciences, 2020Co-Authors: Alex Butsch, Kurt Jörnsten, Jörg KalcsicsAbstract:Recently Beltran-Royo et.al presented a semi-Lagrangean relaxation for the classical p-median location problem. The results obtained using the semi-Lagrangean relaxation framework approach were qui...
-
a new semi Lagrangean relaxation for the p median problem
Research Papers in Economics, 2015Co-Authors: Alex Butsch, Kurt Jörnsten, Jörg KalcsicsAbstract:Recently Beltran-Royo et.al presented a Semi-Lagrangean relaxation for the classical p-median location problem. The results obtained using the Semi-Lagrangean relaxation approach were quite impressive. In this paper we use a reformulation of the p-median problem in order to start from a formulation more suitable for Semi-Lagrangean relaxation and analyse the new approach on examples from the OR library.
-
A New Lagrangean Approach for the Travelling Salesman Problem
SSRN Electronic Journal, 2015Co-Authors: Kurt Jörnsten, Jörg KalcsicsAbstract:In this paper, we use a reformulation of the symmetric and the asymmetric travelling salesman problem more suitable for Lagrangean relaxation and analyse the new approach on examples from TSP Lib. Furthermore the Lagrangean relaxed subproblems are travelling salesman alike which means that almost all that is known on the travelling salesman polytope can be used when the subproblems are to be solved.
-
A New Semi-Lagrangean Relaxation for the K-Cardinality Assignment Problem
SSRN Electronic Journal, 2014Co-Authors: Ivan Belik, Kurt JörnstenAbstract:Recently Beltran-Royo, Vial & Alonso-Ayuso (2012) presented a semi-Lagrangean relaxation for the classical p-median location problem and for the incapacitated facility location problem. The results, obtained using the semi-Lagrangean relaxation approach, were quite impressive. In this paper we use a semi-Lagrangean relaxation to obtain an efficient solution method for the kcardinality assignment problem. The method has only one semi-Lagrangean multiplier that can only take on a limited number of values, making the search for the optimal multiplier easy. Since the semi-Lagrangean relaxation closes the duality gap, this leads to an extremely reliable and easily implementable method for finding k-cardinality assignments in large-scale cases. The method is computationally tested on the examples commonly used in the literature.
