Paul Byrne
email: paul.byrne@univ-rennes1.fr

Nandy Putra

Thierry Maré

Nasruddin Abdallah

Pascal Lalanne

Idrus Alhamid

Patrice Estelle

Ardiyansyah Yatim

Anne-Lise Tiffonnet

Design of a solar AC system including a PCM storage for sustainable resorts in tropical region

Keywords: air conditioning, hotel, net-zero energy, PCM

Environmental concerns worldwide (climate change, global warming, etc.) are pushing to reduce the consumption of fossil fuels. The building sector is responsible for a third of greenhouse gas emissions (40% in France). In tropical countries, the main share of energy consumption in buildings is due to air conditioning systems. Indeed, in a resort of high standing, 60% of energy consumption is due to air conditioning. In the Indonesian context, which welcomes growing real estate projects on more or less isolated islands, it becomes important to put in place passive or autonomous buildings and the corresponding energy solutions. The energy efficiency of buildings is based on two pillars: an efficient building's design and on the effectiveness of the air conditioning system to achieve energy independency in a tropical environment. Considering the decreasing cost of PV cells, the solution to reduce the energy consumption of air conditioning proposed in this article covers a vapour-compression refrigeration system electrically powered by solar cells. To avoid the use of electric batteries, not sustainable in terms of carbon footprint (construction and recycling of batteries) and to overcome the problem of intermittency of solar energy, the choice fell on a variable speed compressor and a storage in a mixture of fatty acids (derived from coconut oil) as phase change material embedded in expanded graphite. The work also focuses on the energy performance of the storage system. This study describes the context and the air conditioning system chosen as a solution for a sustainable resort application in a tropical region. The design and characterization of the coupled PCM and compressed expanded graphite in a latent heat thermal energy storage is also detailed. It uses a TRNSYS simulation for the assessment of the cooling demand. Calculations for a prototype of 25 m 2 apartment showed that with a chiller of 8000 W and a surface of 14 m 2 of photovoltaic panels, it is possible to cool a hotel bedroom with solar energy. The consortium members work jointly at designing and optimizing the system: Indonesian members are focused on the PCM storage and French members are more dedicated to the hygrothermal behaviour of the hotel bedrooms.

Introduction

Environmental concerns worldwide (climate change, global warming, etc.), are pushing to reduce the consumption of fossil energy. The building sector is responsible for a third of greenhouse gas emissions (40% in France). In tropical countries, the impact of energy consumption in buildings is mainly due to the air conditioning systems. Indeed, in a resort of high standing, 60% of energy consumption is due to air conditioning.

In the Indonesian context, showing many new resort projects, especially in islands, it becomes important to investigate passive or autonomous buildings and efficient energy solutions. Energy efficiency of buildings is based on two pillars, an adapted design of the building to reduce expenses and save energy (insulation, materials, orientation, inertia, solar protection, natural ventilation, etc.) [START_REF] Sadineni | Passive building energy savings: A review of building envelope components[END_REF] , and on the efficiency of the air conditioning system (if possible renewable energy source, energy recovery, management and regulatory strategy) 2)3)4)5) .

To reach energy independency with an air conditioning system, some solutions are solar cooling, either absorption or adsorption [START_REF] Al-Alili | Review of solar thermal air conditioning technologies[END_REF] , or a standard system powered by a photovoltaic field 7)8)9) . Because of the intermittency and variability of the solar incident radiation during the day most of the studies use electric batteries as an energy storage. Many studies use the temperature difference between day and night by coupling of the air conditioning system with a cold latent heat storage. With a storage during the day and a use overnight 10)11) the system shows energy savings of 9%.

The adaptation of an autonomous air conditioning system for the case of a tropical climate with a small difference between day and night temperatures does not seem to be addressed. Considering the decreasing cost of PV cells, the solution proposed in this article covers a compression refrigeration system electrically powered by solar cells. To avoid the addition of electric batteries, not sustainable in terms of environmental footprint (construction and recycling of batteries) and to overcome the problem of intermittency of solar energy, the choice fell on a variable speed compressor and a storage by phase change materials.

The results present on an annual basis and during a week, internal temperatures, humidity and energy demands. Characteristics of the materials, windows, ventilation, infiltration, internal contributions, occupation scenario are taken into account in the dynamic simulation of the behavior of the building based on meteorological data. The study is conducted with TRNSYS software 12) . Results without energy storage are presented and conception and the optimisation of the PCM storage solution is discussed.

System sizing

Assumptions

This study is based on a project of construction of standard hotel on the island of Lombok in Indonesia. The hotel is a troglodytic construction of 51 luxury apartments of 180 m 2 and a common area for reception and restaurants. The climate of this region is tropical humid. The seasonal variation of the temperature being imperceptible, the ground temperature will be assumed constant and equal to the average annual temperature of the outside air, which is 27.32 °C.

All apartments have similar characteristics and the assumptions taken into account are the following:

 front length of 12 m,  depth of 15 m,  180 m 2 of floor area,  ceiling height of 2.7 m,  façade is fully glazed; glazing of a 23.5 m 2 . Due to the thickness of the walls, transfers between apartments or from apartments towards the outside by the opaque walls are supposed to be equivalent to heat transfer towards the ground in a semi-infinite medium. The simulation of the outdoor side of the wall boundary condition is a constant equal to the ground temperature after the layer. Vertical walls, the floor and ceiling are made of the same materials (table 1): inner insulation of glass wool type, concrete and a layer of ground. The energy conservation equation is applied to every layer of material and indoor air.

(1)

With m, the material mass, Cp, the specific heat, dT/dt the temperature variation with time and , the thermal capacity that can be a cooling capacity, a solar radiation, external gains through walls or internal gains due to electric appliances, lighting and occupancy.

To simplify the model, reception and restaurant zones are not taken into account in the study and only one apartment is modelled. Modeled glazing are of double glazing lowemissivity argon-filled with a heat transfer coefficient U w of 1.43 W.m -2 .K -1 and a solar g-factor 0.596. Glazing with carpentry wood without opening are chosen. To avoid disrupting of the air conditioning effect two solid wood doors will allow the passage of the occupants.

Following the rules of calculation NF 52-612/CN, the air renewal through the ventilation rate is 0.617 vol/h. This corresponds to a flow of around 300 m 3 /h per apartment. The choice is based on ventilation through air intakes, limiting the renewal during inoccupation of the building.

Air infiltration is neglected in the case of troglodytic dwellings. Internal gains in the apartments are modeled by the thermal powers produced by occupants, lighting and electric equipment (refrigerator, TV...) associated with a scenario of occupation. The powers and scenarios are listed in table 2.

Results

Developments outside temperature, relative humidity and the global sunshine taken into account in our study are extracted from the Trnsys documentation and presented on the following figures (Figure 1).

In the light of these results, for one apartment, annual cooling demand would be 22135 kWh considering an average power of 2526 W and a maximum instantaneous power of 6737 W. The operation on the first week of simulation is presented in Figure 2 for all apartments. This simulation considers centralized cooling system powered directly by photovoltaic solar panels. The refrigerating machine has a variable speed compressor with a coefficient of performance COP equal to 3. The frequency of rotation varies depending on the intensity of the current produced by the solar panels, depending on the solar radiation absorbed by the photovoltaic field.

The rest of the annual simulation observes a similar behavior. The evolution of the outside temperature is described by the blue curve. The temperature varies between 23 and 33 °C. Cold needs depend on this temperature, internal contributions (dark grey curve) and solar (brown curve). Solar gains are slightly delayed from the cooling power (yellow line) because the orientation of the glazing towards the East. The cooling system lowers the indoor temperature (orange curve) in the rooms when the solar radiation hits the photovoltaic panels. When there is more radiation, the temperature increases because of internal contributions due to the arrival of the occupants and a higher outdoor temperature at the end of day.

The evolution of the interior temperature can be compared to the one that would be obtained without cooling system (grey curve). The inside temperature obtained with this AC system directly powered by solar panels can reduce the indoor temperature without reaching the desired point of 24 °C during occupation. Temperatures fluctuate between 27 and 28 °C. The solution that consists to use electrical batteries is considered as expensive and having a strong environmental impact. The less expensive solution left is to use a storage tank a PCM (phase change material). The operation principle is shown in figure 3. The cold production is driven by the solar resource as long as the temperature in the building is above 24 °C. During the morning and early in the afternoon, direct cooling is carried out. When the temperature set point is reached and solar radiation is sufficient, the surplus of energy is used to produce and store cooling energy in the PCM. During the first hours of the night, the PCM storage is discharging. During the end of the night, the cooling energy is expected to be brought freely by over-ventilation with fresh air. The building thermal inertia should also participate to limit the indoor temperature increase due to internal gains. Figure 3 shows the general operational scheme. The simultaneous case of direct air conditioning and cold storage in the tank is possible. The circulating pumps will be supplied with PV electricity. The water of the swimming pool is used as a heat sink for the cooling system. The condenser is thus a plate heat exchanger. The water temperature is assumed constant and equal to 30 °C.

FIGURE 3. Operation principle

PCM characteristics

Different techniques are used, either by microencapsulation in a water circuit or by macroencapsulation in a storage tank 13)14)15) . The phase change materials used can be classified into three categories: organic (paraffins or not), inorganic (salt hydrates), eutectic mixtures (organic or inorganic).

The selection criteria of these materials are the melting temperature, the latent heat, the cost, the density (amount of storage), the vapour pressure (as low as possible), the dangerousness, the reliability of containment materials, supercooling stability (as low as possible) [START_REF] Rathod | Thermal stability of phase change materials used in latent heat energy storage systems: A review[END_REF] . Most of the eutectic have a melting point between 20 and 60°C and a latent heat between 125 and 200 kJ/kg. The majority of organic PCMs are of paraffins and fatty acids. Paraffins show good thermal and chemical stabilities 17)18)19) [START_REF] Al-Abidin | Review of thermal energy storage for air conditioning systems[END_REF] .

The selected PCM for our study is a eutectic mixture of 73 % of capric acid (decanoic) and 27 % of lauric acid (dodecanedioic) in molar compositions. It has a melting temperature around 18 °C21) . The composition of the eutectic mixture has been questioned and approved by Longfei and al. [START_REF] Longfei | Phase diagram of the ternary system lauric acid-capric acid-naphthalene[END_REF] . The main reason for this choice of PCM is that these fatty acids come from coconut oil. This is commercial and environmentally friendly. The problem is that the solidification temperature is low and presents a big hysteresis. To reduce the temperature of solidification, the impact of a surfactant was tested [START_REF] Fauzi | Sodium laurate enhancements the thermal properties and thermal conductivity of eutectic fatty acid as phase change material (PCM)[END_REF] .

Experimental set-up

A volume of 300 ml of coconut oil with a temperature of fusion of 18 °C was placed in a refrigerator at temperature of -10 °C. The environment temperature was 28 °C. A type K thermocouple with an accuracy of 0.1 °C was placed in the centre and an acquisition was used to record the temperature evolution. To improve the mixing of the surfactant and the coconut oil, some water was added to the mixture. This addition reduces the mass of phase change material. To decrease the melting temperature, additions of 5% and 10% percentage of surfactant (sodium laurate) were tested. Figure 4a and4b show the temperature evolutions during cooling-down and heating-up processes. As expected from the literature review, sodium laurate reduces the solidification temperature by 4 K for the supposed well-mixed solution. After coming back to initial temperature, the 5 % sample abnormally shows two phases, one white and the other transparent. The 10 % mixture seems almost homogeneous. Therefore, our final PCM choice is a mixture of capric acid (decanoic) 73 %, lauric acid (dodecanedioic) 27 % in molar compositions and 10% of sodium laurate in mass. The final mass composition is capric acid 63 %, lauric acid 27 % and sodium laurate 10 %. It has a melting temperature around 18 °C. Its latent heat is 140 kJ/kg.

Calculation of energy savings

These calculations are based on a bedroom prototype built in Bali Indonesia. Figure 5 shows photographs of the project site. Figure 6 The heat losses through the walls are calculated following French thermal regulation:

(2)

With flux in W, A area in m 2 , Ti inside temperature considered at 23 °C and 28.5 °C for the ground.

outside temperature is sinusoidal with amplitude from 22 °C to 32 °C and maximum considered at 6 pm.

The wall heat loss coefficient in W.m -2 .K -1 is:

(2) with , the thermal conductivity in W.m -1 .K -1

(3) with w, the width of the wall in m and (4) with p perimeter in m. and a latent heat of 140 kJ/kg. However, the thermal conductivity being quite low, a heat transfer media will have to be used to enhance the effective thermal conductivity of the latent heat storage system 24)25) . Calculations for a prototype of 25 m 2 apartment showed that with a chiller of 8000 W (corresponding to a running time of 80%) and a surface of 14 m 2 of photovoltaic panels, it is possible to cool a hotel bedroom with solar energy. The future works will focus on the choice of a heat exchanger for the PCM tank and on the in-situ experimental tests. The authors would like to acknowledge the PHC Nusantara program from the French Embassy in Indonesia who is participating financially to this joint research between France and Indonesia.

FIGURE 1 :

 1 FIGURE 1: Evolutions of internal temperature and thermal power inlet during one year for one apartment

FIGURE 2 :

 2 FIGURE 2: Temperature and power evolutions over a week 3. System design 3.1. Operating scenario

FIGURE 4 :

 4 FIGURE 4: Temperature evolutions during (a) coolingdown and (b) heating-up processes.

  presents the layout diagram of the apartment and the energy flows. The bed is in limestone and the bathroom is placed behind the bed. The features of this case study include a vertical wall of 31.25 m 2 , a floor of 25 m 2 , a ceiling of 25 m 2 , a glazing of 4.6 m 2 , a wall supporting the window of 5,4 m 2 . The troglodytic room is considered without insulation with a conductivity of 1.7 W/mK. The ratio of fresh air renewal is 15 m 3 /h during day and night, 2 occupants produce 240 W, electric devices produce continuously 300 W and LED lights produce 1.5 W/m 2 . The glass being East-facing surface, a calculation of solar gain is represented in figure 7 between 6 am to 12 am.

FIGURE 5 :

 5 FIGURE 5: Photographs of the project site

FIGURE 6 :

 6 FIGURE 6: Layout diagram of the apartment prototype and energy flows

FIGURE 7 :

 7 FIGURE 7: Simulation results for heat gains in the troglodytic prototypeContributions of day and night heat gains represent 34 kWh. The night free cooling input brings 12 kWh of cooling energy, whereas the mass of PCM chosen corresponds to 311 kg. Considering a horizontal photovoltaique sensor (or tilted at 20%), from 150 W peak /m 2 . A surface of 14 m 2 enables to satisfy a maximum cooling demand of 6300 W. A system of cooling power of 8000 W is chosen allowing to have a maximum hourly rate of operation of 80%. The cooling output and the stored energy evolution is shown in figure8.

FIGURE 8 :

 8 FIGURE 8: Cooling energy production and storage

TABLE 1 :

 1 Material data

	Width	Density
	(cm)	(kg.

m -3 ) Conductivity (W.m -1 .K -1 ) Heat capacity (J.kg -1 .K -1 )

	Ground	30	1750	1.75	1800
	Insulation	5	20	0.035	1000
	Concrete	20	2300	1.75	1000

TABLE 2 :

 2 Internal power by apartment.

	Type of power	Power (W)	Scenarios
	Occupants	2 persons 150 W =	From 6pm to 9am
		300 W
	Lighting	5 W/m 2	From 6pm to 11pm and
		e.g. 900 W	7am to 9am
	Equipment	300 W	Constant or from 6 pm
			to 9am occupants
	.

Acknowledgements

The authors would like to acknowledge the PHC Nusantara program from the French Embassy in Indonesia who is participating financially to this joint research between France and Indonesia. The participation of A. Yatim and I. Alhamid in the research is funded by the United States Agency for International Development (USAID) through Scientific Modeling programs, Applications, Research, and Training for City-Centered Innovation and Technology (SMART CITY) -Universitas Indonesia contract no. 0118/UN.2R3.SC/PPM.00/ 2018.


Agostinho Agra
email: aagra@ua.pt

Rosa Figueiredo
email: rosa.figueiredo@univ-avignon.fr

Carlile Lavor
email: clavor@ime.unicamp.br

Nelson Maculan
email: maculan@cos.ufrj.br

António Pereira
email: antoniop@ua.pt

Cristina Requejo
email: crequejo@ua.pt

Feasibility check for the distance geometry problem: an application to molecular conformations

Keywords: Distance Geometry Problem, Graph Embedding, Integer Programming, Constraint Programming

The Distance Geometry Problem (DGP) consists in finding an embedding in a metric space of a given weighted undirected graph such that for each edge in the graph, the corresponding distance in the embedding belongs to a given distance interval. We discuss the relationship between the existence of a graph embedding in a Euclidean space and the existence of a graph embedding in a lattice.

Different approaches, including two integer programming models (IP) and a constraint programming (CP) approach are presented to test feasibility of the DGP. The two IP models are improved with the inclusion of valid inequalities and the CP approach is improved with the use of an algorithm to perform a domain reduction.

The main motivation to this work is to derive new pruning devices within branch and prune algorithms for instances occurring in real applications related to determination of molecular conformations, which is a particular case of the DGP. A computational study based on a set of small sized instances from molecular conformations is reported. This study compares the running times of the different approaches to check feasibility.

Introduction

The Distance Geometry Problem arises is many practical applications. One of the best known ones is the protein structure calculation, which is a major problem in computational biology [START_REF] Donald | Algorithms in Structural Molecular Biology[END_REF]. The Molecular Distance Geometry Problem (MDGP) arises in nuclear magnetic resonance (NMR) spectroscopy analysis, which provides a set of inter-atomic distances for certain pairs of atoms of a given protein [START_REF] Wütrich | Protein structure determination in solution by nuclear magnetic resonance spectroscopy[END_REF]. The question is how to use this set of distances in order to calculate the spatial positions of the atoms forming the molecule [START_REF] Crippen | Distance Geometry and Molecular Conformation[END_REF]. A very recent review about distance geometry problems and applications is given in [START_REF] Liberti | Euclidean distance geometry and applications[END_REF].

A simple weighted undirected graph G = (V, E, d) can be associated to the MDGP, where V represents the set of atoms, E models the set of atom pairs for which a Euclidean distance is available, and the function d : E → R + assigns distance values to each atom pair. The MDGP can then be formally defined as the following: given a weighted simple undirected graph G = (V, E, d), find a function x : V → R 3 such that

||x u -x v || = d uv ∀{u, v} ∈ E. (1.1)
When G is a complete graph (all the distances are given), a unique three-dimensional structure can be determined by a linear time algorithm [START_REF] Dong | A linear-time algorithm for solving the molecular distance geometry problem with exact inter-atomic distances[END_REF]. Otherwise, MDGP is NP-hard [START_REF] Saxe | Embeddability of weighted graphs in k-space is strongly NP-hard[END_REF].

The MDGP can be naturally formulated as a nonlinear global minimization problem, where the objective function is given by

f (x 1 , . . . , x n ) = {u,v}∈E (||x u -x v || 2 -d 2 uv ) 2 .
Assuming that all the distances are correctly given, x 1 , . . . , x n ∈ R 3 solve the problem if and only if f (x 1 , . . . , x n ) = 0. For MDGP instances provided by NMR experiments, G is not complete and there may exist errors in the given distances. Therefore, a more practical definition of the MDGP (denoted as iMDGP in the next sections) is to replace conditions (1.1) by

d L uv ≤ ||x u -x v || ≤ d U uv ∀{u, v} ∈ E, (1.2)
where d L uv and d U uv are, respectively, lower and upper bounds on the distance between atom u and atom v.

Several algorithms have been proposed for the solution of the MDGP, most of them based on a search in a continuous space [START_REF] Liberti | Molecular distance geometry methods: from continuous to discrete[END_REF]. By exploring some rigidity properties of the graph G, the search space can be discretized and an efficient algorithm called Branch and Prune (B&P ) can be used, particularly when the given distances are precise [START_REF] Lavor | The discretizable molecular distance geometry problem[END_REF].

The main idea behind the discretization is that the intersection among three spheres in the three-dimensional space can produce at most two points in the hypothesis their centers are not aligned. Consider four atoms u 1 , u 2 , u 3 , and v. If the coordinates for u 1 , u 2 , u 3 are known, as well as the distances d u 1 v , d u 2 v , d u 3 v , then three spheres centered at u i with radius d u i ,v , i = 1, 2, 3 can be defined and their intersection provides at most two possible positions for the atom v. The definition of an ordering on the atoms of the protein satisfying such conditions suggests a recursive search on a binary tree containing the potential coordinates for the atoms of the molecule [START_REF] Lavor | The interval branch-and-prune algorithm for the discretizable molecular distance geometry problem with inexact distances[END_REF]. The binary tree of possible solutions is explored starting from its top, where the first three atoms are positioned, and by placing one node per time. At each step, at most two possible positions for the current node v are computed, and two new branches are added to the tree. As a consequence, the size of the binary tree can get very large quite quickly, but the presence of additional distances provided by NMR can help in verifying the feasibility of the computed positions. As soon as a position is found to be infeasible, the corresponding branch can be pruned and the search can be backtracked. When all the distances are exact, each node of the tree refers to one atomic position. However, when one of such distances is represented by an interval, a curve in the three-dimensional space is associated to the corresponding node in the tree [START_REF] Lavor | The interval branch-and-prune algorithm for the discretizable molecular distance geometry problem with inexact distances[END_REF]. In this case, it is possible to choose some distances from the available interval that are associated to atomic positions on the curves. While this strategy was proved to work well for relatively small-sized instances [START_REF] Lavor | The interval branch-and-prune algorithm for the discretizable molecular distance geometry problem with inexact distances[END_REF], it does not have the same efficiency as the strategy applied to the case with exact distances [START_REF] Lavor | The discretizable molecular distance geometry problem[END_REF].

In this paper we consider a lattice representation of the molecule. This lattice is a discretization of R 3 . Lattice models have been used in the past for related protein problems, see [START_REF] Yoon | Optimization Approaches to Protein Folding[END_REF]. In order to handle with errors induced by the discretization we assume interval distances, although we report computational results for the cases of exact and interval distances. Notice that the knowledge of an exact distance d uv is equivalent to considering d L uv = d U uv = d uv in expression (1.2). Our goal is to construct and test discrete optimization models (integer programming models [START_REF] Wolsey | Integer Programming[END_REF]) to decide whether there is an embedding of a graph on a lattice satisfying a set of interval distances.

Let V represent a neighborhood of a node of the original graph G and let G = G[V ] be the subgraph of the original graph (corresponding to the entire molecule) induced by V . The main idea is to locally use discrete optimization models in order to decide whether there is an embedding of G = (V , E , d ) in the lattice. These models can then be used within branch and prune algorithms to solve the MDGP. While in the previous strategies, for exact distances [START_REF] Lavor | The discretizable molecular distance geometry problem[END_REF] and for interval distances [START_REF] Lavor | The interval branch-and-prune algorithm for the discretizable molecular distance geometry problem with inexact distances[END_REF], the pruning is done using only the known distances of a current node to the previous fixed nodes, with our strategy we aim to prune the search tree by using all relevant information on the current node. In particular, by using a neighborhood of a node, it is possible to incorporate distance information on nodes that have not been explored yet, that is, to incorporate the distances to nodes that will be explored in deeper stages of the search tree. Doing so, it may be possible to identify infeasibility sooner and therefore prune the search tree in early stages.

The paper has the following contributions. (i) Propose and compare integer programming models, and one constraint programming model, to decide whether there is a feasible embedding of graph G in a lattice. This study can be applied to any embedding problem and not only for the MDGP. (ii) Provide several improvements on these models such as domain reduction and inclusion of valid inequalities. (iii) Include a new pruning test based on implicit distance information between atoms when the NMR provides no information that relates these atoms.

The paper is organized as follows. Definitions, notations to be used throughout the paper, and relation between embedding problems, are given in Section 2. In Section 3, several integer programming models are introduced and discussed. Section 4 presents a constraint programming model and, in Section 5, several improvements on the models introduced are discussed. In Section 6, we report the computational experiments conducted to compare the models. Additionally, we show that implicit distances from NMR can be used to reduce the size of the search tree of B&P algorithms for the MDGP. Finally, some conclusions and future directions of research are presented in Section 7. An embedding of G in a set

Embedding problems and their relation

R ⊆ R 3 , x : V → R, is called feasible if ∀ {u, v} ∈ E, d L uv ≤ x u -x v ≤ d U uv . (2.1)
The iMDGP can be reformulated as follows.

Problem 1 (iMDGP). Given a simple undirected graph G = (V, E) and a set I(E) of positive intervals, is there a feasible embedding of G in R 3 ?

The intervals (lower and upper bounds) are defined according to the NMR experiments. These experiments give distance information (intervals) for atoms that are close enough. In general, distances related to covalent bonds and covalent angles are considered fixed and defined by real numbers [START_REF] Wütrich | Protein structure determination in solution by nuclear magnetic resonance spectroscopy[END_REF]. The iMDGP has been considered before in [START_REF] Lavor | Clifford Algebra and the Discretizable Molecular Distance Geometry Problem[END_REF][START_REF] Lavor | The interval branch-and-prune algorithm for the discretizable molecular distance geometry problem with inexact distances[END_REF][START_REF]Distance Geometry: Theory, Methods and Applications[END_REF].

A very closely related problem occurs when we ask whether there exists a feasible embedding of G in a discrete set B ⊆ R 3 , which is a grid (lattice) limited by a box centered at the origin (0, 0, 0). Let α > 0 be the distance between consecutive lines of the grid. For a given grid dimension ∆, define K = ∆ α as the number of lines in each positive/negative coordinate. Each side of the box has length 2K × α, and the set of points in the box, denoted by B, is defined by: B = L × L × L where L = {αi : i ∈ Q} and Q = {-K, -(K -1), . . . , -2, -1, 0, 1, 2, . . . , (K -1), K}. Now, we seek an embedding of G in B defined by placing each node v ∈ V on the nearest point n(x v ) of the grid B when v is placed on x v ∈ R 3 , see Figure 1. This new problem can be defined as follows.

Problem 2 (iMDGP-grid). Given a simple undirected graph G = (V, E) and a set I(E) of positive intervals, is there a feasible embedding of G in B? Next, we discuss some relations between the two problems. Clearly, even if there is a feasible embedding of G = (V, E) in R 3 , it may be impossible to find a feasible embedding of G in B considering the same set of intervals I(E). In order to ensure that any embedding of G in R 3 corresponds to an embedding of G in B, we can measure the error induced by the discretization when each v ∈ V placed in x v = (x v1 , x v2 , x v3 ) ∈ R 3 is placed in the nearest point n(x v ) in the grid B given by,

n(x v ) = arg min y∈B x v -y = (α × round(x v1 /α), α × round(x v2 /α), α × round(x v3 /α)). As x vi -α × round(x vi /α) ≤ α 2 , i = 1, 2, 3, then x v -n(x v ) = 3 i=1 (x vi -α × round(x vi /α)) 2 ≤ 3( α 2 ) 2 = √ 3 2 α.
So, given a feasible embedding x, the maximum distance error resulting from the placement of u and v to the nearest positions, respectively, n(x u ) and n(x v ) in B, is given by

| x u -x v - n(x u ) -n(x v ) | ≤ √ 3α.
As a consequence of the discussion above we can state the following trivial result as a remark.

Remark 1. Consider a simple undirected graph G = (V, E) and a set I(E) of positive intervals. If x is a feasible embedding of G in R 3 , then n(x v ), v ∈ V , is a feasible embedding of G in B, for the set Ī(E) where Īe = [ dL uv , dU uv ] is given by dL uv = d L uv - √ 3α > 0, (2.2)
dU uv = d U uv + √ 3α. (2.3)
Remark 1 implies that if there is no feasible embedding of G in B for the set Ī(E), then there is no feasible embedding of G in R 3 for the set I(E).

The size of the iMDGP-grid instances depend on the size of the grid, |B|, and on the number of nodes of G, |V |. For a given ∆ (which defines the box size), as α increases, the number of points of the grid decreases and the same happens to the size of the instances of iMDGPgrid. However, as α increases the tolerance given for each interval (in order to ensure that no feasible solution is lost when moving from iMDGP to iMDGP-grid), denoted by , also increases. Hence, when increasing α, an instance of iMDGP for which there is no feasible embedding can be converted into an instance of iMDGP-grid having a feasible embedding. Thus, when there is no feasible embedding for an instance of iMDGP, the ideal choice of α is the largest α that leads to an instance of the iMDGP-grid problem having no feasible embedding. Therefore, the value of parameter α plays a key role in the feasibility check approaches discussed in this paper. We assume α = √ 3 , where is a tolerance satisfying 0 < < min {u,v}∈E {d L uv }. The last inequality prevents the lower bounds to collapse to zero.

Integer linear programming models

In this section, we present two Integer Programming (IP) models to describe an embedding of a graph G = (V, E) in a grid for a given set I(E) of interval distances.

The objective of the first model is to minimize an error distance function that is the sum of the interval distances violation. A feasible embedding corresponds to a feasible solution whose objective function value is zero. The second model is a feasibility model that checks whether a set of inequalities has feasible binary solutions. The first model always provides a solution (that may or may not correspond to a feasible embedding, depending on whether the objective value is zero or not), while the second model either provides one feasible solution corresponding to a feasible embedding or shows that there is no feasible embedding.

A discrete model to find an embedding that minimizes an error function

For each {u, v} ∈ E, the following model minimizes the distance (weight) error when assigning node u in the graph to position p in the grid and node v in the graph to position q in the grid. We use binary variables w u p indicating whether node u ∈ V is assigned to position p ∈ B, i.e. w u p = 1, or not, i.e. w u p = 0. Let D pq denote the Euclidean distance between positions p and q, p, q ∈ B.

min p,q∈B, {u,v}∈E, Dpq<d L uv (d L uv -D pq )w u p w v q + p,q∈B, {u,v}∈E, Dpq>d U uv (D pq -d U uv )w u p w v q (3.1) subject to p∈B w u p = 1, u ∈ V, (3.2)
u∈V w u p ≤ 1, p ∈ B, (3.3)
w u p ∈ {0, 1}, p ∈ B, u ∈ V. (3.4)
Constraints (3.2) establish that each node u ∈ V must be assigned to exactly one point in the grid. Constraints (3.3) establish that at most one node of the graph is assigned to each point p ∈ B. Constraints (3.4) impose binary restrictions to the variables, while the objective function (3.1) minimizes the error associated with the embedding of G into B. Thus, an optimal solution has an optimal value equal to zero if and only if this solution defines a feasible embedding for the iMDGP-grid.

The quadratic objective function can be linearized by introducing two sets of new variables. For each edge e = {u, v} ∈ E and each pair of grid points p, q ∈ B, we define a continuous variable ε e , as the mapping error of assigning u, v to positions p, q ∈ B, as follows:

ε e = max{0, d L uv -D pq , D pq -d U uv }.
Also, for each pair of positions p, q ∈ B and each edge e = {u, v} ∈ E, let y uv pq be the binary variable defined by:

y uv pq =
1, if nodes u and v are assigned, respectively, to positions p and q 0, otherwise. The integer linear formulation is as follows:

y uv pq ≥ (w u p + w v q -1), p, q ∈ B, {u, v} ∈ E, (3.6)
y uv pq ≤ w u p , p, q ∈ B, {u, v} ∈ E, (3.7)
y uv pq ≤ w v q , p, q ∈ B, {u, v} ∈ E, (3.8)
ε {u,v} ≥ (d L uv -D pq )y uv pq , p, q ∈ B, {u, v} ∈ E : D pq < d L uv , (3.9)
ε {u,v} ≥ (D pq -d U uv )y uv pq , p, q ∈ B, {u, v} ∈ E : D pq > d U uv , (3.10) 0 ≤ y uv pq ≤ 1, p, q ∈ B, {u, v} ∈ E, (3.11
)

ε e ≥ 0, e ∈ E. (3.12)
Constraints (3.6) -(3.8) and (3.11) define the y uv pq variables and correspond to the classical linear reformulation of the quadratic term w u p w v q , that is, y uv pq = 1 iff w u p w v q = 1, which happens only if w u p = w v q = 1. Constraints (3.9), (3.10), and (3.12) model the ε e variables. The objective function (3.5) is to minimize the violated distances. Let us refer to this formulation as MEA (Minimizing Error Assignment).

Discrete feasibility model

Deciding whether there exists a feasible embedding of G in B can be modeled as an assignment problem using the variables w u p defined above, while answering if there exists a feasible assignment is equivalent to solving the following feasibility model: ) can be seen as finding the maximum independent set on a conflict graph G C = (V C , E C ) defined as follows: the set of nodes V C is given by node-position pairs, V C = {(u, p) : u ∈ V, p ∈ B}; there is an edge between two nodes (u, p), (v, q) if the two pairs are incompatible, which occurs when i) u = v; or ii) p = q; or iii)

p∈B w u p = 1, u ∈ V, (3.13) u∈V w u p ≤ 1, p ∈ B, (3.14)
w u p + w v q ≤ 1, p, q ∈ B, {u, v} ∈ E : D pq ∈ [d L uv , d U uv ], (3.15)
w u p ∈ {0, 1}, u ∈ V, p ∈ B. ( 3
D pq ∈ [d L uv , d U uv ]
. This model will be denoted by CG model. Another approach to convert FM into an optimization model is to use the Farkas Lemma. Instead of using its variant for integer problems, we will apply the classical Farkas Lemma [START_REF] Wolsey | Integer Programming[END_REF] to the linear relaxation of FM.

Associate dual variables α u , u ∈ V, with constraints (3.

γ uv pq ≥ 0, u ∈ V, p ∈ B, (3.20)
β p ≥ 0, p ∈ B, (3.21)
γ uv pq ≥ 0, {u, v} ∈ E, p, q ∈ B, p = q, D pq ∈ [d L uv , d U uv ]. (3.22)
We assume in the model that each variable γ uv pq not defined is equal to zero. The following theorem follows from the Farkas' Lemma.

Proposition 1. Let X denote the set of solutions to the linear relaxation of the CG model. Then, either X is nonempty or h(α, β, γ) < 0.

As a result of Proposition 1, if h(α, β, γ) < 0 (it suffices to find a dual solution for the dual problem with negative value) then the linear relaxation of the CG model is infeasible and, therefore, the integer problem is also infeasible. In that case no feasible embedding of G in B exists. The model (3.19)-(3.22) will be denoted by LFM (Linear Feasibility Model). We can easily see that the free variables α u can be bounded to be non-positive.

Observe that when h(α, β, γ) ≥ 0 nothing can be concluded regarding the feasibility of the integer problem. Hence h(α, β, γ) < 0 is just a sufficient condition for infeasibility. On the other hand, h(α, β, γ) < 0 can be checked in polynomial time.

Constraint Programming

Constraint Programming (CP) is a technique that has proved to be competitive when compared against (mixed) integer programming (MIP) for certain combinatorial problems (such as scheduling problems) where the linear relaxations of the MIP models are weak; that is the case of the models discussed in Section 3. We refer a reader not familiar with the CP technique to [START_REF] Marriott | Programming with Constraints: An Introduction[END_REF].

We consider a very simple CP model. For each node u ∈ V , let X(u) be a set variable with domain B u ⊆ B (an algorithm to compute such restricted domain B u is described in the next section). We consider additionally the following constraints for the domain reduction:

d L uv ≤ ||X(u) -X(v)|| ≤ d U uv , ∀(u, v) ∈ E. (4.1)
We used the Xpress-Kalis [START_REF]FICO Xpress Optimization Suite[END_REF] solver in the implementation of the CP model. Constraints (4.1) were encoded with the following GenericBinaryConstraint command to propagate the distance constraint:

GenericBinaryConstraint(X(u),X(v),"Valid Distance Positions"),
where "Valid Distance Positions" is a binary function with inputs p, q ∈ B that returns 1 if the distance between p and q lies in the interval [d L uv , d U uv ], and 0 otherwise.

Improvements

All the models discussed in the previous sections can be improved in different directions.

Domain reduction:

When some atoms are fixed, which is the case of many instances tested, a preprocessing phase can be done in order to reduce the domain of each atom, that is: for each node v ∈ V, the set of grid points that can be assigned to v is reduced by checking its known distances to the fixed nodes. Let V F be the set of fixed nodes. For each u ∈ V F , let PosFix(u) denote the fixed grid position of node u in the grid. Also, for a grid point p ∈ B, (p x , p y , p z ) represents the corresponding grid coordinates. Algorithm 1 is used to set the initial domains of the non-fixed nodes by computing the intersection of several spherical shells on the grid. Given a grid point p ∈ B and two distances L and U , the function BallPoints defined in Algorithm 2 computes the spherical shell of grid points defined by {q ∈ B : L ≤ p -q ≤ U }.

Algorithm 1 allows us to define a restricted domain for each node u ∈ V, denoted by B u . Set B can also be replaced by the restricted set B = u∈V B u . Using the restricted domains we set to zero all the variables y uv pq and w u p in the model MEA, and variables w u p in the models FM and CG, that do not belong to the corresponding domain. It also allows us to remove many constraints in the model MEA and to reduce the domain of the CP variables.

Strengthening model FM:

The linearization proposed in models FM is very weak. Following the ideas from the Adam and Johnson linearization technique [START_REF] Adams | Improved linear programming-based lower bounds for the quadratic assignment problem[END_REF] for the quadratic assignment problem (which can not be applied directly here) the following set of equations can be added.

Algorithm 1 Domain reduction.

for all

u ∈ V F , v ∈ V \ V F do if {u, v} ∈ E then if D(v) = ∅ then D(v) ← BallPoints(P osF ix(u), d L uv , d U uv ) else D(v) ← D(v) ∩ BallPoints(P osF ix(u), d L uv , d U uv ) end if end if end for
Algorithm 2 Ball Points: Given a grid point p ∈ B and the distances L and U , computes all the grid points q ∈ B such that L ≤ p -q ≤ U function BallPoints( p, L,U ) X ← ∅ for i = 0 .. U/α do for j = 0 ..

U 2 /α 2 -i 2 do for k = max {0, L 2 /α 2 -i 2 -j 2 } . . . U 2 /α 2 -i 2 -j 2 do X ← X ∪ (p x +
p∈B y uv pq = w v q ,{u, v} ∈ E, q ∈ B (5.2)
Equations (5.1) state that if w u p is one then y uv pq must be one for some q ∈ B. Similarly for equations (5.2). These equations are not necessary to define the model but they improve the lower bound.

Strengthening model CG:

The model CG can be seen as finding a maximum cardinality independent set in a given graph. As a consequence, all the polyhedral theory known for the independent set problem [START_REF] Rebennack | Stable set problem: branch & cut algorithms, Encyclopedia of optimization[END_REF] can be used here. In particular, since a non maximal clique inequality does not define a facet of the associated polytope, the defining inequalities of CG can be strengthened: each inequality (3.15) can be replaced by a stronger clique inequality that includes the nodes in a clique C of the conflict graph G C :

(u,p)∈C w u p ≤ 1. (5.3)
Finding maximal cliques in G C that allow us to derive inequalities of type (5.3) dominating inequalities (3.15) can be done efficiently using a greedy algorithm. Consider an edge {u, v} ∈ E and a pair p, q ∈ B, such that

D pq ∈ [d L uv , d U uv ].
The first inequality states that if D pq > d U uv , that is, if nodes u, v can not be placed in p, q, respectively (because the distance between p and q is greater than the maximum distance between u and v), then the same holds for every pair of points whose distance is greater than D pq . Let π denote the vector q -p. The hyperplane defined by point p and normal to π is given by (x -p) • π = 0. Similarly, the hyperplane defined by point q and normal to π is given by (x -q) • π = 0. Each one of these hyperplanes defines two half-spaces.

Let H u = {x ∈ B : (x -p) • π ≤ 0} and H v = {x ∈ B : (x -q) • π ≥ 0}. It
w u p + q∈Hv w v q ≤ 1 can be added. Define S( ) = {x ∈ B : x -≤ d L uv }, ∈ B. If D pq < d L uv
, then the following inequalities can be added:

p∈S(q) w u p + w v q ≤ 1, q ∈ B, {u, v} ∈ E, D pq ∈ [d L uv , d U uv ], w u p + q∈S(p) w v q ≤ 1, p ∈ B, {u, v} ∈ E, D pq ∈ [d L uv , d U uv ].
When D pq < d L uv , another possible lifting can be obtained by taking x * = 1 2 p + 1 2 q. Then the inequality p∈S(x * )

w u p + q∈S(x * ) w v q ≤ 1
is valid for the set of feasible solutions.

Optimization strategy: The last improvement is related to the approach used to solve the models MEA and CG. Both are too large to be used as stated is Section 3, therefore a relaxation of each model obtained with the elimination of the larger set of constraints can be considered. The relaxation is solved and if the obtained solution violates one of the relaxed constraints, then those violated constraints are added to the model and the model is re-optimized. For Model MEA inequalities (3.6)-(3.10) are added dynamically as well as the variables that only appear in the constraints that are introduced. For model CG inequalities (3.15) are added dynamically. In both cases, the separation amounts to identifying pairs of nodes u, v ∈ V whose distance in the current solution does not lie in the interval I e , e = {u, v}, e ∈ E.

Computational experiments

In this section, we report some computational experiments to compare the IP models and the CP model, testing the effectiveness of these models in checking embedding feasibility and the improvements discussed in Section 5. We also show that the inclusion of a distance bound for those pairs of nodes for which the distance is not known, can be effective in solving the MDGP instances.

The computations were performed using the optimization software Xpress-Optimizer, Version 23.01.03 with Xpress Mosel Version 3.4.0 [START_REF]FICO Xpress Optimization Suite[END_REF], on a computer with processor Intel Core 2, 2.2 GHz and with 2 GB RAM.

The domain reduction revealed to be crucial in reducing the size of the models considered. Most of the reported instances could not be solved without this reduction, therefore all the tests include the domain reduction as a pre-processing step.

First, we compare the IP models with and without dynamic inclusion of constraints and the CP model. Then, using the approach with the best performance (that is, the IP approach based on the CG model) we test the effectiveness of the strengthening of cuts discussed in Section 5. Finally, we report the improvements in solving the MDGP with the inclusion of implicit inequalities.

Model comparison

We compared the Branch and Bound using the IP models MEA and CG discussed in Section 3, with and without the improvements discussed in Section 5, against the CP model. The first set of instances is generated as follows. First we generate a molecule following the procedure described in [START_REF] Lavor | On generating instances for the molecular distance geometry problem, Global Optimization: From Theory to Implementation[END_REF]. Then we consider small sized instances with 5 or 6 nodes resulting from neighborhoods of atoms of the molecule. Two atoms are considered neighbors if their distance is less than 5.5 Å. The position of the atoms is free. The size of the box is defined by taking ∆ = 20 Å. Three possible values for α, corresponding to different tolerance values (see Section 2) are considered: Table 1 reports the results obtained. Column #atoms indicates the number of nodes. Column named α gives the value of α used in the discretization. Column #NGrid gives the number |B| of the points in the grid after the domain reduction using the algorithm described in Section 5. Columns C Time (fourth and sixth columns) indicate the running time in seconds using the complete model, that is, using the corresponding model with all the model constraints, and with no addition of valid inequalities. Columns S Time (fifth and seventh columns) give the running time in seconds when all the improvements discussed in Section 5 are used, namely the optimization strategy is followed for both models (the larger sets of constraints are relaxed and these constraints are added dynamically); for model MEA we also include equations (5.1) and (5.2); and for model CG the lifted inequalities are included at the root node. Finally, column Time gives the running time in seconds using the CP model. We can see that when the constraints are added dynamically, the Branch and Bound based on the CG model is the strategy that had the best performance. However the CP model was better in three instances.

2 √ 3 , 2.

Impact of using lifted inequalities

Considering only the best approach (the Branch and Bound method based on the CG model) we tested the effectiveness of the use of the strengthened inequalities. For these tests we considered a new set of larger instances based on a set of benchmark instances1 extracted from Protein Data Bank2 .

As explained before the main purpose of this work is to provide feasibility tests that can be embedded in Branch and Prune algorithms where the binary tree of possible solutions is explored starting from its top, where the first three atoms are positioned, and by placing one node at a time following an ordering on the atoms of the protein. For each possible position of the selected node a new branch in the search tree is created. For each branch, a new instance is created based on the selected node and its neighbors. Thus, for each molecule, identified in Table 2 in column Name a set of instances of the iMDGP-grid is generated by considering neighborhoods of atoms. Each of these instances represents a set of atoms that were already fixed by the Branch and Prune (B&P ) algorithm [START_REF] Liberti | A Branch-and-Prune Algorithm for the Molecular Distance Geometry Problem[END_REF] and a set of atoms that must be fixed in the next iterations of this algorithm. From the initial assumptions, the distances between three consecutive nodes are known. Hence, at least the selected node and the two previous ones (which are neighbors of the selected one) are considered in the instance and have fixed positions.

The main idea is to test if this approach enables us to check feasibility of an embedding of a set of atoms (which could be used within the B&P algorithm for the iMDGP). Although the original data comes from exact distances, we considered ∆ = 20 Å and α = 0.1; therefore the exact distances were converted into interval distances by using (2.2) and (2.3).

The first five columns are related to information about the instances. Column #NInst indicates the number of instances considered from the corresponding molecule identified in column Name, column #atoms gives the average number of atoms considered, column #fixed indicates the average number of fixed atoms, and column #NGrid gives the average number of the points in the grid after the elimination procedure described in Section 5. Columns Time give the average time, in seconds, and columns #Uns give the number of instances that couldn't be solved within the time limit of 1500 seconds of the corresponding model: CG is for the model CG with constraints added dynamically as described in Optimization strategies, Section 5, and CG+SI is for the same model with the addition at the root node of the lifted inequalities, described in the same section. We can see that the average running time is lower when the strengthened inequalities are added and the total number of unsolved instances drops from 23 to 9. Among the 159 instances tested, 9 were proved to be infeasible. We ran the LFM for those infeasible instances and in none of them the LFM was able to prove infeasibility. Although this is a negative result, it also indicates that the linear relaxation of the CG model is weak, since for those instances the IP model is infeasible but its linear relaxation is feasible.

Use of implicit information from NMR

The main purpose of this work is to propose and compare feasibility checking models that can be used to improve the performance of a solution approach to the MDGP (as the B&P algorithm described in [START_REF] Lavor | The discretizable molecular distance geometry problem[END_REF]). Additionally, in this section, we discuss a very simple improvement that uses implicit information from the NMR spectroscopy. The NMR spectroscopy analysis provides only few inter-atomic distances. The reason is that only short distances are detected (distances of less than 5.5 Å). Hence, we use the fact that for each (u, v) ∈ E, u, v ∈ V, the distance d uv ≥ 5.5. To the best of our knowledge, such information has not been used before in the B&P algorithm applied to protein structure calculation (see [START_REF] Lavor | On the computation of protein backbones by using artificial backbones of hydrogens[END_REF] for some related questions).

Based on a set of benchmark instances3 with exact distances extracted from the Protein Data Bank4 , we compared the performance of the B&P algorithm described in [START_REF] Lavor | The discretizable molecular distance geometry problem[END_REF] in both cases: with and without the implicit distance d uv ≥ 5 (a tolerance of 0.5 Å was considered). Table 3 reports the computational results. The first three columns characterize the instances. The columns Name, #atoms and #edges indicate the name of the instance, the number of nodes and the number of edges, respectively. Columns 4-8 report information of the B&P algorithm when it is run to find only one feasible embedding in R 3 , while the remaining columns refer to the case where the B&P is run until all feasible embeddings are found. Columns 4-5 and 9-11 give information for the pure B&P , as described in [START_REF] Lavor | The discretizable molecular distance geometry problem[END_REF], while columns 6-8 and 12-15 give information for the B&P where the implicit distances are tested at each tree node. Columns #Nodes indicate the number of the tree nodes, columns Pruned indicate the number of pruned nodes, and %NR indicate the percentage of the reduction of tree nodes by including the implicit distance constraints. Columns #Sol give the number of feasible embeddings (solutions) found.

We can see that the use of the implicit distance allows for a reduction on the number of nodes on average by 10% to obtain one solution and by 12% to obtain all feasible solutions. Considering the implicit distances, we can also eliminate feasible solutions found by the B&P algorithm in instances 1mbn, 1mqq, 3b34. Each solution that has been excluded corresponds to a feasible embedding that satisfies all the distance constraints for all pair {u, v} ∈ E but does not satisfy the new implicit distances. However, it should be clear that the excluded solutions cannot correspond to the real conformation of the molecule.

Conclusions

We introduced different approaches for finding an embedding of a graph on a lattice that satisfies a set of distance intervals. We tested two integer programming models and one constraint programming model. We improved these models and showed that an integer programming model based on a conflict graph, strengthened with clique inequalities and based on an efficient generation of the domain of each variable had the best performance. This model allowed us to solve 150 out of the 159 tested instances within the specified time limit. These results show that this approach can be used to find a feasible embedding of small sized graphs in a lattice while satisfying a set of interval distances associated to the edges of the graph.

As a future line of research, we aim to use the best approach within a Branch and Prune Table 3: Performance of the B&P algorithm with and without the implicit distance constraints. (B&P ) algorithm for the iMDGP, in order to identify infeasible assignments in early stages of the B&P search tree that, otherwise, could only be identified after a deep search. Since the running times of the branch and bound (B&B) algorithm based on the CG model with strengthened inequalities are still high, this approach can only be useful when it identifies infeasibility quickly and allows to cut many search tree nodes. Currently, we are studying graph topologies where the characteristics of the subgraph corresponding to a neighborhood of atoms in the molecule are such that the B&B runs fast over instances nodes corresponding to atoms that appear in early stages of the search tree and others that appear only in latter stages of the tree.

In this paper we have focused only in iMDGP instances. However, for general DGP, it would be interesting to investigate the behaviour of the three modelling approaches on large size instances. Also some of these approaches may be improved. For instance, it may be worthy of investigation other linearization techniques such as t-linearization, see [START_REF] Rodrigues | 0-1 Quadratic Knapsack Problems: An Exact Approach Based on a t-Linearization[END_REF] for the MEA model.

  Consider an undirected graph G = (V, E) with node set V and edge set E. To each edge e = {u, v} ∈ E associate a positive interval I e = [d L uv , d U uv ], 0 < d L uv ≤ d U uv , and denote by I(E) the set of positive intervals I(E) = {I e : e ∈ E}.

!Figure 1 :

 1 Figure 1: (a) A simple representation of a Molecule. (b) The Molecule representation embedded in the grid.

  to (3.2), (3.3), (3.4),

5

 5

  #edges #Nodes Pruned #Nodes %NR Pruned #Sol #Nodes Pruned #Sol #Nodes %NR Pruned

  and v cannot be simultaneously assigned, respectively, to p and q when the Euclidean distance D pq is not in the interval distance [d L uv , d U uv ] related to edge e = {u, v}. These constraints are weak and will be strengthened in Section 5.Let us refer to this formulation as FM (Feasibility Model). Each feasible solution of FM is equivalent to a valid embedding of G in B. This feasibility problem can be converted into the following optimization problem: is to maximize the number of nodes in V that can be mapped onto positions of B while satisfying the distance constraints. Constraints(3.13) are replaced by constraints (3.18) imposing that each node is assigned to at most one position in B. Hence, FM has a feasible solution iff the optimization problem has value equal to |V |. The model given by (3.14), (3.15), (3.16), (3.17) and (3.18

	.16) Constrains (3.13), (3.14), (3.16) are the same as (3.2), (3.3), (3.4). Constraints (3.15) ensure u∈V p∈B w u p (3.17) subject to p∈B w u p ≤ 1, u ∈ V, (3.18) (3.14), (3.15), (3.16), that u max where the objective

  is easy to verify that when D pq > d U uv , every point in H u has distance at least d U uv from every point from H v . Hence, if D pq > d U uv , then the inequality

	p∈Hu

Table 1 :

 1 Performance of the three models MEA, CG and CP.

	MEA	CG	CP

Table 2 :

 2 Performance of the Branch & Bound algorithm based on the CG model with and without the strengthened inequalities.

			Instance			CG		CG+SI
	Name #NInst #atoms #fixed #NGrid Time #Uns Time #Uns
	1a70	18	9.2	4.4	28396	566	3	257	1
	1bpm	43	9.0	4.2	23305	579	5	382	2
	1fs3	46	9.4	4.5	22569	518	8	357	4
	1jk2	29	9.4	4.6	26738	458	3	565	1
	1m40	10	9.7	4.4	23570	614	3	438	1
	1mbn	2	8.0	4.0	21086	55	0	76	0
	1n4w	11	8.6	4.4	22271	259	1	180	0
	All	159	9	4.4	23990.7	436	23	322	9

Available in www.antoniomucherino.it/en/mdjeep.php/tests1.tar.gz.

www.resb.org/pdb

Available in www.antoniomucherino.it/en/mdjeep.php/tests1.tar.gz.

www.resb.org/pdb

Acknowledgements

The authors would like to thank FAPESP, CAPES and CNPq for their financial support. The research of authors 1, 2, 5 and 6 was partially supported by Portuguese funds through the Center for Research and Development in Mathematics and Applications (CIDMA) and FCT, the Portuguese Foundation for Science and Technology, within project UID/MAT/04106/2013.