Operationalization of non-formal theories in operator-models

A column generation approach for the maximal coveringlocation problemMarcos Antonio Pereira a ,Luiz Antonio Nogueira Lorena b andEdson Luiz Franc a Senne aa FEG/UNESP,Department of Mathematics,Sa ˜o Paulo State University Engineering College,12516-410–Guaratingueta ´,SP,Brazil,b LAC/INPE,Associate Laboratory of Applied Mathematics and Computation,Brazilian Institute for Space Research,12201-970–Sa ˜o Jose ´dos Campos,SP,Brazil,E-mails:mapereira@feg.unesp.br [Pereira];lorena@lac.inpe.br [Lorena];elfsenne@feg.unesp.br [Senne]Received 30May 2006;received in revised form 1February 2007;accepted 17March 2007AbstractThis article presents a column generation algorithm to calculate new improved lower bounds to the solution of maximal covering location problems formulated as a p -median problem.This reformulation leads to instances that are difficult for column generation methods.The traditional column generation method is compared with the new approach,where the reduced cost criterion used at the column selection is modified by a Lagrangean/surrogate multiplier.The efficiency of the new approach is tested with real data,where computational tests were conducted and showed the impact of sparsity and degeneracy on column generation-based methods.Keywords:facility location;column generation;Lagrangean/surrogate relaxation1.IntroductionThe logistics for distribution of products or services has been a subject of increasing importance over the years,as part of the strategic planning of both public and private enterprises.Decisions concerning the best configuration for the installation of facilities in order to address demand requests are the subject of a wide class of problems,known as location problems (Drezner,1995;Daskin,1995).Using a graph representation,demand nodes and candidate nodes for the installation of facilities are identified as vertices in a network.Such problems typically occur in a discrete space,that is,a space where the number of candidate locations and network connections is finite.Intl.Trans.in Op.Res.14(2007)349–364INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCHr 2007The Authors.Journal compilation r 2007International Federation of Operational Research SocietiesPublished by Blackwell Publishing,9600Garsington Road,Oxford,OX42DQ,UK and 350Main St,Malden,MA 02148,USA.Depending on the proposed objective,facility location problems can be grouped into two major classes.The first class deals with the minimization of the average or total distance between clients and facilities.The classic model that represents the problems of this class is the p-median problem ,which seeks to select p vertices on a network with n nodes (n 4p )for the installation of facilities,such that the sum of the distances between the demand nodes and its nearest facility is minimized.Models that minimize the average or total distance are best suited to describe problems that occur in the private sector,as the costs are directly related to the travel distances for the satisfaction of the clients’demands.Hillsman (1984)proposes some data manipulation in order to produce new objective function cost coefficients,reducing several location problems to a p -median problem.The second class of facility location problems deals with the maximum distance between any client and the facility designed to attend the associated demand.These problems are known as covering problems and the maximum service distance is known as covering distance .The set covering problem (Toregas et al.,1971)determines the minimal number of facilities that are necessary to attend all clients,for a given covering distance.Owing to formulation restrictions,this model does not consider the individual demand of each client.In addition,the number of needed facilities can be large,incurring high fixed installation costs.An alternative formulation considers the installation of a limited number of facilities,even if this amount is unable to address the total demand.In this formulation,the condition that all clients must be served is relaxed and the objective is changed to locate p facilities such that the maximum part of the existing demand can be addressed,for a given covering distance.This model corresponds to the maximal covering location problem (MCLP).Covering models are often found in problems of public organizations for the location of emergency services.Early techniques for solving the MCLP tried to obtain integer solutions from the linear relaxation equivalent of the model proposed by Church and ReVelle (1974).This pioneer work formalizes the MCLP and presents a greedy heuristic based on vertices exchange.Lorena and Pereira (2002)report results obtained with a Lagrangean/surrogate heuristic using a subgradient optimization method,as a complement to the dissociated Lagrangean and surrogate heuristics presented in Galva o et al.(2000).Arakaki and Lorena (2001)present a constructive genetic algorithm to solve real case instances with up to 500vertices.Column generation methods have gained renewed interest for solving large-scale combinatorial problems,mainly due to the development of faster and reliable commercial optimization software (ILOG,2001),which allow inherently complex problems to be solved in reasonable computing times.These methods were first applied to one-dimensional cutting stock problems (Gilmore and Gomory,1961,1963)and,since then,have been explored in many other applications,such ascutting stocks (Vance et al.,1994;Valerio de Carvalho,1999),vehicle routing (Desrochers and Soumis,1989;Desrochers et al.,1992),crew scheduling (Day and Ryan,1997;Souza et al.,2000a,b)and VLSI design (Souza and Menezes,2000).A complete overview of the column generation theory and its applications can be found in Lu bbecke and Desrosiers (2002)and Desaulniers et al.(2005).The column generation technique can be applied to large linear problems when all variables are not explicitly known or when the problem is to be solved by Dantzig–Wolfe (1960)decomposition (in this case,the columns are the extreme points of the convex hull of the set of feasible solutions).The method alternates between a restricted master problem (RMP)and a column generation subproblem .By starting with a feasible columns subset,the optimal dual solution of the RMP is used to calculate the cost coefficients of the objective function for the column generation M.A.Pereira et al./Intl.Trans.in Op.Res.14(2007)349–364350r 2007The Authors.Journal compilation r 2007International Federation of Operational Research Societiessubproblem,which produces new columns to be added to the RMP formulation.If no productive columns(based on its reduced cost value)are obtained as a solution of the subproblem,the iterative process stops.It is well known that the direct application of column generation methods produces many columns that are not relevant to thefinal solution,slowing the solution process convergence (tailing-off).In such a case,it has been observed that the dual solutions oscillate around the optimal dual solution,justifying the application of stabilization methods to inhibit such behavior and,thus,accelerating the problem resolution.Different techniques to prevent dual solutions to vary have been proposed,like the Boxstep method(Marsten,1975;Marsten et al.,1975),where the optimization in the dual space is explicitly restricted to a bounded region with the current dual solution as the central point.The Analytic Center Cutting Plane method(du Merle et al.,1998) considers the current analytic center of the dual function instead of the optimal dual solution, avoiding dual values to change too dramatically.The Bundle methods(Neame,1999;Briant et al., 2005)define a trust region combined with penalties to prevent significant changes between consecutive dual solutions.Senne and Lorena(2001)show the successful application of Lagrangean/surrogate relaxation to stabilize the column generation process for p-median problems.The Lagrangean/surrogate approach multiplies the dual variables by an explicit parameter,like other regularization methods(Marquardt,1963),but with a direct way to compute the optimal value for this parameter.Other recent alternative methods to stabilize dual solutions have been considered in Desrosiers and Lu bbecke(2005).This article presents the utilization of the Lagrangean/surrogate relaxation in a column generation algorithm to calculate lower bounds to MCLP formulated as a p-median problem.The article is organized as follows:Section2presents the classical model of the p-median problem and the corresponding formulation as a set partitioning problem obtained through direct application of the Dantzig–Wolfe decomposition to the classical formulation.It also presents the MCLP formulated as a p-median problem.Section3defines the RMP and presents the integration of Lagrangean/surrogate relaxation to the proposed column generation algorithm. Section4describes the main aspects of the algorithm implementation and in Section5the computational results with real data are presented.Conclusions are discussed in Section6.2.Mathematical formulations for the p-median problemLet G5(N,A)be a graph where N is the set of vertices,A is the set of arcs and|N|5n.The p-median problem consists in determining p o n vertices(medians)such that the total distance from each vertex to the nearest median is minimized.The distance matrix D5[d ij]nÂn between each pair of vertices is assumed to be previously known.The p-median problem can be formulated as the following optimization problem(Hakimi, 1964):PMPvðPMPÞ¼MinXi2N Xj2Nd ij x ij;ð1ÞM.A.Pereira et al./Intl.Trans.in Op.Res.14(2007)349–364351r2007The Authors.Journal compilation r2007International Federation of Operational Research Societiess :t :X j 2N x ij ¼1;8i 2N ;ð2ÞXj 2N x jj ¼p ;ð3Þx ij )x jj ;8i ;j 2N ;ð4Þx ij 20;1f g ;8i ;j 2N ;ð5Þwhere [x ij ]n Ân is the location–allocation matrix,with x ij 51if vertex i is allocated to the median j ,and x ij 50,otherwise;x jj 51if vertex j is a median,and x jj 50,otherwise.Equation (1)corresponds to the solution cost,which is to be minimized.Constraint set (2)and(4)guarantee that each vertex i is allocated to exactly one vertex j ,which must be a median.Constraint (3)determines the number of medians to be localized and constraint set (5)imposes integrality to the problem variables.An alternative presentation for PMP considers the partition of the set N into p clusters.For this reason,p -median problems are also known as clustering problems (Vinod,1969;Rao,1971;Hansen and Jaumard,1997;Fung and Mangasarian,2000).Swain (1974)and Garfinkel et al.(1974)proposed the application of the Dantzig–Wolfe decomposition to formulation PMP ,aiming at the application of column generation techniques to solve p -median problems.Considering S 5{S 1,S 2,...,S m }as the set of all subsets of N ,Minoux (1987)presents the formulation of a set partition problem with cardinality constraint to describe p -median problems,as follows:SPPv ðSPP Þ¼MinX k 2M c k x k ;ð6Þs :t :Xk 2M A k x k ¼1;ð7ÞXk 2M x k ¼p ;ð8Þx k 20;1f g ;8k 2M ;ð9Þwhere M 5{1,2,...,m }is the index set of elements of S ; c k ¼Min j 2S k P i 2S kd ij ();8k 2M ;M.A.Pereira et al./Intl.Trans.in Op.Res.14(2007)349–364352r 2007The Authors.Journal compilation r 2007International Federation of Operational Research SocietiesA k5[a ik]nÂ1,with a ik51if i A S k;a ik50,otherwise;andx k51if subset(cluster)S k A S belongs to the solution;x k50,otherwise.Each subset S k corresponds to a column A k of the constraint set(7),representing a cluster in which the median is defined as the vertex j A S k that results in the smallest total distance to all i A S k and the corresponding value of c k will be set as the cluster cost.Thus,constraints(4)of PMP are implicitly considered.Constraints(2)and(3)are maintained and updated to(7)and(8), respectively.Assuming b i to be the demand value at each vertex i A N,and U to be the covering distance, Hillsman(1984)proposed new cost coefficients c ij to the objective function(1)as follows:c ij¼0if d ij)U;b i if d ij>U:&ð10ÞThis transformation allows the methods developed to p-median problems to be applied to solve MCLPs(Lorena and Pereira,2002).The optimal value v(PMP)of the objective function(1)with cost coefficients calculated as in (10)denotes the non-attended demand.The optimal value for the corresponding MCLP is calculated as:Attended demand¼Xi2Nb iÀvðPMPÞ:3.A stabilization method for column generationAs commented before,the solution of large-scale linear problems by column generation methods is an iterative process,starting with a feasible subset of columns and adding new columns to a RMP at each iteration.Considering the subset K&M5{1,2,...,m}of all column indexes from the formulation SPP,the corresponding RMP can be formulated as the following linear relaxation of a set covering problem with cardinality constraint:SCPvðSCPÞ¼MinXk2Kc k x k;ð11Þs:t:Xk2KA k x k*1;ð12ÞXk2Kx k¼p;ð13Þx k20;1½ ;8k2K:ð14ÞThe optimal dual solutions l2R nþand m A R,associated with constraint set(12)and constraint(13),respectively,can be used to obtain new incoming columns to SCP and,as presented in SenneM.A.Pereira et al./Intl.Trans.in Op.Res.14(2007)349–364353r2007The Authors.Journal compilation r2007International Federation of Operational Research Societiesand Lorena (2000),to calculate lower bounds by solving the Lagrangean/surrogate relaxation of problem PMP (note that hereafter c ij ,given by (10),replaces d ij ).This relaxation can be obtained as follows.As proposed by Glover (1968),for l 2R n þ,a surrogate relaxation of (PMP )can be defined by:SPMPv ðSPMP Þ¼MinX i 2N X j 2N c ij x ij ;ð15Þs :t :X i 2N Xj 2N l j x ij ¼X i 2N l j and ð3ÞÀð5Þ:ð16ÞThe problem SPMP cannot be easily solved,as it is an integer linear problem with no special structure to be explored.Owing to this difficulty,constraint (16)in problem SPMP is relaxed again,now in the Lagrangean way for t A R ,and the Lagrangean/surrogate relaxation of PMP is given by:LSPMPv ðLSPMP Þ¼Min X i 2N X j 2N ðc ij Àt l i Þx ij þt X i 2Nl i ;s :t :ð3ÞÀð5Þ:For any given l 2R n þ,the best Lagrangean/surrogate multiplier t can be obtained either as the optimal solution of the dual of LSPMP ,defined as:Dv D ðÞ¼Max tv LSPMP ðÞf g ;or by a dichotomous search,as the Lagrangean function l :t !v (LSPMP )is concave and piecewise linear (Parker and Rardin,1988).For any t and l ,it is well known that v (LSPMP )4v (SPMP )4v (PMP ).Setting t 51in LSPMP results in the usual Lagrangean relaxation of PMP with multiplier l .The optimal value v (LSPMP )provides better lower bounds than the usual Lagrangean bounds,as can be observed from the computational results presented in this paper.Let j Ãbe the vertex defined as the median of the cluster with the smallest contribution to v (D ),which is determined as the optimal solution of the following subproblem:M.A.Pereira et al./Intl.Trans.in Op.Res.14(2007)349–364354r 2007The Authors.Journal compilation r 2007International Federation of Operational Research SocietiesCGSv CGS ðÞ¼Min j 2N Min a ij 20;1f g X i 2N c ij Àt l i ÀÁa ij ():Subproblem CGS can be easily solved by inspection,assuming each vertex j A N as median and setting a ij ,8i A N ,as follows:a ij ¼1if c ij Àt l i )0;0if c ij Àt l i >0:&Let S j Ãbe defined as S j üi 2N a ij ü1 ÈÉ.The corresponding column A j Ã1h i will be added toSCP if:Min a ij Ã20;1f g X i 2Nc ij ÃÀl i ÀÁa ij Ã<m :ð17ÞIn effect,in order to accelerate the solution process of column generation methods,every column A j 1h i ,j A N ,satisfying condition (17),can be added to RMP (multi-pricing).It is easy to see that,for t A [0,1],if c ij Àl i 40then c ij Àt l i 40and the corresponding a ij 50in the column A j 1hi isnot modified by using multiplier t .On the other hand,if c ij Àl i 40then c ij Àt l i 40or c ij Àt l i 40and in the column A j h i some a ij 51can be flipped to a ij 50.A straightforward consequence is that the column cost c k ¼Min j 2S k P i 2S k c ij ,calculated by the Lagrangean/surrogate approach,canbe smaller than the one obtained by the traditional Lagrangean,for the same multipliers l i .Hence,as it is possible to consider several values for the multiplier t (as we proceed in some computational tests),a greater number of columns can be added to SCP in the Lagrangean/surrogate case.The effects of these aspects of the Lagrangean/surrogate approach are best shown in the computational tests of Section 5and result in faster convergence,even when a higher number of columns is added to the pool at each iteration of the process.4.The proposed column generation algorithmGenerally,in a column generation algorithm,the dual solutions for the RMP in early iterations present very strong oscillatory behavior around the optimal dual solution,due to the poor quality of the initial columns subset.As these dual solutions are used in the column generation subproblem,the performance of the algorithm can be compromised.In the proposed algorithm,dual solutions are modified by the Lagrangean/surrogate multiplier t .In this manner,at early iterations,the poor dual solutions are multiplied by a small positive value,minimizing their harmful effects.As new better columns are obtained,this multiplier is consistently increased,converging to 1as the process converges to the optimal solution.This is a clever strategy for a stabilized column generation process,as the proper value used to modify the dual solution depends on the dual solution itself,and it is obtained from a simple local search.M.A.Pereira et al./Intl.Trans.in Op.Res.14(2007)349–364355r 2007The Authors.Journal compilation r 2007International Federation of Operational Research SocietiesOther stabilization approaches,such as the ones mentioned in Section 1,rely on more complex techniques to control the dual solutions.The column generation algorithm proposed in this article can be described in Fig.1.Note that the usual column generation algorithm is obtained simply by setting t 51.In this case,v (LSPMP )corresponds to the traditional Lagrangeanbound.Fig.1.Column generationalgorithm.Fig.2.Subroutine for the initial set of columns.M.A.Pereira et al./Intl.Trans.in Op.Res.14(2007)349–364356r 2007The Authors.Journal compilation r 2007International Federation of Operational Research SocietiesThe initial set of columns to SCP (starting master problem)is obtained with the application of the subroutine depicted in Fig.2.In order to compare both the traditional and the proposed approaches,the same initial set was used for the Lagrangean and Lagrangean/surrogate cases.In order to control the problem size,a column removal subroutine was implemented (Fig.3).This subroutine may be executed either if the number of columns in the formulation SCP is greater than a predefined maximum value,or if it is intended to retain in the formulation only columns with a reduced cost smaller than a reference average value.The cost coefficients calculated in (10)do not satisfy the triangular inequality,resulting in slow convergence of iterative Lagrangean-based procedures developed to solve location problems (Schilling et al.,2000).In addition,linear program methods applied to formulations SPP or SCP may suffer from degeneracy .This is more likely to occur in column generation methods,as near-zero cost columns may be selected to enter the basis in advanced iterations.For MCLP,zero-cost columns are highly desirable,as they correspond to clusters with a fully attended demand,making the column generation approach a real challenge.Preliminary computational tests with real data MCLP instances,which are solved by the column generation algorithm developed by Senne and Lorena (2001)for p -median problems,presented non-satisfactory convergence for both the Lagrangean and Lagrangean/surrogate cases.During the solution process,it was verified,in many instances,that the lower bounds provided by LSPMP remained unchanged for many iterations,indicating that the columns of the current master problem SCP always produced the same optimal dual solution l .In order to avoid this,the algorithm ColGen (t )of Fig.1was modified to include two special procedures.The first was to allow all columns obtained as a solution of the column generation subproblem to be included in the RMP,even those with positive reduced cost.This procedure,called perturbation ,caused the dual solutions to change and the lower bounds to increase again.The perturbation procedure was applied,just for a single iteration,every time v (LSPMP )remained unchanged for a prefixed number of iterations.The second procedure is due to the inclusion of more columns in the master problem and the behavior of the multiplier t .The Lagrangean/surrogate multiplier t has zero as the starting value and,as the ColGen (t )algorithm proceeds,its value asymptotically converges to 1.In order to increase the algorithm’s performance at early iterations,we considered the inclusion of columns with negative reduced cost obtained as a solution of the subproblem for the current value for multiplier t and for the values in the set T 5{0.50,0.55,0.60,0.65,0.70,0.75,0.80,0.85,0.90,1}which are greater than the current t ,aiming at the anticipation of information (columns)thatFig.3.Column removal subroutine.M.A.Pereira et al./Intl.Trans.in Op.Res.14(2007)349–364357r 2007The Authors.Journal compilation r 2007International Federation of Operational Research Societieswould be available only in advanced iterations.This procedure was called augmentation and applies to the Lagrangean/surrogate case only.Computational tests showed that the application of the perturbation procedure in some MCLP instances solved for the Lagrangean/surrogate case caused the lower bound convergence sequence to oscillate when t already converged to 1.In this case,the algorithm produced worse values for v (LSPMP )than the previously obtained ones.For this reason,the proposed algorithm includes a control mechanism that inhibits the perturbation procedure,for the Lagrangean/surrogate case only,if the multiplier t has reached the value 1.putational resultsThe algorithms and subroutines presented in this paper were coded in C and compiled with Borland C 11Builder 5,with default compiling options to create a command line executable.Tests were conducted on a PC with an Intel Pentium 42.6GHz processor and 1GB RAM,running Microsoft Windows XP Professional with Service Pack 2.The solutions of the RMPs and column generation subproblems were obtained with ILOG CPLEX 7.5.The instances correspond to real case data for facility location in Sa o Josedos Campos –Brazil.They are available at c.inpe.br/$lorena/instancias.html.The computational results are shown in Tables 1–5.These tables contain:p :number of facilities to be located;iter :number of performed iterations;cols :total number of generated columns;lb :best v (LSPMP )found;gap :relative difference between v (SCP )and the lower bound (in %);andtime :total computational time (in s).Note that the values in Tables 1–5for the Lagrangean case were obtained by setting t 51in the algorithm ColGen (t ).In any case,the perturbation procedure was executed every time the value v (LSPMP )remained unchanged for 10consecutive iterations.Table 1Results for real case instances with n 5324verticesp Lagrangean caseLagrangean/surrogate case itercols lb gap time iter cols lb gap time 20100000117021064522.45 3.24440944.968815108664763.06–523.233059937134219372160.0929.67516451.18225713762142911.73–530.3840747819134831075.4440.1521219.45131311141761537.18–292.24502423700628386.5358.024299.70438326096689.11–83.9260952156259124.31–222.301043176719108.8118.69274.668033112900.00– 2.149276270.00– 1.811081664290.00–0.585162380.00–0.53M.A.Pereira et al./Intl.Trans.in Op.Res.14(2007)349–364358r 2007The Authors.Journal compilation r 2007International Federation of Operational Research Societiesp Lagrangean case Lagrangean/surrogate caseiter cols lb gap time iter cols lb gap time 30100000346543292826.4642.10755877.571044178622814499.20 3.5123393.48 40100000303661351977.7641.16628147.48314638851122816.95–1285.91 50268729101114683.5569.9546364.61345335128111789.38–1133.55 6061892368197À725.1841001122.5818371918008962.86–372.21 702170830359À610.414100312.1712221897366255.3520.792223.74 802925666441.06–28.0510398715132.0530.33631.64 10032128920.00– 2.388278830.00– 1.62 1341571200.00–0.625212160.00–0.59Table3Results for real case instances with n5500verticesp Lagrangean case Lagrangean/surrogate caseiter cols lb gap time iter cols lb gap time 40100000479473482942.8255.21987822.2710797214227055382.43–11403.01 5010000049810865779.8785.51363239.4229107290058634168.679.0488032.36 6010000048017859640.8885.42840509.1224108285073343379.67 3.6926826.83 7010000046476364649.1281.68229953.0166820273691854.00–597.89 805265825102301À260.48410012270.248526109438851792.27–1824.89 10096184703855À1077.1041002420.87108403308433.99–74.89 1303361302060.36–46.192095257 6.83–7.22 16743220100.00– 4.407356170.00– 1.84Table4Results for real case instances with n5708verticesp Lagrangean case Lagrangean/surrogate caseiter cols lb gap time iter cols lb gap time 7010000070801933À8569.144100182079.699467376543853262.17–23566.19 8010000070801933À6273.934100127565.437353280817282651.88–13826.58 9010000070796775À4943.89410084151.889949306289532305.90–10563.38 10010000070719646À3148.53410052267.472358103266181446.75–3222.66 1201638211582316À3.00410038174.0152383893272.47–155.55 14031982199458À877.9341003856.921641053089139.61–185.02 1809557986 3.01–18.62243975730.30–21.18 23625181050.00– 2.507456130.00– 2.43The maximum number of iterations wasfixed at100000.As new columns are obtained and introduced in the formulation,the value v(SCP)decreases,acting as an upper bound.The algorithm stops when the bounds converged to the same value(which is indicated with the symbol ‘‘–’’in the gap column of Tables1–5)or if v(SCP)o v(LSPMP).r2007The Authors.Journal compilation r2007International Federation of Operational Research SocietiesAs the results show,more columns were generated for the Lagrangean case but it did not imply better bounds.The Lagrangean/surrogate multiplier seems to affect drastically the column generation subproblem,resulting in better quality columns and producing better bounds in less computational time.The Lagrangean case was found to be more sensitive to the effects of degeneracy,as can be observed by the number of generated columns,indicating the intense use of the perturbation procedure.The effects of the controlled perturbation and augmentation for the Lagrangean/surrogate case can be observed in Figs 4–6.The graphics show the evolution of primal values v (SCP )(upper portion curve)and dual values v (LSPMP )(lower portion curve)for an MCLP instance withpLagrangean case Lagrangean/surrogate case iter cols lbgap time iter cols lb gap time 808467969268588À3.004100206442.80299471308658214173.9925.059100206.889010000081801981À15780.404100178731.168084402314152901.62–27721.6110010000081801981À11254.104100131980.804948242441862411.3732.19216630.1812010000081535844À3117.134********.923342797745820.88–1597.381402174417627162À2602.1041006055.783972665881509.47–716.2916068455599300À9.0041002289.911971352662176.26–384.90200418295776 6.13–101.0710701150528.0265.228103.5527329238920.00–4.488530020.00–3.2605001000150020002500300035004000010203040506070IterationsO b j e c t i v e v a l u eFig.4.Standard ColGen (t ):LB 52121.40.r 2007The Authors.Journal compilation r 2007International Federation of Operational Research Societies。

中英文对照（适用社会学）专业英语Sociological Terminologies 中英文术语对照第一部分 Part OneI-欧洲古典社会学家Auguste Comte 奥古斯特?孔德Karl Marx 卡尔?马克思Herbert Spencer 赫伯特?斯宾塞Vilfredo Pareto 维尔弗雷多?帕累托Ferdinand Toennies 费迪南德?滕尼斯Emile Durkheim 埃米尔?涂尔干Georg Simmel 格奥尔格?齐美尔Gaetano Mosca 加耶塔诺?莫斯卡Max Weber 马克斯?韦伯Leonard T. Hobhouse 莱奥纳多。

T。

霍布豪斯Robert Michels 罗伯特?米歇尔斯II-北美古典社会学家William Graham Sumner 威廉姆?格拉汉姆?萨姆纳Lester Ward 莱斯特?沃德Albion Small 阿比奥?斯莫尔Franklin Giddings 弗兰克林?吉丁斯Thorstein Veblen 索斯坦?凡勃伦George Herbert Mead 乔治?赫伯特?米德W. I. Thomas W。

I。

托马斯Charles Horton Cooley 查尔斯?霍顿?库利Robert E. Park 罗伯特。

E。

帕克E. A. Ross E。

A。

罗斯III-现代早期Pitirim Sorokin 皮特里姆?索罗金Elton Mayo 埃尔顿?梅约Georg Lukacs 格奥尔格?卢卡奇William F. Ogburn 威廉姆。

F。

奥格本Karl Mannheim 卡尔?曼海姆Alfred Schutz 阿尔弗雷德?舒茨Herbert Blumer 赫伯特?布鲁默Paul Lazarsfeld 保罗?拉扎斯菲尔德George Gallup 乔治?盖洛普Tarcott Parsons 塔尔科特?帕森斯George Homans 乔治?霍曼斯IV-现代晚期David Riesman 大卫?里斯曼Robert King Merton 罗伯特?金?默顿Barrington Moore 巴林顿?摩尔Lewis Coser 刘易斯?科塞Reinhard Bendix 莱因哈特?本尼迪克斯C. W. Mills C 。

语⽤学⽐喻metaphor表达类expressives表述句constatives不可分离性non-detachability不可取消性non-cancellability不确定性indeterminacy承诺类commissives代码模式code model等级含意scalar implicatures地点指⽰space deixis调节性规则regulative rules动态语⽤学dynamic pragmatics断⾔类assertives对⽅修正other-repair⼆元关系dyadic relation发展语⽤学developmental pragmatics反讽/反语irony⽅式准则manner maxim⾮规约性non-conventionality讽刺sarcasm符号sign符号关系学syntactics符号学semiotics负⾯礼貌策略negative politeness strategy 负⾯⾯⼦negative face 负向转移negative transfer概念意义conceptual meaning功能语⾔学functional linguistics共知common knowledge构成性规则constitutive rules 关联/关联性relevance关联理论relevance theory关系准则relevant maxim规定语法prescriptive grammar规约含意conventional implicature规约性conventionality规则rule含混ambivalence含意implicature合适条件felicity condition后指⽤法cataphoric use互补性complementarity互动语⽤学interactive pragmatics互明mutual manifestness互知mutual knowledge互指co-referential话轮turn-taking话语utterance话语分析discourse analysis话语意义utterance meaning话语指⽰discourse deixis缓叙meiosis会话分析conversation analysis会话含意conversational implicature 会话结构conversational structure会话修正conversational repair会话原则conversational principle或然性probability记号symbol间接⾔语⾏为indirect speech act交际⽬的communicative goal/purpose 交际能⼒communicative competence 交际意图communicative intention交际⽤意communicative force交际原则communicative principle近指proximal terms经济原则principle of economy旧信息old information句法学syntax句⼦意义sentence meaning可接收性acceptability可取消性cancellability可推导性calculability可⾏性feasibility客观环境physical situation夸张hyperbole跨⽂化语⽤学cross-cultural pragmatics离格deviance礼貌politeness礼貌策略politeness strategy礼貌原则politeness principle连贯coherence两可性ambiguity量准则quantity maxim临床语⽤学clinical pragmatics笼统性generality论⾔有所为How to do things with words逻辑语义学logical semantics蒙塔古语法Montague grammar⾯⼦face1明⽰-推理过程ostensive-inferential process 明说explicature 命题⾏为propositional act模糊限制语hedges模糊性fuzziness内嵌施为句embedded performatives恰当性appropriateness前提presupposition前提触发语presupposition triggers前指⽤法anaphoric use⼈称指⽰person deixis⼈类⽂化⽅法论ethnomethodology认知效果cognitive effect认知语⽤学cognitive pragmatics认知语⽤学cognitive pragmatics认知原则cognitive principle弱陈meiosis三元关系triadic relation社会语⽤学societal pragmatics社交语⽤学social pragmatics社交-语⽤学socio-pragmatics社交指⽰social deixis施为动词performative verb施为假设performative hypothesis施为句performatives施为⽤意illocutionary force时间指⽰time deixis实⽤主义pragmatism顺应理论adaptation theory说话⼈意义speaker meaning 随意⾔谈loose talk 特殊含意particularized conversational implicature 同义反复句tautology投射规则projection rule推理努⼒processing effort威胁⾯⼦的⾏为face threatening acts委婉语understatement未知信息unknown information衔接机制cohesive device显性施为句explicit performatives新格赖斯会话含意理论neo-Gricean theory of conversational implicature新格赖斯语⽤学neo-Gricean pragmatics新信息new information信息意图informative intention信息照应information bridging形式语⽤学formal pragmatics修辞学rhetoric宣告类declarations选择限制selectional restriction⾔语交际verbal communication⾔语情景speech situation⾔语⾏为speech act⾔语⾏为理论speech act theory⼀般会话含意generalized conversational implicature 已知信息known information以⾔成事perlocutionary act以⾔⾏事illocutionary act以⾔⾏事⽬的/施为⽬的illocutionary goal以⾔指事locutionary act意思sense意图intention意向性intentionality隐含结论implicated conclusion隐含前提implicated premise隐性施为句implicit performatives隐喻metaphor语法性grammaticality语际语interlanguage语际语⽤学interlanguage pragmatics语境暗含contextual implication语境化contextualization语境假设contextual assumptions语境效果contextual effect语境意义contextual meaning语境因素contextual factor语句sentence语句意义sentence meaning语⾔学转向linguistic turn语⾔语境linguistic context语⾔语⽤学linguistic pragmatics语义前提semantic presupposition语义学semantics语⽤代码pragmatic code语⽤含糊pragmatic vagueness语⽤含意pragmatic force语⽤类属pragmatic category语⽤能⼒pragmatic competence语⽤歧义pragmatic ambiguity语⽤迁移pragmatic transfer2语⽤前提pragmatic presupposition语⽤推理pragmatic inference语⽤⾏为pragmatic act语⽤学pragmatics语⽤移情pragmatic empathy语⽤语⾔学pragmalinguistics语⽤原则pragmatic principle寓意⾔谈metaphorical talk元交际⾏为metacommunicative behaviour 元指⽤法meta-phoric use原意或刻意⾔谈literal talk原则principle远指distal terms约略性approximation蕴涵entailment哲学语⽤学philosophical pragmatics正⾯礼貌positive politeness正⾯⾯⼦positive face正向转移positive transfer指称reference指令类directives指⽰词语deictic expressions指⽰语deixis, indexicals质准则quality maxim中介语/语际语interlanguage主题topic字⾯⽤意literal force⾃我修正self-repairadaptability顺应性（1.2.2）affective mutuality情感共享（4.5.3）agreement maxim⼀致准则（2.2.1）anaphora前照应（6.1.1）anaphoric use前照应⽤法（6.1.1）approbation maxim赞誉准则（3.2.4）appropriate conditions合适条件（3.2.4）assertives断⾔类（以⾔⾏事）（3.2.3）behabitives表态类以⾔⾏事（3.2.1）calculability（含意的）可推导性（4.4.2）calendric time units历法时间单位（6.1.3）cancellability（含意的）可取消性（4.4.2）change-of-state verbs状态变化动词（6.2.4）code model代码（交际）模式（2.1.1）cognitive environment认知环境（5.2）cognitive mutuality认知共享（4.5.3）cognitive pragmatics认知语⽤学（1.5）collaborative performatives协作性施为句（3.2.1) commissives承诺类（以⾔⾏事）（3.2.1) common knowledge共知（5.2）communicative competence交际能⼒（7.1）communicative intention交际意图（1.3.2）communicative language ability语⾔交际能⼒（7.1）constatives表述句（3.2.1)context语境（1.1)context of situation情景语境（5）contextual assumptions语境假设（1.5.4）contextual correlates语境相关因素（5.1.1) contextual effects语境效果（1.5.4）contextual features语境特征（5.1.1）contextual implication语境暗含（1.5.4）contextual meaning语境意义（1.2.3)contrastive markers对⽐性标记语（6.4.1) contrastive pragmatics对⽐语⽤研究（1.5.2）conventional implicature常规含意（4.4.1）conventionalization规约化（1.3.2）conversation analysis/CA会话分析（1.2.2）conversational implicature会话含意（4.4.1）conversation structure会话结构（1.2.2）cooperative principle/CP合作原则（2.1.2）co-text上下⽂（5.1.1）cross-cultural communication跨⽂化交际（8.1）cross-cultural pragmatics跨⽂化语⽤学（1.2.2）culture-loaded words富含⽂化内涵词语（8.2.1）declarations宣告类（以⾔⾏事）（3.2.3）decoding解码（2.1.1）defeasibility（含意的）可废除性（6.2.5）deictic center指⽰中⼼（6.1.1）deictic expression指⽰语（1.1）deictic use指⽰⽤法（6.1.1）deictics指⽰语（1.1）deixis指⽰语（1.1）developmental pragmatics发展语⽤学（1.6）directives指令类（以⾔⾏事）（3.2.3）disambiguation消除歧义（5.4）discourse deixis话语指⽰（6.1.1）discourse markers话语标记语（1.2.4)discourse meaning语篇意义（1.2.4）discourse operator话语操作语（6.4）3discourse particles话语⼩品词（6.4）dynamic pragmatics动态语⽤学（4.6）elaborative markers阐发性标记语emphathetic deixis移情指⽰encoding编码encyclopaedic information百科信息entailment蕴涵equivalent effect等值效果/等效essential condition（实施⾔语⾏为的）基本条件ethnography（of communication）（交际中的）⼈类⽂化学exercitives⾏使类（以⾔⾏事）explicature明说explicit performatives显性施为句expositives阐述类（以⾔⾏事）expressives表情类（以⾔⾏事）extended speech act theory扩充的⾔语⾏为理论face⾯⼦face theory⾯⼦理论face threatening acts/FTA威胁⾯⼦的⾏为factive verbs叙实性动词felicity conditions合适条件filler填充语gambits话语策略语general pragmaticsgeneralized implicature⼀般会话含意generosity maxim慷慨准则gestural use⼿势⽤法grammatical competence语法能⼒group performatives群体性施为句guiding culture主⽂化hearing meaning听话⼈意义hedge模糊限制语illocutionary competence施为能⼒illocutionary force施为⽤意implicated conclusion暗含结论implicated premise暗含前提implicative verbs含蓄性动词implicature暗含/含意implicit performatives隐性施为句indeterminacy（含意的）不确定性indirect speech act间接⾔语⾏为inference推理inferential markers推导性标记语语⽤学重要术语英汉对照解释1、Adjacency pair: 相邻对 A sequence of two utterances by different speakers in conversation. The second is a response to the first, e.g., question-answer.2、Background entailment: 背景蕴涵Any logical consequence of an utterance.3、Commissive: 承诺句A speech act in which the speaker commits himself or herself to some future action, e.g. a promise.4、Content conditions: 内容条件In order to count as a particular type of speech act, an utterance must contain certain features, e.g. a promise must be about a future event.5、Conversational implicature: 会话含义An additional unstated meaning that has to be assumed in order to maintain cooperative principle, e.g.if someone says “The President is a mouse”, something that is literally false, the hearer must assume the speaker means to convey more than is being said.6、Declaration: 宣告句A speech act that brings about a change by beinguttered, e.g. a judge pronouncing a sentence.-7、Deixis: 指⽰“Pointing” via language, using a deictic expression,e.g. “this”, “here”.8、Directive: 指令句A speech act used to get someone else to do something,e.g. an order.9、Discourse analysis: 话语分析The study of language use with referenceto the social and psychological factors that influence communication.10、Dispreferred: 不期待The structurally unexpected next utterance as aresponse, e.g. an invitation is normally followed by an acceptance, so a refusal is dispreferred.411、Entailment: 蕴涵Something that logically follows from what is asserted.12、Expressive: 表达句A speech act in which the speaker expresses feelings or attitudes, e.g. an apology.13、Face: ⾯⼦A person’s public self-image.14、Felicity conditions: 恰当条件 The appropriate conditions for a speech act to be recognized as intended.15、Generalized conversational implicature: ⼀般性会话含义An additional unstated meaning that does not depend on special or local knowledge. 16、Honorific: 敬语 Expression which marks that the addressee is of higher status.17、Illocutionary force: ⾔外之⼒The communicative force of an utterance.18、Insertion sequence: 插⼊系列 A two part sequence that comes between the first and second parts of another sequence in conversation.19、Manner Maxim: ⽅式准则One of the maxims, in which the speaker is to be clear, brief, and orderly.20、Maxim: 准则One of the four sub-principles of the cooperative principle.21、Particularized conversational implicature: 特殊会话含义An additional unstated meaning that depends on special or local knowledge.22、Performative verb: ⾏事动词A verb that explicitly names the speech act, e.g. the verb “promise” in the utterance “I promise to be there”.23、Perlocutionary act: 以⾔成事 The effect of an utterance used to perform a speech act.24、Person deixis: ⼈称指⽰Forms used to point ot people, e.g. “me”, “you”.25、Pragmatics: 语⽤学 The study of speaker meaning as distinct from word or sentence meaning. 26、Preferred: 期待的The structurally expected next utterance used ina response.27、Preparatory conditions: 准备条件Specific requirements prior to an utterance in order for it to cont as a particular speech act.28、Presupposition: 前提Something the speaker assumes to be the case.29、Projection problem: 映射问题The problem of the presupposition of a simple structure not surviving when part of a more complex structure.30、Quality maxim: 质量准则One of the maxims, in which the speaker has to be truthful.31、Quantity maxim: 数量准则One of the maxims, in which the speaker has to be neither more nor less informative than is necessary.32、Reference: 照应An act by which a speaker uses a word, or words, to enable a listener to identify someone or something.33、R elation maxim: 相关准则One of the maxims, in which the speaker has to be relevant.34、Representative: 阐述句A speech act in which the speaker states what is believed or known, e.g. an assertion.35、Sincerity conditions: 诚意条件Requirements on the genuine intentions of a speaker in order for an utterance to count asa particular speech act.36、Social deixis: 社会指⽰Forms used to indicate relative social status.37、Speech act: ⾔语⾏为An action performed by the use of an utterance to communicate.38、Textual function: 篇章功能The use of language in the creation of well-formed text.39、Turn-taking: 轮换The change of speaker during conversation5。

ad hoc hypothesis 特设性假说anomaly 反常auxiliary assumption 辅助假定auxiliary hypothesis 辅助假说basic statement 基本陈述behaviourism 行为主义conceptual framework 概念框架confirm 确证confirmation 确证conjecture 推测conventionalism 约定论conversion 改宗、改变信仰corroborate 确认corroboration 确认counter-induction 反归纳critical rationalism 批判理性主义critical realism 批判实在论critical thought 批判思维crucial experiment 判决性实验deduction 演绎、演绎法degree of corroboration 确认度demarcation 分界determinism 决定论disposition 素质、倾向dogmatic thought 教条思维downward causation 下向因果性emergence 突现epiphenomenalism 附带现象论epistemological anarchy 认识论无政府状态 epistemology 认识论error-elimination 除错essentialism 本质论explanation 解释fallibilism 易谬主义fallibility 易谬性falsifiability 可证伪性falsification 证伪falsificationism 证伪主义falsify 证伪falsity content 虚假性内容first world 第一世界formal language 形式语言gestalt switch 格式塔转换guess 猜测heuristic 启发法hypothesis 假说improbablity 不可几性indeterminism 非决定论induction 归纳、归纳法inductionism 归纳主义initial condition 初始条件instant rationality 即时理性instrumentalism 工具主义interactionism 相互作用论irrationalism 非理性主义irrefutability 不可反驳性justification 证明justificationism 证明主义justify 证明logical positivism 逻辑实证主义macrologic 宏观逻辑mentalism 精神主义metalanguage 元语言metascience 元科学metatheory 元理论micrologic 微观逻辑naive falsificationism 朴素证伪主义 naive instrumentalism 朴素工具主义 naive realism 朴素实在论negative heuristic 反面启发法non-normal science 非常规科学non-science 非科学normal science 常规科学object language 对象语言objectivism 客观主义observational statement 观察陈述operativism 操作主义panpsychism 泛心论paradigm 规范parallelism 平行论perceptual experience 知觉经验physicalism 物理主义pluralism 多元论pluralistic realism 多元实在论positive heuristic 正面启发法positivism 实证主义potential falsifier 潜在证伪者prescience 前科学principle of induction 归纳原理principle of proliferation 扩散原理principle of tenacityradical instrumentalism 激进工具主义 rationality 理性rationlism 理性主义realism 实在论reality 实在reductionism 还原论refutability 可反驳的refutation 反驳research programme 研究纲领second world 第二世界simplicity 简单性singular statement 单称陈述sophisticated falsificationism 精致的证伪主义 subjectioism 主观主义tentative theory 试验性理论test 检验testability 可检验性theory-laden 渗透理论third world 第三世界thought experiment 思想实验trial and error 试错法truth content 真理性内容universal statement 全称陈述upward causation 上向因果性verifiability 可证实的verification 证实verify 证实verisimilitude 逼真性world 1 世界1world 2 世界2world 3 世界3。

心理学英语测试题及答案一、选择题1. Which of the following is NOT a branch of psychology?a) Cognitive psychologyb) Social psychologyc) Clinical psychologyd) Biological psychology答案：d) Biological psychology2. According to Sigmund Freud, which part of the mind operates on the pleasure principle?a) Idb) Egoc) Superegod) None of the above答案：a) Id3. Which of the following is NOT a type of psychological disorder?a) Depressionb) Schizophreniac) Bipolar disorderd) Archimedes' syndrome答案：d) Archimedes' syndrome4. Which theorist is associated with the concept of self-actualization?a) B.F. Skinnerb) Carl Rogersc) Abraham Maslowd) Ivan Pavlov答案：c) Abraham Maslow5. What is the primary focus of industrial-organizational psychology?a) Treating mental disordersb) Studying individual behaviorc) Optimizing workplace productivityd) Analyzing dreams and unconscious desires答案：c) Optimizing workplace productivity二、填空题1. The __________ is responsible for processing sensory information.答案：brain2. __________ is a neurotransmitter associated with pleasure and reward.答案：Dopamine3. __________ is a defense mechanism in which unacceptable impulses are pushed into the unconscious mind.答案：Repression4. The __________ perspective emphasizes the influence of genes and biological processes on behavior.答案：Biological5. The __________ is a part of the brain that is important for memory and learning.答案：hippocampus三、简答题1. What is the nature-nurture debate in psychology?答案：The nature-nurture debate in psychology is the argument about whether human behavior is determined by genetics (nature) or the environment (nurture). Some psychologists believe that behavior is primarily influenced by genetics, while others believe that environmental factors play a larger role. The debate seeks to understand the relative contributions of nature and nurture in shaping human behavior.2. Explain the concept of classical conditioning.答案：Classical conditioning is a type of learning in which a neutral stimulus becomes associated with a response through repeated pairings withan unconditioned stimulus. The classic example is Ivan Pavlov's experiments with dogs, where a bell (neutral stimulus) was paired with the presentation of food (unconditioned stimulus). Over time, the dogs learned to associate the bell with the food and began to salivate (conditioned response) at the sound of the bell alone (conditioned stimulus).3. What is the difference between operationalization and measurement in psychological research?答案：Operationalization refers to the process of defining and specifying the variables or concepts being studied in a way that can be measured or observed. It involves turning abstract concepts into concrete, measurable variables or indicators. Measurement, on the other hand, refers to the actual process of assigning numerical values or categories to the operationalized variables in order to collect data. In psychological research, operationalization and measurement are crucial steps in designing studies and collecting meaningful data.四、问答题1. How does cognitive psychology contribute to our understanding of human behavior?答案：Cognitive psychology explores how people perceive, think, and solve problems. It focuses on mental processes such as attention, memory, language, and decision-making. By studying these cognitive processes, cognitive psychologists aim to understand how they influence human behavior. For example, cognitive psychology has provided insights into how people encode and retrieve information, make judgments and decisions, andprocess emotions. This knowledge can be applied to various fields, such as education, marketing, and therapy, to improve human performance and well-being.2. Describe the main elements of Abraham Maslow's hierarchy of needs.答案：Maslow's hierarchy of needs is a theory in psychology that proposes that people are motivated by a hierarchy of needs, with basic physiological needs at the bottom and higher-level needs at the top. The main elements of Maslow's hierarchy include:- Physiological needs: These are basic survival needs, such as food, water, shelter, and sleep.- Safety needs: Once physiological needs are met, individuals seek security, stability, and protection from harm.- Belongingness and love needs: People have a need for social connections, love, and a sense of belonging in relationships and communities.- Esteem needs: This refers to the need for self-esteem, respect from others, and recognition of one's achievements.- Self-actualization: At the top of the hierarchy, self-actualization represents a need for personal growth, fulfillment, and reaching one's fullest potential.According to Maslow, individuals strive to meet these needs in a sequential order, with each level building upon the previous one.五、综合题1. Discuss the main ethical considerations in psychological research.答案：Ethical considerations are important in psychological research to protect the rights and well-being of participants. Some main ethical considerations include:- Informed consent: Researchers must inform participants about the nature and purpose of the study, any potential risks or benefits, and their right to withdraw from the study at any time.- Confidentiality: Researchers should ensure that participants' personal information and data remain confidential and are not disclosed without consent.- Deception: If deception is necessary for the study, researchers must debrief participants afterward and ensure that they do not experience any harm or negative consequences as a result of the deception.- Protection from harm: Researchers should minimize any physical or psychological harm to participants and take steps to ensure their well-being throughout the study.- Voluntary participation: Participation in research should be voluntary, and participants should not be coerced or manipulated into taking part.By following these ethical considerations, researchers can uphold the integrity and trustworthiness of psychological research.。

(0,2) 插值||(0,2) interpolation0#||zero-sharp; 读作零井或零开。

0+||zero-dagger; 读作零正。

1-因子||1-factor3-流形||3-manifold; 又称“三维流形”。

AIC准则||AIC criterion, Akaike information criterionAp 权||Ap-weightA稳定性||A-stability, absolute stabilityA最优设计||A-optimal designBCH 码||BCH code, Bose-Chaudhuri-Hocquenghem codeBIC准则||BIC criterion, Bayesian modification of the AICBMOA函数||analytic function of bounded mean oscillation; 全称“有界平均振动解析函数”。

BMO鞅||BMO martingaleBSD猜想||Birch and Swinnerton-Dyer conjecture; 全称“伯奇与斯温纳顿－戴尔猜想”。

B样条||B-splineC*代数||C*-algebra; 读作“C星代数”。

C0 类函数||function of class C0; 又称“连续函数类”。

CA T准则||CAT criterion, criterion for autoregressiveCM域||CM fieldCN 群||CN-groupCW 复形的同调||homology of CW complexCW复形||CW complexCW复形的同伦群||homotopy group of CW complexesCW剖分||CW decompositionCn 类函数||function of class Cn; 又称“n次连续可微函数类”。

Cp统计量||Cp-statisticC。

A Formal Approach to Software Component SpecificationKung-Kiu Lau Department of Computer Science University of ManchesterManchester M139PLUnited Kingdomkung-kiu@Mario OrnaghiDip.di Scienze dell’Informazione Universita’degli studi di Milano Via Comelico39/41,20135MilanoItalyornaghi@dsi.unimi.itAbstractThere is a general consensus that the paradigm shift to component-based software development should be accom-panied by a corresponding paradigm shift in the underlying approach to specification and reasoning.Work in modu-lar specification and verification has shown the way,and following its lead,in this position paper,we outline our approach to specifying and reasoning about components, which uses a novel notion of correctness.1What is this paper about?As the title suggests,this paper is about an approach to formal specification of software components.The purpose of such an approach is to allow formal reasoning about com-ponents.The ultimate goal of Component-based Software Development(CBD)is third-party assembly.To achieve this,it is necessary to be able to specify components in such a way that we can reason about their construction and com-position,and correctness thereof,a priori.Work in mod-ular specification and verification,e.g.[9,14]has shown the way,and our approach follows its lead.However,our approach is novel and hence different in the way we define correctness.In this paper,we will discuss how we spec-ify components,and in particular how we define and reason about correctness,and why this is useful for CBD.2Specifying ComponentsIdeally components should be black boxes,in order that users can(re)use them without knowing the details of their innards.In other words,the interface of a component should provide all the information that users need.Moreover,this information should be the only information that they need. Consequently,the interface of a component should be the only point of access to the component.It should therefore contain all the information that users need to know about the component’s operations,i.e.what its code does,and its context dependencies,i.e.how and where the component can be deployed.The code,on the other hand,should be completely inaccessible(and invisible),if a component is to be used as a black box.The specification of a component is therefore the spec-ification of its interface,which must consist of a precise definition of the component’s operations and context depen-dencies,and nothing else.3Reasoning about ComponentsTo reason about components and their construction and composition,we will coin a phrase,a priori reasoning,which is essential for CBD to achieve its goal of third-party assem-bly.As its name suggest,a priori reasoning takes places be-fore the construction takes place,and should therefore pro-vide an assembly guide for component composition.For CBD,a priori reasoning would work as follows: it requires that it is possible to show a priori that theindividual components in question are correct(wrttheir own specifications);(This enables us to do component certification,seebelow.)it then offers help with reasoning about the composi-tion of these components:–to guide their composition in order to meet thespecification of a larger system;–to predict the precise nature of any composite,so that the composite can in turn be used as aunit for further composition.(This enables us to do system prediction,see below.)4Predictable Component AssemblyA priori reasoning addresses an open problem in CBD, viz.predictable component assembly.It does so because it enables component certification and system prediction.Consider Figure1.Two components A and B each have their own interface and code.If the composition of AandFigure1.Predicting component assembly.B is C,can we determine or deduce the interface and code ofC from those of A and B?The answer lies in component certification.4.1Component CertificationCertification should say what a component does(in terms of its context dependencies)and should guarantee that it will do precisely this(for all contexts where its dependencies are satisfied).A certified component,i.e.its interface,should therefore be specified properly,and its code should be ver-ified against its specification.Therefore,when using a cer-tified component,we need only follow its interface.In con-trast,we cannot trust the interface of an uncertified compo-nent,since it may not be specified properly and in any case we should not place any confidence in its code.In the context of a priori reasoning,a certified compo-nent A is a priori correct.This means that:A is guaranteed to be correct,i.e.to meet its ownspecification;A will always remain correct even if and when it be-comes part of a composite.This is illustrated by Figure2,where component A hasbeenponent certification.certified,so we know how it will behave in the composite C.However,we do not know how B will behave in C,since it is not certified.Consequently,we cannot expect to know C’s interface and code from those of A and B,i.e.we cannot predict the result of the assembly of A and B.4.2System PredictionFor system prediction,obviously we need all constituent components to be certified(a priori correct).Moreover,for any pair of certified components A and B whose composi-tion yields C:before putting A and B together,we need to knowwhat C will be;and furthermore,we need to be able to certify C. This is illustrated by Figure3.The specification of CmustFigure3.System prediction.be predictable prior to composition.Moreover,we need to know how to certify C properly,and thus how to use C in subsequent composition.A priori correctness is just what we need in order to do system prediction.5Modular Specification and VerificationCurrent approaches to modular(formal)specification and verification,e.g.[9,14],use modular reasoning.This is specification-based reasoning that tries to say before run-ning the software whether it will behave as specified or not (subject to relevant assumptions).This is illustrated in Fig-ure4.Before a composite module C is deployed,wecanFigure4.Module composition.predict whether it will work according to its specification. For example,if component modules,say A and B,are to be used in C,the correctness of C is established based on the specifications of A and B(even before A and B have been implemented).The components A and B are then verified independently.The contexts of A and B are taken in account when using and verifying A and B.Thus modular reasoning is a priori in nature.It predicts correctness,based on specification.This kind of prediction is we believe subtly different from the prediction that weintend to convey in Figure 3,which predicts specification,based on (certified)correctness (we will discuss this in Sec-tion 11).6Our Approach to Specifying ComponentsIn the rest of this paper,we outline our approach to spec-ifying components,so that we can carry out a priori reason-ing about their construction and composition.Our approach differs from current work in modular specification and ver-ification,however,in that we use a novel notion of a priori correctness.Diagrammatically,our component looks like Figure 5,and in the subsequent sections,we will explain the keyin-Figure 5.Ingredients of a component.gredients,viz.the context and the interface ,and their spec-ifications.We should point out that this is work in progress,so we do not yet have all the answers,so to speak.7ContextA component is defined in a problem domain ,or a con-text .We will represent a context as a full first-order logicaltheory with an intended (mathematical)model.7.1Signature and AxiomsA context is composed of a signature (containing sort symbols,function declarations and relationdeclarations)and a finite or recursive setof -axioms.A context axiomatises a problem domain and thus enables us to reason about it.More specifically,a context contains the abstract data types (ADTs)and all the concepts that are needed to build a model of the application at hand.A con-text is thus a (first-order)theory with an intended model.We distinguish between closed and open (or parametric )contexts.A context is closed if its signature does not contain any parameters.In this case,’s axioms have one fixed model.By contrast,a contextis open if its signature contains parameters.In this case,’s axioms have many potential models,depending on the parameters in the signature .Example 7.1A simple example of a closed context is first-order arithmetic .contains the unary function (successor)and the binary functions (sum)and (product).contains the usual Peano’s ax-ioms for (and all the instances of the first-order in-duction schema).CONTEXT;S IGNATURE :Sorts:;Functions:A XIOMS :The standard structure of natural numbers is the intended of .Example 7.2A simple example of an open context is the following,which axiomatises lists with generic elements and a generic total ordering on .CONTEXT I MPORT :;S IGNATURE :Sorts :;Functions:Relations:A XIOMS :The context(ADT)is imported,together with its signature and axioms.and are the constructors for the sort of lists of elements of sort.(For an element and a list, stands for the list with head and tail.)Their axioms are the list constructor axioms(plus structural induction).means that the element occurs at position in the list,where positions start from.is the number of occurrences of the element in the list.7.2ConstraintsIn an open context,some of the parameters in the sig-nature may not be instantiated just anyhow.In fact their instantiation must be subject to strictly defined constraints. Example7.3In the context,in or-der to ensure that is a total ordering,we have to add the following constraints:CONTEXTI MPORT:;S IGNATURE:Sorts:;Functions:Relations:A XIOMS:C ONSTRAINTS:The purpose of constraints is tofilter out illegal param-eters of the context:only parameters that satisfy the con-straints are allowed.For example,if in the context,we want to substitute by the sort of natural numbers,and the ordering by on,then we can express this as a closure(or instance):CLOSURE OFC LOSE:BY;BY.This closure of the context sat-isfy the constraints of the context since is a total ordering on.In this example,we have closed and within itself,for simplicity.In general,of course,they could also be closed within another context,after importing into.Obviously constraints define context dependencies.8InterfaceThe interface of a component is defined in the context of the component.The interface is the only part of the com-ponent that is visible to the users,and it should provide all the information that the users need in order to deploy the component.Since the interface is defined within the con-text,the latter should be regarded as part of the former.As we already made clear,the interface should contain specifi-cations for the operations,and the context dependencies,of the component.8.1OperationsIn the interface,operations are represented by their spec-ifications.In a context,a specification of a new(re-lation)symbol is a set of axioms that define in termsof the symbols of the signature.For example,suppose in we have operations for sorting,such as insertion sort and bubble sort.The specification for these two operationsare as follows:1We represent operations as logic programs.For example, the operations insertion sort and bubble sort are represented by the following logic programs:Operation:insertionSortThe operation insertionSort computes the relation (as specified by the specification given above)in terms of the relation(also as specified above).It therefore needs a program for in order to complete the sorting operation.As a result insertionSort has as a param-eter,hence we write insertionSort().In any context that is a closure(instance)of,insertionSort will need a program for.Thus parameters to operations also define context depen-dencies.By contrast,the operation bubbleSort has only the pa-rameter ,which is the parameter of the context.So bub-bleSort will work for any context in which is instantiated (closed)by any total ordering.8.2Context DependenciesThese consist of the (global)parameters in the signature of the component,the (local)parameters of the operations,together with the constraints in the context.So now we can define the context dependencies com-pletely in a component.9CodeThe code should be inaccessible (invisible)to the user.It is usually binary.However,if we allow parameters in the operations,then the code has to be source code,which has to be instantiated before execution.If the source code is available,then the user or the de-veloper can also verify its correctness with respect to the specifications in the context.10A New Notion of A Priori CorrectnessIn our work the basis for a priori reasoning is a new no-tion of a priori correctness.So having laid out the speci-fication of a component,we now turn to our definition ofa priori correctness of a component.Specifically,we con-sider a notion of a priori correctness of the operations in a component,that we call steadfastness .10.1SteadfastnessA steadfast operation (program)Op is one that is cor-rect (wrt to its specification)in each intended model of thecontext of the component.Since the (reducts of the)in-tended models of its specialisations and instances are in-tended models of ,a steadfast program Op is correct,and hence correctly reusable,in all specialisations and instances of .A formalisation of steadfastness is given in [8],with both a model-theoretic,hence declarative ,characterisation and a proof-theoretic treatment of steadfastness.Here we give a simple example (based on an example in [8])to illustrate the intuition behind steadfastness.Example 10.1Consider the following component:where the open context is defined as fol-lows:Figure 6.The Iterate component.CONTEXT;IMPORT :;S IGNATURE :Sorts:;Functions:A XIOMS :where is the closed context for first-order Peano arith-metic defined in Example 7.1.In the open context :(i)is a (generic)domain,with a binary operation and a distinguished element (see the first axiom);(ii)the usual structure of natural numbers is imported;(iii)the function symbolrepresents the iteration opera-tion(see the second axiom).We can use the Iterate component to iterate times thebinary operation on some (generic)domain .Suppose in Iterate ,or more precisely its context,we specify the operation by the following relation:(1)The predicatemeans that is the resultof applying the iteration operation to,i.e..This specification of can be implemented by theoperation iterate()defined by the following logicprogram:Operation:iteratespecifications:(2) The predicate means is the distinguished element ,and means that is the result of applying the operation just once to and.Therefore in the program for iterate,if,i.e.is just,thencomputes.Otherwise,if, i.e.,and,i.e.,thencomputes.The operation iterate()is defined in terms of the parameters and.If we can assume that operations for and are a priori correct,i.e.they are correct wrt their specifications(2)in any interpretation of,then we can prove that the operation iterate()is stead-fast,i.e.it is always correct wrt(1)(and(2)).For example,suppose we have a component Naturals as shown in Figure7,in which the context is,andtheFigure7.The Naturals component. operations unit and op are specified as follows:(3)(i.e.means is,and means) and defined as follows:Operation:-unitThen in Naturals,unit and op are(trivially)a priori cor-rect wrt to their specifications(3),and if we compose the components Iterate and Naturals,the operation iterate in the composite Iterate+Naturals will be fully instantiated (and therefore executable),and more importantly it will be correct wrt its specification(1)(and(2)).The composition here is of course just the simple closure operation on Iterate,but it is sufficient to illustrate the idea of steadfastness.In this closure of Iterate:(i)is the set of natural numbers;(ii)is;(iii)is;(iv). Consequently,the specification(1)specialises toand similarly(in(2))specialises to(in(3)),and(in(2))to(in(3)).Since,the operations unit and op are correct with respect to their(specialised)specifications(3),the operation (iterate(unit op)will compute,and is cor-rect wrt its(specialised)specification in Iterate+Naturals.To illustrate the correct reusability of the iterate opera-tion in Iterate,suppose now we have a componentIntegersFigure8.The Integers component.as shown in Figure8,where the operations unit and op are specified by:(4) and defined by:Operation:-unitObviously the operations unit and op in Integers are a priori correct wrt their specifications(4).We can com-pose Iterate and Integers by a closure operation on Iter-ate,and get a correct iterate operation in the composite It-erate+Integers.In Iterate+Integers:(i)is the set of integers;(ii)is;(iii)is0;(iv),and the specification((1)in Iterate)specialises to (in(2))specialises to(in(4)),and(in(2))to(in(4)).Since unit and op are correct wrt their specifica-tions(4),the operation(iterate unit op)com-putes for an integer,and is correct wrt its(specialised) specification in Iterate+Integers.The iterate operation is thus a priori correct in Iterate and we say it is steadfast.It can be correctly reused in any composite with operations for unit and op as long as these operations are in turn steadfast.The component Iterate has no constraints in its context de-pendencies.To further illustrate the notion of steadfastness, we now consider a component whose context dependencies include constraints.Example10.2Consider the component Iterate*(Figure9)followingobtained from Iterate(Figure6)by adding theconstraints to its context dependencies:(5) (these constraints stipulate that should be associative)and by replacing the iterate operation in Iterate by the following operation iterate*:Operation:iterate*a steadfast component,when composed with another stead-fast component will also be steadfast.In other words,stead-fastness is not only compositional,but is also preserved through inheritance hierarchies.Consequently,in the context of system prediction(as shown in Figure3)when composing steadfast components, not only can we be sure that the composite will be steadfast, but we can also predict the specification of the composite. This is illustrated in Figure10.posing steadfast components.In the context of modular specification and verification (as shown in Figure4),steadfast modules can be verified and the specification of the composite can be predicted,prior to composition.This is illustrated in Figure11.Weunder-posing steadfast modules.stand that current approaches to modular reasoning need to know the specification of the composite before predicting if the composite will work according to its specification.If this is the case(as shown in Figure4),then steadfastness offers the advantage of being able to predict the specifi-cation of the composite prior to composition.Thus,with steadfast modules,we can do system prediction as shown in Figure10.12.ConclusionFor lack of space,we have presented the intuition be-hind steadfastness by means of simple examples.We hope this does not detract from its presentation.A full account of steadfastness can be found in[8].Steadfastness is defined in terms of model-theoretic semantics.It is thus declarative in nature.We believe that declarative semantics in general will be important for lifting the level of abstraction.Our approach to specifying components is very generic. The component may be just a class or ADT.It may be a module,in particular what Meyer[10]calls an abstracted module,which is the basic unit of reuse in the CBD method-ology RESOLVE[14].It may be an object model[2]as in OMT[11]or UML[12].It may yet be an OOD framework, i.e.a group of interacting objects[6],such as frameworks in the CBD methodology Catalysis[3,5].It could even be a design pattern or schema[4].We believe that our approach to component specification can enable predictable component assembly,which is cur-rently an open problem in CBD.In addition,we believe it can provide a hybrid,spiral approach to CBD[7]that is both top-down and bottom-up for CBD,as illustrated in Fig-ure12.First a library of steadfast components has tobeFigure12.A spiral model for CBD.built.The nature of steadfastness,coupled with the use of a priori reasoning,then allows these components to be com-posed into larger systems in either a top-down(following the traditional waterfall model or the software architecture approach[13,1]),or bottom-up manner,or indeed a combi-nation of both.Bottom-up development in particular is more in keep-ing with the spirit of position of steadfast com-ponents can show the specification of the composite,and therefore the specification of any software constructed can be compared with the initial specification for the whole sys-tem.Guidance as to which components to‘pick and mix’can also be provided by component specifications. AcknowledgementsWe are grateful to Murali Sitaraman and the reviewers for their helpful comments in general,and for correcting our misunderstanding of modular specification and verification in particular.References[1]L.Bass,P.Clements,and R.Kazman.Software Architecturein Practice.Addison-Wesley,1998.[2]R.Bourdeau and B.H.Cheng.A formal semantics for objectmodel diagrams.IEEE Trans.Soft.Eng.,21(10):799–821, 1995.[3] D.D’Souza and A.Wills.Objects,Components,and Frame-works with UML:The Catalysis Approach.Addison-Wesley, 1999.[4]P.Flener,u,M.Ornaghi,and J.Richardson.An ab-stract formalisation of correct schemas for program synthe-sis.Journal of Symbolic Computation,30(1):93–127,July 2000.[5]J.K¨u ster Filipe,u,M.Ornaghi,K.Taguchi,A.Wills,and H.Yatsu.Formal specification of Catalysisframeworks.In J.Dong,J.He,and M.Purvis,editors,Proc.7th Asia-Pacific Software Engineering Conference,pages 180–187.IEEE Computer Society Press,2000.[6]J.K¨u ster Filipe,u,M.Ornaghi,and H.Yatsu.Ondynamic aspects of OOD frameworks in component-based software development in computational logic.In A.Bossi, editor,Proc.LOPSTR99,Lecture Notes in Computer Sci-ence,volume1817,pages43–62.Springer-Verlag,2000. [7]ponent certification and system prediction:Is there a role for formality?In I.Crnkovic,H.Schmidt, J.Stafford,and K.Wallnau,editors,Proceedings of the Fourth ICSE Workshop on Component-based Software Engi-neering,pages80–83.IEEE Computer Society Press,2001.[8]u,M.Ornaghi,and S.-˚A.T¨a rnlund.Steadfast logicprograms.J.Logic Programming,38(3):259–294,March 1999.[9]G.Leavens.Modular specification and verification ofobject-oriented programs.IEEE Software,pages72–80,July 1991.[10] B.Meyer.Object-oriented Software Construction.Prentice-Hall,second edition,1997.[11]J.Rumbaugh,M.Blaha,W.Premerlani, F.Eddy,andW.Sorenson.Object-Oriented Modeling and Design.Prentice-Hall,1991.[12]J.Rumbaugh,I.Jacobson,and G.Booch.The Unified Mod-eling Language Reference Manual.Addison-Wesley,1999.[13]M.Shaw and D.Garlan.Software Architecture:Perspectiveson an Emerging Discipline.Prentice Hall,1996.[14]M.Sitaraman and B.Weide,ponent-based soft-ware using RESOLVE.Special feature,ACM Sigsoft Soft-ware Engineering Notes19(4):21-65,October1994.。