A Scalable P arallel Algorithm for Multiple Ob jectiv e Linear Programs y Malgorzata M Wiecek Hong Zhang Abstract This pap er presen ts an ADBASE based parallel algorithm for solv ing m ultiple ob jectiv e linear programs MOLPs Job balance sp eedup and scalabilit y are of primary in terest in ev aluating e ciency of the new algorithm Implemen tation results on In tel iPSC and P aragon m ultipro cessors sho w that the algorithm signi can tly sp eeds up the pro cess of solving MOLPs whic h is understo o d as generating all or some e cien t extreme p oin ts and un b ounded e cien t edges The al gorithm giv es sp ecially go o d results for large and v ery large problems Motiv ation and justi cation for solving suc h large MOLPs are also included Departmen t of Mathematical Sciences Clemson Univ ersit y Clemson SC U S A wmalgor c lem so n c le mso n edu Researc h supp orted in part b y the National Science F oundation under con tract DMS y Institute for Computer Applications in Science and Engineering NASA Langley Re searc h Cen ter Hampton V A U S A On lea v e from Departmen t of Mathematical Sciences Clemson Univ ersit y Clemson SC hongsu ma th cl ems on ed u Researc h supp orted b y the National Aeronautics and Space Administration under NASA Con tract No NAS i In tro duction Complex decision problems related to econom y en vironmen t business and engineering are m ultidimensional and ha v e m ultiple and con icting ob jec tiv es In the presence of m ultiple ob jectiv es a decision problem has to b e treated in the m ulticriteria decision making framew ork Multiple ob jectiv e programming is concerned with generating solution sets of m ultiple ob jectiv e problems that usually include a large or in nite n um b er of p oin ts referred to as e cien t solutions Those e cien t p oin ts are then the can didates for optimal solutions of the m ulticriteria decision making problem Multicriteria problems are therefore naturally w ell structured to b e solv ed on parallel arc hitectures It has b een already pro v en that parallel algorithms o er substan tial sa vings in execution time facilitate solving more complex computational problems and mak e real time resp onse p ossible for problems that w ere previously considered as in tractable b ecause of their magnitude Sev eral studies on the p oten tial of using parallel pro cessing in the eld of m ulticriteria optimization ha v e b een already undertak en Evtushenk o et al recognized that m ulticriteria optimization deals with one of the most sophisticated asp ects of h uman activit y whic h is to ac hiev e sev eral goals b y a single act of decision making Driv en b y this idea they dev elop ed DISO a dialogue system for solving optimization problems whose one of the main parts is the m ulticriteria optimization pac k age They also suggested a p ossi bilit y of organizing parallel calculations within this pac k age The study re p orted b y Climaco et al seems to b e the rst completed researc h task in the area of m ulticriteria optimization and fo cuses on using parallel pro cess ing in in teractiv e m ultiple ob jectiv e linear programming Grauer and Bo den discussed opp ortunities in parallelization for mathematical programming problems and in teractiv e decision supp ort Ng and Y ang prop osed to sample the e cien t fron tier of a m ultiple ob jectiv e program b y sim ultane ously solving related single criterion optimization problems dev elop ed using the constrain t approac h A m ultiple reference p oin t approac h to solv ing m ultiple ob jectiv e linear programs MOLPs w as dev elop ed b y Costa and Climaco and parallel pro cessors w ere k ept to con trol the reference p oin ts and help the decision mak er searc h for e cien t and optimal solutions Lew ando wski rep orted parallel implemen tation of selected m ulticriteria optimization algorithms The eld of engineering pro vides v arious applications of m ulticriteria optimization recen tly also implemen ted on parallel arc hitectures Chang prop osed a pattern recognition approac h for optimization of p o w er systems in a m ultiob jectiv e en vironmen t The researc h w ork rep orted in this pap er as a con tin uation of prelimi nary studies rep orted in and is related to solving an MOLP whic h is understo o d as generating all or a subset of e cien t solutions of this prob lem MOLPs often ha v e a large n um b er of solutions in the form of extreme e cien t p oin ts EEPs and un b ounded e cien t edges The pro cess of nding all of them or ev en a subset of them is v ery space and time consuming Sp eeding up the pro cess can b e naturally supp orted b y new algorithms executed on parallel computers The a v ailabilit y of sequen tial algorithms for generating e cien t p oin ts of m ultiple ob jectiv e programs and rising in terest in parallel computations motiv ated to dev elop a parallel algorithm for MOLPs The structure of the e cien t set of MOLPs turns out to b e v ery helpful in designing a parallel algorithm Since ev ery e cien t extreme p oin t is connected to ev ery other e cien t extreme p oin t b y a series of e cien t edges the pro cess of nding e cien t p oin ts can b e organized so that subsets of the e cien t set can b e generated sim ultaneously The parallel algorithm prop osed in this w ork is based on ADBASE a w ell kno wn sequen tial computer pac k age for solving MOLPs The pap er is organized as follo ws In the next section the soft w are AD BASE is brie y presen ted with emphasis on sev eral ideas for its paralleliza tion Some of these ideas are discussed in more detail since they ha v e b een tested in the rst stage of this researc h and resulted in a basic parallel al gorithm Section discusses t w o strategies that signi can tly impro v ed the e ciency of the basic parallel algorithm and includes the actual parallel algorithm The algorithm has b een implemen ted on an In tel iPSC and a P aragon m ultipro cessors for man y MOLPs fo cusing on large and extremely large problems Its e ciency and scalabilit y ha v e b een measured and are rep orted in Section Incen tiv es for dealing with large m ultiple ob jectiv e programs are discussed in the same section Conclusions as w ell as some directions for further researc h are giv en in the nal section ADBASE and its basic parallel algorithm Consider an MOLP form ulated as follo ws maxfz C x j x S g where S fx j A x b A x b A x b g m m m m m m C is an k n matrix A are m n matrices and b are m v ectors with m i m i i i nonnegativ e comp onen ts i The soft w are ADBASE generates all e cien t extreme p oin ts and un b ounded e cien t edges of MOLPs A p oin t x in S is called an e cien t solution of an MOLP if there is no other p oin t x in S suc h that C x C x with strict inequalit y holding for at least one comp onen t In general solving an MOLP can b e view ed as nding a subset of all ex treme p oin ts asso ciated with the feasible set S whic h is someho w similar to solving a linear program with m ultiple solutions ADBASE consists of three main phases In Phase a single ob jectiv e linear program SOLP related to the original MOLP is solv ed for an initial feasible extreme p oin t of the MOLP Phase searc hes for an initial e cien t extreme p oin t IEEP of the problem and Phase includes generating all e cien t extreme p oin ts and un b ounded e cien t edges In Phase all non basic v ariables of an IEEP are c hec k ed for feasibilit y and e ciency whic h iden ti es all e cien t extreme solutions adjacen t to the initial one The feasibilit y and e ciency test is con tin ued at e cien t extreme p oin ts subsequen tly found b y p erforming sim plex piv ot op erations b et w een a curren t and adjacen t e cien t extreme p oin t this op eration will b e referred to as the e cient pivot op er ation The b o ok k eeping includes storing EEPs that ha v e b een already found and their bases referred to as e cient b ases The pro cess go es on un til all solutions are generated Assigning the e cien t solutions to no des and e cien t edges to arcs one can construct a graph referred to as the EEP gr aph along whic h the searc h can b e p erformed Since using this pro cedure Phase dominates computations and searc hing in the graph the parallelization is naturally started from there The op eration of mo ving from one co ded basis to another is called cr ash ing and the related subroutine CRASH p erforms it in ADBASE Once a pro cessor nished w orking on a curren t basis it ma y crash to another one b y p erforming a required n um b er of not necessarily feasible piv ots that are needed to mo v e b et w een the t w o bases A basic parallel algorithm presen ted b elo w is based on the assumption that eac h of pro cessors searc hes a subgraph of the EEP graph along the no des and edges that are generated b y itself with minim um o v erlapping so that v ery limited b o okk eeping has to b e emplo y ed A pro cessor has its o wn list on whic h e cien t bases are co ded as when a basis is found b y itself or as when a basis is found b y other pro cessors Basic P arallel Algorithm All pro cessors nd an iden tical IEEP b y running Phase and Phase of ADBASE Statically assign the non basic v ariables of this IEEP to all pro cessors In parallel do on all pro cessors Examine curren t non basic v ariable If a new e cien t basis is found broadcast a co ded message called list message to all the other pro cessors and put it on its o wn list with co de Chec k its bu er for p ossible new bases sen t b y other pro cessors and up date its list accordingly If there is a subsequen t e cien t basis with co de on its list crash to it and go bac k to Step otherwise go to Step Send a done message to all the other pro cessors since it has nished examining all e cien t bases found b y itself Receiv e either list message or done message un til all done messages from the other pro cessors ha v e b een receiv ed This basic parallel algorithm has b een tested on an In tel iPSC h yp er cub e mac hine T able sho ws the parallel execution times for p pro cessors as w ell as for sequen tial ADBASE p on small testing problems The second column of this table sp eci es the n um b er of e cien t bases and EEPs F or example problem has e cien t bases and EEPs while problem has e cien t bases and EEPs P arallel execution time is deter mined b y the slo w est pro cessor In order to see the parallel e ciency of the algorithm the shortest time used b y a pro cessor is listed inside paren theses One can see that in all cases but one this basic parallel algorithm did b et ter than the sequen tial algorithm and more pro cessors solv ed the problems faster The algorithm ho w ev er has t w o disadv an tages Firstly it su ers from sev ere job im balance Eac h pro cessor examines only those e cien t solutions that ha v e b een found b y itself The non basic v ariables that lead to e cien t T able Execution Time of the Basic P arallel Algorithm Seconds Problem No of Solutions p p p bas ex bas ex bas ex piv ots mak e their pro cessors w ork and progress through the graph while the pro cessors assigned to the non basic v ariables that failed the e ciency test stop w orking and b ecome idle ev en that there are still man y e cien t p oin ts to b e found Secondly the algorithm is v ery m uc h dep enden t up on the IEEP An IEEP with more e cien t piv ots w ould allo w more pro cessors to do actual w ork and th us result in a faster p erformance It w as b eliev ed that the large time discrepancies b et w een the slo w est and the fastest pro cessors sho wn in T able are mainly caused b y these t w o shortcomings of the algorithm P arallel algorithm In this section w e shall discuss sev eral impro v emen ts made on the basic parallel algorithm and presen t a more adv anced algorithm The adv an tage of parallel computation can b e easily lost when the load is un balanced V ery visibly the basic parallel algorithm describ ed in Section su ers from sev ere job im balance The nature of the MOLP mak es the task of job balancing di cult First subgraphs of the EEP graph ha v e to b e searc hed dynamically since they cannot b e equally distributed among pro cessors b efore the execution Second re activ ating idle pro cessors un a v oidably increases the b o okk eeping complexit y comm unication as w ell as redundan t computations In order to ha v e eac h pro cessor w ork un til all the e cien t p oin ts are found the strategy called r e cr ashing is prop osed The dynamic searc h of the subgraphs and recrashing are no w describ ed In the basic parallel algorithm if a new basis has b een found a pro ces sor normally just sends the co ded basis to all other pro cessors No w along with sending this the pro cessor also sends a n um b er referred to as w ork n um b er indicating its w orking status F or example a implies the pro cessor is still w orking on a basis found b y itself is a done message and rep orts that this pro cessor has re started and is w orking on a basis sen t to it Eac h pro cessor also has an in teger N um done on its list This n um b er indicates ho w man y pro cessors are not w orking an ymore The program terminates when all pro cessors ha v e stopp ed w orking When a pro cessor receiv es message from other pro cessors it adds attac hed w ork n um b er to its N um done F or instance when is receiv ed b y a pro cessor it kno ws that a previously idle pro cessor has b egun to w ork again and decremen ts its N um done When a pro cessor nished examining all bases found b y itself and sen t a done message to all other pro cessors instead of simply receiving messages and w aiting for other pro cessors to nish their searc h this pro cessor will crash to an y coming new basis and p erform the e cien t piv ot op eration on it If a new e cien t solution is found its co de together with the w ork n um b er are sen t out The pro cessor then progresses from there and searc hes the rest of the graph Note when a pro cessor nds a new e cien t solution it will not start searc hing from this solution un til it has nished w orking on its curren t basis Then the pro cessor will crash to the next basis in its arra y and w ork from there Th us when an idle pro cessor receiv es a new basis it will most lik ely w ork on this new basis prior to the pro cessor that sen t the basis It w as conjectured that this distribution of the w ork should sp eed up the pro cess of solving an MOLP As far as the sensitivit y of the basic algorithm to the initial solution is concerned a natural remedy is to giv e eac h pro cessor a di eren t initial p oin t to w ork with since there is no guideline for generating an IEEP with more e cien t piv ots F or this Phase m ust b e able to robustly pro vide m ultiple initial e cien t solutions Tw o approac hes w ere initially tried The rst one attempted w as to use the random w eigh t metho d RAND WEIGHT to nd the initial solutions In the random w eigh t metho d the comp osite function is formed b y randomly w eigh ting ob jectiv e functions of the original MOLP and this single ob jectiv e function is maximized o v er the original feasible set Relationships b et w een MOLPs and the w eigh ting metho d in general are discussed in detail in and man y other related publications Applying the random w eigh t metho d in Phase w ould then p ossibly lead to nding up to p di eren t IEEPs for p pro cessors used Ho w ev er this w as not the case Among our testing problems the most frequen t n um b er of IEEPs found w as one and the maxim um n um b er found w as three The other approac h w as to ha v e di eren t pro cessors use di eren t metho ds emplo y ed in Phase In general v e options for nding an IEEP are pro vided b y ADBASE Three of them in v olv e lexicographic maximization and t w o in v olv e the equal w eigh t metho d In our exp erimen ts the equal w eigh t metho d w as assigned to half of the pro cessors and the lexicographic metho d to the other half WEIGHT LEX A comparison of RAND WEIGHT and WEIGHT LEX in Phase using pro cessors w as conducted It suggested that the latter w ork ed b etter in general b ecause in all cases it found t w o di eren t initial solutions The strategies discussed ab o v e i e the tec hnique of recrashing for ac tiv ating idle pro cessors and the com bination of the equal w eigh t and the lexicographic metho d for generating di eren t IEEPs ha v e b een tested on an In tel iPSC mac hine Results on the same testing problems as in T able are listed in T able that includes the execution time in seconds and the sp e e dup de ned as Execution time using pro cessor sp eedup Execution time using p pro cessors The sp eedups of the basic parallel algorithm on the same problems are listed inside the paren theses for comparison T able clearly sho ws that these t w o strategies ha v e signi can tly increased the e ciency of the basic parallel algorithm in almost all cases ev en though this new v ersion of the algorithm ma y in v olv e more redundan t computations T able T esting Results of Prop osed Strategies p p Problem Time Sp eedup Time Sp eedup The use of the t w o a v ailable subroutines in ADBASE the random w eigh t metho d and lexicographic metho d for generating di eren t IEEPs w as pri marily for the con v enience of initial testing and certainly should not b e recommended for a parallel algorithm that allo ws concurren t execution on large n um b er of pro cessors In fact the approac h of emplo ying di eren t metho ds for solving the same initial SOLP in order to sim ultaneously gener ate m ultiple IEEPs is impractical The theory of m ulticriteria optimization do es not address the issue of m ultiple IEEPs The n um b er of existing meth o ds for nding an IEEP is far less than the n um b er of pro cessors a v ailable In addition applying di eren t metho ds concurren tly on m ultipro cessors w ould result in programming complexit y and load im balance whic h ob viously pro hibits practical usage of suc h an approac h After a careful study of the metho ds used b y ADBASE it w as found that form ulating m ultiple SOLPs from the giv en MOLP and solving these SOLPs b y the same metho d w ould b e a b etter approac h Actually a small mo di cation of ADBASE w as quite satisfactory ADBASE is capable of p erforming the lexicographic maximization pro cess that is carried out in accordance with the recursiv ely de ned reduced feasible regions S S S fy c y max c x j x S g i i S fy c y max c x j x S g i i k k S fy c y max c x j x S g k k with c C k c In particular the pro cess maximizes the ob jectiv e functions in the order in whic h they are stored b y ro ws in criterion matrix C Ob viously a di eren t maximization pro cess can b e obtained from a reordering of the ob jectiv e functions or equiv alen tly a reordering of ro ws in matrix C There are k orderings in all a n um b er usually m uc h larger than the n um b er of pro cessors a v ailable A short subroutine that p erm utes the ro ws of C w as then added in to AD BASE Exp erimen ts on all orderings for MOLPs with k ob jectiv e functions sho w that the orderings S S i i S fy c y max c x j x S g S f g i k are guaran teed to generate k di eren t IEEPs That is di eren t sets S in this pro cess are guaran teed to pro duce di eren t IEEPs When the solution in S is unique c hanging the orderings of ob jectiv e functions in subsequen t sets S i k mak es no di erence in IEEPs pro duced i whic h has o ccurred in the test Incorp orating the t w o tec hniques recrashing and pro ducing m ultiple IEEPs b y means of the lexicographic pro cess resulted in the nal parallel algorithm Step of the algorithm b elo w refers to an SOLP related to the MOLP b eing solv ed This SOLP is originally form ulated in Phase of ADBASE no w equipp ed with the additional subroutine p erm uting the ro ws of C P arallel Algorithm for MOLPs In parallel do on eac h of pro cessors P i p un til N um done i p F orm ulate an SOLP from the giv en MOLP Find an IEEP b y solving this SOLP Initialize N um done F ollo w Steps of the Basic P arallel Algorithm Receiv e messages from other pro cessors and up date its o wn list When a new co ded basis is receiv ed Crash to and do e cien t piv ot op eration on it If the basis leads to a new e cien t solution send its co de with the w ork n um b er to all other pro cessors go bac k to Step Otherwise go to Step This parallel algorithm has b een implemen ted on the In tel P aragon m ul tipro cessor at NASA Langley Researc h Cen ter Exp erimen tal results are giv en in the next section Numerical results P arallel algorithms are dev elop ed for solving computationally extensiv e prob lems The sp eedup e ciency and scalabilit y are imp ortan t criteria in the p erformance ev aluation The scalabilit y referred to in this pap er is un dersto o d as the follo wing feature of the algorithm when the problem size increases linearly with the n um b er of pro cessors the ac hiev ed e ciency of the algorithm de ned as sp eedup on p pro cessors e ciency p is main tained Clearly the testing problems should consist of MOLPs whose size is scaled with the n um b er of pro cessors F ortunately using ADBASE al most an y problem of desired size can b e generated b y sp ecifying the n um b er of ob jectiv e functions k n um b er of structural v ariables n and n um b er of constrain ts m An in teresting phenomenon initially observ ed is that the n um b er of EEPs gro ws rapidly as k n m sum of the parameters increases F or example the solution sets could gro w b y sev eral thousand when the n um b er of ob jectiv e functions is incremen ted b y one Similar observ ations w ere rep orted in where random problem generation for creating MOLP test problems w as discussed In general an MOLP ma y ha v e a h uge n um b er of solutions whic h is b e y ond capabilit y of data pro cessing or exceeds the mac hine memory capacit y In this situation nding all e cien t solutions is no longer practical and the goal of generating all EEPs could b e questioned Ho w ev er in the presence of a large n um b er of EEPs the solution pro cess of MOLPs go es further and in v olv es maximizing a decision mak er s o v erall utilit y function o v er the e cien t set in order to obtain a p ossibly unique most preferred solution Optimization o v er the e cien t set has recen tly b ecome a direction of v ery activ e researc h In fact optimizing a linear function o v er the e cien t set of an MOLP is already a di cult global optimization problem and requires n umerically in tensiv e algorithms Studies in this direction yielding exact or heuristic algorithms w ere carried out b y Benson Benson and Sa yin and others While exact algorithms en tail hea vy computational burden heuristics o er only estimates of the global solution Giv en the a v ailabil it y of fast parallel algorithms for MOLPs complete en umeration of EEPs previously considered impractical for larger problems seems to b e comp et itiv e with the sp ecially designed algorithms The global solution ob viously T able Execution Time Seconds Problem No of Solutions p p p p bas ex bas ex bas ex dep ends on the c hoice of the utilit y function and as suc h it cannot b e deter mined uniquely Selection of the utilit y function is a di cult task usually p erformed b y a decision mak er who can mak e a b etter c hoice if more infor mation ab out the e cien t set is a v ailable Therefore abilit y to nd a subset of the e cien t set within a giv en time p erio d is of great imp ortance as it ma y con tribute to the decision mak er s learning pro cess ab out the e cien t fron tier Using that partial information the decision mak er can mo dify the utilit y function that will b etter represen t his her preferences In this pap er MOLPs that in v olv e more than thousand EEPs are classi ed as extremely large problems Accordingly for small and large MOLPs the goal is to generate all EEPs as fast as p ossible otherwise to nd as man y solutions as p ossible within a giv en time p erio d T able constructed in the same fashion as T able sho ws the parallel execution times on the In tel P aragon mac hine on testing problems The problems are selected so that their sizes measured b y the total n um b er of e cien t bases are linearly scaled with the n um b er of pro cessors b eing used T able lists the sp eedup for the same testing problems and Figure depicts the parallel e ciency de ned b y Eq for all the problems tested in the exp erimen ts Figure P arallel E ciency T able Sp eedup Problem No of Solutions p p p bas ex bas ex bas ex The structure of the EEP graph suggests that when an MOLP includes more solutions to b e found the c hances of splitting the w ork b et w een pro cessors will increase b ecause there is less c hance for more than one pro cessor to b e terminated at the same time and th us to recrash to the same solution Therefore the algorithm is inheren tly scalable whic h has b een con rmed b y the exp erimen ts Note the three stars mark ed in Figure They indicate that the e ciency of the algorithm has b een main tained when the total n um b er of solutions generated increased linearly with the n um b er of pro cessors emplo y ed In addition for a xed n um b er of pro cessors the e ciency of the parallel algorithm w en t up quic kly to its optim um when the n um b er of solutions of MOLPs increased as illustrated in Figure The implemen tation results on extremely large MOLPs are presen ted in T able These problems in v olv e h uge n um b ers of solutions so they are iden ti ed b y the input parameters used in the problem generator of ADBASE Three groups of testing problems w ere c hosen The problems in eac h group are de ned o v er the same feasible set sp eci ed b y n m and are listed in the ascending order according to their n um b er of ob jectiv e functions Solu tions w ere found in seconds using p pro cessors All the ro ws of this table sho w that in general more solutions w ere generated sim ultaneously when more pro cessors w ere used Since the sp eedup de ned b y Eq is based on the execution time sp en t on generating all e cien t solutions and is no longer v alid for the p erformance ev aluation in this situation the r atio de ned as n um b er of solutions found b y p pro cessors ratio n um b er of solutions found b y pro cessor is then used The ratio actually measures the sp eedup of the computation T able Num b er of Solutions F ound in Seconds n m k p p p p p p pro cess in terms of the n um b er of solutions found within a giv en time p erio d T able lists the ratios computed from the data in T able F or the giv en n m as parameters of a feasible set the ratios in most of the columns of T able increase steadily with the n um b er of ob jectiv e functions indicating once again that the algorithm generally p erforms b etter on larger problems and is w ell scalable Note that the n um b er of solutions generated b y pro cessors can b e as large as times of the n um b er of solutions found b y pro cessor in the same time p erio d Conclusions This pap er presen ts pioneering researc h on designing a parallel algorithm for MOLPs based on the sequen tial soft w are ADBASE and implemen ting it on an In tel iPSC and a P aragon m ultipro cessors The pap er rst rep orts a straigh tforw ard approac h in the form of basic parallel algorithm In the subsequen t researc h the tec hniques of re activ ating idle pro cessors and gen erating m ultiple IEEPs ha v e b een prop osed The resulting parallel algorithm has b een applied to large and v ery large MOLPs All exp erimen ts sho w that this parallel algorithm signi can tly sp eeds up the pro cess of nding e cien t solutions of MOLPs F urthermore the algorithm is w ell scalable whic h is considered a v ery imp ortan t feature of parallel algorithms The algorithm is also v ery w ell suited for a wide range of parallel computers and it is not sp eci c to the distributed m ultipro cessors on whic h it w as tested T able Ratio n m k p p p p p Although the literature on MOLPs is v ery ric h and div erse computa tional issues of these problems ha v e not b een widely in v estigated A sec ondary pro duct of this researc h is the rep ort on the n um b ers of EEPs p os sessed b y MOLPs of large and v ery large sizes as w ell as on m utual relation ships b et w een the n um b er of ob jectiv e functions v ariables and constrain ts Additionally the curren t structure of ADBASE hea vily a ects this al gorithm and lea v es space for further impro v emen t F or instance since AD BASE do es not k eep trac k of infeasible or ine cien t bases curren tly in the parallel algorithm m ultiple pro cessors rep eatedly c hec k the same infeasible or ine cien t bases whic h generates redundan t computations If b o okk eep ing of ine cien t bases w as main tained the comm unication b et w een pro cessors could b e set up for transmitting the additional information ab out e cien t and ine cien t bases On the other hand ADBASE is a v ersa tile pac k age that can solv e a range of linear optimization problems i e pre emptiv e goal programming MOLPs with in terv al criterion w eigh ts and p oin t estimate w eigh ted sum problems The curren t parallel algorithm could b e further mo di ed and extended to handle some of the other options AD BASE o ers The ultimate goal of an y researc h in the area of m ulticriteria optimiza tion is to design new to ols supp orting decision making In the course of this pro cess the decision mak er usually in teractiv ely examines the e cien t set and c ho oses a most preferred e cien t solution as the optimal one Optimiz ing decision mak er s preferences o v er the e cien t set although in general considered a di cult problem has b een more attractiv e than generating all e cien t p oin ts b y means of traditional sequen tial algorithms The researc h presen ted in this pap er sho ws that parallel algorithms can substan tially alle viate this tedious pro cess and mak e en umeration of e cien t p oin ts a decision aid for m ulticriteria decision making References H P BENSON A n al l line ar pr o gr amming r elaxation algorithm for optimizing over the e cient set Journal of Global Optimization pp A nite nonadjac ent extr eme p oint se ar ch algorithm for opti mization over the e cient set Journal of Optimization Theory and Applications pp H P BENSON and S SA YIN A fac e se ar ch heuristic algorithm for optimizing over the e cient set Na v al Researc h Logistics pp C S CHANG Co or dinate d static and dynamic monitoring and op timization of p ower systems using a p ar al lel ar chite ctur e and p attern r e c o gnition te chniques IEEE Pro ceedings C pp V Chank ong and Y Y Haimes Multiobje ctive De cision Making The ory and Metho dolo gy North Holland New Y ork J N Clima co J P Cost a C Antunes and M J Al ves Par al lel pr o c essing in molp metho d b ase development discussion using two c ase studies P ap er presen ted at the IX th In ternational Conference on Multiple Criteria Decision Making F airfax V A J P Cost a and J N Clima co A multiple r efer enc e p oint p ar al lel appr o ach in mc dm Pro ceedings of the T en th In ternational Conference on Multiple Criteria Decision Making T aip ei pp Y Evtushenk o V Mazourik and V Ra tkin Multicriteria op timization in the diso system Optimization P arallel Pro cessing and Application eds A Kurzhanski K Neumann and D P allasc hk e Springer V erlag Berlin pp M Gra uer and H Boden Opp ortunities on p ar al lel and distribute d c omputation for optimization and de cision supp ort Pro ceedings of the T en th In ternational Conference on Multiple Criteria Decision Making T aip ei pp A Lew ando wski Par al lel implementation of sele cte d mc dm algo rithms P ap er presen ted at the TIMS ORSA Join t National Meeting Chicago W Y Ng and J Y ang Inter active sampling of e cient fr ontier in multi obje ctive pr o gr amming by p ar al lel distribute d c omputation Pro ceedings of the T en th In ternational Conference on Multiple Criteria Decision Making T aip ei pp R E Steuer Multiple Criteria Optimization The ory Computation and Applic ation John Wiley New Y ork Manual for the adb ase multiple obje ctive line ar pr o gr amming p ackage Departmen t of Managemen t Science and Information T ec h nology Univ ersit y of Georgia A thens GA R andom pr oblem gener ation and the c omputation of e cient ex tr eme p oints in multiple obje ctive line ar pr o gr amming priv ate comm u nication M M Wiecek H Zhang J L Ma tthews and J R Sol tys A p ar al lel algorithm for multiple obje ctive line ar pr o gr ams to app ear in Pro ceedings of the XI In ternational Conference on MCDM Coim bra P ortugal H Zhang and M M Wiecek Solving multiple obje ctive line ar pr o gr ams on the intel p ar agon to app ear in Pro ceedings of Mardi Gras Conference T o w ard T era op Computing and New Grand Challenge Applications Baton Rouge Louisiana