CRPC-TR90091-S

Computational Results with Another Method of Solving Very Long and Thin LPs

                         Petra Mutzel
                         
                         (Abstract)

Given a very long and thin Linear Program, the idea is to initially solve a 
smaller subproblem containing only a few variables (columns of the LP). Any
optimal solution of the subproblem is feasible for the original Linear Program.
Therefore, if all the remaining columns have nonnegative reduced costs, the 
solution of the subproblem is also optimal for the original Linear Program.
Hence in this case we are done. In case that there are columns with negative 
reduced costs, we select new columns of the constraint matrix and solve this 
new subproblem. This report describes computational results for several stra-
tegies in selecting the new columns for the subproblem.

The first idea is to select the columns with minimal reduced costs. It turned 
out to be very useful, but also time-consuming, to choose those columns which 
have minimum normalized reduced costs (Steepest Edge Pricing). Therefore we 
implemented a combination of both strategies. In special situations it turned
out to be a good idea to replace only 70% of the columns of the subproblem by 
new columns. Solving the subproblem only almost to optimality led to further 
improvements. We also introduced some random factors and varied the number of
restarts during the execution of the algorithm.

Ms. Petra Mutzel
Institut f. Informatik
Universitaet zu Koeln
Pohligstr. 1
50969 Koeln
Germany

mutzel@informatik.uni-koeln.de
0221 / 3671114