Friday, September 12, 2008

Restarts

> 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,*);

loop(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.