Conference rusure::math

1018.0. "Large-Scale 0-1 Linear Programming" by DACT6::CANNON (Tim Cannon - Washington DC, ACT) Thu Jan 26 1989 09:09

 	This note is related to 671 and addresses large-scale 0-1 linear
    programming.  I have recently extended and implemented a method
    for solving large scale 0-1 problems using workstations on an Ethernet.
     So far our testing has been on problems supplied by IBM.  I'm looking
    for any large (2000-5000 variables) problems formulated as 0-1 models.
    To date, I have a lead on PCB layout and on distributed database
    segregation.  
    
    Any leads on people or groups who are trying to solve these problems
    will be much appreciated.
    
    The abstract for the research follows.
    
    Tim
 
 

                      Large-Scale 0-1 Linear Programming
                          on Distributed Workstations




Minicomputer workstations connected by an Ethernet network have been used to 
solve large-scale zero-one linear programming problems.  On the largest 
problems, linear and super-linear speedup have been achieved.  Using the 
``branch-and-cut'' approach of Hoffman, Padberg and Rinaldi, eight 
workstations have been used in parallel to solve the full test set documented 
in Crowder, Johnson and Padberg's 1983 Operations Research article.  Very 
inexpensive, networked workstations are now solving in minutes, problems which 
were once considered not solvable in economically feasible times.  

This implementation extends the original work by generating a ``pool'' of 
facial cuts that may be used by any processor.  Because facial cuts are valid 
at any point in the polytope, and because different workstations are generally 
working at different points in the polytope, cuts are generated and placed in 
the pool earlier than would have otherwise been experienced.  By scanning the 
pool prior to generating cuts, each processor may choose as many violated 
inequalities as apply to that point in the polytope.  The selection of cuts 
that may have been identified by other CPUs has led to a significant decrease 
in running time for large problems. 

In this peer-to-peer (as opposed to master-worker) implementation, 
interprocess communication was accomplished by exploiting the VAX-system 
architecture.  Using shared files and resource locks, effective communication 
between processes was accomplished with a minimum of overhead.

The method of implementation and computational results will be presented. 
    

    The note to which this entry relates is really 691.  Sorry for the
    confusion....
    
    
    Tim