[Clp] Fwd: Solving Linear Relaxation of Generalized Assignment Problem with COIN-OR CLP

[Stefan Vigerske]

Don't know why this was send to me. Maybe someone on the list wants to help.


-------- Original Message --------
Subject: Solving Linear Relaxation of Generalized Assignment Problem 
with COIN-OR CLP
Date: Tue, 1 Jul 2014 15:52:49 +0800
From: Huahui Liu <liuhuahui88 at gmail.com>
To: Stefan at gams.com

Hi,

I've model my problem at hand as a Linear Relaxation of Generalized
Assignment Problem(LRGAP), and I'm searching for fast Linear
Programming(LP) implementation to solve it.

I tried both Simplex and Interior Point method in various open source LP
implementations. So far as I know, COIN-OR CLP with GUB(testGub.cpp)
dominates all. But it's still NOT fast enough.

I'm wondering whether we could improve the performance by leveraging other
special structures in LRGAP(e.g. Generalized Network Structure).

I tried to read the code of ClpDynamicMatrix and ClpDynamicExampleMatrix
but it seems hard to understand.

Here're my questions:

1. Could you give me some detailed doc about Dynamic Matrix?
2. In your opinion, is it prospective to substantially improve the
performance based on CLP with GUB by leveraging Generalized Network
Structure in LRGAP?
3. Is there any specific algorithm to tackle LRGAP?

Thank you very much!

Sincerely, Neo