Eric Leclercq

Marinette Savonnet

Andrès-Camillo Troya

Stéphane Büttner
email: stephane.buttner@cem-auxerre.fr

Éric Leclercq

Andrés-Camilo Troya

Investigating a multi-paradigm system for the management of archaeo-logical data : Corpus Lapidum Burgundiae

Keywords: Scientific Information System, Archaeological Corpus, Semantic Annotation, Semantic Wiki

come   L'archive ouverte pluridisciplinaire

I. INTRODUCTION

SIS must move beyond data repositories and closed systems, to allow collaborations among different research disciplines, to include new types of data, to control the quality of derived data, and to enable semantic interoperability. SIS aim to produce, improve and manage knowledge on a subject through activities of research and development. Unlike enterprise information systems, SIS do not support activities of production or services. Thus, SIS are strongly collaborative systems involving different kinds of users (scientists of different disciplines, domain professionals, etc.).

Scientific data have the following properties: 1) they include collections of large datasets; 2) they use complex spatiotemporal models; and 3) they enclose both explicit and implicit, hard-to-discover relationships. Moreover, scientific data are heterogeneous as they come from different sources (for example observation and reanalysis data in climatology) and from different acquisition technologies (for example mass spectroscopy in biology, 3D scanner in cultural heritage, thermoluminescence sensors for dating in archaeology). A large variability of data models have been observed in the last decade that come from the evolution of scientific knowledge and methods (migration from purely experimental to statistical way of thinking [START_REF] Sȃvoiu | The scientifiv way of thinking in statistics, statistical physics and quantum mechanics[END_REF]) and from high performance computing that allows computation at the molecular level as well as at astronomical scales. As database management systems are essential component of SIS they should provide extensibility mechanism.

DBMS are essential component of SIS nevertheless R-DBMS does not provide enough extensibility, schema evolutions usually impact applications and are costly. NoSQL databases such as key-value, column oriented, document oriented or graph have been design for specific purpose and does not meet the requirement of SIS as constraint checking and query languages. XML and associated Semantic Web technologies provide extensibility but does not scale well for scientific data. Only a multi-paradigm approach can satisfy all the properties required by SIS.

We propose to investigate a multi-paradigm approach for data management in the context of archaeological SIS used for building and publishing a corpus [START_REF] Gray | Scientific data management in the coming decade[END_REF] about Burgundy Stones. The archaeological data include textual information, quantifiable values and measures, sketches, photographies, 3D models, and lots of links among data and historical information sources.

The Burgundy (Bourgogne) Region in France has an identity strongly marked by the arts of the construction and the statuary. It's also a territory with many quarries in which some remarkable qualities stones were exploited and are still exploited today. These different aspects are the object of particular and complementary treatments, both in behalf of researchers (archaeologists, historians, geologists) and of stone sector professionals. The objective of the Corpus Lapidum Burgundiae project is to determine statements which defined Burgundy as an innovative and influential region in the fields of art history and architecture through the ages. We develop a digital corpus of stone extractions in the Burgundy region and stone usages in the construction (buildings, sculptors, sarcophagus, etc.) from antiquity period to modern time. The circulation and the broadcasting of stones in the space and in the time is analyzed. At the same time, Geographical Information System (GIS) tools are used to identify the most important quarries and the areas of distribution of their products in the regional territory and beyond. Indicating the specific qualities of each type of stone (density, hardness, porosity, etc.) and associated techniques (modules, tool marks, etc.), it's also possible to understand the possible links between the choice specific of stone, technical treatment and the use as a building component. Textual and archaeological evidences show the dating of these changes and adjustments, and maybe determine the origin and geographical spread of Burgundy stones. Primary data come from existing databases, historical documents and many other types of resources such as photographies, sketches. The results are given to the scientific community, the restoration professionals, the stone sector professionals and the large public, by the development of a collaborative Web platform. For historians and archaeologists working on these aspects, the platform should renew the perception of technical and economic operations for the old building in Burgundy; especially regarding trade flows of stones. Moreover, historians of art and architecture should also find something to think about the propagation of models and issues regarding stylistic affiliation. It's also a way to provide information to restoration professionals of old buildings and to make advertising to the "Pierre de Bourgogne" industry with scientific references its current production with the most distinguished buildings in Burgundy and elsewhere.

To meet the required feature of the Corpus Lapidum Burgundiae project, we have developed a Web platform that relies on our framework architecture SemLab [START_REF] Leclercq | Enhancing scientific information systems with semantic annotations[END_REF]. In SemLab, knowledge takes the form of a domain ontology used to define ontology-based annotations which are used: 1) to give a semantics to existing data; 2) to extend dynamically schema without modifying application and; 3) to bridge data model in order to construct a multi-paradigm data management layer. We use a wiki as user interface to meet the requirements of a Web platform with collaborative capabilities for establishing and publishing the digital corpus. The rest of this article is structured as follows, in section II we describe data management layer of SemLab architecture and we focus on the annotation model and query operators. In section III we describe an instantiation of SemLab for the Corpus Lapidum Burgundiae application, we describe the master data and the domain ontology as well as the analysis database (one of the specificity of the project) that is dynamically populated and used by GIS analysis tools. Finally, in section ?? we summarize our contribution and we discuss our future work.

II. SEMLAB: A MULTI-PARADIGM APPROACH

We propose a multi-paradigm data management system approach [START_REF] Ghosh | Multiparadigm Data Storage for Enterprise Applications[END_REF] that relies on master data and ontology-based annotations. In the following section we give an outline of the architecture, we describe our annotation model and we define the basis for a multi-paradigm query language.

A. Architecture outline

The master data are strongly structured and they can be identified during the analysis phase, they are recognized by all the application partners and evolve very rarely [START_REF] Dreibelbis | Enterprise Master Data Management: An SOA Approach to Managing Core Information[END_REF]. SemLab uses a hybrid register/repository architecture style for the master data. In this architecture style, the most important data are duplicated in a RDBMS, and data which need a specific models or data for which it is not possible to set-up a schema are separately stored in specific storage systems.

Ontology-based annotations are used as links between data modelled with different paradigms and the semantics of the domain. Most of the existing annotation models ( [START_REF] Oren | What are semantic annotations[END_REF]) share a common representation written as a triple (s, p, o) where s is the subject or the annotated resource; p is a predicate or a relationship being specified by the annotation; and o is the object or the annotating resource. The domain ontology is used to constrain the annotation components. Thus, ontology-based annotations are formal annotations [START_REF] Oren | What are semantic annotations[END_REF] that can be understood by a machine and allow to make analysis and treatments in an automatic way. Moreover, by using association reasoning tools on annotations it is possible to check their consistency and to discover implicit relationship among data. 1) A data access layer in charge of persistence and integrates various data management systems. For example, archaeological domain manipulates essentially documents, that can be stored in NoSQL document-oriented databases such as MongoDB 1 . 2) A multi-paradigm management layer includes a specific repository for master data, a persistency service for annotations, and a triple store for the ontology. Master data can be stored in a key value NoSQL database or in a RDBMS depending on their volume. Annotations can be stored in a RDBMS, in a NoSQL graph database as Neo4j 2 or in a column oriented NoSQL database. This layer also include reasoning tools such as Pellet and SPARQL service to query the ontology; 3) An application layer includes domain specific applications such as Wiki to publish results or spatial analysis tools to produce maps. In our approach ontology-based annotation allows extensibility at two different levels: at the data schema level, they can be used to add information without modifying the existing applications because annotation is a very simple and universal structure which allows to develop generic components; and at the models level (among different models), they can be used to connect, in a transparent way, data modelled by different paradigms with master data. Furthermore, SemLab allows traceability of data and quality control as well as semantic interoperability.

B. Ontology-based annotation model

Annotated databases include annotations as additional information used to allow a better understanding of data. They offer mechanisms to create, store and query annotations linked with tuples. First, they were studied by the database research community, for specific purposes. Annotation models have been developed to deal with uncertainty, trustworthiness, multi-set data and incomplete information [START_REF] Green | Provenance semirings[END_REF]. All of this models have simple annotation structure in which terms must conform to a specific semiring. Moreover, annotations cannot be restricted by using constraints and consistency checking is not possible.

Our annotation model defines three basic structures of annotation: simple, complex, and recursive. They share the same basic triple structure (s, p, o), s, p, o are constrained by a domain ontology terms [START_REF] Leclercq | Enhancing scientific information systems with semantic annotations[END_REF] and thus, allows to develop consistency checking and tools to guide users in the annotation process by using the structure and rules of the ontology.

The definitions of the three basic structures are the following:

1) Simple annotation has the structure (s, p, o) where s and p cannot be null. These kind of annotations can be compared to constraints on attribute in the database context; 2) Complex annotation is a list of simple annotations related to the same subject; 3) Recursive annotation is used to explain or to give more details on how the object and the predicate are linked together with the subject by a sub-annotation which is a simple or a complex annotation.

To combine annotations to operators have been defined: + is the set builder and . the ordered list builder for complex and recursive annotations respectively. For one subject s, by using simple annotations and operators, we can obtain an annotation 2 Neo4j:http://neo4j.org/ Fig. 2. Annotation tree string which is a finite set of triples. One can easily find an isomorphism between string representation and oriented graph (tree). Figure 2) give an example of the tree for the following annotation string:

((s, p 1 , o 1 )((o 1 , p 2 , o 2 ), (o 1 , p 3 , o 3 )((o 3 , p 4 , o 4 )), (s, p 5 , o 5 ))
Let A be the set of all annotations, x 1 = (a, b, c) ∈ A and, x 2 = (d, e, f ) ∈ A, the two operators are defined as follows (for the sake of brevity, we use a tree representation): 1) Addition: x 1 + x 2 is defined by a connection of annotation trees using their subject, it merges two different simple annotations into a complex annotation which subjects are the same (a = d). As a result, a is annotated by two objects c and f with respect of the predicates b and e (figure 3); 2) Product: x 1 .x 2 is defined by the creation of new graph with a path going from a to f (annotations are concatenated), c and dd must be equal. This operator puts two different simple annotations into a recursive annotation where the subject a is annotated by c which is annotated in his turn by f (figure 4). It is used to give details on the previous annotation.

C. Formal basis for a query language

It is essential to have good theoretical basis to manage and query data and annotations. Formal annotation models as Krelations showed their ability; by annotating relational data with elements from a particular algebraic structure (usually a commutative semiring) it is possible to compute the corresponding annotations for query results, and also to compute their provenance [START_REF] Green | Provenance semirings[END_REF].

To combine expressiveness and flexibility of annotations with the theoretical formalisms of K-relations, we characterized a structure of semiring K = (K, +, ., , ♦) for our annotation model based on (s, p, o) triples. Annotation can be formally represented by a string belonging to a given alphabet Σ = { , ♦, a, ..., z, A, ..., Z, ( , ) , , }. Σ * is the set of words in alphabet Σ and K ⊂ Σ * . Let (s, p, ) be the neutral annotation. It means that the annotation is not complete and should not be used as long as the object is equal to . Let (s, p, ♦) be the neutral annotation it means that the annotation is supposed to be false. We showed that K is a semiring [START_REF] Troya | Annotated Databases for Scientific Information Systems -an Application to Cultural Heritage[END_REF].

We characterized the behaviour of a subset of relational algebra operators (union, semi-join, selection, projection) on annotations [START_REF] Troya | Annotated Databases for Scientific Information Systems -an Application to Cultural Heritage[END_REF]. For example, we give an informal definition of union and semi-join:

• two annotation trees T 1, T 2 are compatible for union if they have the same subject s as root, then T 1 ∪ T 2 is the annotation tree having s as root without duplicated sub-trees; • two annotation trees T 1, T 2 are compatible for semi-join if the root s of T 2 is identical to one of the leaves l in T 1. Then T 1 ⋉ T 2 is the annotation tree T 1 completed by the concatenation of T 2 starting from l (figure 5). Note that, x is not commutative so the join operator of relational algebra cannot be defined on annotations.

Therefore, we have a specification of how annotations behave towards relational queries and so it would be possible to define an unified language to query in parallel annotated data as well as their associated annotations.

III. DESCRIPTION OF THE Corpus Lapidum Burgundiae

APPLICATION

In this section, we describe the instantiation and the implementation of specific components of SemLab for a collaborative Web platform for the Corpus Lapidum Burgundiae. We describe the domain ontology and a specificity of the project, i.e. an analysis database.

A. Instantiation of SemLab

The objective of the platform, based on Web 2.0 and Semantic Web technologies, is to facilitate the processes of interpretation and analysis of documents and data using the annotation mechanism. From a technical point of view, the users interface of the platform is deployed a semantic Wiki.

Archaeological data manipulated by researchers can be organized into three levels: 1) the raw data or source material which, in Corpus Lapidum Burgundiae, are an aggregation of textual and multimedia resources (images, documents, sketches, etc.); 2) the structure which takes the shape of a classic relational database which stores master data and a triple store which stores annotations and allows extensibility of the data structure; and 3) the meaning of a whole document or of a part of a document. This level describes essential information such a semantic context, provenance, quality, and makes an intensive use of ontology-based annotations. During search or analysis of the corpus all the three levels can be queried using an API. The first stage is the identification of salient concepts and properties which let us to build a conceptual model. Three groups of elements in the conceptual model have been identified: quarries from where are extracted (or supposed to be extracted) stones and buildings in which stones are used (as an architectural elements, ground, wall or as a scattered object which is somewhere else, in a museum for example). In a second stage, we construct an application ontology for our application by specializing a domain ontology and by selecting, organizing all the concepts and properties identified in the previous stage. Concepts and properties that can easily quantifiable are stored as master data, i.e. concept that are used to describe stones and their properties, properties of buildings, manufacturing techniques, tools, etc. (figure 6). Individual of the ontology are used to populate values in lists for master data attributes. The master data structure from the conceptual model is translated into Wiki templates. Moreover, Wiki template allows users to define the structure of a generic article [START_REF] Haake | Wiki-templates: adding structure support to wikis on demand[END_REF] used as starting point for the creation of new articles having the same structure. Semantic Forms 3 developed for MediaWiki allows to define such templates with automatic annotation capabilities. Other templates are defined to provide users with a synthetic articles aggregating some essential information (right part of figure 7). Semantic Forms and Wiki templates have been extended to automatically store master data in a RDBMS.

B. Master data and wiki template

Wiki make alarge use of links, links towards pages of the wiki (e.g. link between a quarry and an extracted stone), links towards external resources (like other databases such as Mérimée 4 , Palissy 5 , CARE [START_REF] Chevalier | WikiBridge: a Semantic Wiki for Archaeological Applications[END_REF]) (figure 8). All kind of links in and outside the Wiki can be annotated.

C. Ontology-based annotations

The semantic component consists of annotations made by experts, that are guaranteed by the application ontology. In computer science, ontologies are defined as a formal specification of a shared conceptualization [START_REF] Nico | Construction of Engineering Ontologies for Knowledge Sharing and Reuse[END_REF] which theoretical basis is the description logic. Within the cultural heritage domain, the CIDOC Conceptual Reference Model (CIDOC) 6 has emerged as a standard domain ontology. CIDOC CRM deals with concepts at a high level of generality. Typically, application ontologies are a mix of concepts that are taken from domain ontologies and from specific application. We have developed an application ontology as a CIDOC CRM extension covering the Corpus Lapidum Burgundiae concepts.

The Corpus Lapidum Burgundiae ontology has several parts: a) concepts related to buildings, their spatial relationships and characteristics; b) stone and their characteristics; c) stone cutter tools (chisel, bush hammer, pick, etc.) and technique of construction; and d) quarry. Figure 9 represents all these concepts (blue concepts with EXX are CIDOC-CRM concepts). Buildings (e.g. temple, chapel, amphitheatre) are individual of the concept Building, with its decomposition into different ElementArchitectural to describe foundation, pavement, door, column, etc. and scattered object. These concepts have been placed under the concept E24 Physical Man-Made Thing CIDOC-CRM like TOOL concept. Indeed, CIDOC-CRM defines this concept as "all persistent physical items that are purposely created by human activity". STONE concept is a specialization of E57 Material, QUARRY is a E27 Site and Construction technique is E28 Coneptual Object.

CIDOC-CRM covers specific concepts related to time [START_REF] Binding | Implementing Archaeological Time Periods Using CIDOC CRM and SKOS[END_REF]. The concept E2Temporal Entity describes all phenomena which happen over a limited extent in time. Time model extensions are based on following criteria: some absolute benchmarks and a relative chronology based on intervals.

IV. CONCLUSION

In this article, we have demonstrated that extensibility and semantic data quality required by scientific applications can be achieved by using a multi-paradigm data management system that shares with the Semantic Web the same theoretical foundations. Ontology-based annotations allow researchers to establish relationship between data and domain knowledge. The semantics of annotations is guaranteed by an ontology which describes accurately domain knowledge. We have extended previous works on annotation from the database research community to define a formal model for ontology-based annotation. We have proved that our extension comply with a semiring algebraic structure that guarantee essential properties for query languages. We have instantiated our framework architecture SemLab to meet the requirement of a collaborative web platform.

An archaeological application based on a combination of Wiki and Semantic Web technologies is described. This combination preserves the key advantages of both technologies: the simplicity of wiki systems as shared content authoring tool, and the power of Semantic Web technologies w.r.t. structuring and retrieving knowledge. In the near future, we will instantiate SemLab for two other applications one for a corpus of french toponym and another one for a corpus describing medieval sculptures.

Our future work is directed towards well-founded theoretical models in order to define a meaningful query language. For that purpose, we proposed an analogy between relations and semantic annotations for positive relational algebra operators. This analogy has been used to define operators in an API and will allow us to develop extension of a query language on annotations for multi-paradigms data management system.

Figure 1 summarizes

 1 Fig. 1. SemLab Architecture

Fig. 4 . 1 O 2 O 3 P 3 O 4 P 4 P 2 P 1 O 4 O 5 O 6 P 6 P 5 S O 1 O 2 O 3 P 3 O 4 O 5 O 6 P 6 P 5 P 4 P 2 P 1 ⋉Fig. 5 .

 412334421456651233456654215 Fig. 3. Addition of two annotations

Fig. 6 .

 6 Fig. 6. Extract from the conceptual model of the Lapidum Burgundiae Corpus

Fig. 7 .

 7 Fig. 7. Wiki interface including master data and documentation

  Fig. 8. Templates and links

Fig. 9 .

 9 Fig. 9. Structure of Corpus Lapidum Burgundiae ontology

MongoDB:http://mongodb.org/

http://www.cidoc-crm.org

ACKNOWLEDGMENT

This work is supported by the Burgundy Region (CPER) and the European Union (FEDER).


Paul Alain Nana

Zéphyrin Fokam

Guy Martial

Ntoungwa Ebague

Pierre Ngassam

Geneviève Bricheux

Philippe Bouchard

Télesphore Sime-Ngando

Géneviève Bricheux

Télesphore Sime Ngando

Description of five new species of hysterocinetian ciliates (Ciliophora, Hysterocinetidae), endocommensal in a terrestrial oligochaete of the genus

Keywords: Alma, ciliates, Hysterocinetidae, phylogeny, Proptychostomoides n. g., Ptychostomoides n. g., Ptychostomum

come   L'archive ouverte pluridisciplinaire

Introduction

Alma nilotica is a soil dwelling oligochaete widely distributed in a damp mud along the river Sanaga (at Ebebda and Batchenga) in the region of Yaoundé. The worm harbours within its digestive tract both a rich fauna of Astome ciliates and a variety of ciliates from the family Hysterocinetidae. In these latter Paul Alain Nana, Zéphyrin Fokam, Guy Martial Ntoungwa Ebague et al. organisms, the morphogenetic process associated with cell replication and the ultrastructure of the cortical and buccal architecture has been described by [START_REF] Ngassam | Contribution à la connaissance des ciliés hystérocinétiens du Cameroun[END_REF], [START_REF] Njiné | Morphogenèse de bipartition de deux espèces de Ciliés Hysterocinetidae du genre Ptychostomum Stein, 1890, endocommensaux d'Oligochètes Glossoscolecidae[END_REF], [START_REF] Ngassam | Six espèces nouvelles d'Hysterocinetidae appartenant aux deux genres nouveaux Metaptychostomum et Proptychostomum, Ciliés endocommensaux d'un Oligochète terricole du Cameroun[END_REF][START_REF] Ngassam | Ciliés Hysterocinetidae des genres Amieta et Thurstonia: description de 4 espèces; dont 3 nouvelles, endocommensales de l'Oligochète Alma nilotica[END_REF][START_REF] Ngassam | Contribution to the study of Hysterocinetidae ciliates of the genus Ptychostomum. Description of six new species[END_REF][START_REF] Ngassam | Description of the new genus Hysterocinetoides (Ciliophora, Hysterocinetidae) and revision of the systematics of the subclass Hysterocinetia[END_REF], and [START_REF] Ngassam | Contribution à l'étude des Ciliés Hysterocinetidae: le genre Preptychostomum de Puytorac[END_REF][START_REF] Ngassam | On Paraptychostomum almae n. g., n. sp., a commensal ciliate from the digestive tract of oligochaetes of the Cameroons, in a new subclass Hysterocinetia[END_REF].

Furthermore, during the course of studying the patterns of morphological variation in those species of hysterocinetian cilates, commensal in Glossoscolecidae, we have noted a certain structural conservatism at the level of the buccal apparatus, which comprises one paroral and three adoral organelles [START_REF] Ngassam | Description of the new genus Hysterocinetoides (Ciliophora, Hysterocinetidae) and revision of the systematics of the subclass Hysterocinetia[END_REF]. Such morphological variation as occurs in these species is confined essentially to the topography of the anteriorly located adhesion apparatus.

Since that earlier report, further examination of a great number of Glossoscolecidae has resulted in identification of two additional kinds of anterior adhesion apparatus that, to our knowledge, have hitherto remained undescribed. In this paper, we propose a revision of the morphological classification of these hysterocinetians, commensal in the digestive tract of Glossoscolecidae earthworms.

Material and methods

The host of hysterocinetian ciliates is the Glossoscolecidae oligochaete Alma nilotica found in the central region of Cameroon. Portions of this worm's digestive tract were opened either in physiological Ringer's solution or in commercial mineral water (Volvic™ in France or Supermont™ in Cameroon). Ciliates observed under a stereomicroscope to be actively swimming in the electrolyte were collected by micropipette and examined in the living state. After fixation, staining was carried out either by pyridinated ammoniacal silver carbonate method of [START_REF] Fernandez-Galiano | Une nouvelle méthode pour la mise en évidence de l'infraciliature des Ciliés[END_REF][START_REF] Fernandez-Galiano | The ammoniacal silver carbonate method as a general procedure in the study of protozoa from sewage (and other) waters[END_REF], or by silver proteinate according to Bodian's method modified by [START_REF] Dragesco | Compléments à la connaissance des Ciliés libres du Cameroun[END_REF], employed to control and complete our observations. Morphometric data were gathered by the examination of groups of 30 separate cells of each species. Drawings of these cells were made with the aid of a camera lucida attached to a Wild M20 microscope. P. bacteriophilus is commonly found, along with Metaptychostomum ebepdae [START_REF] Ngassam | Six espèces nouvelles d'Hysterocinetidae appartenant aux deux genres nouveaux Metaptychostomum et Proptychostomum, Ciliés endocommensaux d'un Oligochète terricole du Cameroun[END_REF], M. piriformus Ngassam and Grain, 1997, M. graini Ngassam and Grain, 1997and Proptychostomum commune Ngassam and Grain, 1997, in the mid-and hind-gut of Alma collected along the river Sanaga at Ebebda where they attain a frequency of 60% and an average population density of 43 ciliates per worm.

Results

MORPHOLOGICAL STUDIES

Ptychostomum bacteriophilus

Rather ovoid in shape, broad in the middle, with a rounded posterior and narrowing at the anterior where the sucker is situated, P. bacteriophilus is somewhat flattened laterally. This ciliate is 97-102 µm in length and 71-76 µm at its broadest part.

The cylindrical macronucleus (length 40 µm, width 14 µm), situated anteriorly, is aligned orthogonally to the anterior-posterior axis of the cell (Fig. 1, Plate 1). The rounded micronucleus (3-4 µm in diameter) is situated above the macronucleus with respect to which it occupies an anterior-dorsal position.

From 48 to 52 kineties are equally distributed over the two faces of the ciliate. On the lower face, the ends of some of these kineties define a rather discrete secant line, located dorsally above the infundibular part of the buccal cavity.

The components of the buccal apparatus of the hysterocinetian ciliates have been described from several species. These components form a paroral organelle consisted of two rows of kinetosomes of which only the external, at the furthest right of the buccal apparatus, bears cilia. Together they form an undulating membrane parallel to the posterior edge of the cell in the peristome region before descending into the infundibulum in a spiral manner. This paroral organelle, according to [START_REF] Puytorac | Sur quelques Ciliés Hysterocinetidae endoparasites des vers Oligochètes de vers Oligochètes au Gabon[END_REF], would correspond to the undulating membrane of Hymenostomes. On the left-hand side of the peristome, two longitudinal adoral organelles are found: Ad 1 , the more external, is formed by 2 parallel rows of ciliated kinetosomes confined to the peristome itself; Ad 2 , the more internal, similarly is composed of 2 ciliated rows that extend into the infundibulum in a spiral path that is named Ad 2 '. The spiral path is called Ad 2 ' because sometimes there is a slight disjunction between the peristomal and infundibular parts of this organelle (Figs 1, 3). A third organelle (Ad 3 ), absent from the peristome, extends within the infundibulum. It consists of a single row of ciliated kinetosomes accompanied by a row of argentophilic granules and intercalates between the paroral and Ad 2 '. Thus, the buccal infraciliature is composed of a paroral and 3 adoral organelles, and this justifies In the descriptions of ciliates that follow below, mention will not always be made of the structural organization of the buccal apparatus. The primary reason for this is that the pattern of buccal ciliature in the representatives of all genera of the family Hysterocinetidae stands in accordance with the description given above.

The left lateral face (also called the "lower face") of the ciliate bears a clearly defined anterior thigmotactic area or sucker, with its cord-like rim, which represents the zone of the cell responsible for securing adhesion to the wall of the host intestine. The ceiling of the sucker, almost at the surface in front, sinks down progressively towards the back, extending below the posterior edge of the opening for a distance of 5 to 8 µm. Thus, there is a major anterior part (25-31 µm in diameter) opening directly to the exterior, and a posterior part of the sucker that is invaginated beneath the somatic cortex. The central part is occupied by 5-8 short oblique kineties.

The wall of the sucker ceiling contains skeletal fibres that reinforce the adhesive apparatus. These fibres are disposed in 4 superimposed layers which proceed from the lower to the upper face of the cell as follows (Fig. 2, Plate 2):

-a layer of external fibres F1 is situated close to the lower face of the ciliate and is composed of a dozen curved skeletal fibres; it is lying at the lateral edges of the sucker and arranged orthogonally to the antero-posterior axis of the cell;

-a layer F2 is consisted of 6-8 fibres showing a brush-shaped arrangement; these fibres emanate from a common point at the edge of the right posterior of the cell and spread out in a fan-shape towards its anterior part;

-a most substantial layer F3 is composed of 8-12 fibres that expand anteriorly in a fan-shape from the lower left side of the cell and in crossing beneath the F2 bundle form with the latter an inverted V-shaped structure;

-a layer F4 includes 13-15 short fibres that go from the lower left edge of the cell in a fan-shape and terminate at the neighboring F3 layer with which they fuse in the centre to form an obvious thickened zone.

Like many other Hysterocinetidae ciliates found as endocommensals in the oligochaetes of Cameroon, P. bacteriophilus harbours many bacteria throughout its cytoplasm. However, unlike phagocytosed prokaryotes, these particular bacteria are not enclosed in host membranes and are in intimate contact with the ciliate cytoplasm.

The cytoskeleton is composed of several groups of fibres arranged in different planes and directions in a manner characteristic of the genus Ptychostomum. However, we have found one small departure from this standard pattern concerning the size of the groups F3 and F4 (Fig. 2) that consists respectively of 12 and 15 fibres rather than of 5 and 7 as in Ptychostomum elongatum [START_REF] Njiné | Morphogenèse de bipartition de deux espèces de Ciliés Hysterocinetidae du genre Ptychostomum Stein, 1890, endocommensaux d'Oligochètes Glossoscolecidae[END_REF]. This is presumably a random change in the transmission of epigenetic information, for example the result of a chance doubling of these fibres, which would be transmitted during successive cell divisions of the ciliate.

However, the superficial F1 bundle is in all respects similar to that of other Ptychostomum Paul Alain Nana, Zéphyrin Fokam, Guy Martial Ntoungwa Ebague et al. species, and layers F3 and F4, in spite of their greater size, do crossover deeper in the cytoplasm in the form of the typical inverted "V".

On balance, the above consideration of the morphology of the cytoskeletal fibre system reinforcing the adhesive apparatus of this ciliate does not support the creation of a new genus distinct from Ptychostomum. On the other hand, the ubiquitous presence of bacteria naked within its cytoplasm justifies the creation of a new species for it within the existing genus as P. bacteriophilus. Although not the most abundant, P. nilotica is one of the most commonly found ciliate in the midand hind-gut of Alma nilotica. We have collected the worms from different localities along the river Sanaga, and in all cases P. nilotica ciliates were found in 60-80% of worms studied.

Ptychostomoides nilotica

Ovoid and rounded at the poles, this ciliate is 74-82 µm long and 54-62 µm wide at the level of the macronucleus where it is at its broadest (Fig. 4, Plate 3).

The macronucleus is aligned with the anteroposterior axis and is curved back at the anterior pole of the cell where an outgrowth connects it to the thigmotactic zone. Cylindrical in form, the macronucleus is 29-32 µm long and 18-21 µm at its widest. At its antero-dorsal portion, it has a depression in which the ovoid micronucleus about 4 µm in diameter sits.

The somatic ciliature consists of 22-26 parallel, meridional kineties that are equally distributed on the 2 faces and bipolar in arrangement. On the lower face, the kineties terminate anteriorly at the edge of the rounded sucker.

The peristome region of the buccal apparatus measuring 48-52 µm long and 16-19 µm width is very well developed. Aligned obliquely with respect to the antero-posterior axis of the cell, it occupies the entire posterior pole hugging the cell contour (Figs 5,6).

A prominent feature of the ciliate is the cytoplasmic structure underlying the anterior adhesive apparatus. It is composed of a field of dense material occupying the entire sucker from which fine fibres radiate out.

According to the diagnostic features of the Hysterocinetidae ciliates defined by [START_REF] Puytorac | Sur quelques Ciliés Hysterocinetidae endoparasites des vers Oligochètes de vers Oligochètes au Gabon[END_REF], the nature of the anterior thigmotactic zone of this organism (reduced to a dense undivided fibrillar mass in composition but remaining undifferentiated into skeletal fibres) is most likely to be distinct at the generic level. For this reason, we create a new genus for it -Ptychostomoides and a new species, P. nilotica. Without a doubt P. gigas is the largest member of the genus Ptychostomoides found in the alimentary canal of Alma nilotica where it occurs at low frequency and in low numbers although being very widespread. Found in the mid-gut along with Ptychostomum macrostomum [START_REF] Njiné | Morphogenèse de bipartition de deux espèces de Ciliés Hysterocinetidae du genre Ptychostomum Stein, 1890, endocommensaux d'Oligochètes Glossoscolecidae[END_REF] and in the hindgut with Kozloffia de [START_REF] Puytorac | Sur quelques Ciliés Hysterocinetidae endoparasites des vers Oligochètes de vers Oligochètes au Gabon[END_REF], the number of individuals encountered varies between 10 and 18 per worm.

Ptychostomoides gigas

The cell is elongate, 135-146 µm long and 72-78 µm at its widest part, with the anterior being much narrower than the posterior and terminating in a sucker. The macronucleus, median and rounded, measuring 28-32 µm in diameter, lies along the antero-posterior axis of the cell. It is flanked dorsally by a micronucleus 2.5 µm in diameter (Plate 4). Paul Alain Nana, Zéphyrin Fokam, Guy Martial Ntoungwa Ebague et al.

Plate 3. Ammoniacal silver carbonate impregnated specimen of Ptychostomoides nilotica n. g. n., sp.; FDM -field of dense material, Mi -micronucleus, Mn -macronucleus; ×1400.

The entire cell is covered by 39-44 kineties that are unequally distributed over its two faces; on the lower face there are 18-20 kineties. These kineties have a spacing of 4.5 µm in the mid-region and 2.5 µm laterally. On the upper face they are distributed uniformly.

The buccal apparatus is reasonably developed with the peristome measuring 45-48 µm long and 18-20 µm wide. Situated obliquely to the anteroposterior axis of the cell, it occupies the entire posterior pole forming its contour. Similarly, the infundibulum is considerably developed enabling the cell to ingest bacteria; 36-41 µm long, it forms 2 turns of a spiral making an angle of 60° to the peristome and extending to the mid-third of the cell (Fig. 7).

The sucker, appearing like an adhesive button with a network of radially disposed fine skeletal fibres, is in all respects similar to that of the preceding species.

By its size and general appearance, the great development of the buccal apparatus, and the shape of the macronucleus this ciliate can be distinguished from the preceding species which it resembles only in the constitution of the buccal apparatus. It can be regarded as a new species that we name Ptychostomoides gigas. P. minus lives in the mid-and hind-gut of large specimens of Alma collected both at Ebebda and Batchenga at low frequency and population density.

Ptychostomoides minus

The ovoid cell is 56-62 µm long by 34-36 µm wide. The prominent macronucleus is narrower in its anterior half if compared with its posterior half which is much stouter. The macronucleus is situated along the antero-posterior axis of the cell, closer to the lower face of the cell. On its dorsal side, it is always flanked by an ovoid micronucleus 4 µm in diameter (Fig. 8, Plate 5).

There are 24-28 kineties equally distributed over both faces of the ciliate.

The buccal apparatus is relatively small; the peristome (18-21 µm long) leads into a very short (7-9 µm) infundibulum.

The thigmotactic zone, that forms a dark area in the lower anterior of the cell, has the same appearance as the two preceding species. However, this ciliate differs from those latter ones in its relatively small size and the shape of the macronucleus. Because of this we create a new species for it -Ptychostomoides minus. P. camerounensis is a small ciliate, elongate in form and circular in cross-section (Fig. 9); its mean length is 52 µm (50-55 µm) and width is 27 µm (25-30 µm). We have found it accompanied by Metaptychostomum graini, M. ebepdae, and M. piriformis in the mid-and hind-gut of large specimens of Alma, collected both at Batchenga and Ebebda, where it appears at low frequency and population density.

Proptychostomoides camerounensis

The median nuclear apparatus is always situated along the antero-posterior axis of the cell, closer to its Plate 4. Ammoniacal silver carbonate impregnated specimen of Ptychostomoides gigas n. g., n. sp.; BA -buccal apparatus, Mi -micronucleus, Mn -macronucleus; ×1400. Plate 5. Ammoniacal silver carbonate impregnated specimen of Ptychostomoides minus n. g. n. sp.; BA -buccal apparatus, FDM -field of dense material, Mi -micronucleus, Mn -macronucleus; ×1000. lower face. It consists of a cylindrical macronucleus, (17-20 µm long and 10-12 µm at its widest, situated posteriorly) and a large micronucleus (4.5 µm in diameter) always located on the antero-dorsal face of the macronucleus.

On average, there are 22 kineties that are distributed equally over the two faces of the ciliate.

The buccal apparatus is short, with a peristome region some 9-11 µm long and a similarly reduced infundibulum that makes an angle of 120° with the latter.

One of the striking features of the ciliate rests in the structure of the anterior adhesion apparatus. As in the preceding genus, this apparatus is composed of a fibrillar field forming a single dense mass; however, a major difference is that a discrete bare patch occurs in the centre of this field for which there is no equivalent in the preceding genus (Fig. 9, Plate 6). Emerging from this field are skeletal fibres which layout is modeled on the arrangement of the kineties of the cell lower face. Morphological and ultrastructual studies mentioned above allow us to set up a new genus -Proptychostomoides.

DIVERSITY WITHIN THE HYSTEROCINETIDAE

The establishment of the new genera Ptychostomoides and Proptychostomoides leads us to look a new at diversity within the Hysterocinetia. The buccal infraciliature being the most remarkably homogeneous feature of all those genera so far described, variation in morphology principally involves the structure of the anterior adhesive apparatus [START_REF] Ngassam | Description of the new genus Hysterocinetoides (Ciliophora, Hysterocinetidae) and revision of the systematics of the subclass Hysterocinetia[END_REF].

One could suppose the most primitive type of sucker to consist of a thigmotactic zone lacking a ciliature differentiated from the rest of the somatic ciliature and devoid of a cytoskeleton (Hysterocinetoides [START_REF] Ngassam | Description of the new genus Hysterocinetoides (Ciliophora, Hysterocinetidae) and revision of the systematics of the subclass Hysterocinetia[END_REF]Thurstonia Ngassam and Grain, 1998;Amietia Ngassam and Grain, 1998). From this starting point evolution could have led, on the one hand, to the isolation of parts of the anterior kineties and their self-organisation into an autonomous ciliated zone, and on the other hand, to the acquisition and development of fibres and/or skeletal material there into arrangements of increasing complexity.

Taking into account only species of ciliates commensal in Glossoscolecidae, we can imagine from a lineage consisting of Hysterocinetoides -Thurstonia -Amietia, which is divergent from the genus Kozloffia (a framework of thin fibres spread over the entire surface of the cup arranged for the most part antero-posteriorly). We assume the emergence of a branch based on the genus Preptychostomum [START_REF] Puytorac | Sur quelques Ciliés Hysterocinetidae endoparasites des vers Oligochètes de vers Oligochètes au Gabon[END_REF] (some segments of kineties devoid of an associated cytoskeleton in the thigmotactic depression) which itself diverges, on the one hand, into one lineage including Ptychotomoides (whose thigmotactic area consists of a dense fibrillar field), Metaptychostomum, and Ptychostomum (skeletal fibres in superimposed and antagonistic layers), and on the other hand, a separate lineage with Proptychostomoides (glabrous area with a dense fibrillar centre) and Proptychostomum Ngassam and Grain, 1997 (skeletal fibres in a radiating arrangement) (Fig. 10).

Discussion and conclusion

Ptychostomum bacteriophilus sp. n. displays the following features characteristic for the genus Ptychostomum: (1) an ovoid shape of the cell, (2) cytoskeletal architecture of the sucker built on a common model and composed always of 4 main layers of interlocking fibres, (3) short cilia-bearing strips in the central depression of the sucker divorced from the kineties wherein they were generated, (4) an ellipsoidal macronucleus aligned with its major axis orthogonal to that of the cell, and (5) the micronucleus situated anterior to the macronucleus. These are indeed the ptychostomian features. However, in its more impressive cytoskeleton (with 4, not 3 layers, of fibres superimposed and antagonistically arranged in a very diverse manner), by the anteriorly situated macronucleus with its major axis orthogonal to that of the cell, this ciliate bears no resemblance to any other Ptychostomum so far described.

The skeletal architecture of the adhesive apparatus is considered to be a fundamental character in the definition of Hysterocinetidae genera. From this viewpoint, the skeletal framework of the adhesive apparatus of the ciliates Ptychostomoides nilotica n. g., n. sp., Ptychostomoides gigas n. g. n. sp., and Ptychostomoides minus n. g., n. sp. composed of a dense field of fibrillar components, probably originating from the infraciliature. This type of sucker, with no equivalent in other genera, defines a new genus called Ptychostomoides.

Given that the skeletal fibres have a kinetodesmal origin, the genus Ptychostomoides would derive from Pretychostomum by the resolution of the short segments of kineties. These kineties are isolated in the central depression of the sucker into a fibrillar field from which those skeletal fibres differentiate that would organize themselves later into superimposed and antagonistic layers (Metaptychostomum, Ptychostomum). Also, from Proptychostomoides n. g. the edifice of skeletal fibers arranged radially from a central glabrous area (Proptychostomum) would derive.

  Nana, Fokam, Ntoungwa et al. n. sp. (Figs 1-3, Plates 1, 2).

Figs 1- 3 .

 3 Figs 1-3. Ptychostomum bacteriophilus n. sp. 1 -Left (lower) face showing the sucker (S), the somatic infraciliature and the buccal apparatus (BA); A -anterior part of the cell, D -dorsal side of the cell, V -ventral side of the cell, Mn -macronucleus, Mi -micronucleus. 2 -Detail of the sucker with its bundles of skeletal fibres (F 1 , F 2 , F 3 , F 4 ). 3 -Detail of the buccal infraciliature; AD 1 , AD 2 , AD 2 ', AD 3adoral organelles, IN -infundibulum, Pa -paroral, PE -peristome.

Plate 1 .

 1 Ammoniacal silver carbonate impregnated specimen of Ptychostomum bacteriophilus n. sp.: general view of the cell, left (lower) face showing the buccal apparatus (posterior part of the cell); Bact. -bacteria, Mi -micronucleus, Mnmacronucleus, S -sucker; ×1000.. Plate 2. Partial view of the anterior part of Ptychostomum bacteriophilus n. sp. showing the sucker (S); ×1400.

Figs 4- 6 .

 6 Figs 4-6. Ptychostomoides nilotica n. g., n. sp. 1 -Left (lower) face showing the sucker and the somatic infraciliature; A -anterior part of the cell, D -dorsal side of the cell, F -fibre, FDM -field of dense material, Mn -macronucleus, Mi -micronucleus, S -sucker, V -ventral side of the cell. 5 -Left (lower) face showing the buccal infraciliature apparatus (posterior part of the cell). 6 -detail of the buccal apparatus; IN -infundibulum, PE -peristome.

  Nana, Fokam, Ntoungwa et al. n. g., n. sp. (Fig. 7, Plate 4).

Fig. 7 .

 7 Fig. 7. Ptychostomoides gigas n. g., n. sp. Left (lower) face showing the buccal apparatus (posterior part of the cell); BA -buccal apparatus, Mn -macronucleus, Mi -micronucleus.

Fig. 8 .

 8 Fig.8. Ptychostomoides minus n. g., n. sp.; A -anterior part of the cell, BA -buccal apparatus, FDM -field of dense material, Mnmacronucleus, Mi -micronucleus.

Fig. 9 .

 9 Fig. 9. Proptychostomoides camerounensis n. g., n. sp.; A -anterior part of the cell, BA -buccal apparatus, FDM -field of dense material, Mnmacronucleus, Mi -micronucleus.

Fig. 10 .

 10 Fig. 10. Scheme of diversification in Hysterocinetidae.

Diagnoses of new genera and species

Ptychostomum bacteriophilus n. sp.

Commensal in the digestive tube of Alma nilotica; cell ovoid, with a broad mid-region nar-rowing anteriorly; size 97-102 × 71-76 µm ; 48-52 kineties equally spaced over the two faces; infundibulum in a spiral turn.

Type material. Photoholotype deposited in the 2011 year collections of the Unit of Protistology, Laboratory of General Biology, Faculty of Science, University of Yaoundé I, as well as in the Laboratory of Zoology, Department of Biology, Higher Teacher Training College, University of Bamenda, Cameroon.

Ptychostomoides n. g.

The anterior thigmotactic zone is reduced to a dense and undivided fibrous mass without differentiation of skeletal fibres.

Type species: P. nilotica n. sp.

Ptychostomoides nilotica n. sp.

Commensal in the digestive tube of Alma nilotica; ovoid in shape and rounded at the extremities; 74-82 × 54-62 µm; 22-26 bipolar kineties, distributed equally on the two faces; infundibulum in a spiral turn.

Type material. Photoholotype deposited in the 2011 year collections of the Unit of Protistology, Laboratory of General Biology, Faculty of Science, University of Yaoundé I, as well as in the Laboratory of Zoology, Department of Biology, Higher Teacher Training College, University of Bamenda, Cameroon.

Ptychostomoides gigas n. sp.

Commensal in the digestive tube of Alma nilotica; cell elongated, with the anterior part much narrower than the posterior; 135-146 × 72-78 µm; 39-44 kineties unequally distributed on the two faces; infundibulum in a spiral turn.

Type material. Photoholotype deposited in the 2011 year collections of the Unit of Protistology, Laboratory of General Biology, Faculty of Science, University of Yaoundé I, as well as in the Laboratory of Zoology, Department of Biology, Higher Teacher Training College, University of Bamenda, Cameroon.

Paul Alain Nana, Zéphyrin Fokam, Guy Martial Ntoungwa Ebague et al.

Ptychostomoides minus n. sp.

Commensal in the digestive tube of Alma nilotica; cell elongated, with the anterior part much narrower than the posterior; 56-62 × 34-36 µm; 24-28 kineties distributed equally on the two faces; infundibulum in a very short spiral turn.

Type material. Photoholotype deposited in the 2011 year collections of the Unit of Protistology, Laboratory of General Biology, Faculty of Science, University of Yaoundé I, as well as in the Laboratory of Zoology, Department of Biology, Higher Teacher Training College, University of Bamenda, Cameroon.

Proptychostomoides n. g.

Possesses a glabrous zone in the centre of a dense anterior fibrillar field.

Type species: P. camerounensis n. sp.

Proptychostomoides camerounensis n. sp.

Commensal in the digestive tube of Alma nilotica; elongated cell, circular in cross-section; 50-55 × 25-30 µm; on average 22 kineties, distributed equally on the two faces of the ciliate; infundibulum in a spiral turn.

Type material. Photoholotype deposited in the 2011 year collections of the Unit of Protistology, Laboratory of General Biology, Faculty of Science, University of Yaoundé I, as well as in the Laboratory of Zoology, Department of Biology, Higher Teacher Training College, University of Bamenda, Cameroon.


Dominique Quadri

Eric Soutif

Pierre Tolla

Exact solution method to solve large scale integer quadratic multidimensional knapsack problems

Keywords: Integer programming, separable quadratic function, linearization, surrogate relaxation, branch-and-bound

In this paper we develop a branch-and-bound algorithm for solving a particular integer quadratic multi-knapsack problem. The problem we study is defined as the maximization of a concave separable quadratic objective function over a convex set of linear constraints and bounded integer variables. Our exact solution method is based on the computation of an upper bound and also includes pre-procedure techniques in order to reduce the problem size before starting the branch-and-bound process. We lead a numerical comparison between our method and three other existing algorithms. The approach we propose outperforms other procedures for large-scaled instances (up to 2000 variables and constraints).

Introduction

We develop in this paper an exact solution method for solving a particular class of nonlinear knapsack problems. The integer quadratic multidimensional knapsack problem (QMKP ), which is known to be NP-hard [START_REF] Lueker | Two np-complete problems in nonnegative integer programming[END_REF] [START_REF] Lueker | Two np-complete problems in nonnegative integer programming[END_REF], involves the maximization of a concave quadratic and separable function over a convex set of linear constraints 1 A extended abstract of this paper appeared in LNCS 4362 pp. 456-464, 2007 † LAMSADE, Université Paris-Dauphine, 75775 Paris cedex 16, France.

{quadri, tolla}@lamsade.dauphine.fr ¶ CEDRIC, Conservatoire des Arts et Métiers, 292 rue Saint Martin, 75003 Paris, France. soutif @cnam.fr (called knapsack constraints) and bounded (pure) integer variables. It can be written as:

(QMKP )        max f (x) = n j=1 f j (x j ) = n j=1 c j x j -d j x 2 j s.t.
n j=1 a ij x j ≤ b i , i = 1, ..., m 0 ≤ x j ≤ u j , j = 1, ..., n x j ∈ N, j = 1, ..., n where the coefficients c j , d j , a ij , b i are nonnegative. The bounds u j of variables x j are integers such that u j ≤ ( c j 2d j ) because of the concavity of each f j , x * j ≤ ( c j 2d j ), where x * j is the optimal solution of the program max x j ≥0 f j (x j ). Problem (QMKP ) has wide applications, including financial models [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF] [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF], [START_REF] Faaland | An integer programming algorithm for portfolio selection[END_REF] [START_REF] Faaland | An integer programming algorithm for portfolio selection[END_REF] production and inventory management [START_REF] Bretthauer | The nonlinear knpasack problem -algorithms and applications[END_REF] [START_REF] Bretthauer | The nonlinear knpasack problem -algorithms and applications[END_REF]. However, most of the knapsack problems literature has addressed attention to specialized versions. For instance, there are large bodies of literature focusing on knapsack problems with linear objective function and a single constraint or m contraints (see [START_REF] Fayard | Reduction algorithms for single and multiple constraints 0-1 linear programming problems[END_REF] (Fayard and Plateau, 1974), [START_REF] Martello | Knapsack problems: algorithms and computer implementations[END_REF] [START_REF] Martello | Knapsack problems: algorithms and computer implementations[END_REF]), [START_REF] Fréville | The multidimensionnal 0-1 knapsack problems -bounds and computational aspects[END_REF] ( [START_REF] Fréville | The multidimensionnal 0-1 knapsack problems -bounds and computational aspects[END_REF], on knapsack problem with the quadratic objective function of (QMKP ) over a single linear constraint and 0-1 or pure integer variables (see [START_REF] Billionnet | An exact method based on lagrangian decomposition for the 0-1 quadratic knapsack problem[END_REF] ( [START_REF] Billionnet | An exact method based on lagrangian decomposition for the 0-1 quadratic knapsack problem[END_REF]), [START_REF] Pisinger | Solution of large quadratic knapsack problems through agressive reduction[END_REF] [START_REF] Pisinger | Solution of large quadratic knapsack problems through agressive reduction[END_REF], [START_REF] Bretthauer | The nonlinear knpasack problem -algorithms and applications[END_REF], [START_REF] Mathur | A branch and bound algorithm for a class of nonlinear knapsack problems[END_REF] [START_REF] Mathur | A branch and bound algorithm for a class of nonlinear knapsack problems[END_REF]). Nevertheless several applications require the use of pure integer variables and m capacity constraints, such as capital budgeting.

Even if many theoretical approaches have been proposed to solve integer quadratic problems (see for instance [START_REF] Cooper | A survey of methods for pure nonlinear integer programming[END_REF] [START_REF] Cooper | A survey of methods for pure nonlinear integer programming[END_REF], [START_REF] Körner | Integer quadratic progarmming[END_REF][START_REF] Körner | On the numerical realization of the exact penalty method for quadratic programming algorithms[END_REF] (Korner 1985 and 1990), only few of these methods have been implemented in practice so few experimental results can be found. There have been a limited number of papers studying (QMKP ). [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF] [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF] proposed a branch-and-bound algorithm specifically designed to solve (QMKP ), unfortunately the computational results were limited to instances up to 20 variables and constraints. However, the real-world applications require effective methods which are able to solve large scale instances of the problems. Since, (QMKP ) is NPhard, one should not expect to find a polynomial time algorithm for solving it exactly. Hence, we are usually interested in developing branch-and-bound algorithm. A key step in designing an effective exact solution method for such a maximization problem is to establish a tight upper bound on the optimal value. In a previous study [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF], we present an effective upper bound method based on a linearization and surrogate relaxation. We have compared analytically and computationally our upper bound to the bound suggested by [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF] [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF], the basic LP-relaxation of (QMKP ), and the LP-relaxation of the equivalent linearized formulation (MKP ). Simulation results, over a set of large instances (up to 2000 variables and constraints), showed that our upper bound is of good quality and closer to the optimum than the three other. Finally, the proposed upper bound can be computed in a very quick CPU time.

We propose in this present study, using our tight upper bound [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] to develop an exact solution method to solve (QMKP ). Our algorithm also incorporate preprocessing procedures in order to reduce the size of the initial problem before starting the branch-and-bound and a heuristic to find a good feasible solution given in [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] ( [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF]. We then compare the computational time of our method with three other existing methods which include the three upper bounds previously mentioned. Our computational testing, presented latter in this paper, over a set of large instances (up to 2000 variables and constraints) evidences the computational performance of our branchand-bound and its ability to solve real-sized instances.

The paper is organized as follows. The next section is dedicated to a description of the existing exact solution methods to (QMKP ). Section 3 summarizes the upper and lower bounds algorithms we proposed in a previous work and we use in the proposed branchand-bound to solve (QMKP ). Our branch-and-bound also incorporates pre-processing procedures which are details in Section 3. The computational results are reported in Section 4. We finally conclude in Section 5.

In the remainder of this paper, we adopt the following notations: letting (P ) be an integer or a 0-1 program, we will denote by (P ) the continuous relaxation problem of (P ). We let Z[P ] be the optimal value of the problem (P ) and Z[P ] the optimal value of (P ).

Existing exact solution methods

In this section we describe three existing exact solution methods to tackle (QMKP ). Each of them include an upper bound whose quality has been established in a previous work in [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF]. We will compare the computational performance of the exact solution method we proposed with these three other branch-and-bound algorithms in Section 4.

The Djerdjour, Mathur and Salkin exact solution method (DMS) [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF]. These authors develop a branch-and-bound algorithm based on the computation of an upper bound of better quality than the one provided by solving the LP-relaxation of (QMKP ). This upper bound is computed solving a polynomial problem derived from a linearization of the initial problem and a surrogate relaxation. The authors first use a direct expansion originally proposed by Glover [START_REF] Glover | Improved linear integer progamming formulations of nonlinear integer problems[END_REF] (Glover, 1975) of the integer variables and apply a piecewise linear interpolation to the initial objective function initially used by [START_REF] Mathur | A branch and bound algorithm for a class of nonlinear knapsack problems[END_REF] [START_REF] Mathur | A branch and bound algorithm for a class of nonlinear knapsack problems[END_REF]. [START_REF] Mathur | A branch and bound algorithm for a class of nonlinear knapsack problems[END_REF] ( [START_REF] Mathur | A branch and bound algorithm for a class of nonlinear knapsack problems[END_REF] an exact solution method for the single constraint integer quadratic knapsack problem. These authors transform the initial quadratic problem into a 0-1 linear equivalent formulation by applying a direct expansion on the integer variables and a linear interpolation on each quadratic function f j . They simply solve the equivalent problem using a solver so as to obtain the optimal value of the original problem. The 0-1 linearization branch-and-bound we suggest to test to solve to optimality (QMKP ) is a straightforward application of [START_REF] Mathur | A branch and bound algorithm for a class of nonlinear knapsack problems[END_REF] [START_REF] Mathur | A branch and bound algorithm for a class of nonlinear knapsack problems[END_REF] to the case of m capacity constraints. Following the approach of these authors we convert (QMKP ) to a 0-1 multidimensional knapsack problem (MKP ) which optimal value is equal to the one of (QMKP ) (the formulation of (MKP ) is given in Section 3.1). The corresponding branch-and-bound algorithm computes at each node of the search tree the LP-relaxation of (MKP ) which provides an upper bound of the optimal value of (MKP ). This approach has never been used to solve directly (QMKP ).

A zero-one linearization branch-and bound (LBB). Mathur and Salkin develop in

A standard branch-and-bound algorithm (SBB). Since the objective function of (QMKP ) is concave and the feasible set is convex the LP-relaxation of this problem can be found and thus provides an upper bound for (QMKP ). Consequently, a classical branch-andbound consists of computed this bound at each node of the search tree.

The proposed branch-and-bound algorithm

In this section we develop a branch-and-bound algorithm which key step is the computation of a tight upper bound [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF]. This upper bound method involves two improvements of the algorithm proposed by [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF] [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF] summarized in Section 2. We also develop a heuristic which provides a good feasible solution we use as a starting point of the process. Before starting the solution procedure we implement three pre-processing procedures to reduce the problem size. We implemented the proposed branch-and-bound algorithm using a best bound strategy which chooses the node with the best (the lowest) upper bound.

Upper bound computation

The proposed upper bound is computed by applying a linearization and a surrogate relaxation presented in [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF], which is derived from two improvements of the bound suggested by [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF] [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF]. The first one speeds up the computational time of the bound. The second improvement increase the quality of the bound. We now summarize the main steps of our method to get a tight upper bound for (QMKP ).

First an equivalent formulation of (QMKP ) is obtained by using a direct expansion of the integer variables x j and by applying a piecewise linear approximation to the ini-tial problem as employed in [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF] [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF]. Consequently, (QMKP ) is converted into a 0 -1 multidimensional knapsack problem (MKP ):

(MKP )    max n j=1 ( u j k=1 s jk y jk ) s.t. n j=1 (a ij u j k=1 y jk ) ≤ b i , i = 1, ..., m y jk ∈ {0, 1}
where

u j k=1 y jk = x j , s jk = f jk -f j,k-1 and f jk = c j k -d j k 2 .
The second step consists in getting the surrogate problem associated to the LP-relaxation of (MKP ) as also discussed in [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF] [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF]. The resultant problem (KP, w) can be written as

(KP, w)    max n j=1 ( u j k=1 s jk y jk ) s.t. n j=1 [ m i=1 w i a ij ] u j k=1 y jk ≤ m i=1 w i b i y jk ∈ {0, 1}
The LP-relaxation of (KP, w) provides an upper bound for (QMKP ) (a proof is given in [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF]). Nevertheless the quality of this bound depends on the surrogate vector employed to establish the surrogate problem.

The optimal surrogate multiplier, denoted by w * , corresponds to the optimal solution of the dual surrogate problem (SD) (see [START_REF] Glover | Surrogate constraint duality in mathematical programming[END_REF] (Glover, 1975)). The problem (SD) can be expressed as min w≥0 Z[KP, w]. Since the objective function of (SD) is quasi-convex [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF] [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF] solve (SD) via a local descent method which is shown in [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] ( [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] to be very time consuming. We then suggest, in [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] , an alternative way to compute w * which is assessed to be quicker than the local descent method, using the result that the optimal solution of dual of (MKP ) provides an optimal solution of (SD).

Experiment results assess the computational efficiency of this alternative way for computing w * (see [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] ).

The second improvement proceeds from an additional stage in which we solve (KP, w * ) in 0-1 variables rather than in continuous variables as it is done by [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF] in [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF]. Analytically the quality of the bound is increased. The experiments quantify the gap provides by this additional step.

Lower bound computation

In this section we sum up the main steps to get a feasible solution for (QMKP ). This lower bound is used in [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] to assess the quality of our upper bound.

In this present work it will be used as a good starting solution. The main idea of the proposed heuristic is the following. Since it is proved in [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] that the optimal value of (MKP ) is closer to the optimum of (QMKP ) than the optimal value of (QMKP ), we start from the optimal solution, y * , of (MKP ), to tackle a feasible solution for (QMKP ). Letting k y * jk = α j , for each variable x j of (QMKP ), we add to (QMKP ) the constraint ⌊α j ⌋ ≤ x j ≤ ⌊α j ⌋+1, where ⌊α j ⌋ denotes the greatest integer smaller or equal to α j . Thus, each variable becomes bivalent, and since the objective function is separable, it can straightforwardly be shown that the resulting problem is a 0-1 linear multidimensional knapsack problem. Obviously, solving this knapsack problem yields a feasible solution for (QMKP ) which is not necessarily optimal for (QMKP ).

Pre-processing techniques

Most commercial integer programming solvers propose a pre-processing phase which simplifies the problem being solved before starting a branch-and-bound procedure. This pre-processing phase consists of reducing the number of variables and constraints of the initial problem, using logical issues and variable fixation techniques. In this section we describe the pre-processing procedures we implemented in order to speed up the solution of (QMKP ) and discuss the utility of such procedures.

We use three pre-processing procedures: the first one detects and discards some redundant constraints, the second one reduces the bound of the integer variables (using [START_REF] Hammer | Constraints pairing in integer programming[END_REF] (Hammer et al., 1975) ), and the third and last one fixes some 0-1 variables to their optimal values.

Eliminating redundant constraints

We first discard constraints which are trivially implied by a strong one. Since (QMKP ) only includes knapsack constraints, this strong constraint is simply found by considering the constraint with the smallest right-hand-side, say b i 0 . Then we set α i = max 1≤j≤n

a ij a i 0 j . Suppose that a constraint i verifies α i ≤ b i b i 0 , we have: ∀j ∈ {1, . . . , n}, a ij a i 0 j ≤ α i ,
and since for all i and j a ij ≥ 0:

∀x verifying constraint i 0 , n j=1 a ij x j ≤ n j=1 α i a i 0 j x j ≤ α i n j=1 a i 0 j x j ≤ α i b i 0 ≤ b i Consequently, when a constraint i satisfies α i ≤ b i b i 0
, this constraint is immediately satisfied when constraint i 0 is verified. This criterion allows us to detect the constraints obviously dominated by constraint i 0 .

We could iterate this technique using not only the constraint included the smallest right-hand-side but also the one with the second smallest right-hand-side (and so on). However, this idea does not appear experimentally efficient. This simple technique, whose complexity is O(mn), allowed us to significantly reduce the number of constraints of all the considered instances. As discussed in Section 4. its efficiency strongly depends of the structure of the considered instance. Indeed, we randomly generate three kinds of instances: squared instances (n = m), rectangular instances (m = 5%n) and correlated instances. The reductions obtained are of good quality (between 52% and 56% of the constraints can be removed) concerning the squared and correlated instances.

Reducing the bounds of the integer variables

Since the objective function f of problem (QMKP ) is separable into n concave subfunctions f j , each integer variable x j is naturally bounded by c j 2d j . Consequently, the bound u j of variable x j is always chosen between 1 and max 1, c j 2d j when instances are randomly generated. However a high value of parameter u j may considerably increase the difficulty to solve the problem (for example the most difficult instances generated in Section 4 involve integer bounds up to 70). [START_REF] Hammer | Constraints pairing in integer programming[END_REF] propose in [START_REF] Hammer | Constraints pairing in integer programming[END_REF] a technique called constraint pairing to reduce the bounds of some integer variables verifying a set of linear inequalities. The idea of this method is to arbitrarily choose two inequalities from the set, say n j=1 a j x j ≤ a 0 and n j=1 b j x j ≤ b 0 , and to establish a third surrogate one obtained by multiplying the second constraint by a positive parameter t and by summing it with the first constraint. The surrogate constraint is: n j=1 (a j + tb j )x j ≤ (a 0 + tb 0 ). When t is judiciously chosen, the surrogate constraint may allow us to tighten the bounding interval of variable x j , [0, u j ], for instance by noting that variable x j may no more take the value 0 or u j without violating the surrogate constraint. The authors show it suffices to successively affect only n + 2 values to t in order to get as many conclusions as possible about the bounds of all the variables from the two constraints initially chosen. The complexity of the whole procedure is O(n 2 ) for each couple of pairing inequalities. This technique seems relatively useful if we consider the experimental results in Section 4. These experiments show for instance that the number of pure integer variables (those having u i > 1) decrease on average from 70% to 40% for the correlated instances and from 38% to 21% for the squared instances.

Fixing some 0-1 variables to their optimal value

When applying the last pre-processing technique, the number of 0-1 variables has probably increased. Thus, it is natural to try to fix some of the 0-1 variables to their optimal value in order to decrease the problem size. Let a 0-1 variable, say x i , we first need to guess its value in the optimal solution. We use the value of x i in the best known feasible solution and try to prove that x i cannot have a different value in any optimal solution. Considering a set I of variables indices that all are supposed to be equal to 0 in an optimal solution, we add the following constraint to the problem:

i∈I x i ≥ 1
then we compute an upper bound UB of the modified problem using the method presented in [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF]. If the computed upper bound is strictly lower than the value of the best known feasible solution then we can conclude that all the variables indexed in I can definitively be fixed to 0. A similar constraint can be added for fixing variables to 1 instead of 0 as explained in [START_REF] Billionnet | An exact method based on lagrangian decomposition for the 0-1 quadratic knapsack problem[END_REF] [START_REF] Billionnet | An exact method based on lagrangian decomposition for the 0-1 quadratic knapsack problem[END_REF].

The size of the set I is an important parameter for the success of such a fixation method. Choosing |I| = 1 comes down to fix variables one by one, and choosing |I| too large generally fails since no fixation can be done (the quality of the upper bound does not allow us to simultaneously fix all the variables indexed in I when I is too large). Experiments show that for (QMKP ) and the bound used to solve it, a good compromise consists in choosing |I| = 2.

This procedure allows us to fix on average 51% of the 0 -1 variables. However it appears much more time-consuming than the two previous ones. It can sometimes constitute more than 10% of the whole CPU-time necessary to find the exact solution using the branch-and-bound procedure.

Computational results

The computational performance of the four branch-and-bound procedures was tested through a set of 100 randomly generated squared problems (i.e. n = m) and correlated problems (i.e. c j = m i=1 a ij and d j = c min /2, where c min is the minimum of all c j values). The correlated problems are well-known to be more difficult to solve in practice for 0 -1 linear multidimensional knapsack problem (MKP ), which is a special case of (QMKP ), than squared instances. The number of variables take their values in the set {100, 500, 1000, 1500, 2000}, with 10 replications per n-value. As in [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF] ( [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF] integer coefficients a ij , c j , d j were uniformly drawn at random The percentage of pure integer variables (with u j > 1) rises 38.6% on average for squared instances rather than it is equal to 70% on average for correlated problems. The average value of the bound u j for the pure integer variables reaches 21.2 with a standard deviation 2.24 over 50 instances for squared problems and rises 54.1 on average with a standard deviation 6 over 50 for correlated problems.

Our branch-and-bound as well as DMS were coded in C language whereas the optimal solution provided by SBB and LBB were got using a commercial solver ILOG-Cplex9.0. Simulations were run on a bi-xeon 3.4 Ghz with 4Go of main memory.

General comments on the comparison of the computational time of the four methods

Table 1 displays, for the four exact solution methods mentioned in this paper, the average computational time in CPU seconds over 10 replications for each problem type and size. We limited to 10800 seconds (3 hours) the solution time.

The results in Table 1 indicate clearly the poor performance of DMS which was not able to reach the optimum in the chosen limit time for all problems types with 500 variables and more. It is proved in [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] (Quadri et al.) that is due to the fact that DMS employs a very time consuming local descent search method to obtain the optimal surrogate multiplier w * (see Sections 2 and 3).

Squared instances. Our branch-and-bound clearly outperforms the three other procedures. For large scaled instances (n ≥ 1000) our exact solution method is approximately 4 times quicker than the second best approach LBB and it is almost 7 times faster than SBB. This conforts the ability of our method to solve large sized problems in a very competitive time with an average of 5 ′′ 05 minutes (305 seconds) for the 2000-variables instances.

Correlated instances. As expected the correlated problems are difficult to be solved by the four exact methods. The size of the instances only up to 1000 variables and constraints. Nevertheless, concerning 500-variable problems LBB is the most appropriate algorithm taking 10 ′′ 00 minutes on average to find the optimum. Our branch-and-bound still solves the same instances in a competitive CPU time (2 times slower than LBB).

Analysis of the experiments results

The improvement capability of our branch-and-bound can be explained by three features, namely: (i) the feasible solution, (ii) the upper bound and (iii) the pre-processing procedures.

Our feasible solution (see [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF]. Actually, providing to our branch-and-bound algorithm another feasible solution (of poorer quality) did not significantly debase its solution time. Consequently, the good quality of the initial feasible solution does not clearly explain the performance of our exact solution method.

Our upper bound and pre-processing procedures: squared instances. The impact of both the upper bound we proposed in [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] and the pre-procedures used clearly appear. Indeed, our upper bound is always closer to the optimum than the three other utilized in DMS, LBB and SBB. Moreover, this bound takes about 10 seconds on average to be computed. On the other hand, our method includes part of the procedure of [START_REF] Hammer | Constraints pairing in integer programming[END_REF] [START_REF] Hammer | Constraints pairing in integer programming[END_REF] to reduce the bounds u j of the pure variables. This actually leads to convert many pure integer variables into 0-1 variables. The average proportion of pure integer variables decreases from 38% to 21.02%. The fixation technique eliminates 50.25% of variables which value is fixed to 1. Finally, the search of redundant constraints allows to keep 48% of the initial constraints. Consequently, both the upper bound method and the pre-procedure techniques are very effective for squared instances.

Our upper bound and pre-processing procedures: correlated instances. The upper bound is of poor quality in comparison with the result obtain for the squared problems.

Nevertheless, the relative gap is on average 20% and the bound is computed in 1 ′′ 30 on average (see [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF] [START_REF] Quadri | Upper bounds for large scale integer quadratic multidimensional knapsack problems[END_REF]). On the other hand, the pre-procedure techniques are quite well effective. Indeed, 56.6% of constraints can be removed on average, 27% of variables are fixed to their bound. Before starting the pre-procedure process, only 30% of variables are binaries. The impact clearly appears: 60% of variables are 0 -1 after applying the techniques. In spite of the fact that these results are of good quality, our branch-and-bound does not solve 1000-variable problems faster than LBB.

Conclusion

We develop in this paper a branch-and-bound algorithm to solve the integer quadratic multidimensional knapsack problem. The upper bound and the pre-procedure techniques that we incorporate allow us to solve large-sized squared instances, up to 2000 variables and constraints. The classical branch-and-bound, which is usually used to solve such convex problems is of poor quality as well as the method proposed by [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF] [START_REF] Djerdjour | A surrogate-based algorithm for the general quadratic multidimensional knapsack[END_REF]. Moreover, the method suggested by [START_REF] Mathur | A branch and bound algorithm for a class of nonlinear knapsack problems[END_REF] [START_REF] Mathur | A branch and bound algorithm for a class of nonlinear knapsack problems[END_REF] we extended to the case of (QMKP ), which has never been utilized to solve (QMKP ) directly, outperforms the three other branch-and-bound concerning the correlated problems.

Table 1 :

 1 Average computational time of the four methods for each problem type Coefficients b i and u j are integers uniformly distributed such that 50 ≤ b i < n j=1 a ij u j and 1 ≤ u j ≤ ⌈ c j 2d j ⌉, where ⌈x⌉ denotes the smallest integer greater than or equal to x.

	n	m	SBB	LBB DMS Our BB
	Squared
	100	100	1.31	0.63	2.13	1.5
	500	500 120.12	16.1	-	11.5
	1000	1000 346.56 283.3	-	50.5
	1500	1500 1178.4 392.5	-	183.7
	2000	2000 2557.9 1369.4	-	305.2
	Correlated
	100	100	0.7	0.1	3.35	0.4
	500	500	955.7	129.4	-	410.4
	1000	1000 1480.24 650.13	-	1280.2
	1500	1500	-	-	-	-
	2000	2000	-	-	-	-
	in the range {1..100}.

Cahiers du LAMSADE