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 
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 LPsolution. See the paper
For more detail. answered 12 Mar '15, 03:16 Sune 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

Can you explain why you don't want to use an LP solver?
Hi Austin, Its mainly because of the processing time and I dont have access to cplex