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.