Friday, September 12, 2008


> I am dealing with a class of large scale LPs. The class has nice
> structure though, let's say it has 1000 constraints. The objective
> function and the first 999 constraints are identical among all
> instances of the problems in this class. So everytime that user wants
> to solve a new problem it is only different from other problems in the
> 1000th constraint.
> I was wondering if this feature can be exploited to improve the speed
> of solving problems in this class. Is it possible that something be
> pre-computed and stored about the problem from the fixed part
> (objective and 999 constraints) and then everytime that user inserts
> the 1000'th constraint, that knowledge be used efficiently?

Absolutely. 1000 constraints is very small, but in general simplex based LP solvers have excellent restart facilities using the concept of a basis. Using the GAMS modeling language this even completely automated. I.e. the fragment:
set scenario /s1*s5/;

parameter growthq_s(scenario) /
s1 2
s2 2.2
s3 2.3
s4 2.5
s5 2.7

parameter report(scenario,*);

growthq = growthq_s(scenario);
solve wsisn maximizing cps using lp;
report(scenario,'time') = wsisn.resusd;
report(scenario,'iterations') = wsisn.iterusd;

display report;

solves a series of related LP's: one coefficient in the model
changes here. Iteration count and cpu time are recorded and
they are displayed as:
 ----   3642 PARAMETER report

time iterations

s1 0.630 3704.000
s2 0.108 76.000
s3 0.070 76.000
s4 0.066 76.000
s5 0.069 76.000

so indeed the first solve is the most expensive one.

No comments:

Post a Comment