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's gravatar image

accept rate: 0%

edited 11 Mar '15, 15:53


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

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

  journal={Mathematical Programming},
  title={Two “well-known” properties of subgradient optimization},
  author={Anstreicher, KurtM. and Wolsey, LaurenceA.},

For more detail.


answered 12 Mar '15, 03:16

Sune's gravatar image

accept rate: 20%

edited 12 Mar '15, 06:48

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
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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



Asked: 11 Mar '15, 14:35

Seen: 803 times

Last updated: 12 Mar '15, 15:06

OR-Exchange! Your site for questions, answers, and announcements about operations research.