survey for the quadratic assignment problem

Invited Review

A survey for the quadratic assignment problem q

Eliane Maria Loiola a ,Nair Maria Maia de Abreu a ,

Paulo Oswaldo Boaventura-Netto a ,Peter Hahn b,*,Tania Querido

c,1a

Federal University of Rio de Janeiro,Brazil b Department of Electrical and Systems Engineering,University of Pennsylvania,2127Tryon Street,Philadelphia,

PA 19146-1228,United States

c Federal Center for Technological Education,Brazil

Received 13September 2004;accepted 2September 2005

Available online 27December 2005

Abstract

The quadratic assignment problem (QAP),one of the most di?cult problems in the NP-hard class,models many real-life problems in several areas such as facilities location,parallel and distributed computing,and combinatorial data https://www.doczj.com/doc/905612015.html,binatorial optimization problems,such as the traveling salesman problem,maximal clique and graph par-titioning can be formulated as a QAP.In this paper,we present some of the most important QAP formulations and classify them according to their mathematical sources.We also present a discussion on the theoretical resources used to de?ne lower bounds for exact and heuristic algorithms.We then give a detailed discussion of the progress made in both exact and heuristic solution methods,including those formulated according to metaheuristic strategies.Finally,we analyze the contributions brought about by the study of di?erent approaches.

ó2005Elsevier B.V.All rights reserved.

Keywords:Assignment;Integer programming;Combinatorial optimization;Facilities planning and design;Metaheuristics;Branch and bound

1.Introduction

Let us consider the problem of assigning facilities to locations in such a way that each facility is designated to exactly one location and vice-versa.The distances between locations,the demand ?ows 0377-2217/$-see front matter ó2005Elsevier B.V.All rights reserved.doi:10.1016/j.ejor.2005.09.032

q

A preliminary version of this survey,with 278references,is Loiola et al.(2004).

*Corresponding author.

E-mail addresses:eliane@pep.ufrj.br (E.M.Loiola),nair@pep.ufrj.br (N.M.M.de Abreu),boaventu@pep.ufrj.br (P.O.Boaventura-Netto),hahn@https://www.doczj.com/doc/905612015.html, (P.Hahn),tania.querido@https://www.doczj.com/doc/905612015.html, (T.Querido).

1Present address:University of Florida,Gainesville,supported by CNPq,

Brazil.European Journal of Operational Research 176(2007)

657–690

https://www.doczj.com/doc/905612015.html,/locate/ejor

658 E.M.Loiola et al./European Journal of Operational Research176(2007)657–690

among the facilities and,in the general case,the facility versus location assignment costs are known.The international literature identi?es the quadratic assignment problem(QAP)as the problem of?nding a min-imum cost allocation of facilities into locations,taking the costs as the sum of all possible distance-?ow products.

The main motivation for this survey is the continuous interest in QAP,shown by a number of research-ers worldwide,for the theory,applications and solution techniques for this problem.Among the many ref-erences listed at the end of this paper,we found over100that were published since1999.The last surveys, books and review articles in the literature are Burkard(1991),Malucelli(1993),Pardalos et al.(1994),Bur-kard and C?ela(1996),C?ela(1998)and Burkard et al.(1998a).The article of Anstreicher(2003)reviews only the recent advances on algorithms.An article by Drezner et al.(in press)surveys the state-of-the-art in both heuristic and exact methods.

Koopmans and Beckmann(1957)?rst proposed the QAP as a mathematical model related to economic activities.Since then,it has appeared in several practical applications:Steinberg(1961)used the QAP to minimize the number of connections between components in a backboard wiring;He?ey(1972,1980) applied it to economic problems;Francis and White(1974)developed a decision framework for assigning a new facility(police posts,supermarkets,schools)in order to serve a given set of clients;Geo?rion and Graves(1976)focused on scheduling problems;Pollatschek et al.(1976)invoked the QAP to de?ne the best design for typewriter keyboards and control panels;Krarup and Pruzan(1978)applied it to archeology; Hubert(1987)in statistical analysis;Forsberg et al.(1994)used it in the analysis of reaction chemistry and Brusco and Stahl(2000)in numerical analysis.Nevertheless,the facilities layout problem is the most popular application for the QAP:Dickey and Hopkins(1972)applied the QAP to the assignment of build-ings in a University campus,Elshafei(1977)in a hospital planning and Bos(1993)in a problem related to forest parks.Benjaafar(2002)introduced a formulation of the facility layout design problem in order to minimize work-in-process(WIP).In his work,he shows that layouts obtained using a WIP-based formu-lation can be very di?erent from those obtained using the conventional QAP-formulation.For example,a QAP-optimal layout can be WIP-infeasible.Rabak and Sichman(2003),Miranda et al.(2005)and Duman and Ilhan(in press)studied the placement of electronic components.

The index assignment problem(Ben-David and Malah,2005)has to do with error control in communi-cations and can be shown to be a special case of the QAP.Wess and Zeitlhofer(2004)studied the problem of memory layout optimization in signal processors.Other applications can be found in Scriabin and Ver-gin(1975),Hubert and Schulz(1976),He?ey(1977),Los(1978),Khare et al.(1988a,b),Krackhardt(1988), Bland and Dawson(1991),Balakrishnan et al.(1992),Lacksonen and Enscore(1993),Medova(1994),Phil-lips and Rosen(1994),Gouveia and Vo?(1995),Bozer and Suk-Chul(1996),Talbot and Cawley(1996), White(1996),Mason and Ro¨nnqvist(1997),Ostrowski and Ruoppila(1997),Ball et al.(1998),Haghani and Chen(1998),Kochhar et al.(1998),Martin(1998),Sarker et al.(1998),Spiliopoulos and So?anopou-lou(1998),Tansel and Bilen(1998),Tavakkoli-Moghaddain and Shayan(1998),Urban(1998),Gong et al. (1999),Rossin et al.(1999),Bartolomei-Suarez and Egbelu(2000),Ho and Moodie(2000),Urban et al. (2000),Hahn and Krarup(2001),Pitsoulis et al.(2001),Takagi(2001),Siu and Chang(2002),Wang and Sarker(2002),Youssef et al.(2003),Yu and Sarker(2003),Ciriani et al.(2004),Solimanpur et al. (2004)and Abbiw-Jackson et al.(in press).

Since its?rst formulation,the QAP has been drawing researchers’attention worldwide,not only because of its practical and theoretical importance,but also because of its complexity.The QAP is one of the most di?cult combinatorial optimization problems.In general,instances of size n>30cannot be solved in rea-sonable time.Sahni and Gonzales(1976)had shown that QAP is NP-hard and that,unless P=NP,it is not possible to?nd an f-approximation algorithm,for a constant f.Such results are valid even when?ows and distances appear as symmetric coe?cient matrices.Due to its high computation complexity,the QAP has been chosen as the?rst major test application for the GRIBB project(great international branch-and-bound search).This project is seeking to establish a software library for solving a large class of parallel

E.M.Loiola et al./European Journal of Operational Research176(2007)657–690659 search problems by the use of numerous computers around the world accessed by Internet.Preliminary results from test runs are presented in Moe(2003).

Several NP-hard combinatorial optimization problems,such as the traveling salesman problem,the bin-packing problem and the max clique problem,can be modeled as QAPs.The search for local optima in classical internet-available instances is a tendency that allows for the comparison of technique perfor-mances,even when the optimum is unknown,or when the use of exact algorithms in these instances is pos-sible,Burkard et al.(1996a,1998b)and C?ela(1998)).In the QAP case,we can mention as examples, instances with recently proved optimal solutions:Bur26(b to h),(2004)and Tai25a(2003)by Hahn;Ste36a (2001)by Brixius and Anstreicher;Bur26a(2001)by Hahn;Kra30a by Hahn;Kra30b,Kra32and Tho30 (2000)by Anstreicher,Brixius,Goux and Linderoth;Nug30(one of the most renowned and challenging instances)(2000)by Anstreicher,Brixius,Goux and Linderoth;Ste36b and Ste36c(1999)by Nystro?m. In2003,Misevicius enhanced the best-known solution for Tai50a,Tai80a and Tai100a using a modi?ed tabu search.Those results motivated the article of Anstreicher(2003)that registers the recent advances in QAP-solutions and describes the new algorithms and computational structures used.Besides,the new instances are available for tests in Burkard et al.(1991,1997),Li and Pardalos(1992)and QAPLIB (2004).Also,there are instance generators with known optimum values that are currently used for testing algorithms,C?ela(1998).Finally,Palubeckis(1999,2000),Drezner et al.(in press)and Stu¨tzle and Fernan-des(2004)present new instance sets that are reported to be di?cult for metaheuristics.

Experts in combinatorial optimization tend to search for particular polynomially solvable versions of NP-hard problems and research mechanisms to measure the di?culty of problem instances.In the case of the QAP,Christo?des and Gerrard(1981)studied some special instances of the QAP;Sylla and Babu (1987)developed a methodology for an orderly quadratic assignment problem;Chen(1995)presented other QAP-cases,followed by C?ela(1998),who presented several polynomially solvable instances;Herroeleven and Vangils(1985),Cyganski et al.(1994),Mautor and Roucairol(1994b)showed that Palubetski’s QAP instances are degenerate;Angel and Zissimopoulos(1998,2000,2001,2002)discussed the di?culty of other QAP instances based on the variance of their?ow and distance sets;Abreu et al.(2002)derived a polynomial expression for the variance of the solution costs and de?ned a measure of the di?culty instances and Barvinok and Stephen(2003)constructed a distribution of QAP solution-values.

In the challenge of identifying new structural properties for QAP instances,many formulations have appeared,based on various points of view.Here we propose to collect these formulations,highlighting their most important features,and to classify them according to the technique used,such as integer program-ming,positive semi-de?nite programming,discrete and combinatorial mathematics,graph and group the-ory,or linear algebra via spectral theory.Most of these formulations are equivalent,except for those that characterize more general problems.Considering the di?culty of the QAP,these formulations encourage addition of mathematical resources for the development of new solution techniques.By the end of this arti-cle,we discuss the contributions obtained from these formulations,building several tables and charts from the extensive bibliography concerning the elaboration of exact and heuristic algorithms,lower bound cal-culation,instance class characteristics and recording the development of QAP since1957to the present.

The following surveys are essential references for those who want to have a more complete understand-ing of this problem:Hanan and Kurtzberg(1972),Burkard(1984,1991,2002),Pardalos et al.(1994)and Burkard et al.(1998a),as well as,the books by Pardalos and Wolkowicz(1994),Padberg and Rijal(1996), Dell’Amico et al.(1997)and C?ela(1998).

2.Formulations of QAP and related problems

In this section,we present the most important QAP formulations and describe the type of solution approach adopted for each formulation.

2.1.Selected QAP formulations

2.1.1.Integer linear programming formulations(IP)

First,we present the QAP as a Boolean program followed by a linear programming problem,where the binary constraints are relaxed.The Boolean formulation was initially proposed by Koopmans and Beck-mann(1957)and later used in several works such as Steinberg(1961),Lawler(1963),Gavett and Plyter (1966),Elshafei(1977),Bazaraa and Sherali(1979),Bazaraa and Kirca(1983),Christo?des and Benavent (1989),Bos(1993),Mans et al.(1995),Ju¨nger and Kaibel(2000,2001a,b),Liang(1996),Torki et al.(1996), Tsuchiya et al.(1996,2001),Ball et al.(1998),Ishii and Sato(1998),Kaibel(1998),Kochhar et al.(1998), Martin(1998),Spiliopoulos and So?anopoulou(1998),and most recently,Siu and Chang(2002),Yu and Sarker(2003)and,?nally,Fedjki and Du?uaa(2004).

We consider f ij the?ow between facilities i and j,and d kp the distance between locations k and p.It is our goal to calculate:

min

X n

i;j?1X n

k;p?1

f ij d kp x ik x jpe2:1T

s.t.

X n

i?1

x ij?116j6n;e2:2TX n

j?1

x ij?116i6n;e2:3Tx ij2f0;1g16i;j6n.e2:4TIf we consider the cost of assignment of activities to locations,a general form for a QAP instance of order n is given by three matrices F=[f ij],D=[d kp]and B=[b ik],the?rst two matrices de?ning the?ows between facilities and the distances between locations,b ik being the allocation costs of facilities to locations.This problem can be de?ned as:

min

X n

i;j?1X n

k;p?1

f ij d kp x ik x jpt

X n

i;k?1

b ik x ike2:5T

s.t.(2.2),(2.3)and(2.4).

Since the linear term of(2.5)is easy to solve,most authors discarded it.

A more general QAP version was proposed by Lawler(1963)and involves costs c ijkp that do not neces-sarily correspond to products of?ows and distances.The Lawler formulation is as follows:

min

X n

i;j?1X n

k;p?1

c ijkp x ik x jpe2:6T

s.t.(2.2),(2.3)and(2.4).

This model was also used in Bazaraa and Elshafei(1979),Drezner(1995),Sarker et al.(1995,1998),Bru¨ng-ger et al.(1997,1998),Chiang and Chiang(1998),Hahn and Grant(1998),Hahn et al.(1998),Gong et al. (1999)and Rossin et al.(1999).

2.1.2.Mixed integer linear programming(MILP)formulations

The QAP,as a mixed integer programming formulation,is found in the literature in di?erent forms.All of them replace the quadratic terms by linear terms.For example,Lawler(1963)used n4variables,

c ijkp?f ij

d kp and y ijkp?x ik x jp;16i;j;k;p6n.

660 E.M.Loiola et al./European Journal of Operational Research176(2007)657–690

Other formulations use relaxations of the original problem.In this category,one can?nd the papers by Love and Wong(1976a,b),Kaufman and Broeckx(1978),Bazaraa and Sherali(1980),Christo?des et al. (1980),Burkard and Bonniger(1983),Frieze and Yadegar(1983),Assad and Xu(1985),Adams and Sherali (1986),Christo?des and Benavent(1989)and the works of Adams and Johnson(1994),Drezner(1995), Gouveia and Vo?(1995),Milis and Magirou(1995),Padberg and Rijal(1996),White(1996),Ramachan-dran and Pekny(1998),Karisch et al.(1999)and of Ramakrishnan et al.(2002).

In general,QAP linearizations based on MILP models present a huge number of variables and con-straints,a fact that makes this approach unpopular.However,these linearizations,together with some con-straint relaxations,lead to the achievement of much improved lower bounds for the optimal solution.In this regard,we have the works of Kaufman and Broeckx(1978),Bazaraa and Sherali(1980),Frieze and Yadegar(1983),Adams and Sherali(1986),Adams and Johnson(1994)and Padberg and Rijal(1996).C?ela (1998)mentions three QAP linearizations:Kaufman and Broeckx(1978),which has the advantage of a smaller number of restrictions;Frieze and Yadegar(1983),for achieving the best lower bounds via Lagran-gean relaxation and Padberg and Rijal(1996)owing to its polytope description.The formulation presented by Frieze and Yadegar(1983)describes the QAP in a linear form,using n4real variables,n2Boolean vari-ables and n4+4n3+n2+2n constraints.The authors show that the formulation given in(2.7)–(2.16) below is equivalent to Eqs.(2.1)–(2.4),C?ela(1998).

min

X n

i;j?1X n

k;p?1

f ij d kpáy ijkpe2:7T

s.t.

X n

i?1

x ik?116k6n;e2:8TX n

k?1

x ik?116i6n;e2:9T

X n i?1y

ijkp

?x jp16j;k;p6n;e2:10T

X n j?1y

ijkp

?x ik16i;k;p6n;e2:11T

X n k?1y

ijkp

?x jp16i;j;p6n;e2:12T

X n p?1y

ijkp

?x ik16i;j;k6n;e2:13T

y

iikk

?x iik16i;k6n;e2:14Tx ik2f0;1g16i;k6n;e2:15T

06y

ijkp

6116i;j;k;p6n.e2:16T

2.1.

3.Formulations by permutations

Taking a simple approach,the pairwise allocation of facility costs to adjacent locations is proportional to?ows and to distances between them.The QAP formulation that arises from this proportionality and uses the permutation concept can be found in Hillier and Michael(1966),Graves and Whinston(1970), Pierce and Crowston(1971),Burkard and Stratman(1978),Roucairol(1979,1987),Burkard(1984),Frenk et al.(1985),Bland and Dawson(1991,1994),Battiti and Tecchiolli(1994),Bui and Moon(1994),Chakra-pani and Skorin-Kapov(1994),Fleurent and Ferland(1994),Li et al.(1994b),Mautor and Roucairol

E.M.Loiola et al./European Journal of Operational Research176(2007)657–690661

(1994a,b),Li and Smith(1995),Taillard(1995),Bozer and Suk-Chul(1996),Colorni et al.(1996),Huntley and Brown(1996),Peng et al.(1996),Tian et al.(1996,1999),Cung et al.(1997),Mavridou and Pardalos (1997),Merz and Freisleben(1997),Nissen(1997),Pardalos et al.(1997),Angel and Zissimopoulos(1998), Deineko and Woeginger(1998),Talbi et al.(1998a,b,2001),Tansel and Bilen(1998),Abreu et al.(1999), Fleurent and Glover(1999),Gambardella et al.(1999)and Maniezzo and Colorni(1999).More recently, the following articles were released:Ahuja et al.(2000),Angel and Zissimopoulos(2000,2001,2002),Stu¨t-zle and Holger(2000),Arkin et al.(2001),Pitsoulis et al.(2001),Abreu et al.(2002),Gutin and Yeo(2002), Hasegawa et al.(2002),Boaventura-Netto(2003)and Rangel and Abreu(2003).Costa and Boaventura-Netto(1994)studied the non-symmetrical QAP through a directed graph formulation.

Let S n be the set of all permutations with n elements and p2S n.Consider f ij the?ows between facilities i and j and d p(i)p(j)the distances between locations p(i)and p(j).If each permutation p represents an alloca-tion of facilities to locations,the problem expression becomes:

min p2S n X n

i;j?1

f ij d peiTpejT.e2:17T

This formulation is equivalent to the?rst one presented in(2.1)–(2.4),since the constraints(2.2)and(2.3) de?ne permutation matrices X=[x ij]related to S n elements,as in(2.17),where,for all16i,j6n,

x ij?

1;if peiT?j;

0;if peiT?j.

e2:18T

2.1.4.Trace formulation

This formulation is supported by linear algebra and exploits the trace function(the sum of the matrix main diagonal elements)in order to determine QAP lower bounds for the cost.This approach allows for the application of spectral theory,which makes possible the use of semi-de?nite programming to the QAP.The trace formulation,by Edwards(1980),can be stated as:

min

X2S n

treFáXáDáX tT.e2:19TAfterwards,this approach was used in several works:Finke et al.(1987),Hadley et al.(1990,1992a,b,c), Hadley(1994),Karisch et al.(1994),Karisch and Rendl(1995),Zhao et al.(1998),Anstreicher et al. (1999),Wolkowicz(2000a,b)and Anstreicher and Brixius(2001).

The following formulations de?ne QAP relaxations through the dual of the Lagrangean dual,as we?nd in Karisch et al.(1994),Zhao et al.(1998),Wolkowicz(2000a,b).Let e be a vector with each coordinate equal to1.If X is a permutation matrix and B is a cost matrix,then the SDP formulation is: min treFáXáDà2BTX te2:20Ts.t.Xe?e;e2:21TX t e?e;e2:22T

X ij2f0;1g8i;j.e2:23TAnother formulation that follows this approach,Zhao et al.(1998),is

min tr FáXáDáX tà2BX te2:24Ts.t.XX t?X t X?I;e2:25TXe?X t e?e;e2:26T

X2

ij àX ij?08i;j.e2:27T

662 E.M.Loiola et al./European Journal of Operational Research176(2007)657–690

From the formulations(2.20)–(2.23)and(2.24)–(2.27)one can derive semi-de?nite relaxations for the QAP. Roupin(2004)presents a simple algorithm to obtain SDP relaxations for any quadratic or linear program with bivalent variables,starting from an existing linear relaxation of the considered combinatorial problem. This algorithm is applied to obtain semi-de?nite relaxations for three classical combinatorial problems:the k-Cluster Problem,the Quadratic Assignment Problem,and the Constrained-Memory Allocation Problem.

2.1.5.Graph formulation

Let us consider two undirected weighted complete graphs,the?rst one having its edges associated to ?ows and the second one,to distances.The QAP can be thought as the problem of?nding an optimal allo-cation of the vertices of one graph on those of the other.In this formulation the solution costs are given as the sum of products of corresponding edge weights(see Fig.1).

The algebraic and combinatorial approach adopted by Abreu et al.(1999)was the impetus for Marins et al.(2004)to de?ne a new algebraic graph–theoretical approach involving line-graph automorphisms.The line-graph of a given graph G,denoted L(G),is determined by taking each edges of G as a vertex of L(G), while an edge of L(G)is de?ned as a pair of edges that are adjacent in G.A graph automorphism is a per-mutation of its vertices that preserves the edges.The set of all automorphisms of G together with the per-mutations composition is a group denoted by Aut(L(G))(Kreher and Stinson(1998)).

From a theorem by Whitney(1932),if G=K n,n52and4,then Aut(G)and Aut(L(G))constitute iso-morphic groups.Based on this result,Marins et al.(2004)noticed that solving the QAP means either?nd-ing a permutation p2S n or?nding a L(K n)automorphism,which is a C n,2permutation,that minimizes the following expression:

min

p2AuteLeK nTTX N

i?1

f i d peiT.e2:28T

It is appropriate to mention White(1995),wherein a number of QAP representations are discussed with respect to their convexity and concavity and also Yamada(1992),where a formulation is presented for the QAP on an n-dimensional grid.

2.2.QAP related problems

The most classical QAP-related problem is,obviously,the Linear Assignment Problem(LAP),which is polynomial and easily solved by the Hungarian method.As several presentations of this problem can be found in the literature(for example,Burkard,2002),we do not discuss the LAP here.We prefer to begin with another linear problem also used in QAP studies.

The three-index assignment problem(3-dimensional AP or3AP),?rst suggested by Pierskalla(1967a,b, 1968),searches for two permutations p and u2S n,so that the following expression is minimized:

min p;u2S n X n

i?1

c i peiTueiT.e2:29

TFig.1.Allocation of cliques K F over K D concerning permutation p=(4,2,1,3).

E.M.Loiola et al./European Journal of Operational Research176(2007)657–690663

Burkard and Fro¨hlich(1980)proposed a branch-and-bound algorithm to solve the3AP.Emelichev et al. (1984)described transportation models with multiple indices,with details,based on this formulation.The 3-dimensional AP has been studied by several QAP experts:Vlach(1967),Frieze(1974,1983),Frieze and Yadegar(1981),Burkard et al.(1986,1996a,b),Euler(1987),Balas and Saltzman(1989,1991),Bandelt et al.(1991),Crama and Spieksma(1992),Balas and Qi(1993),Burkard and Rudolf(1993),Qi et al. (1994),Magos and Miliotis(1994),Poore(1994a,b,1995),Burkard and C?ela(1996),Magos(1996),Poore and Robertson(1997)and Burkard(2002).

A wide range of QAP theoretical studies involve several related quadratic problems,such as the qua-dratic bottleneck assignment problem,the biquadratic assignment problem,the3-dimensional QAP,the quadratic semi-assignment problem and the multiobjective QAP.Almost all of these problems were reported in Burkard(2002).

2.2.1.The quadratic bottleneck assignment problem(QBAP)

Steinberg(1961)considered QBAP a variation of QAP with applications to backboard wiring.In that work,a placement algorithm was presented for the optimal connection of n elements in individual locations so that the length wire needed to connect two elements is minimized.The basic claim of the paper is:the opti-mal weighted-wire-length equals the least among the maximum-wire-length norms.This concept arises from the principle that it may be better to minimize the largest cost in a problem,than to minimize the overall cost.

The QBAP general program is obtained from the QAP formulation by substituting the maximum oper-ation in the objective function for the sums,which suggests the term bottleneck function: min

p2S n

max f f ij d peiTpejT:16i;j6n g.e2:30TA general formulation related to(2.30)was studied in Burkard and Finke(1982),Burkard and Zimmer-mann(1982),Kellerer and Wirsching(1998)and Burkard(2002).

2.2.2.The biquadratic assignment problem(BiQAP)

Proposed by Burkard et al.(1994),this problem can be found in other works,such as Burkard and C?ela (1995),Mavridou et al.(1998)and Burkard(2002).The?ow and distance matrices are order n4and the BiQAP-formulation is:

min p2S n

X n

i;j;k;l?1

f ijkl d peiTpejTpekTpelT.e2:31T

2.2.

3.The quadratic3-dimensional assignment problem(Q3AP)

Pierskalla(1967b)introduced it in a technical memorandum.The work was never published in the open literature.Since then,nothing on the subject has been found in the publication databases.Hahn et al.(2004) re-discovered the Q3AP while working with others on a problem arising in data transmission system design. The purpose of the work is to jointly optimize pairs of mappings for multiple transmissions using higher order signal constellations.The resulting problem formulation is:

min

P N

i?1

P N

j?1

P N

p?1

b ijp u ij w ipt

P N

i?1

P N

j?1

P N

p?1

P N

k?1

P N

n?1

P N

q?1

?C ijpknq u ij u kn w ip w kq:u2X;w2X;u;w binary

8

><

>:

9

>=

>;;e2:32T

where

x2X x P0:

X N

i?1x ij?1for j?1;...;N;

X N

j?1‘

x ij?1for i?1;...;N

()

.e2:33T664 E.M.Loiola et al./European Journal of Operational Research176(2007)657–690

2.2.4.The quadratic semi-assignment problem(QSAP)

This is a special case used to model clustering and partitioning problems by Hansen and Lih(1992).It can be written as:

min

X m

k?1X n

i;j?1

c ij x ik x jke2:34T

s.t.

X m

k?1

x ik?116i6n;e2:35T

x ij2f0;1g16i;j6n.e2:36T

Other applications can be found in Simeone(1986a,b)and Bullnheimer(1998).References for polynomial heuristics and lower bounds are found in Freeman et al.(1966),Magirou and Milis(1989),Carraresi and Malucelli(1994)and Billionnet and Elloumi(2001).Samra et al.(2005)presented a simple,but e?ective method of enhancing and exploiting diversity from multiple packet transmissions in systems that employ non-binary linear modulations such as phase-shift keying(PSK)and quadrature amplitude modulation (QAM).The optimal adaptation scheme reduces to solving the general form of the QAP,wherein the prob-lem costs cannot be expressed as products of?ows and distances(see Eq.(2.6),above).

2.2.5.The multiobjective QAP(mQAP)

Knowles and Corne(2002)presented another QAP variation considering several?ow and distance matrices.This problem is a benchmark case for multiobjective metaheuristics or multiobjective evolutionary algorithms.According to the authors,this model is more suitable for some layout problems,such as the allocation of facilities in hospitals,where it is desired to minimize the products of the?ows by the distances between doctors and patients,and between nurses and medical equipment simultaneously.The mathemat-ical expression is then,

min

p2S n

~CepT?f C1epT;C2epT;...;C mepTg;

where C kepT?

X n

i;j?1f k

ij

d peiTpejT;16k6m:

e2:37T

In this last constraint,f k

ij denotes the k th?ow between i-and j-facilities.More recently,Knowles and Corne

(2003)presented instance generators for the multiobjective version of QAP.Lopez-Ibanez et al.(2004)dis-cuss the design of ACO algorithms.Paquete and Stu¨tzle(2004)developed a study of stochastic local search algorithms for the biobjective QAP with di?erent degrees of correlation between the?ow matrices.Kle-eman et al.(2004)analyze a parallel technique and Day and Lamont(2005)present a speci?c algorithm.

A combination QAP queuing model is discussed by Smith and Li(2001),in the context of tra?c networks.

3.Lower bounds

The study of lower bounds is very important for the development of algorithms to solve mathematical programming and combinatorial optimization problems.Generally,the exact methods employ implicit enumeration,in an attempt to guarantee the optimum and,at the same time,to avoid the total enumeration of the feasible solutions.The performance of these methods depends on the computational quality and e?-ciency of the lower bounds.

E.M.Loiola et al./European Journal of Operational Research176(2007)657–690665

Lower bounds are fundamental tools for branch-and-bound techniques and for the evaluation of the quality of the solutions obtained from some heuristic algorithms.One can measure the quality of a lower bound by the gap between its value and the optimal solution.Good lower bounds should be close to the optimum.Lower bounds are useful in exact solution methods,only when they can be calculated quickly. When used in heuristic methods,their quality is more important than speed of calculation.

The QAP lower bound presented by Gilmore(1962)and Lawler(1963)is one of the best known.Its impor-tance is due to its simplicity and its low computational cost.However,it shows an important drawback as its gap grows very quickly with the size of the problem,making it a weak bound for bigger instances.The most recent and promising trends of research are based on semi-de?nite programming,reformulation–lineariza-tion and lift-and-project techniques,although they usually need an extra computational e?ort.Anstreicher and Brixius(2001)reported a new QAP bound using semi-de?nite and convex quadratic programming with good relation between cost and quality.White(1994b)used a data decomposition method,linking the actual data to the data of a special class of assignment problems for which bounds are computationally tractable.

The Gilmore and Lawler lower bound(GLB)is given by the solution of the following linear assignment problem(LAP):

min

X n

i;j?1

eb ijtl ijTáx ije3:1T

s.t.

X n

i?1x ij?116j6n;e3:2T

X n

j?1

x ij?116i6n;e3:3Tx ij2f0;1g16i;j6n.e3:4TIn order to solve(3.1)–(3.4),it is necessary to?nd the coe?cients l ij,as below:

l ij?min

X n

k;p?1

c ijkpáy ijkp k?i;p?je3:5T

s.t.

X n

k?1y

ijkp

?116i;j;p6n;e3:6T

X n p?1y

ijkp

?116i;j;k6n;e3:7T

y

ijkp

2f0;1g16i;j;k;p6n.e3:8TRoucairol(1979,1987),Edwards(1980),Frieze and Yadegar(1983),Finke et al.(1987),White(1994a), Burkard(1991),Bru¨ngger et al.(1997,1998),and Spiliopoulos and So?anopoulou(1998)present improve-ment methods for the GLB and its application to algorithms used to solve QAP.

3.1.Bounds based on MILP relaxations

The optimal solution for a MILP-formulation is a lower bound for the corresponding QAP and each dual solution of the linear programming is also a lower bound for the QAP.Several researchers as in Frieze and Yadegar(1983),Assad and Xu(1985),Adams and Johnson(1994),Ramachandran and Pekny(1998) and Karisch et al.(1999)used this https://www.doczj.com/doc/905612015.html,grangean relaxation has been applied to the QAP(Michelon and Maculan,1991).Drezner(1995)also proved that the linear programming relaxation is equal or better than the GLB bound.Adams et al.(in press)calculate bounds using a level-2reformulation linearization technique(2-RLT)due to Hahn et al.(2001b).The RLT is a general theory for reformulating mixed0–1 666 E.M.Loiola et al./European Journal of Operational Research176(2007)657–690

E.M.Loiola et al./European Journal of Operational Research176(2007)657–690667

linear and polynomial programs in higher-variable spaces in such a manner that tight polyhedral outer-approximations of the convex hull of solutions are obtained(Adams and Sherali,1986,1990).In Sherali and Adams(1999a,b)both?rst and second-level constructs for the QAP were presented as an illustration of the general methodology.

3.2.Bounds based on GLB reformulations

These bounds were adopted by several authors including Frieze and Yadegar(1983),Assad and Xu (1985),Carraresi and Malucelli(1992,1994)and Adams and Johnson(1994).A bound based on a dual formulation was proposed in Hahn and Grant(1998)and Hahn et al.(1998).The bounds given by Assad and Xu(1985)and by Carraresi and Malucelli(1992,1994)are comparable to the ones obtained by Frieze and Yadegar(1983)in terms of quality,with the advantage that they demand less computational time. However,there is no theoretical proof concerning its convergence.Those bounds characterize a?nite sequence of problems related to the original one,producing a non-decreasing GLB sequence.The compu-tational results in Hahn and Grant(1998)have shown that these bounds are competitive in terms of quality when compared to some of the best bounds and still better in computational time.Sergeev(2004)works with a continuous relaxation of the Adams–Johnson technique.

3.3.Bounds based on interior points methods

Resende et al.(1995)used Drezner(1995)theory and solved a MILP linear relaxation using an interior points algorithm(Karmarkar and Ramakrishnan,1991).This technique gives better quality lower bounds than those obtained by Adams and Johnson(1994).However,these bounds require much computational e?ort,and they are not recommended for branch-and-bound algorithms.In this case,it is better to use the Hahn and Grant(1998)dual ascent lower bound.

3.4.Variance reduction bounds

Initially proposed by Li et al.(1994a),these bounds are based on reduction schemes and are de?ned from the variance of F and D matrices.These bounds,when used in a branch-and-bound algorithm,take less computational time and generally obtain better performance than GLB.They show more e?ciency when the?ow and distance matrices have high variances.

3.5.Bounds based on graph formulation

As we discussed previously,a pair of n·n matrices F and D associated to a given QAP instance can be seen as the adjacency matrices of two weighted complete graphs K F and K D.It is known that p2S n de?nes an isomorphism between K F and K D,then solving the QAP means?nding an isomorphism p2S n such that Z p is minimum.Gavett and Plyter(1966)and Christo?des and Gerrard(1981)used this concept,decom-posing K F and K D in isomorphic spanning subgraphs to?nd lower bounds through an LAP relaxation.

3.6.Spectral bounds

We consider here the bounds derived from the trace formulation,using the calculation of data matrix eigenvalues.For some time,the quality of the results compensated the computational hardness of the cal-culations,but recently some of these bounds have been superseded by reformulation–linearization and semi-de?nite programming bounds.Some references on spectral bounds are Finke et al.(1987),Rendl (1985),Hadley et al.(1990,1992a,b),Rendl and Wolkowicz(1992)and Karisch et al.(1994).

3.7.Semi-de?nite programming and reformulation–linearization bounds

This new trend uses a number of theoretical tools to obtain linear programming representations of QAP.Zhao et al.(1998)study semi-de?nite programming (SDP)relaxations;Anstreicher (2001)compares SDP relaxations and eigenvalue bounds;Anstreicher and Brixius (2001)propose a SDP representation of a basic eigenvalue bound;Burer and Vandenbussche (2006)applied Lagrangean relaxation on a lift-and-project

QAP relaxation,following the ideas in Lova

′sz and Schrijver (1991),thus obtaining very tight SDP bounds.A report,by Rendl and Sotirov (2003),discusses a very good semi-de?nite programming (SDP)lower bound for the QAP.In 2003,when the report was written,it reported the tightest lower bounds for a large number of QAPLIB instances.The Rendl and Sotirov bound is also found in Fischer et al.(2006).In an as yet un?nished technical report,Povh and Rendl (2006)point out that the strongest relaxation (R3)from Rendl and Sotirov (2003)and the relaxation from Burer and Vandenbussche (2006)are actually the same.The di?ering lower bound values in the two papers are due to the fact that Rendl and Sotirov use the bundle method,which gives only underestimates of the true bound,while Burer and Vandenbussche are able to compute this bound more accurately.

3.8.A comparison of QAP lower bounds

Table 1presents a comparison of the di?erent QAP lower bounds discussed above.In the table,GLB62is the Gilmore-Lawler bound from Gilmore (1962);RRD95is the interior-point bound from Resende et al.(1995);HG98is the 1-RLT dual ascent bound from Hahn and Grant (1998);KCCEB99is the dual-based bound from Karisch et al.(1999);AB01is the quadratic programming bound from Anstreicher and Brixius (2001);RRRP02is the 2-RLT interior point bound from Ramakrishnan et al.(2002);RS03is the SDP bound from Rendl and Sotirov (2003),BV04is the lift-and-project SDP bound from Burer and Vanden-bussche (2006)and HH01is the Hahn-Hightower 2-RLT dual ascent bound from Adams et al.(to appear).The best lower bounds are in the shaded cells of the table.Lower bounds are listed in the table in order of date they were published,with the exception of HH01.The HH01bound was ?rst published in 2001,but the HH01bound calculations in Table 1were recently calculated and thus were placed in the rightmost Table 1

Comparison of lower

bounds

668 E.M.Loiola et al./European Journal of Operational Research 176(2007)657–690

E.M.Loiola et al./European Journal of Operational Research176(2007)657–690669 column.It should be noted that HH01is a dual ascent procedure that underestimates the RLT-2lower bound described in Adams et al.(to appear)and in Ramakrishnan et al.(2002).

4.Resolution methods

The methods used in combinatorial optimization problems can be either exact or heuristic.In the?rst case,the most frequent used strategies are branch-and-bound or dynamic programming general methods. On the other hand,there are a number of heuristic techniques using di?erent conceptions.In what follows, we discuss both approaches and we quote their most important references.

4.1.Exact algorithms

The di?erent methods used to achieve a global optimum for the QAP include branch-and-bound, cutting planes or combinations of these methods,like branch-and-cut,and dynamic programming. Branch-and-bound are the most known and used algorithms and are de?ned from allocation and cutting rules,which de?ne lower bounds for the problem.We can?nd the?rst enumerative schemes that use lower bounds to eliminate undesired solutions:Gilmore(1962),Land(1963)and Lawler(1963).Several references concerning QAP branch-and-bound algorithms are available,as Gavett and Plyter(1966),Nugent et al. (1968),Graves and Whinston(1970),Pierce and Crowston(1971),Burkard and Stratman(1978),Bazaraa and Elshafei(1979),Mirchandani and Obata(1979),Roucairol(1979),Burkard and Derigs(1980),Edwards (1980),Bazaraa and Kirca(1983),Kaku and Thompson(1986),Pardalos and Crouse(1989),Burkard (1991),Laursen(1993),Mans et al.(1995),Bozer and Suk-Chul(1996),Pardalos et al.(1997),Bru¨ngger et al.(1998),Ball et al.(1998),Spiliopoulos and So?anopoulou(1998),Brixius and Anstreicher(2001) and Hahn et al.(2001a,b).In recent years,procedures that combine branch-and-bound techniques with parallel implementation are being widely used.Due to them,the best results for the QAP are being achieved.Yet,it is important to observe that the success for the instances of bigger sizes is also related to the hardware technological improvements,Roucairol(1987),Pardalos and Crouse(1989),Mautor and Roucairol(1994a),Bru¨ngger et al.(1997),Clausen and Perregaard(1997).

Dynamic programming is a technique used for QAP special cases where the?ow matrix is the adjacency matrix of a tree.Christo?des and Benavent(1989)studied this case using a MILP approach to the relaxed problem.It was then solved with a dynamic programming algorithm,taking advantage of the polynomial complexity of the instances.This technique was also used by Urban(1998).

Cutting plane methods introduced by Bazaraa and Sherali(1980),initially,did not present satisfactory results.However,they contributed in the formulation of some heuristics that use MILP and Benders decomposition.The employed technique is not widely used so far,but good quality solutions for QAP cases are being presented.The slow convergence of this method makes it proper only for small instances(Kauf-man and Broeckx(1978),Bazaraa and Sherali(1980,1982)and Burkard and Bonniger(1983).Recently, Miranda et al.(2005)use Benders decomposition algorithm to deal with a motherboard design problem, including linear costs in the formulation.

The branch-and-cut technique,a variation proposed by Padberg and Rinaldi(1991),appears to be an alternative cutting strategy that exploits the polytope de?ned by the feasible solutions of the problem. Its main advantage over cutting planes is that the cuts are associated with the polytope’s facets.Cuts associated with facets are more e?ective than the ones produced by cutting planes,so the convergence to an optimal solution is accelerated.The dearth of knowledge about the QAP polytope is the reason why polyhedral cutting planes are not widely used for this problem.In this context,some researchers have been describing basic properties of the polytope that can contribute to future algorithm development: Ju¨nger and Kaibel(2000,2001a,b),Padberg and Rijal(1996),Kaibel(1998)and Blanchard et al.(2003).

4.1.1.The e?ects of methodology and computer speed improvements

In Table2,we present a summary of what was achieved by QAP research in the last35years,using as an example the progress made on solving exactly the classical Nugent instances,Nugent et al.(1968).The data came from Hahn(2000)and Brixius and Anstreicher(2001).The?rst result(for Nug08)was obtained by complete enumeration;all the others have been obtained by several branch-and-bound variations.Owing to lack of space,the references within the table are quoted by their number in the reference list.The column ‘‘Single CPU seconds’’allows for some comparison of results obtained on di?erent machines.

A number of important problem instances have been solved to optimality in recent years.The details can be found on the QAPLI

B homepage(QAPLIB(2004)):Ste36b-c(by Nystro¨m in1999);Bur26a(by Hahn in October2001);Ste36a(by Brixius and Anstreicher in October2001);Kra30b,Kra32and Tho30(by Ans-treicher et al.in November2000);Kra30a(by Hahn in December2000);Tai25a(by Hahn in2003);and Bur26b-h(by Hahn in2004).

Table2

Progress made on solving the Nugent instances exactly

Size Bound Year Machine CPU

speed Single CPU

seconds

No.

nodes

Who

[Ref.]

Mins

(Norm)

8–1968GE265a337440,320Palubeckis(2000)

8GL1975CDC CYBER-76<1Burkard(1975)

12GL1978CDC CYBER-7629Burkard and Stratman(1978)

15GL1980CDC CYBER-762947Burkard and Derigs(1980)

15GL1994Cray2121Merz and Freisleben(2000)

16GL1994Cray2969Merz and Freisleben(2000)

20GL1995i86040MHz811,440360,148,026Colorni et al.(1996)845 20RLT11995SPARC1075MHz159,900724,289Hahn et al.(1998)333 20QP1999HP-C3000300MHz87481,040,308Anstreicher and Brixius(2001)146 20RLT11999UltraSPARC10360MHz5087181,073Hahn et al.(2001a)42

22C-M199516i86040MHz48,308,40048,538,844,413Colorni et al.(1996)50,321 22RLT11995DEC Alpha500300MHz1,812,42010,768,366Hahn et al.(1998)10,270 22QP1999HP-C3000300MHz80581,225,892Anstreicher and Brixius(2001)134 22RLT11999UltraSPARC10360MHz48,9171,354,837Hahn et al.(2001a)408

24GL199732Motorola60482,252,800Unknown Bru¨ngger et al.(1997)466,099 24RLT11997DEC Alpha500300MHz4,859,94049,542,338Hahn(2000)27,540 24QP2000HP-C3000300MHz349,79431,865,440Anstreicher and Brixius(2001)5830 24RLT22000DEC Alpha500300MHz1,487,72416,710,701Hahn et al.(2001b)8430 25RLT11998UltraSPARC10360MHz5,698,818108,738,131Hahn(2000)64,207 25QP2000HP-C3000(1)a300MHz715,02071,770,751Anstreicher et al.(2002)11,917 25RLT12000HP-J5000440MHz1,393,11727,409,486Hahn et al.(2001a)31,879 25RLT22000Dell7150733MHz254,17911,796Hahn et al.(2001b)5816

27QP2000HP-C3000(2)a300MHz5,676,480$402,000,000Anstreicher et al.(2002)94,608 27RLT22001IBM S80450MHz1,579,956.3146,315Hahn et al.(2001b)37,639 28QP2000HP-C3000(3)a300MHz27,751,680$2,230,000,000Anstreicher et al.(2002)462,528 28RLT22001IBM S80450MHz8,682,044202,295Hahn et al.(2001b)206,922

30QP2000HP-C3000(4)a300MHz218,859,84011,892,208,412Anstreicher et al.(2002)3,647,664 30RLT22004Dell7150733MHz59,986,514543,061Adams et al.(in press)1,369,692 a Means equivalent single CPU seconds in HP-C3000,for time on computational pools with active machines(average):(1)185;(2) 185;(3)224;(4)653.

670 E.M.Loiola et al./European Journal of Operational Research176(2007)657–690

E.M.Loiola et al./European Journal of Operational Research176(2007)657–690671

4.2.Heuristic algorithms

Heuristic algorithms do not give a guarantee of optimality for the best solution obtained.Approximate methods are included in this category.These have the additional property that worst-case solutions are known.As a matter of fact,it is not unusual to?nd approximate algorithms called heuristic algorithms in the Combinatorial Optimization literature,as in Osman and Laporte(1996).In this context,we consider heuristic techniques as a procedure dedicated to the search of good quality solutions.Heuristic procedures include the following categories:constructive,limited enumeration and improvement methods.The most recent techniques that can be adapted to a wide range of optimization problems are called metaheuristics and will be discussed in the next section.

Gilmore(1962)introduced a constructive method that completes a permutation(i.e.,feasible solution)at each iteration of the algorithm.In this method,sets A and L are introduced,the?rst concerning the allocated facilities and the second the occupied locations,both initially empty.The construction of a permutation p is made by means of a heuristic and,in each step,a new allocation(i,j)is chosen,so that i2A,j2L and making p(i)=j.For an instance of size n,the process is repeated until a complete permu-tation on the problem order is achieved.Constructive methods were used in Armour and Bu?a(1963), Bu?a et al.(1964),Sarker et al.(1995,1998),Tansel and Bilen(1998),Burkard(1991),Arkin et al. (2001),Gutin and Yeo(2002)and Yu and Sarker(2003).At the end of1990,multistart techniques are used to begin heuristic or metaheuristic methods.In this category,we cite Misevicius(1997),Fleurent and Glo-ver(1999)and Misevicius and Riskus(1999).

Enumerative methods:Enumeration can guarantee that the obtained solution is optimum only if they can go to the end of the enumerative process.However,it is possible that a good solution,or even an optimal solution,is found by the beginning of Enumeration.It can be observed that the better the information used to guide the enumeration,the greater the chances of?nding good quality solutions early.However,it usu-ally takes much longer to guarantee optimality.In order to bound the runtime of this enumeration,stop-ping conditions are de?ned:maximum number of loops for the whole execution,or between two successive improvements;a limit for the execution time and so on.It becomes clear that any one of these stopping criteria can eliminate the optimum solution,a fact that requires some attention when using bounded enu-meration methods(Burkard and Bonniger,1983;West,1983).Nissen and Paul(1995)applied the threshold accepting technique to the QAP.

Improvement methods correspond to local search algorithms.Most of the QAP heuristics are in this category.An improvement method begins with a feasible solution and tries to improve it,searching for other solutions in its neighborhood.The process is repeated until no improvement can be found.The basic elements for this method are the neighborhood and the selection criterion that de?nes the order in which the neighbors are analyzed(Heider,1973;Mirchandani and Obata,1979;Bruijs,1984;Pardalos et al., 1993;Burkard and C?ela,1995;Li and Smith,1995;Anderson,1996;Talbi et al.,1998a;Deineko and Woeginger,2000;Misevicius,2000a;Mills et al.,2003).Improvement methods are frequently used in metaheuristics.

It is worthwhile to mention that up to this date,approximate algorithms with performance guaranteed for one constant were only obtained for special cases of QAP.Examples are the cases where the distance matrix satis?es the triangular inequality(Queyranne,1986)or when the problem is treated as a maximal clique problem with given maximum bound(Arkin et al.,2001).White(1993)proposed a new approach, where the actual data are relaxed by embedding them in a data space that satis?es an extension of the metric triangle property.The computations become simpler and bounds are given for the loss of optimality.

More recently,Arora et al.(2002)proposed a randomized procedure for rounding fractional perfect assignments to integral assignments.This extends the well-known LP rounding procedure of Raghavan and Thompson,which is usually used to round fractional solutions of linear programs.This procedure may be used to design an additive approximation algorithm for solving the QAP.

672 E.M.Loiola et al./European Journal of Operational Research176(2007)657–690

4.3.Metaheuristics

Before the end of the1980s,most of the proposed heuristic methods for combinatorial optimization prob-lems were speci?c and dedicated to a given problem.After that period,this paradigm has changed.More general techniques have appeared,known as metaheuristics.They are characterized by the de?nition of a priori strategies adapted to the problem structure.Several of these techniques are based on some form of simulation of a natural process studied within another?eld of knowledge(metaphors).With the advent of metaheuristics,QAP research received new and increased interest.Recall that the QAP is considered a classical challenge or‘‘benchmark’’as we mentioned earlier,Moe(2003).

4.3.1.The following metaheuristics are based on natural process metaphors

Simulated annealing is a local search algorithm that exploits the analogy between combinatorial optimi-zation algorithms and statistical mechanics(Kirkpatrick et al.,1983).This analogy is made by associating the feasible solutions of the combinatorial optimization problem to states of the physical system,having costs associated to these states energies.Let E i and E i+1be two energy successive states,corresponding to two neighbor solutions and let D E=E i+1àE i.The following situations can occur:if D E<0,there is an energy reduction and the process continues.In other words,there is a reduction on the problem cost function and the new allocation may be accepted;if D E=0,there is a stability situation and there is no change in the energy state.This means that the problem cost function was not changed;if D E>0,an increase on the energy is characterized and it is useful for the physical process to permit particle accommo-dation,i.e.,the problem cost function is increased.Instead of eliminating this allocation,its use is subjected to the values of a probability function,to avoid convergence into poor local minima.Burkard and Rendl (1984)proposed one of the?rst applications of simulated annealing to the QAP.After that,Wilhelm and Ward(1987)presented the new equilibrium components for it.Connolly(1990)introduced an optimal tem-perature concept that gave valuable https://www.doczj.com/doc/905612015.html,ter,Abreu et al.(1999)applied the technique by trying to reduce the number of inversions associated to the problem solution,together with the cost reduction.Other approaches for the simulated annealing applied to the QAP are Bos(1993),Yip and Pao(1994),Burkard and C?ela(1995),Peng et al.(1996),Tian et al.(1996,1999),Mavridou and Pardalos(1997),Chiang and Chiang(1998),Misevicius(2000b,2003c),Tsuchiya et al.(2001),Siu and Chang(2002)and Baykasoglu (2004).

Genetic algorithms are techniques that simulate the natural selection and adaptation found in nature. These algorithms keep a population formed by a subset of individuals that correspond,in the QAP case, to the feasible permutations,with?tness values associated to their permutation cost.By means of the so-called genetic operators,and of selection criteria,the algorithm replaces one population by another with best available?tness values.The scheme is based on the idea that the best individuals survive and generate descendents that carry their genetic characteristics,in the same way that biological species propagate in nature.

Genetic algorithms generally begin with a population of randomly generated initial individuals(i.e., solutions).Their costs are evaluated and a subset with the lowest cost solutions is selected.Genetic oper-ations are applied to this subset,thus generating a new solution set(a new population).The process con-tinues until some stopping criterion is met.See Davis(1987)and Goldberg(1989).Various ideas for the use of genetic algorithms on the QAP can be found in Bui and Moon(1994),Tate and Smith(1995),Mavridou and Pardalos(1997),Kochhar et al.(1998),Tavakkoli-Moghaddain and Shayan(1998),Gong et al.(1999), Drezner and Marcoulides(2003),El-Baz(2004),and Wang and Okazaki(2005).Drezner(2005a)presented a two-phase genetic algorithm.The?rst one is a quick genetic strategy that runs several times,keeping the best solution at each iteration to build a starting population for Phase2.The use of these algorithms in the QAP context presents some di?culties in getting the optimal solution,even for small instances.However, some hybrid ideas using genetic algorithms have shown to be more e?cient,as discussed later in this paper.

E.M.Loiola et al./European Journal of Operational Research176(2007)657–690673

Scatter search is a technique introduced by Glover(1977)in a heuristic study of integer linear program-ming problems.It is an evolutionary method that takes linear combinations of solution vectors in order to produce new solution vectors in successive generations.This metaheuristic is composed of initial and evo-lutionary phases.In the initial phase,a reference set of good solutions is made.In each subsequent(evo-lutionary)phase,new solutions are generated using strategically selected combinations of the reference subset.Then,a set of the best newly generated solutions is moved into the reference set.The evolutionary phase procedure is repeated until a stop criterion is satis?ed.Application of scatter search to the QAP can be found in Cung et al.(1997).

Ant colony optimization(ACO)refers to a class of distributed algorithms that has as its most important feature the de?nition of properties in the interaction of several simple agents(the ants).Its principle is the way in which ants are able to?nd a path from the colony to a food source.The set of ants,cooperating in an ordinary activity to solve a problem,constitute the ant system.The main characteristic of this method is the fact that the interaction of these agents generates a synergetic e?ect,because the quality of the obtained solutions increases when these agents work together,interacting among themselves.Numerical results for the QAP are presented in Maniezzo and Colorni(1995,1999),Colorni et al.(1996)and Dorigo et al.(1996). Gambardella et al.(1999)show ant colony as a competitive metaheuristic,mainly for instances that have few good solutions close to each other.Other references are in Stu¨tzle and Dorigo(1999),Stu¨tzle and Hol-ger(2000),Talbi et al.(2001),Middendorf et al.(2002),Solimanpur et al.(2004),Randall(2004)and Ying and Liao(2004).A novel external memory implementation is introduced,based on the use of partially com-plete sequences of solution components from above-average quality individuals(i.e.,ants),over a number of previous iterations.Elements of such variable-size partial permutation sequences are taken from ran-domly selected locations of parental individuals and stored in an external memory called the partial permu-tation memory,Acan(2005).

Although neural networks and Markov chains are structurally di?erent from metaheuristics,they are also based on a nature metaphor and they have been applied to the QAP,Bousonocalzon and Manning(1995), Liang(1996),Obuchi et al.(1996),Tsuchiya et al.(1996),Ishii and Sato(1998,2001),Rossin et al.(1999), Shin and Niitsuma(2000),Nishiyama et al.(2001),Hasegawa et al.(2002)and Uwate et al.(2004).

4.3.2.The following metaheuristics are based directly on theoretical and experimental considerations

Tabu search is a local search algorithm that was introduced by Glover(1989a,b)to?nd good quality solutions for integer programming problems.Its main feature is an updated list of the best solutions that were found in the search process.Each solution receives a priority value or an aspiration criterion.Their basic ingredients are:a tabu list,used to keep the history of the search process evolution;a mechanism that allows the acceptance or rejection of a new allocation in the neighborhood,based on the tabu list informa-tion and on their priorities;and a mechanism that allows the alternation between neighborhood diversi?-cation and intensi?cation strategies.Adaptations for the QAP can be found in Skorin-Kapov(1990,1994), Taillard(1991),Bland and Dawson(1991),Rogger et al.(1992),Chakrapani and Skorin-Kapov(1993), Misevicius(2003a,2005)and Drezner(2005b).Despite the inconvenience of depending on the size of the tabu list and the way this list is managed,the performances of those algorithms show them as being very e?cient strategies for the QAP,as analyzed by Taillard(1991)and Battiti and Tecchiolli(1994).Taillard (1995)presents a comparison between the uses of tabu search and genetic algorithm,when applied to the QAP.

Greedy randomized adaptive search procedure(GRASP)is a random and iterative technique where,at each step,an approximate solution for the problem is obtained.The?nal solution is the best resulting one among all iterations.At each step,the?rst solution is constructed through a random greedy function and the following solutions are obtained by applying on the previous solution a local search algorithm that gives a new best solution regarding to the previous one.At the end of all iterations,the resulting solution is the best generated one.It is not guaranteed that GRASP solutions do not stick to a local optimum,so it is

674 E.M.Loiola et al./European Journal of Operational Research176(2007)657–690

important to apply the local search phase to try to improve them.The use of suitable data structures and careful implementations allow an e?cient local search.This technique was applied to the QAP by several researchers,as follows:Li et al.(1994b),Feo and Resende(1995),Resende et al.(1996),Fleurent and Glo-ver(1999),Ahuja et al.(2000),Pitsoulis et al.(2001)and Rangel et al.(2000).Oliveira et al.(2004)built a GRASP using the path-relinking strategy,which looks for improvements along the paths joining pairs of good solutions.GRASP was also applied to a QAP variation:BiQAP,Mavridou et al.(1998).

Variable neighborhood search(VNS)was introduced by Mladenovic and Hansen(1997).It is based on systematic movement within a set of neighborhoods,conveniently de?ned.A number of change rules can be invoked.A change is applied when the exploring the current neighborhood does not produce a better solution.VNS has been applied to large combinatorial problem instances.In Taillard and Gambardella (1999),three VNS strategies are proposed for the QAP.One of them is a search over variable neighbor-hood,according to the basic paradigm.The other two are hybrids in combination with some of the previ-ously described methods.

Stu¨tzle(in press)applied an iterated local search(ILS),a simple and powerful stochastic local search, wherein,to avoid stagnation behavior,using acceptance criteria that allow moves to poorer local optima enhances the algorithm.The paper proposes population-based ILS extensions.

There are several other hybrid algorithms for the QAP.In Bo¨lte and Thonemann(1996),a combination of simulated annealing and genetic algorithm is presented.Battiti and Tecchiolli(1994),Bland and Dawson (1994),Chiang and Chiang(1998)and Misevicius(2001,2004a)use tabu search with simulated annealing, while Talbi et al.(1998b)and Hasegawa et al.(2002)use tabu search with a neural network,and Youssef et al.(2003)use tabu search,simulated annealing and fuzzy logic together.Some hybrid algorithms com-bine a genetic algorithm with tabu search,Fleurent and Ferland(1994),Drezner(2003),or with a greedy algorithm,Ahuja et al.(2000).All were proved to be more promising than the genetic algorithm alone.

More recently,there are more complex procedures in this class,such as Lim et al.(2000,2002),who work with hybrid genetic algorithms based on k-gene exchange local search and Misevicius(2004b),who introduced new results for the quadratic assignment problem used an improved hybrid genetic procedure. Dunker et al.(2004)combined dynamic programming with evolutionary computation for solving a dynamic facility layout problem.Balakrishnan et al.(2003)used GATS,a hybrid algorithm that considers a possible planning horizon,which combines genetic with tabu search and is designed to obtain all global optima.

Some categories of hybrid genetic algorithms are known as mimetic algorithms or evolutionary algo-rithms and some works can be found in this context:Brown and Huntley(1991),Nissen(1994),Huntley and Brown(1996),Merz and Freisleben(1997,1999,2000),Nissen(1997),Ostrowski and Ruoppila (1997).Misevicius et al.(2002)presented an algorithm based on the reconstruct and improve principle. The main components of this meta-heuristics are a reconstruction(mutation)procedure and an improve-ment(local search)procedure.Misevicius(2003b,d)presented a new heuristic,based on the run and recre-ate cause.The main components are ruin(mutation)and a recreate(improvement)procedure.

There is also a technique introduced by Goldbarg and Goldbarg(2002)that uses a variation of the genetic algorithms,known as transgenetic heuristics.In the QAP case,the results presented are comparable to others,with virtually no improvement in computational times.The use of several metaheuristics and hybrid proposals on QAP is discussed and their results are compared and analyzed in Maniezzo and Col-orni(1995)and Taillard et al.(2001).Kelly et al.(1994)studied diversi?cation strategies for the QAP;Fed-jki and Du?uaa(2004)developed a work using extreme points in a search algorithm to solve the QAP. Finally,several techniques use parallel and massive computation,Roucairol(1987),Pardalos and Crouse (1989),Brown and Huntley(1991,1996),Taillard(1991),Chakrapani and Skorin-Kapov(1993),Laursen (1993),Mans et al.(1995),Obuchi et al.(1996),Bru¨ngger et al.(1997,1998),Clausen et al.(1998),Talbi et al.(1998a,b,2001),Anstreicher et al.(2002)and Moe(2003).Most of these references were cited in other procedure classes.

E.M.Loiola et al./European Journal of Operational Research176(2007)657–690675

5.The main research trends and tendencies

In this section,we seek to identify the research trends with time,during the almost50years after the QAP?rst appeared in the literature.This study raises a number of questions concerning researcher prefer-ences and also the needs for formulations,techniques and theoretical developments.We also consider the in?uence of hardware development throughout di?erent periods and the possibilities brought about by the most recent conquests represented by parallel processing and metacomputing.

The bibliography presented in this work lists365publications,of which about95%deal directly with QAP. The curve in Fig.2shows a steady increase in interest in the QAP in recent years.The2005data collected from January through July have been extrapolated in Figs.2,8and9in order to estimate what they would have been for the entire year.Apparently,there is a moderate drop in QAP research interest in2005.

In the following?gures,the publications are grouped by the approach strategy,determined by the for-mulation classi?cation given in Section2;the kinds of lower bounds adopted according to classi?cation of Section3;the solution techniques or procedures given in Section4;the reference distribution concerning algorithmic,theoretical or applied work along the time(periods of5years).To?nish this section,we point out new research tendencies based on recent advances.

Fig.3presents the number of publications related to the di?erent QAP formulations classi?ed in this work as graphs(GR),trace(TR),mixed integer linear programming(MILP),integer linear programming (ILP)and permutations(PM).We observed that the QAP approach that identi?es solutions with permu-tations is the most used,followed by ILP,MILP and TR formulations.The formulations using exclusively graphs are not encountered as often,perhaps because they are more recent.

Fig.4presents the number of publications whose primary subject is lower bounds,categorized by the classi?cations that are adopted in this article:graph formulation,variance reduction and interior points based bounds(OTHERS),semi-de?nite programming(SDP),spectral bounds(SB),MILP relaxation based bounds,(MILP)and,?nally,Gilmore and Lawler(GLB)bounds.

Observing Fig.4,we conclude that most works use lower bounds derived from the GLB and MILP bounds,followed by SB relaxation based bounds.However,GLB is the most traditional and frequently results.

the quickest to produce

676 E.M.Loiola et al./European Journal of Operational Research176(2007)657–690

Fig.5shows the distribution of publications,categorized by solution techniques that were classi?ed in this work as Heuristic Methods,Exact Methods and Metaheuristics.

About30papers deal with exact methods,while more that one hundred are dedicated to heuristic or metaheuristic methods,a natural consequence of the NP-hardness of the problem.In writing this survey, the space dedicated to these three general techniques follows this trend.

Fig.6shows the distribution of references by metaheuristic resolution methods.In this?gure,we have scatter search(SS),variable neighborhood search(VNS),greedy randomized adaptive search procedure (GRASP),genetic algorithm(GA),neural networks and others(NNO),tabu search(TS),ant colony (AC),simulated annealing(SA)and hybrid algorithms(HA).

Hybrid procedures that result from di?erent metaheuristic compositions are by far the most utilized solution procedure.However,when we look for a comparison among pure metaheuristics,the procedures based on more traditional simulated annealing and more recently de?ned ant colony are the most popular.

Fig.7shows the distribution of QAP publications with respect to the categories:applications,theory (i.e.,formulations,complexity studies and lower bounding techniques)and algorithms.

Fig.8distributes the number of articles by5-year periods since1957,when the QAP was?rst proposed. For each period,the work is also classi?ed according to the same categories of Fig.7.We observe that an explosion of interest in theory and algorithm development occurred in the period from1992-to the present. The last period is only partially over,but level of interest and trends remain the same.

国际会计准则第36号

国际会计准则第号资产减值 国际会计准则第号 目的 本准则的目的是，规定企业用以确保其资产以不超过可收回价值（）的金额进行计量的程序。如果资产的帐面价值超过通过使用或销售而收回的价值，该资产就是按超过其可收回价值计量的，如果是这样，该资产应视为已经减值，本准则要求企业确认资产减值损失。本准则也规定了企业何时应冲回资产减值损失，以及减值资产的有关披露内容。 范围 .本准则适用于除下述资产以外的所有资产减值的会计核算： （）存货（参见《国际会计准则第号存货》）； （）建造合同形成的资产（参见《国际会计准则第号建造合同》）； （）递延所得税资产（参见《国际会计准则第号所得税》）； （）雇员福利形成的资产（参见《国际会计准则第号雇员福利》）； （）包括在《国际会计准则第号金融工具：披蹲和列报》范围内的金融资产。 .本准则不适用于存货、建造合同形成的资产、递延所得税资产或雇员福利形成的资产，因为适用于这些资产的现行国际会计准则已经包含了有关其确认和计量的特定要求。 .包括在《国际会计准则第号金融工具：披落和列报》范围内的金融资产，其减值损失的会计核算取决于国际会计准则委员会有关金融工具项目的结果。以下投资属于金融资产，但《国际会计准则第号金融工具：披露和列报》没有包括，因而本准则也适用于这些金融资产： （）《国际会计准则第号合并财务报表和对子公司投资的会计》中定义的子公司； （）《国际会计准则第号对联营企业投资的会计》中定义的联营企业； （）《国际会计准则第号合营中权益的财务报告》中定义的合营企业。 .根据其他国际会计准则，以重估价值（公允价值）计量的资产，如按《国际会计准则第号固定资产》以重估价值作为允许选用的方法计量的资产，本准则也适用。但是，认定某项重估资产是否已经减值，取决于用以确定其公允价值的基础： （）如果资产的公允价值是其市场价值，则资产的公允价值与其销售净价之间的唯一差额是处置该资产的直接增量费用：

战神的挑战2——图文流程攻略

战神的挑战2——图?流程攻略 【游戏封?】 游戏名称：P u z z l e Q u e s t2 中?名称：战神的挑战2 游戏发?：N a m c o N e t w o r k s A m e r i c a,I n c. 游戏制作：I n?n i t e I n t e r a c t i v e 游戏语种：英? 游戏类型：R P G??扮演 发??期：2010年8?13?

%{p a g e-b r e a k|游戏介绍|p a g e-b r e a k}% 野蛮?的技能表(括号中学得该技能所需的等级)： 连捶(1)：战场上有多少红宝?，则造成1/2数量的伤害值，需要4的红魔法。 部落的标记(2)：消掉战场上所有的红宝?，每4颗红宝?增加1点头?伤害奖励，该效果?直持续。 狂怒(3)：在战场上随机位置?成14颗红宝?。 部落的守护(4)：消掉战场上所有的绿宝?，没颗绿宝?增加2点防御，效果?直持续。 猛击(5)：减少敌?每种颜?的魔法值各10。 头?粉碎者(6)：消掉所有头?，敌?损失的回合数为1+1/5消掉的头?数。 野蛮咆哮(7)：敌?防御减少75%，持续3回合，本回合未结束。 破坏狂(8)：消掉所有的绿宝?，增加相等数量的红魔法。 反冲(10)：使?后该回合内通过武器攻击造成的伤害增加50%。 战争狂嚎(12)：随机位置增加3颗红?头?，如果当前红魔法值不少于25则本回合未结束。 最后的反击(15)：使?后每损失25点?命值增加1点头?伤害，该技能

践踏(20)：选择?颗宝?，消掉周边3*3区域的宝?并获得所有这些宝?的效果，对敌?造成8的伤害。 残暴(25)：在后6回合内使头?伤害加倍。 猎头者(30)：消掉最上2?的宝?，获得它们的效果。对敌?造成10的伤害。 嗜?(35)：接下来的6个回合，对敌?造成伤害值的25%转化为??的?命值。 毁灭者(40)：增加50点武器攻击点数，本回合未结束。 迷幻之怒(50)：选择?种宝?，战场上所有该颜?的宝?转变为头?，红魔法不少于25则本回合未结束。 战?的?些分析：消宝?增加该颜?魔法，六个?格为装备的武器，拳头形状表?武器攻击点数，消掉战场中的拳头增加该点数，满?武器使?需求后点击武器?格可以释放，图中我?3、3的数值分别标?了?前的头?伤害加成值和防御值，前者增加消掉头?后对敌?的伤害值，后者标?有该数值%的机会使任何敌?对我?造成的伤害减半。左下?为现在装备的五个技能，注意战?中只能装备五个所以需要在战?前在技能选项中先选择好最有利于战?的技能。 野蛮?战?的?些?得： 消4个或以上的宝?能奖励?个回合，单回合连续消掉?批宝?会有更多奖励(?如稀有武器)。 消宝?时注意看看消去后是否会给对?造成机会，如果没有什么好的

《战神3》图文流程攻略Chapter 11 -奥林

《战神3》图文流程攻略Chapter 11 -奥林匹亚要塞 跟随赫尔墨斯的脚步，抵达木桥上，桥会被迎空飞来的火球砸断，并且背后会不断燃烧，被火追上便会坠崖而亡，中途桥会更改一起方向，不用搭理摇杆向上推一路按×注意面前的平民会阻挡你的道路，用攻击键杀死他们而不是圆圈，跨上平台，平台上有许多平民，抓住处决可以回血，他们的生杀大权就掌握在你的手中。 一路上连跑带揍也没能追上神使，不过最终这个罗嗦的家伙还是被逼在一个锁头上，去左边触发剧情，不用被赫尔墨斯所干扰，掌握自己的节奏一路上利用跳跃点抵达安全区域，上面拼命、小恶魔、狗仔龙蛇混杂，推荐使用太阳神的头颅△蓄力镇住他们，然后L ?清理。

接着向前走，赫尔墨斯把正门关了没办法，我们只能绕远路了，从门左边的楼梯左右开工跃上房顶，发现点赫尔墨斯已经跑到很远的地方等奎托斯了，无奈ing到圆台下方右侧拉动摇杆，腾出缺口跳上平台，拉动巨型投石车，利用QTE跟随巨石抵达赫尔墨斯所在的雅典娜巨像上，酷毙了～ 跟随赫尔墨斯的血迹到达与赫尔墨斯决战的平台，这家伙的速度非常快，天天跑路可不是 盖的，也许一开始会适应不来，用L ?来攻击命中率会比较大，或者直接重攻击的收尾重击的伤害非常大看准时机可以给予赫尔墨斯很大的伤害，途中会有QTE对抗，无外乎是正转或者是反转半圈摇杆，几下重击周后赫尔墨斯被击倒在地，显然他累了，这家伙临死之前还唧唧歪歪拿斯巴达人的荣耀来说事。

已经没有力气的赫尔墨斯坐在地上任你鱼肉，按下圈就开始华丽的表演，非常非常的血腥……未成年人绝对禁止观看…以上以及以下的图片纯属欣赏，完事之后获得“赫尔墨斯之靴”这件物品可以让你跑得飞快。

国际会计科目对照表(中英)

精心整理 ccount?帐户 Accounting?system?会计系统? American?Accounting?Association?美国会计协会? American?Institute?of?CPAs?美国注册会计师协会? Audit?External?users?外部使用者? Financial?accounting?财务会计? Financial?Accounting?Standards?Board?财务会计准则委员会? Financial?forecast?财务预测? Generally?accepted?accounting?principles?公认会计原则? General-purpose?information?通用目的信息 Government?Accounting?Office?政府会计办公室? ? Management?accounting?管理会计? Return?of?investment?投资回报? Return?on?investment?投资报酬? Securities?and?Exchange?Commission?证券交易委员会?

Statement?of?cash?flow?现金流量表? Statement?of?financial?position?财务状况表? Tax?accounting?税务会计? Accounting?equation?会计等式? Assets? Creditor? Deflation? Disclosure?批露? Expenses?费用? Financial?statement?财务报表? Financial?activities?筹资活动? Going-concern?assumption?持续经营假设Inflation?通货膨涨? Investing?activities?投资活动? Liabilities?负债? Solvency?清偿能力? Stable-dollar?assumption?稳定货币假设? Stockholders?股东? Stockholders?equity?股东权益?

23.国际会计准则

对国际会计准则第8号——当期净损益、重大差错和会计政策变更（1993年修订）的改进建议1 1主译，丁度翻译Invitation to comment, Summary of main changes & Appendix，丁度主校对。

国际会计准则第8号——会计政策、会计估计变更和差错 （200X年修订） （备注：尽管本征求意见稿是以“清样稿”形式列示，上述标题仍以作出标记的形式列示建议的改动。）

征询意见 理事会将特别欢迎对下列问题的回答。意见中最好能指明有关的准则段落，包含明晰的基本原理，并在合适的地方提出备选措辞的建议。 问题1 您是否同意会计政策自愿变更和差错更正的允许选用的处理方法应当被删除，即这些变更和更正应当用追溯调整法处理，如同新的会计政策一直在运用或该差错从未发生那样（参见第20段、21段、32段和33段）？ 问题2 您是否同意删除重大差错和其他重要差错的区别（参见第32段和33段）？ 主要改动摘要 主要的改动建议有： ●通过下列方式修改本准则的范围： ?包含《国际会计准则第1号——会计报表的列报》的第20至22段，该 段详细说明了会计政策选择的标准； ?删除IAS8第7至18段涉及到收益表项目列报的要求。这些要求，包括 所作的修改，将转入IAS1。 因此，本准则的名称该为《会计政策、会计估计变更和差错》。 ●删除重大差错和其他重要差错的区别，并在建议的第3段增加差错的定 义。重大差错的概念被删除 ●删除IAS8第38至40段所列的差错更正允许选用的处理方法。因此，某个 实体不再被允许： ?将差错更正的金额包含在当期损益中；

PSP《战神-奥林匹斯之链》图文攻略流程

【首发】PSP战神Ω奥林匹斯之链图文流程攻略! https://www.doczj.com/doc/905612015.html,-自由自在游戏社区奉献 《战神Ω奥林匹斯之链》（God of War:Chains of Olympus）是以PS2上大畅销的《战神》（God of War）系列为题材的PSP原创新作，本作由 Ready at Dawn研发，充分发挥PSP所具备的 3D处理性能，呈现出不亚于PS2版壮阔的游 戏场景以及细腻角色。此外，在日前SCEA旗下 工作室Ready at Dawn高级制作人Eric Koch也 通过官方博客PlayStation Blog对外确认，自 2007年起就备受注目的PSP游戏《战神Ω奥 林匹斯之链》已经顺利宣告完工，游戏已经交厂 压碟准备上市，现在这款PSP超级大作将于2008 年3月4日在北美地区发售。 游戏承袭相同的故事背景与游戏类型，玩家将再 度扮演斯巴达战士奎托斯，继续施展“浑沌双刃” 等致命武器，面对全新的难关、敌人与奥林匹斯 诸神的试炼，体验与不同于本传的原创故事剧 情。游戏承袭PS2系列作的特色，在PSP上 重现了广受欢迎的电影运镜式精采游戏画面与 刺激的动作战斗系统，并加入全新的招式、关卡、 机关与怪物，以及以希腊神话为基础的全新剧 情。玩家将扮演斯巴达战士奎托斯，从人间的雅 典一直到冥王哈帝斯的冥府之门，一路朝向地狱 的深渊迈进，体验希腊神话中黑暗且残暴的世 界，并对抗各种传说中的怪物以及强大的头目角 色。 游戏名称：战神Ω奥林匹斯之链/战神Ω奥林帕斯之链 英文名称：God of War:Chains of Olympus 代理发行：SCEA/Ready At Dawn Studios LLC.游戏类型：ACT-Action Game（动作游戏） 制作厂商：SCEA/Ready At Dawn Studios LLC.对应主机：Play Station Portable（PSP） 语言版本：英文（美版）发行日期：2008年03月04日 载体容量：UMD×1参考价格：$:39.99美元 介绍网站点击进入

中英文会计科目对照表

中英文会计科目对照表如下: 会计科目中英对照表会计科目 accounting subject 顺序号serial number 编号code number 会计科目名称accounting subject 会计科目适用范围accounting subject range of application 一、资产类 1 1001 库存现金 cash on hand 2 1002 银行存款 bank deposit 5 1015 其他货币资金 other monetary capital 9 1101 交易性金融资产 transaction monetary assets 11 1121 应收票据 notes receivable 12 1122 应收账款 Account receivable 13 1123 预付账款 account prepaid 14 1131 应收股利 dividend receivable 15 1132 应收利息 accrued interest receivable 21 1231 其他应收款 accounts receivable-others 22 1241 坏账准备 had debts reserve 28 1401 材料采购 procurement of materials 29 1402 在途物资 materials in transit 30 1403 原材料 raw materials 32 1406 库存商品 commodity stocks 33 1407 发出商品 goods in transit 36 1412 包装物及低值易耗品 wrappage and low value and easily wornout articles 42 1461 存货跌价准备 reserve against stock price declining 43 1501 待摊费用 fees to be apportioned 45 1521 持有至到期投资 hold investment due 46 1522 持有至到期投资减值准备 hold investment due reduction reserve

国际会计准则第无形资产

国际会计准则第38号无形资产 1998-06发布 发布时间：2000年08月27日 目的 本准则的目的是对其他国际会计准则中没有具体涉及的无形资产的会计处理进行规范。本准则要求，当且仅当特定条件满足时，企业应确认无形资产。本准则亦对如何计量无形资产的账面金额作了规定，并就无形资产的特定放过提出了要求。 范围 1．本准则应适用于所有企业除以下各项之外的无形资产的会计核算： (1)由其他国际会计准则规范的无形资产； (2)《国际会计准则第32号金融工具：披露和列报》中定义的金融资产； （3）矿产权，以及矿产、石油、天然气和类似非再生性资源的勘探支出或开发和采掘支出；

（4）保险公司与保单持有人之间签订的合同所产生的无形资产。 2．如果其他国际会计准则涉及了特定类型的无形资产，那么企业应运用该项准则而不是本准则。例如，本准则不适用于以下各项无形资产： （1）企业在正常经营过程中为出售而持有的无形资产（见《国际会计准则第2号存货》和《国际会计准则第11号建造合同》）； （2）递延所得税资产（见《国际会计准则第12号所得税》）； （3）属于《国际会计准则第17号租赁》范围内的租赁； （4）雇员福利所形成的资产（见《国际会计准则第19号雇员福利》）； （5）企业合并中形成的商誉（见《国际会计准则第22号企业合并》）； （6）《国际会计准则第32号金融工具：披露和列报》中定义的金融资产。金融资产的确认和计量由以下准则规范：《国际会计准则第27号合并财务报表和对于公司投资的会计》、《国际会计准则第28号在联营企业投资的会计》、《国际会计准则第31号合营中权益的

财务报告》和《国际会计准则第39号金融工具：确认和计量》。 3．一些无形资产可能会以实物为载体，例如磁盘（对计算机软件而言）、法律文件（对许可证或专利权而言）或胶片式确定一项包含无形和有形要素的资产应按《国际会计准则第历号一固定资产》核算，还是作为一项无形资产而按本准则核算，需要进行判断，以评价哪个要素更重要。例如，一台计算机控制的机械工具没有特定计算机软件就不能正常运行时，则说明该软件构成相关硬件不可缺少的组成部分，从而该软件应作为固定资产核算。同样的原则适用于计算机控作系统。如计算机软件不是相关硬件不可缺少的组成部分，则该软件应作为无形资产核算。 4．本准则还适用于广告、培训、开办活动、研究与开发活动支出等。研究与开发活动的目标是开发知识。因此，虽然这些活动可能会产生有实物形态的资产（例如，样品），但该资产的实物要素次于其无形要素（即含在实物要素中的知识）。 5．就融资租赁而言，标的资产可能是有形的，也可能是无形的。初始确认后，承租人应按本准则的规定核算因融资租赁而持有的无形资产。电影、录相、戏剧、手稿、专利权和版权等项目的许可证协议中的权利不在《国际会计准则第对号一租赁》范围之内，而在本准则范围之内。 6．如果某些活动或交易特殊，可能需要用其他方式进行会计处理，那么该活动或交易可能会被排除出某项国际会计准则的范围。采掘业中因石油、天然气和矿产的勘探或开发和采

《战神的挑战2》图文流程攻略

《战神的挑战2》图文流程攻略 事情还没有结束，在更深的地下有人知道Laurella母亲的情况，打开通往下面的门离开地下墓穴的世界我们进入了地精实验室。 这扇巨大的金门在其他3个地方上锁了，分别拉下这3个地方的闸门。

石器时代的食人魔，有铁头功技能：造成20伤害并震晕一回合，附加当前对方蓝魔法数值的伤害。

来自希腊神话故事的人身牛头怪守卫第一道闸门的开关，战斗时你的武器会被替换成一件“斗牛士的披风”(需要8行动点数)，它的作用是防止被神牛冲倒。神牛的冲刺技能：造成10的伤害并击倒对方5个回合。另一个技能Gore：造成5的伤害，如果对方处于击倒状态则附加25点的伤害。 [pagesplitxx][pagetitle][/pagetitle] 这只枭守卫着南方闸门的开关，没有什么特殊的能力。

西方闸门开关由著名的美杜莎驻守，除了石化技能之外，它的毒武器造成14*8(回合)的伤害并给自己增加10的防御。其他生命和防御都较低，不难对付。拉下第三个开关，任务更新：逃离地精实验室。

看起来暴乱已经激怒了堕落的精灵，精灵boss和它的两个手下以及一个巨大的钢铁侠一起出现在这里。一番嘘寒问暖之后站在最前面的精灵族战士手持双刀前来切磋，解决掉开胃菜之后，对上身后那位女性战法师。她有一个Mirror Shield技能：将对方的防御值全部吸到自己身上，持续10+1/8自身蓝魔法的回合，而她初始防御就有47，所以使用该技能后基本上防御值超过100，注意使用减防技能。另一个Dark Blast技能如果紫色魔法多的话伤害也会很高，而且只消耗3的红色魔法。

会计科目中英对照表

资产Assets 流动资产Current assets 货币资金Cash at bank and on hand 交易性金融资产Financial assets held for trading 应收票据Notes receivable 应收账款Accounts receivable 预付款项Advances to suppliers 应收利息Interest receivable 应收股利Dividends receivable 其他应收款Other receivables 存货Inventories 一年内到期的非流动Current portion of non-current assets

资产 其他流动资产Other current assets 流动资产合计Total current assets 非流动资产Non-current assets 可供出售金融资产Available-for-sale financial assets 持有至到期投资Held-to-maturity investments 长期应收款Long-term receivables 长期股权投资Long-term equity investments 投资性房地产Investment properties 固定资产Fixed assets 在建工程Construction in progress 工程物资Construction materials

固定资产清理Fixed assets pending for disposal 生产性生物资产Bearer biological assets 油气资产Oil and gas assets 无形资产Intangible assets 开发支出Development costs 商誉Goodwill 长期待摊费用Long-term prepaid expenses 递延所得税资产Deferred tax assets 其他非流动资产Other non-current assets 非流动资产合计Total non-current assets 资产总计Total assets

企业会计准则第38号——首次执行企业会计准则

企业会计准则第38号——首次执行企业会计准则 第一章总则 第一条为了规范首次执行企业会计准则时的确认、计量和财务报表列报，根据《企业会计准则——基本准则》，制定本准则。 第二条首次执行企业会计准则，是指企业第一次执行2006年发布的企业会计准则体系，包括基本准则、各项具体准则和会计准则应用指南。 第三条首次执行企业会计准则后发生的会计政策变更，适用《企业会计准则第28号——会计政策、会计估计变更和差错更正》。 第二章确认和计量 第四条在首次执行日，企业应当对所有资产、负债和所有者权益按照企业会计准则的规定进行重新分类、确认和计量，并编制期初资产负债表，本准则规定不应追溯调整的除外。 第五条对于首次执行日的长期股权投资，应当分别下列情况处理： (一)对于按照《企业会计准则第20号——企业合并》规定，属于同一控制下企业合并产生的长期股权投资，尚未摊销完毕的股权投资差额全额冲销，并调整留存收益，以冲销股权投资差额后的长期股权投资账面价值作为首次执行日的认定成本。 (二)除上述第(一)项以外的其他采用权益法核算的长期股权投资，存在股权投资贷方差额的，应冲销贷方差额，调整留存收益，并以冲销贷方差额后的长期股权投资账面价值作为首次执行日的认定成本；存在股权投资借方差额的，应当将长期股权投资的账面价值作为首次执行目的认定成本。 第六条在首次执行日，企业应当根据《企业会计准则第3号——投资性房地产》，将符合投资性房地产定义、原包括在固定资产(或无形资产、存货)账面价值中的相应金额，确认为投资性房地产。 对于有确凿证据表明可以采用公允价值模式计量的投资性房地产，应当按照其公允价值进行计量，账面价值与公允价值的差额，调整留存收益。 第七条在首次执行日，对于符合预计负债确认条件且该日之前尚未计入固定资产成本的弃置费，应当增加该项资产成本和负债；同时，将应补提的折旧调整留存收益。

战神的挑战1代全捕捉攻略

Arboreth 死亡腾蔓 第1列的骷髅头向右移7次 第7列的紫星向左移6次 第3列的红宝石向下移 第6列的绿宝石向下移 Arkliche 大巫妖 第3列的绿宝石向右移 第6列的绿宝石向左移 第2列的紫星向右移 第7列的紫星向左移 第2列的骷髅头向上移 第7列的骷髅头向上移 Catapult 攻城机 第2列的黄宝石向左移 第7列的绿宝石向右移 第4列的蓝宝石向右移 第4列的紫星向右移 第3、6列的闪光骷髅头向上移 Centaur 半人马 第3列的蓝宝石向右移 第6列的蓝宝石向左移 第2列的红宝石向右移 第7列的红宝石向左移 第4列的骷髅头向左移 第5列的骷髅头向右移 Dark Dwarf 黑暗矮子 第8列的绿宝石向上移 第6列最上方的骷髅头向右移 第3列最上方的绿宝石向右移 第1列的绿宝石向上移 第3列的红宝石向上移 第6列的绿宝石向左移 第4列的红宝石向上移 第6列的金币向下移 Doom Knight 末日骑士 第２、４、６、８行最上方的骷髅头向下移 第１（最上方）、３（最下方）、５（最下方）、７（最下方）行的骷髅头向下移第３、７行的骷髅头向上移

Dragon Spider 龙蜘蛛 第２列的骷髅头向右移 第７列的骷髅头向左移 第４列最上方的黄宝石向上移 第５列最上方的黄宝石向上移 第４列最下方的红宝石向左移 第５列的红宝石向右移 Elven Guard 精灵守卫 第２列最下方的黄宝石向右移 第７列最下方的黄宝石向左移 第２列最下方的绿宝石向右移 第２列的绿宝石向右移 第２列的骷髅头向左移 第７列最上方的绿宝石向下移 第７列的骷髅头向右移 Fire Elemental 火元素 第５列最上方的骷髅头向下移 第３列最上方的骷髅头向下移 第６列最上方的骷髅头向下移 Fire Giant 火巨人 第８列的金币向左移 第２列的闪光骷髅头向右移 第５列的骷髅头向下移 第１列的金币向右移 第５列的红宝石向右移 Flame Dragon 火焰龙 第２、４列最下方的骷髅头向左移 第２列的骷髅头向下移２次 第４列的黄宝石向左移 第４列最下方的红宝石向上移 第６、８列最下方的骷髅头向左移 第６列的骷髅头向下移 第８列的骷髅头向左移 第６列的骷髅头向下移 第８列的黄宝石向左移 Frost Dragon 霜龙 第３列上方第２个骷髅头向右移 第６列最上方的骷髅头向左移

国际会计科目中英文对照

国际会计科目中英文对照Account帐户 Accounting system会计系统AmericanAccountingAssociation美国会计 协会 AmericanInstituteofCPAs美国注册会计师 协会 Audit审计 Balance sheet资产负债表 Bookkeepking簿记 Cash flow prospects现金流量预测 Certificate in Internal Auditing内部审计证书CertificateinManagementAccounting管理 会计证书 Certificate Public Accountant注册会计师 Cost accounting成本会计 External users外部使用者 Financial accounting财务会计 Financial Accounting Standards Board财务会 计准则委员会 Financial forecast财务预测

Generallyacceptedaccountingprinciples公认会计原则 General-purpose information通用目的信息GovernmentAccountingOffice政府会计办公室 Income statement损益表InstituteofInternalAuditors内部审计师协会InstituteofManagementAccountants管理会计师协会 Integrity整合性 Internal auditing内部审计 Internal control structure内部控制结构Internal Revenue Service国内收入署Internal users内部使用者 Management accounting管理会计Return of investment投资回报 Return on investment投资报酬SecuritiesandExchangeCommission证券交易委员会 Statement of cash flow现金流量表

企业会计准则第38号

企业会计准则第38号 财会[2006]3号 第一章总则 第一条为了规范首次执行企业会计准则对会计要素的确认、计量和财务报表列报，依照《企业会计准则——差不多准则》，制定本准则。 第二条首次执行企业会计准则，是指企业第一次执行企业会计准则体系，包括差不多准则、具体准则和会计准则应用指南。 第三条首次执行企业会计准则后发生的会计政策变更，适用《企业会计准则第28号——会计政策、会计估量变更和差错更正》。 第二章确认和计量 第四条在首次执行日，企业应当对所有资产、负债和所有者权益按照企业会计准则的规定进行重新分类、确认和计量，并编制期初资产负债表。 编制期初资产负债表时，除按照本准则第五条至第十九条规定要求追溯调整的项目外，其他项目不应追溯调整。 第五条关于首次执行日的长期股权投资，应当分别下列情形处理： （一）依照《企业会计准则第20号——企业合并》属于同一操纵下企业合并产生的长期股权投资，尚未摊销完毕的股权投资差额应全额冲销，并调整留存收益，以冲销股权投资差额后的长期股权投资账面余额作为首次执行日的认定成本。 （二）除上述（一）以外的其他采纳权益法核算的长期股权投资，存在股权投资贷方差额的，应冲销贷方差额，调整留存收益，并以冲销贷方差额后的长期股权投资账面余额作为首次执行日的认定成本； 存在股权投资借方差额的，应当将长期股权投资的账面余额作为首次执行日的认定成本。 第六条关于有确凿证据说明能够采纳公允价值模式计量的投资性房地产，在首次执行日能够按照公允价值进行计量，并将账面价值与公允价值的差额调整留存收益。 第七条在首次执行日，关于满足估量负债确认条件且该日之前尚未计入资产成本的弃置费用，应当增加该项资产成本，并确认相应的负债；同时，将应补提的折旧（折耗）调整留存收益。 第八条关于首次执行日存在的解除与职工的劳动关系打算，满足《企业会计准则第9号——职工薪酬》估量负债确认条件的，应当确认因解除与职工的劳动关系给予补偿而产生的负债，并调整留存收益。

《战神3》图文流程攻略

《战神3》图文流程攻略 听完奎爷讲述一下自己在战神1以及战神2之后，玩家跟随奎托斯坠入冥河，顺着河流游，途中会被怨灵吸去生命/魔法以及武器能力，不用挣扎，这是剧情需要，上岸之后失去神力的奎爷疲倦不堪，拖着疲惫的步伐向前走吧，向前不用走多远便可以触发剧情，宙斯的姐姐-智慧女神雅 典娜，并且给失去光芒的混沌双刃注入了新的能力，变成了“流亡双刃”，拿起它，踏上冥界的征途。 向右走，通过跳跃点到达对面远处的平台，不要忘了下方有重要物品-两个红魂箱子以及一个装有“美杜莎之眼”的宝箱，拿完之后就可以上去继续征途了，一路向前解决一波杂兵，适应一下实力大不如前的奎托斯，抵达第三个存档点，此时有两条路，左边一条是通往蕴有四个红魂箱子的平台，右边则是继续流程。

喜欢搞基的-冥王哈迪斯在和你对话了，你明白不明白他话中的话呢……几句话之后获得新魔法“斯巴达军团”(怎么来的?有点莫名其妙～)接下来出现的一些敌人是给你练魔法的;面前有“地狱藤蔓”暂时还开不了，通过右方的锁链一路到对面，途中会有一些杂兵干扰，从锁链上下来之后补充一下生命以及魔法，继续赶路，跳下低处，别忘了背后有两个红魂箱子，然后向前推开大门，首先是一大堆被折磨的灵魂再被美杜莎虐待，上前解决掉两只美杜莎后大门便会打开，往左继续流程。 [pagesplitxx][pagetitle][/pagetitle]

一路向前到达“受折磨的皮尔埃托斯”处，开始一个小解谜，以皮尔埃托斯头上的平台为跳板，进入到里面的房间将“易燃的荆棘”推到对面地狱犬牢笼处，再回头跳上皮尔埃托斯头前方的平台，然后到达“易燃的荆棘”上方飞上上方的平台，触发机关放出地狱犬，几下攻击之后，触发QTE，骑上地狱犬自由的奔驰吧，清理掉路上的杂兵，驾驭地狱犬靠近皮尔埃托斯喷火，让他脱离苦海，随后处决胯下的地狱犬，去获取“阿波罗之弓”。 (使用方法是：按住L2锁定敌人，右摇杆切换目标，?射箭，按住?可以蓄力，带有穿透效果，杀伤力很可观。) 用阿波罗之弓燃烧掉场景中部上方的藤蔓，然后将“易燃的荆棘”推到如上图所示的位置，站在上面即可飞进地图中上方场景内奖励一个红魂箱子以及一个“凤凰羽毛”(增加魔法最大值物品)

《最新国际会计科目中英文对照》(2013.9)

中国会计科目中英文对照 代码名称代码名称代码名称代码名称英译 1 资产assets 11~ 12 流动资产current assets 111 现金及约当现金cash and cash equivalents 1111 库存现金cash on hand 1112 零用金/周转金petty cash/revolving funds 1113 银行存款cash in banks 1116 在途现金cash in transit 1117 约当现金cash equivalents 1118 其它现金及约当现金other cash and cash equivalents 112 短期投资short-term investment 1121 短期投资-股票short-term investments - stock 1122 短期投资-短期票券short-term investments - short-term notes and bills 1123 短期投资-政府债券short-term investments - government bonds 1124 短期投资-受益凭证short-term investments - beneficiary certificates 1125 短期投资-公司债short-term investments - corporate bonds 1128 短期投资-其它short-term investments - other 1129 备抵短期投资跌价损失allowance for reduction of short-term investment to market 113 应收票据notes receivable 1131 应收票据notes receivable 1132 应收票据贴现discounted notes receivable 1137 应收票据-关系人notes receivable - related parties 1138 其它应收票据other notes receivable 1139 备抵呆帐－应收票据allowance for uncollec- tible accounts- notes receivable 114 应收帐款accounts receivable 1141 应收帐款accounts receivable 1142 应收分期帐款installment accounts receivable 1147 应收帐款-关系人accounts receivable - related parties 1149 备抵呆帐－应收帐款allowance for uncollec- tible accounts - accounts receivable 118 其它应收款other receivables 1181 应收出售远汇款forward exchange contract receivable 1182 应收远汇款-外币forward exchange contract receivable - foreign currencies 1183 买卖远汇折价discount on forward ex-change contract 1184 应收收益earned revenue receivable 1185 应收退税款income tax refund receivable 1187 其它应收款- 关系人other receivables - related parties 1188 其它应收款- 其它other receivables - other 1189 备抵呆帐- 其它应收款allowance for uncollec- tible accounts - other receivables 121~122 存货inventories 1211 商品存货merchandise inventory 1212 寄销商品consigned goods

[PSP]《战神》详细完美图文全攻略及心得

[PSP]《战神》详细完美图文全攻略及心得 游戏介绍 《战神Ω奥林匹斯之链》（God of War : Chains of Olympus）是以 PS2 上大畅销的《战神》（God of War）系列为题材的PSP 原创新作，本作由 Ready at Dawn 研发，充分发挥 PSP 所具备

的 3D 处理性能，呈现出不亚于 PS2 版壮阔的游戏场景以及细腻角色。 游戏承袭相同的故事背景与游戏类型，玩家将再度扮演斯巴达战士奎托斯，继续施展“浑沌双刃”等致命武器，面对全新的难关、敌人与奥林匹斯诸神的试炼，体验与不同于本传的原创故事剧情。游戏承袭 PS2 系列作的特色，在 PSP 上重现了广受欢迎的电影运镜式精采游戏画面与刺激的动作战斗系统，并加入全新的招式、关卡、机关与怪物，以及以希腊神话为基础的全新剧情。玩家将扮演斯巴达战士奎托斯，从人间的雅典一直到冥王哈帝斯的冥府之门，一路朝向地狱的深渊迈进，体验希腊神话中黑暗且残暴的世界，并对抗各种传说中的怪物以及强大的头目角色。 战神故事背景 人类不断制造战火，加上战神阿瑞斯在凡间不断的挑动纷争，使凡间陷入一片混乱。于是战神的香火日渐鼎盛，势力也一天比一天强大，终于招致了众神的不满和嫉妒。众神的矛盾不断加剧，阿瑞斯更开始了向别的神公开宣战。 斯巴达战士奎托斯，是斯巴达的军队统领，他体格过人，英勇善战，但为人残酷，贪婪，嗜战。某一年，他率领大军和北方的日尔曼人决战，尽管他使出浑身解数，斯巴达战士视死如归，

仍然无法挽回己方的败局，残酷的战斗中，斯巴达军渐渐处于下风，越来越多人被杀，领袖奎托斯更被日尔曼首领逼到绝境。 在敌人的刀快要刺下来，奎托斯生死的瞬间，英勇的斯巴达人向天怒吼：“阿瑞斯！！！！我乞求您的帮助，让我打败我的宿敌吧！！当我达成心愿，我的灵魂将属于您！！”话音刚落，一道闪电从天而降，击中奎托斯。一副带锁链的利刃紧紧地缠在了他的手上，日尔曼首领被奇迹惊得呆住了。奎托斯乘他不备，挥动了手上的双刀，那硕大的躯体在一瞬间就被砍得四分五裂，只剩下那头颅圆睁着充满困惑和不解的眼睛。阿瑞斯接受了斯巴达人的交易，战场上日尔曼战士都被无形的力量宰杀，好一场血腥的屠戮！战斗过后，阿瑞斯告诉斯巴达人，这刻起，你就是我的仆人，灵魂永远属于我，必须为我永世效劳，手上那不能取下的双刀就是契约的证明。 从此，奎托斯整天陷入无休止的战争中，不断地屠杀着，征服着。直到一天，他把战火烧到了一个村落，他肆无忌惮地杀戮着，见人就剁，还吩咐部下烧村。神庙旁的老妇极力地劝说他放过庙里的人，那是神圣的地方啊！可是奎托斯已经毫无人性了，他闯进庙中，见人就杀，不久，人们都倒在血泊中。杀红了眼的奎托斯却惊讶地发觉妻儿已经死在他眼前，而凶手正是他本人！这一刻，后悔，懊恼，愤恨同时涌上他的心头，人性和良知渐渐回到他的脑中。他认为这是阿瑞斯的陷阱，是让他彻底地为战神

新会计准则会计科目表(中英文对照)知识分享

一、资产类 1 1001 库存现金cash on hand 2 1002 银行存款bank deposit 5 1015 其他货币资金other monetary capital 9 1101 交易性金融资产transaction monetary assets 11 1121 应收票据notes receivable 12 1122 应收账款Account receivable 13 1123 预付账款account prepaid 14 1131 应收股利dividend receivable 15 1132 应收利息accrued interest receivable

21 1231 其他应收款accounts receivable-others 22 1241 坏账准备had debts reserve 28 1401 材料采购procurement of materials 29 1402 在途物资materials in transit 30 1403 原材料raw materials 32 1406 库存商品commodity stocks 33 1407 发出商品goods in transit 36 1412 包装物及低值易耗品wrappage and low value and easily wornout articles 42 1461 存货跌价准备reserve against

stock price declining 45 1521 持有至到期投资hold investment due 46 1522 持有至到期投资减值准备hold investment due reduction reserve 47 1523 可供出售金融资产financial assets available for sale 48 1524 长期股权投资long-term stock ownership investment 49 1525 长期股权投资减值准备long-term stock ownership investment reduction reserve 50 1526 投资性房地产investment real eastate 51 1531 长期应收款long-term account

国际会计科目对照表中英

ccount?帐户 Accounting?system?会计系统? American?Accounting?Association?美国会计协会? American?Institute?of?CPAs?美国注册会计师协会? Audit?审计? Balance?sheet?资产负债表? Bookkeepking?簿记? Cash?flow?prospects?现金流量预测? Certificate?in?Internal?Auditing?内部审计证书? Certificate?in?Management?Accounting?管理会计证书? Certificate?Public?Accountant注册会计师? Cost?accounting?成本会计? External?users?外部使用者? Financial?accounting?财务会计? Financial?Accounting?Standards?Board?财务会计准则委员会? Financial?forecast?财务预测? Generally?accepted?accounting?princip les?公认会计原则? General-purpose?information?通用目的信息 Government?Accounting?Office?政府会计办公室? Income?statement?损益表? Institute?of?Internal?Auditors?内部审计师协会? Institute?of?Management?Accountants?管理会计师协会? Integrity?整合性? Internal?auditing?内部审计?