[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

RE: [Help-glpk] time - glpk test

From: Robert Horvath
Subject: RE: [Help-glpk] time - glpk test
Date: Mon, 12 Apr 2004 19:23:27 +0200

It is because the solver works like this:
* first finds a relaxation for the problem,
* checks for infeasibilities in the structural integer variables.
* branches on an integer he chooses (using the Driebeck and Tomlin
heuristics by default)
* then it solves all the problems created by the brancing above (uses best
projection heuristics by default)

I had some system with more than 7000 binary variables solved successfully
by glpk within a minute, because the relaxation itself was integer optimal.
I guess you were not that lucky with your second problem.

My suggestions:
- try a different branching method
- try a different backtracking method
(Or when IOS will have been fully implemented: -use a cutting plane method)

Otherwise it is sometimes normal for an LP solver to work on a problem for
more days, or even a week. It completely depends on the specific problem
(and is not at all proportional to the size of it)


-----Original Message-----
From: address@hidden
[mailto:address@hidden On Behalf Of
Sent: Monday, April 12, 2004 9:56 AM
To: address@hidden
Subject: [Help-glpk] time - glpk test

Hi all,
I have two sets of problems with following
Set 1:
number of variables: n
number of constraints: 6*sqrt(n)-2 (always n is
perfect sq)
Set 2:
number of variables: n
number of constraints: n

all variables are binary (0 or 1)

I modelled these two problem sets in glpk and here is
the results
Set 1:
number of variables: 900
number of constraints: 178
takes about 5 mins on a P4 128MB ram running Linux and
Gnome etc..
Set 2:
number of variables: 518
number of constraints: 518
ILP takes too long time (i waied for more than 1.5 hrs
and still could not get an optimal)

Is there any problem here ?. I could not get why the
Set 2 takes this long despite lesser number of

In both cases relaxed simplex works equally fast.


Yahoo! Messenger - Communicate instantly..."Ping" 
your friends today! Download Messenger Now

Help-glpk mailing list

reply via email to

[Prev in Thread] Current Thread [Next in Thread]