[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Help-glpk] Initial Basis
From: |
Ulrich Spörlein |
Subject: |
[Help-glpk] Initial Basis |
Date: |
Fri, 14 Oct 2005 15:18:15 +0200 |
Hello all,
I have some trouble understanding how I can pass an initial basis to
GLPK. First of all, with my LP-class, roughly 80-90% of the time is
spent with constructing an initial feasible solution. Now of course I'd
like to improve this time.
Since I am load balancing a number of flows in a graph, all my variables
(except one!) are bound by [0, 1]. And all variables of one load
balancing group have to add up to 100%.
Now, I can *always* give an initial feasible solution by setting all the
variables of one LB-group to 1/x. That is, use 50:50 or 33:33:33 as load
balancing scheme.
Thus I immediately have a working, but far from optimal, solution. Now I
could let the LP solver improve upon that solution, and if I'm
restricted by a run time of, say, 10 minutes, I get an acceptable
solution.
You see, it is better for me, to have a somewhat working solution after a
short period, than to wait 90% of the time (hours!) to get the first
workable solution (which is very, very good already, but the run time
...)
Now I read the GLPK manual and I know that I can only set the status of
a variable, not the actual value. What I don't know is, what a basic and
a non-basic variable is. What's the difference of an active and
non-active constraint? As you already guessed, Linear Programming is not
my field of expertise. Any pointers are greatly appreciated!
Ulrich Spoerlein
--
PGP Key ID: F0DB9F44 Encrypted mail welcome!
Fingerprint: F1CE D062 0CA9 ADE3 349B 2FE8 980A C6B5 F0DB 9F44
Ok, which part of "Ph'nglui mglw'nafh Cthulhu R'lyeh wgah'nagl fhtagn."
didn't you understand?
pgpbnbgkVzotS.pgp
Description: PGP signature
- [Help-glpk] Initial Basis,
Ulrich Spörlein <=