A Parallel Algorithm for Linear Programs with an Additional Reverse Convex Constraint

✍ Scribed by Shih-Mim Liu; G.P. Papavassilopoulos

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 211 KB
• Volume: 45
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.1997.1366

✦ Synopsis

A parallel method for globally minimizing a linear program with an additional reverse convex constraint is proposed which combines the outer approximation technique and the cutting plane method. Basically p (≤n) processors are used for a problem with n variables and a globally optimal solution is found effectively in a finite number of steps. Computational results are presented for test problems with a number of variables up to 80 and 63 linear constraints (plus nonnegativity constraints). These results were obtained on a distributed-memory MIMD parallel computer, DELTA, by running both serial and parallel algorithms with double precision. Also, based on 40 randomly generated problems of the same size, with 16 variables and 32 linear constraints (plus x ≥ 0), the numerical results from different number processors are reported, including the serial algorithm's.