# approximating continuous generalized assignment problem (GAP)

 0 Hi, I am looking for a heuristic algorithm that can efficiently solve the linear relaxation of generalized assignment problem which can have a large dataset. We want to let variable x be continuous between 0 and 1. I appreciate if you can suggest me an algorithm to find a solution with an acceptable quality in a reasonable time (without using linear solvers like Cplex, etc). asked 11 Mar '15, 14:35 Mehrdad 47●4●7 accept rate: 0% 1 Can you explain why you don't want to use an LP solver? (11 Mar '15, 23:09) Austin Buchanan Hi Austin, Its mainly because of the processing time and I dont have access to cplex (12 Mar '15, 08:43) Mehrdad

 1 One way to approach this is to use a Lagrangean relaxation of either the capacity or assignment constraints (or both) and then use a subgradient procedure to approximate the Lagrangean multipliers. It turns out that if you choose your step size in the right way, a simple average of the solutions to the Lagrangean subproblems approximates an optimal LP-solution. See the paper @article{ year={2009}, journal={Mathematical Programming}, volume={120}, number={1}, title={Two “well-known” properties of subgradient optimization}, publisher={Springer-Verlag}, author={Anstreicher, KurtM. and Wolsey, LaurenceA.}, pages={213-220}, language={English} }  For more detail. answered 12 Mar '15, 03:16 Sune 958●4●13 accept rate: 20% Thank you Sune for your detailed answer. Subgradient methods can be applied to any optimization problem and sometimes, specially if you are dealing with a large scale model, it is not so easy. Here I want to take some benefits of special structure of the problem(GAP) to derive a fast solution. There are several algorithms to find an approximative binary solution for GAP. but I am looking for a near optimal solution with continuous variables. or even get a better upper bound after getting a binary solution Thanks again for your time (12 Mar '15, 08:40) Mehrdad If you relax the capacity constraints in a Lagrangean manner, you end up with a very easy subproblem. I could imagine there is some range for the optimal Lagrangean multipliers listed somewhere in the literature you could us to "box" the multipliers in order to speed up convergence. Have never actually tried it, though. (12 Mar '15, 15:06) Sune
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags: