RE: [Help-glpk] time - glpk test

[Robert Horvath]

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)

Regards
Robert

-----Original Message-----
From: address@hidden
[mailto:address@hidden On Behalf Of
Pradeep
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
characteristics
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
variables.

In both cases relaxed simplex works equally fast.

Thanks
Pradeep


        
        
                
____________________________________________________________
Yahoo! Messenger - Communicate instantly..."Ping" 
your friends today! Download Messenger Now 
http://uk.messenger.yahoo.com/download/index.html


_______________________________________________
Help-glpk mailing list
address@hidden
http://mail.gnu.org/mailman/listinfo/help-glpk