Improved Lagrangian bounds and heuristics for the generalized assignment problem
- Systems Analysis and Operations Research
- Published: 24 April 2017
- Volume 56 , pages 803–809, ( 2017 )
Cite this article
- I. Litvinchev 1 , 2 , 3 ,
- M. Mata 1 , 2 , 3 ,
- J. Saucedo 1 , 2 , 3 &
- S. Rangel 1 , 2 , 3
69 Accesses
Explore all metrics
Modified Lagrangian bounds are proposed for the generalized assignment problem. The approach is based on a double decomposable structure of the formulation. A family of greedy heuristics is considered to get Lagrangian based feasible solutions. Numerical results for problem instances with number of agents close to number of tasks are provided.
This is a preview of subscription content, log in via an institution to check access.
Access this article
Price includes VAT (Russian Federation)
Instant access to the full article PDF.
Rent this article via DeepDyve
Institutional subscriptions
Similar content being viewed by others
Other Applications in General Integer Programming
Variable-fixing then subgradient optimization guided very large scale neighborhood search for the generalized assignment problem
Salim Haddadi
Some results on an assignment problem variant
Pritibhushan Sinha
L. S. Lasdon, Optimization Theory for Large Scale Systems (Dover, New York, 2002).
MATH Google Scholar
V. Jeet and E. Kutanoglu, “Lagrangian relaxation guide problem space search heuristics for generalized assignment problem,” Eur. J. Operat. Res. 182 , 1039–1056 (2007).
Article MATH Google Scholar
M. Laguna, J. P. Kelly, J. L. Gonzalez Velarde, and F. Glover, “Tabu search for the multilevel generalized assignment problem,” Eur. J. Operat. Res. 82 , 176–189 (1995).
C. Lemaréchal, “Lagrangian relaxation,” in Computational Combinatorial Optimization , Ed. by M. Junger and D. Naddefs (Springer, Berlin, 2001), pp. 115–160.
Google Scholar
C. Lemaréchal, “The omnipresence of lagrange,” Ann. Operat. Res. 153 , 9–27 (2007).
Article MathSciNet MATH Google Scholar
M. Boschetti and V. Maniezzo, “Benders descomposition, lagrangian relaxation and metaheuristics design,” J. Heuristics 15 , 283–312 (2009).
I. S. Litvinchev, “Refinement of lagrangian bounds in optimization problems,” Comput. Math. Math. Phys. 47 , 1101–1107 (2007).
Article MathSciNet Google Scholar
I. Litvinchev, S. Rangel, and J. Saucedo, “A lagrangian bound for many-to-many assignment problems,” J. Combin. Optimiz. 19 , 241–257 (2010).
R. Bukard, M. DellAmico, and S. Martello, Assignment Problems (SIAM, Philadelphia, 2009).
Book Google Scholar
D. W. Pentico, “Assignment problems: a golden anniversary survey,” Eur. J. Operat. Res. 176 , 774–793 (2007).
R. K. Martin, Large Scale Linear and Integer Programming: A Unified Approach (Kluwer, Boston, 1999).
P. C. Chu and J. E. Beasley, “A genetic algorithm for the generalized assignment problem,” Comput. Operat. Res. 24 , 17–23 (1997).
H. E. Romeijn and D. Romero, “A class of greedy algorithms for the generalized assignment problem,” Discrete Appl. Math. 104 , 209–235 (2000).
M. Yaguira and T. Ibaraki, “Generalized assignment problem,” in Handbook of Approximation Algorithms and Metaheuristics, CRC in Comput. Inform. Sci. Ser. , Ed. by T. F. Gonzalez (Taylor, CRC, Boca Raton, FL, 2007), Chap.48.
M. Posta, J. A. Ferland, and P. Michelon, “An exact method with variable fixing for solving the generalized assignment problem,” Comput. Optimiz. Appl. 52 , 629–644 (2012).
K. Sethanan and R. Pitakaso, “Improved differential evolution algorithms for solving generalized assignment problem,” Expert Syst. Appl. 45 , 450–459 (2016).
Article Google Scholar
S. Martello and P. Toth, Knapsack Problems. Algorithms and Computer Implementations (Wiley, Chichester, 1990).
A. A. Mironov and V. I. Tsurkov, “Network models with fixed parameters at the communication nodes I,” Izv. Akad. Nauk, Tekh. Kibernet., No. 4, 212–223 (1993).
MathSciNet MATH Google Scholar
A. A. Mironov and V. I. Tsurkov, “Network models with fixed parameters at the communication nodes II,” Izv. Akad. Nauk, Tekh. Kibernet., No. 6, 3–14 (1993).
A. A. Mironov and V. I. Tsurkov, “Transportation problems with minimax criteria,” Dokl. Akad. Nauk 346 (2), 1–4 (1996).
A. A. Mironov and V. I. Tsurkov, “Hereditarily minimax matrices in models of transportation type,” J. Comput. Syst. Sci. Int. 37 , 927–944 (1998).
A. A. Mironov and V. I. Tsurkov, “Minimax under nonlinear transportation constraints,” Dokl. Math. 64 , 351–354 (2001).
A. A. Mironov and V. I. Tsurkov, “Minimax in transportation models with integral constraints: I,” J. Comput. Syst. Sci. Int. 42 , 562–574 (2003).
A. A. Mironov, V. V. Fedorchuk, and V. I. Tsurkov, “Minimax in transportation models with integral constraints: II,” J. Comput. Syst. Sci. Int. 44 , 732–752 (2005).
Download references
Author information
Authors and affiliations.
Computing Center Russian Academy of Sciences, Moscow, Russia
I. Litvinchev, M. Mata, J. Saucedo & S. Rangel
Faculty of Mechanical and Electrical Engineering(UANL), New Leon, Mexico
Department of Applied Mathematics (UNESP), Saint Paulo, Brasil
You can also search for this author in PubMed Google Scholar
Corresponding author
Correspondence to I. Litvinchev .
Additional information
Original Russian Text © I. Litvinchev, M. Mata, J. Saucedo, S. Rangel, 2017, published in Izvestiya Akademii Nauk, Teoriya i Sistemy Upravleniya, 2017, No. 5, pp. 53–59.
Rights and permissions
Reprints and permissions
About this article
Litvinchev, I., Mata, M., Saucedo, J. et al. Improved Lagrangian bounds and heuristics for the generalized assignment problem. J. Comput. Syst. Sci. Int. 56 , 803–809 (2017). https://doi.org/10.1134/S1064230717050070
Download citation
Received : 01 December 2015
Published : 24 April 2017
Issue Date : September 2017
DOI : https://doi.org/10.1134/S1064230717050070
Share this article
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative
- Find a journal
- Publish with us
- Track your research
- Victor Mukhin
Victor M. Mukhin was born in 1946 in the town of Orsk, Russia. In 1970 he graduated the Technological Institute in Leningrad. Victor M. Mukhin was directed to work to the scientific-industrial organization "Neorganika" (Elektrostal, Moscow region) where he is working during 47 years, at present as the head of the laboratory of carbon sorbents. Victor M. Mukhin defended a Ph. D. thesis and a doctoral thesis at the Mendeleev University of Chemical Technology of Russia (in 1979 and 1997 accordingly). Professor of Mendeleev University of Chemical Technology of Russia. Scientific interests: production, investigation and application of active carbons, technological and ecological carbon-adsorptive processes, environmental protection, production of ecologically clean food.
Title : Active carbons as nanoporous materials for solving of environmental problems
Quick links.
- Conference Brochure
- Tentative Program
Current time by city
For example, New York
Current time by country
For example, Japan
Time difference
For example, London
For example, Dubai
Coordinates
For example, Hong Kong
For example, Delhi
For example, Sydney
Geographic coordinates of Elektrostal, Moscow Oblast, Russia
City coordinates
Coordinates of Elektrostal in decimal degrees
Coordinates of elektrostal in degrees and decimal minutes, utm coordinates of elektrostal, geographic coordinate systems.
WGS 84 coordinate reference system is the latest revision of the World Geodetic System, which is used in mapping and navigation, including GPS satellite navigation system (the Global Positioning System).
Geographic coordinates (latitude and longitude) define a position on the Earth’s surface. Coordinates are angular units. The canonical form of latitude and longitude representation uses degrees (°), minutes (′), and seconds (″). GPS systems widely use coordinates in degrees and decimal minutes, or in decimal degrees.
Latitude varies from −90° to 90°. The latitude of the Equator is 0°; the latitude of the South Pole is −90°; the latitude of the North Pole is 90°. Positive latitude values correspond to the geographic locations north of the Equator (abbrev. N). Negative latitude values correspond to the geographic locations south of the Equator (abbrev. S).
Longitude is counted from the prime meridian ( IERS Reference Meridian for WGS 84) and varies from −180° to 180°. Positive longitude values correspond to the geographic locations east of the prime meridian (abbrev. E). Negative longitude values correspond to the geographic locations west of the prime meridian (abbrev. W).
UTM or Universal Transverse Mercator coordinate system divides the Earth’s surface into 60 longitudinal zones. The coordinates of a location within each zone are defined as a planar coordinate pair related to the intersection of the equator and the zone’s central meridian, and measured in meters.
Elevation above sea level is a measure of a geographic location’s height. We are using the global digital elevation model GTOPO30 .
Elektrostal , Moscow Oblast, Russia
IMAGES
VIDEO
COMMENTS
We present a heuristic for this problem in which an assignment of customers to vehicles is obtained by solving a generalized assignment problem with an objective function that approximates delivery cost. This heuristic has many attractive features. It has outperformed the best existing heuristics on a sample of standard test problems.
The generalized assignment problem is a classical combinatorial optimization problem that ... M.L. Fisher and R. Jaikumar, A generalized assignment heuristic for vehicle routing, Net-works, 11 (1981) 109-124. [3] B. Gavish and H. Pirkul, Allocation of databases and processors in a distributed computing
In applied mathematics, the maximum generalized assignment problem is a problem in combinatorial optimization.This problem is a generalization of the assignment problem in which both tasks and agents have a size. Moreover, the size of each task might vary from one agent to the other. This problem in its most general form is as follows: There are a number of agents and a number of tasks. Any ...
The classical generalized assignment problem ... Lagrangian relaxation guided problem space search heuristics for generalized assignment problems. European Journal of Operational Research, Vol. 182, No. 3. An LP-based heuristic procedure for the generalized assignment problem with special ordered sets.
We present new Branch-and-Bound algorithm for the generalized assignment problem. A standard subgradient method (SM), used at each node of the decision tree to solve the Lagrangian dual, provides an upper bound. Our key contribution in this paper is a new heuristic, applied at each iteration of the SM, which tries to exploit the solution of the ...
A new approach for solving the generalized assignment problem (GAP) is proposed that combines the exact branch & bound approach with the heuristic strategy of tabu search (TS) to produce a hybrid ...
A special purpose branch-and-bound algorithm that utilizes linear programming cuts, feasible-solution generators, Lagrangean relaxation, and subgradient optimization that can be used quite effectively as a heuristic when proof of optimality is not an absolute requirement is described. The classical generalized assignment problem (GAP) may be stated as finding a minimum-cost assignment of tasks ...
Abstract. We present new Branch-and-Bound algorithm for the generalized assignment problem. A standard subgradient method (SM), used at each node of the decision tree to solve the Lagrangian dual ...
Because the Generalized Assignment Problem is NP-hard, optimization methods tend to require larger computation times for large-scale problems. This paper presents a new heuristic, Variable-Depth-Search Heuristic (VDSH). We show that on the sets of large test problems, the quality of the solution found by VDSH exceeds that of the leading ...
The generalized assignment problem (GAP) seeks the minimum cost assignment of n tasks to m agents such that each task is assigned to precisely one agent subject to capacity restrictions on the agents. The formulation of the problem is: where \ ( c_ {ij} \) is the cost of assigning task j to agent i , \ ( a_ {ij} \) is the capacity used when ...
It is shown that on the sets of large test problems, the quality of the solution found by VDSH exceeds that of the leading heuristic by an average of over twenty percent, while maintaining acceptable solution times. The Generalized Assignment Problem, in the class of NP-hard problems, occurs in a wide range of applications — vehicle packing, computers, and logistics, to name only a few ...
The generalised assignment heuristic for the basic vehicle routing problem (VRP) can be extended by adjusting seed positions to reduce the optimal objective value for the generalised assignment problem (GAP). Combined with a simple Lagrangean heuristic, this gives a relatively straightforward method for obtaining solutions within a few percent ...
Modified Lagrangian bounds are proposed for the generalized assignment problem. The approach is based on a double decomposable structure of the formulation. A family of greedy heuristics is considered to get Lagrangian based feasible solutions. Numerical results for problem instances with number of agents close to number of tasks are provided.
The solution obtained by the generalized assignment. heuristic has cost 159.59 and is shown in figure 2. For comparison, the Sweep solution which has a cost of 166.73 is shown. in figure. 3. The Clarke and Wright solution had a cost of 164.03. Seed customers can be selected either by an automatic.
This paper presents a heuristic for this problem in which an assignment of customers to vehicles is obtained by solving a generalized assignment problem with an objective function that approximates delivery cost and shows that it has outperformed the best existing heuristics on a sample of standard test problems. Abstract : We consider a common variant of the vehicle routing problem in which a ...
We present a heuristic for this problem in which an assignment of customers to vehicles is obtained by solving a generalized assignment problem with an objective function that approximates delivery cost. This heuristic has many attractive features. It has outperformed the best existing heuristics on a sample of standard test problems.
Catalysis Conference is a networking event covering all topics in catalysis, chemistry, chemical engineering and technology during October 19-21, 2017 in Las Vegas, USA. Well noted as well attended meeting among all other annual catalysis conferences 2018, chemical engineering conferences 2018 and chemistry webinars.
1. Introduction. The Generalized Assignment Problem (GAP) is a classical combinatorial optimization problem: We are given a set M of agents and a set N of tasks. Assigning a task j to an agent i produces a profit pij and requires an amount wij of resource ( weight ). Each agent i has a maximum resource capacity ci.
In 1954, Elemash began to produce fuel assemblies, including for the first nuclear power plant in the world, located in Obninsk. In 1959, the facility produced the fuel for the Soviet Union's first icebreaker. Its fuel assembly production became serial in 1965 and automated in 1982. 1. Today, Elemash is one of the largest TVEL nuclear fuel ...
Geographic coordinates of Elektrostal, Moscow Oblast, Russia in WGS 84 coordinate system which is a standard in cartography, geodesy, and navigation, including Global Positioning System (GPS). Latitude of Elektrostal, longitude of Elektrostal, elevation above sea level of Elektrostal.
Elektrostal, city, Moscow oblast (province), western Russia.It lies 36 miles (58 km) east of Moscow city. The name, meaning "electric steel," derives from the high-quality-steel industry established there soon after the October Revolution in 1917. During World War II, parts of the heavy-machine-building industry were relocated there from Ukraine, and Elektrostal is now a centre for the ...