Anne Roly

Obah Kosso

Julie Broggi

Sébastien Redon
email: sebastien.redon@univ-amu.fr

Patrice Vanelle
email: patrice.vanelle@univ-amu.fr

Convenient and Rapid Synthesis of 3-Selenocyanato-4H-chromen-4-ones

Keywords: Selenocyanate, Chromones, Triselenodicyanide, Selenium dioxide, Malononitrile, Electrophile Addition, Oxidation, Rearrangement

Organic selenocyanates (RSeCN) interest medicinal chemists because of for their remarkable activities as antileishmanial [START_REF][END_REF] and cancer chemopreventive agents. 2 The chemical field has known organo selenocyanates for almost a century, but recent advances led to a revival of interest in these compounds. Compared to the arylselanyl group, the SeCN functional group offers the advantage of being an air-and moisture-stable intermediate. They behave like pseudohalides, where the CN acts as a leaving group. 3a-c They can also be transformed by base-or NaBH4-mediated decyanation. 3d For the selenocyanation of electron-rich arenes, potassium selenocyanate (KSeCN) is typically used as radical source with an oxidant such as cerium ammonium nitrate 4a or K2S2O8, 4b or as an electrophilic source with N-iodosuccinimide 4c or N-chlorosuccinimide 4d . The disadvantage with most of these methods is that they require odorous, airsensitive and expensive potassium selenocyanate, along with tedious product purification by column chromatography.

Developing a more attractive industry-compatible process requires a straightforward, odorless, inexpensive and scalable method. Triselenodicyanide (Se(SeCN)2) represents an ideal electrophilic source, [START_REF] Verneuil | First synthesis: (a)[END_REF] especially considering its simple and cheap generation from malononitrile and odorless selenium dioxide. So far, this reagent has only been employed for the direct selenocyanation of activated nitrogen-containing heterocycles (indoles 6a and imidazoheterocycles 6b ). In continuation of our research centered on efficient one pot synthesis, 6c we investigated the reactivity of triselenodicyanide in a one pot two-step procedure for the selenocyanation of chromones from o-hydroxyacetophenones. Chromone structures, widely found in many natural products, are valued in pharmacology notably for their antiallergic, anti-inflammatory, antidiabetic, antitumoral, and antimicrobial properties. 7 We hypothesized that combining selenocyanates with chromones could enhance these biological properties. Selenation for chromones has so far only concerned the introduction of arylselanyl groups 8 in the C3-position; to our knowledge, no C3-selenocyanation has been performed to date.

To validate the sequential one pot procedure, we first optimized the insertion of the dimethylamino group to activate the enaminones (2a) [START_REF] Zhang | For similar one-pot procedure from o-hydroxyacetophenone via enaminone species see[END_REF] thus-formed for the subsequent addition of the electrophilic selenocyanate. The o-hydroxyacetophenone (1a) was heated with different equivalents of N,N-dimethylformamide dimethyl acetal (DMF-DMA) under neat conditions at temperatures ranging from 80 to 120 °C; and the reaction monitored by LC-MS. The best result was obtained at 100 °C for 2 hours with 1 equiv. of DMF-DMA. We then explored the electrophilic addition of triselenodicyanide without prior isolation of the intermediate. Using a previously optimized solvent system (DMSO, 1 mol.L -1 ), 6b we tested different amounts of SeO2 and malononitrile at room temperature for 1 hour (Table 1, entries 1-4). With a SeO2/malononitrile proportion of 1/0.5, low conversion of 1a was obtained (31%). Moderate conversion was obtained with a proportion of 2/1 (entry 2). Surprisingly, increasing the amount of malononitrile decreased the conversion, probably due to the formation of unreactive selenium-based intermediate. An excellent NMR conversion was obtained with SeO2/malononitrile proportion of 3/1 after only 30 min at r.t. (entry 4). Addition of 3 volumes of water precipitated the pure selenocyanated product to give 76% yield. Lower conversion was obtained when the reaction was conducted with dry DMSO under nitrogen atmosphere, probably due to lower SeO2 solubility in the absence of water (entry 5). Next, we examined the scope of our selenocyanation method with variously decorated o-hydroxyacetophenones (Scheme 1). 10 Scheme 1 Scope of the synthesis of 3-selenocyanato-4H-chromen-4-ones. a) Reaction conditions: A mixture of o-hydroxyacetophenone 1a-p (1 mmol, 1 equiv.) and DMF-DMA (1 equiv.) was heated for 2 h at 100°C; then a pre-prepared solution of SeO2 (3 equiv.) and malononitrile (1 equiv.) in DMSO (1 mL) stirred at 25°C for 20 min was added at 25°C. The reaction mixture was stirred for 30 min under air atmosphere. b) Isolated yield based on 1a-p.

The selenocyanation led to good yields and tolerated numerous functional groups such as halogen (3b, 3c, 3d, 3i, 3j, 3k), methyl (3e, 3l), alkoxy (3f, 3m) or nitrile groups (3g). Both electron-rich and -deficient substituents were well tolerated. Only the ohydroxyacetophenone bearing a NO2 group at the para-position of the phenol did not react. The relative positioning of the substituent on the aromatic ring (ortho, meta-or para-position) did not affect the efficiency of the reaction. Replacing the phenyl moiety by a naphthalene led to a better yield of 3-cyanoselenatochromone (3h, 81%). In contrast, the yield in presence of two hydrophilic substituents (two methoxy) was moderate (3o, 56%).

To further explore the applicability of the procedure, we performed a gram-scale synthesis of (3a) with 10 mmol of ohydroxyacetophenone. This reaction was accomplished with a slight increase in yield (79%) without changing reaction time (scheme 2).

Scheme 2 Gram synthesis.

We suggest the following mechanism to explain our experimental results (scheme 3). First, the o-hydroxyacetophenone (1a) is converted into the enaminone (2a) with DMF-DMA. Meanwhile, the reaction between 3 equiv. of selenium dioxide and 1 equiv. of malononitrile gives the triselenodicyanide (4). 6a The enaminone (2a) reacts on the most electrophilic selenium of (4) atom, leading to an iminium salt. Cyclization with phenol may occur, leading to a new iminium salt. After elimination of the volatile dimethylamine, the 3selenocyanato-4H-chromen-4-one (3a) is isolated. To demonstrate the utility of the selenocyanated chromones, two transformations of the SeCN functional group were explored (Scheme 4). The 3-selenocyanato-4H-chromen-4-one (3a) was converted into (5a) bearing a seleno ester group in 80% yield via a reduction with NaBH4 into a selenolate followed by addition of an electrophile (acetyl chloride). The chromen-4-one (3a) was then subjected to H2O2 oxidation (1 equiv.) in dichloromethane. To our surprise, no selenoxide was isolated; instead only unexpected ohydroxybenzoic acid appeared. The reaction was not complete even after one day at room temperature. Adding 3 equiv. of H2O2, allowed complete conversion into o-hydroxybenzoic acid with a 76 % yield.

Scheme 4 Transformations of the selenocyanated group in 5a and 6a.

Assuming that the chromone first lost the double bond and the SeCN group and that the ketone was secondly converted into carboxylic acid, a cascade reaction of several oxidations and rearrangements could be involved. The proposed mechanism is based on previous studies on the oxidative rearrangement of selenium (scheme 5). [START_REF] Redon | [END_REF] The selenocyanate group could first be oxidized by H2O2 into selenoxide species. A polarizable double bond further oxidized would be easily convertible into epoxide by H2O2. Then addition of water on position 2 could open this activated epoxide, inducing the expulsion of "HOSeCN". HOSeCN could then be further oxidized by the excess of H2O2 into CNSe(O)OOH (cyanoperseleninic acid). Perseleninic acid is know as a selective oxidant able to perform Baeyer-Villiger reactions. 12 The Baeyer-Villiger oxidation of the diketone could give the acid anhydride derivative. The hemiacetal formed upon opening of the seven-membered ring could expulse the oxoacetic acid and the o-hydroxybenzoic acids in the presence of water. The requirement of four equivalents of H2O2 for complete reaction is in agreement with the mechanism described. These successive oxidation steps demonstrate that these chromone-4-ones with a selenium on position 3 could be compounds of interest due to their antioxidant properties. In summary, we have developed an efficient approach for the preparation of 3-selenocyanato-4H-chromen-4-ones using readily available selenium dioxide and 2-hydroxyacetophenones. This one pot two-step reaction led to good yields with easy purification by simple filtration. The method uses odorless and inexpensive starting materials. Oxidation of the core of the chromones gave the ohydroxybenzoic acid by rearrangement of the selenium. This result indicates that insertion of SeCN in position 3 of chromones could increase their antioxidant properties.

  conditions: o-hydroxyacetophenone 1a (0.5 mmol, 1 equiv.), DMF-DMA (1 equiv.) at 100°C for 2h. Then a pre-prepared solution of SeO2 and malononitrile in DMSO (0.5 mL) at 25 °C for 20 min was added under air atmosphere. The reaction mixture was stirred for a further 1h.b) 1 H NMR yield of 3a (isolated yield). c) 30 min. d) with dry DMSO under nitrogen atmosphere.

Scheme 3

 3 Scheme 3 Suggested mechanism of the reaction.

Scheme 5

 5 Scheme 5 Mechanism for the peroxidation of selenium.

Table 1

 1 Optimization of the reaction conditions. a

	Entry	SeO2 (equiv.)	Malononitrile (equiv.)	Yield (%) b
	1	1	0.5	31
	2	2	1	72
	3	2	2	39
	4	3	1	100 (76) c

Acknowledgment

We warmly thank Vincent Remusat and the Spectropole (http://www.spectropole.fr) for NMR and HRMS analysis.

Funding Information

Aix-Marseille Université and the Centre National de la Recherche Scientifique (CNRS) are gratefully acknowledged for financial support. A. R. Obah Kosso thanks OGES-Congo for her PhD grant.


Arnaud De

La Fortelle

Claude Laurgeau
email: claude.laurgeau@ensmp.fr

Paul Muhlethaler
email: paul.muhlethaler@inria.fr

Yasser Toor
email: yasser.toor@inria.fr

COM2REACT: V2V COMMUNICATION FOR COOPERATIVE LOCAL TRAFFIC MANAGEMENT

Keywords: TOPICS 4.8 Wireless Communications to/from/among Vehicles Secondary: 10.4 Probe Data Processing V2V Communication, collaborative system, Traffic management. Secondary: Traffic, safety, efficiency, sensors, probe vehicles, communication, intelligent transportation systems (ITS), peer-to-peer application, Virtual Sub-Center (VSC)

The European project COM2REACT aims at building a local cooperative traffic management system through a peer-to-peer application, the Virtual Sub-Center (VSC), based on vehicle-to-vehicle (V2V) communication. COM2REACT is an enhancement of the REACT system, which relies on a central server that gathers data from probe vehicles, aggregates and analyzes them by an integrated set of models, and generates both vehicle-specific recommendations and information for relevant authorities. This additional collaborative layer will increase the reactivity of the system and avoid an overload of communication and of the central server with information only relevant at a local level. The goal of this paper is to give the reader an overview of the new technologies developed to reach the ambitious goals of COM2REACT: V2V communication, VSC and local traffic applications.

INTRODUCTION

Effective large-scale control of traffic, geared to address both efficiency and safety, requires a system incorporating a hierarchy of control levels:

1. High control level over an urban, metropolitan or regional area provided by a Regional Control Centre (RCC) that acts as a strategic controller 2. Middle control level provided by local sub-centres, each operating over a limited number of nodes and links in the road network 3. Low control level implemented within an individual vehicle COM2REACT's (COoperative CoMmunication System TO Realise Enhanced Safety And EffiCiency In European Road Transport) overall objective is to establish the feasibility of such a three-layer, scalable, cooperative system. Its implementation will involve the deployment of two two-way communication systems: vehicle to vehicle (V2V), and vehicle to infrastructure (V2I). This structure will facilitate significant improvement in the flow of information acquired by moving vehicles and in its quality and reliability, thereby enhancing road efficiency and traffic safety on urban, intercity arterials and rural roads.

A key objective of COM2REACT is the implementation of the middle control level by means of a virtual traffic control sub-centre, which manages a moving group of vehicles in close proximity. The virtual subcentre (VSC) functions locally via the V2V communication system. It obtains and processes data acquired by the vehicles and rapidly provides instructions related to local traffic and safety situations. It also transmits, by means of the V2I communication, selective data to an RCC and receives, in return, instructions to distribute to the vehicles. The role of VSC is set, unnoticeable by the driver, to one of the vehicles in the group according to rules imbedded in all COM2REACT vehicles.

The COM2REACT system will build upon the DG Research REACT project to create the high level and the low level layers of the system. REACT comprises RCC, V2I communication and sensorequipped vehicles. COM2REACT's newly developed VSC will interface with REACT's RCC, utilizing REACT's V2I communication, with the appropriate adaptations. At the low layer REACT's vehicles will be used, complemented with additional sensors, in order to test the COM2REACT system and confirm its feasibility under the conditions pertinent to traffic safety: vehicle state, driver state, road state and intervehicle situations.

Hence the most significant developments that are developed hereafter are:

• A V2V ad hoc network using WiFi communication.

• The VSC: a peer-to-peer layer enabling local cooperative traffic applications.

• The integration of the COM2REACT system within vehicles and applications tests.

VEHICLE-TO-VEHICLE COMMUNICATION

COM2REACT did not undertake new communication development, but to overcome current limitation, e.g. range limitation. The project performed extensive testing to choose the best available wireless technologies (focusing on 802.11 devices). The goal is to enable experiments of the whole COM2REACT system while keeping modularity: e.g. WiFi 802.11b/g cards can easily be replaced in the future by 802.11p. The same conception lead to remain untouched subjacent layers, such as MAC or physical layer.

The network operation is ensured at a higher level by routing protocols, adaptable to mobility situations. The implementation is based on the existing Optimized Link State Routing Protocol (OLSR), which is especially developed for mobile ad-hoc networks. It operates as a table driven and proactive protocol, thus exchanges topology information with other nodes of the network regularly. The COM2REACT consortium is well aware that routing algorithms and models for vehicle and mobile adhoc networks are already offered today by research consortiums projects such as Network on Wheels (NoW), CarToCar or IETF (MANETs). However, these protocols do not meet the requirements of the project. Some of them are not yet available while other do not offer the required parameters (e.g. the communication topology is necessary for the VSC). Hence OLSR has been chosen and a special version that satisfies COM2REACT needs is being implemented. OLSR has been developed by INRIA and standardized at IETF, is already well recognized by the industry (OLSR is implemented on CISCO routers) and will be proposed in other European projects (Cyvercars2, CVIS…). Besides, the protocol does not require reliable transmission of control messages. Some other topic have been addressed such as:

Geographic id vs. IP id.

Type of communications: Unicast vs. multicast communications (geo-cast routing).

Dynamic initialization.

Finally, at the intersection between communication and application, negotiation algorithms are being developed to assign the roles of each entity behind a local area network, within the VSC.

VSC : P2P LOCAL TRAFFIC MANAGEMENT

A main objective of COM2REACT is the design and analysis the different options for the communication and control process that is needed for the functioning of the novel VSC-concept. In the current developments, and excepting the functionalities covered by the REACT system (V2I), the principles underlying the VSC are as follows:

• All COM2REACT vehicles are equipped with compatible communication and processing systems and identical capabilities and can function as either VSC or an individual vehicle.

• V2V module detects neighbouring vehicles, as soon as vehicles are in communication range. There the adapted ad-hoc protocol links the vehicles: a group is formed. A signal will be send to the VSC host so that it takes into account the arriving vehicle. This holds for departing vehicles. Special cases are group creation, host departure and group destruction. These cases are handled by the routing protocol, but it is necessary to ensure the correct communication between the routing layer and the VSC layer.

• Vehicles in a group communicate with their VSC (using V2V) (1) routinely, informing it of their location, destination and status (communication rate to be determined) and ( 2) upon the occurrence of special events, as detected by their in-car sensors. Such events could be related to vehicle status, road conditions, state of the driver or neighbouring vehicles.

• Vehicles are capable of direct communication (V2V) with each other but avoid it except for emergencies such as collision avoidance.

• Vehicles association with a group is done according to prescribed rules that depend on parameters such as range and local vehicle density. These parameters will be periodically continually observed by the vehicles, which will join with, or depart from groups of vehicles accordingly.

There are a variety of open issues that will be investigated in more detail, e.g. the frequencies for communication and positioning information, the decision process to direct communication to the VSC or to other vehicles, the synchronization of different information flows, the dynamic adjustment process dealing with a constantly changing constellation of moving vehicles etc.

Figure 1 The COM2REACT system and VSC concept

Traffic models are also being developed to fit the COM2REACT system. They will provide the data and decisions necessary for the 4 applications that have been defined:

• Local navigation system • Traffic flow control
• Collision warning by locating "hazards" (static obstacle or inattentive driver)

• Traffic state assessment and fusion

Since the beginning of 2007, a lot of experiments have been conducted in order to test the concept of VSC and the technological specification of such a system. Concerning V2V communication, the system uses a standard 802.11b card with 9 dB antennas on top of the roof. With such hardware, ranges of 700m on motorways and 300m in cities can be achieved with a sufficient stability.

The networking layer based on the routing standard OLSR ensures the diffusion of the messages inside a VANET. Here, again, the concept has been refined. Originally, it was thought that the whole VANET (the topologically OLSR-connected component) would be the VSC cluster. In fact, it is only necessary that the VSC cluster is a subset of the VANET, constituted by vehicle sharing the same informational need (e.g. vehicles driving in the same direction). Experiments prove that OLSR is not currently entirely satisfactory since it increases some latency (at reconfiguration times), but it is sufficient for the current system.

VSC layer experiments have proved the system is functional. The information in all vehicles is exactly the same with a very small latency. With the same information, all vehicles decide for themselves with exactly the same algorithms, hence decisions are consistent. Moreover, with the same information (similar to the Safespot local map), more applications can be easily designed without much strain on the communication links.

EXPERIMENTS & CONCLUSION

All the technologies will be integrated into 5 cars: 4 identical C3 cars from Mines Paris and one additional C3 from Sphericon (integrating the DAISY Sensor). Figure 3 Several tests will take place. WiFi is being tested to chose the hardware. Then VSC tests will validate the VSC basic functionality (formation, dynamic management…). A third step is a system test combining the VSC capabilities with the Regional Control Center (RCC, centralized management). A last set of experiments will prove that VSC can be deployed without a RCC. Finally a public demonstration will take place by the end of October in Paris, France. The last two sets of experiments will demonstrate that the COM2REACT system is operational and easily deployable for the next generation of traffic management systems.

  shows the C3 at INRIA: these vehicles are part of the Joint Research Unit "LaRA" (www.lara.prd.fr) between Mines Paris and INRIA. The in-car architecture is derived from REACT, with extension in communication, maps calculation (ADAS-RP), sensing and local application (VSC).

Figure 2 .

 2 Figure 2. REACT sensor vehicles: 4 LaRA C3.

ACKNOWLEDGEMENTS

COM2REACT (www.com2react-project.org) is a project funded by the European Commission within the Sixth Framework Program.


R Othman
email: othman@lms.polytechnique.fr

G Gary

M N Bussac

P Collet

APPLICATION OF THE LIKELIHOOD METHOD TO THE ANALYSIS OF WAVES IN ELASTIC AND VISCOELASTIC RODS

In this paper, we are interested in separating waves in elastic and viscoelastic rods propagating in opposite direction. N strain and P velocity measurements are taken into account. This application of the likelihood method gives a solution in the frequency domain. Using the inverse Fourier transform, one can recover the strain, stress, displacement and velocity at any section of the rod. In experimental conditions, the results are stable against noise when N+P>2 and NP ¢0.

Introduction

In the classical configuration, the loading time in the SHB (Split Hopkinson Bar) system is limited by the length of the bars together with the maximum measured strain in the specimen, because of the need to separate opposite waves propagating in the bar. Hence, for many materials, it is of no interest to carry out tests with the SHB apparatus at medium strain-rates. As mechanical testing machines are limited at much lower strain rates because of sensor oscillations, "alternative solutions have been already investigated, in particular the wave separation technique. They are based on a two strain measurement and they take account of wave dispersion 1 • ?-s or noe• [START_REF] Park | Separation of elastic waves in split Hopkinson bars using one-point strain measurements[END_REF] • Bussac and al. [START_REF] Bussac | An optimisation method for separating and rebuilding one-dimensional dispersive waves from multi-point measurements. Application to elastic or viscoelastic bars[END_REF] showed that the noise is amplified on the reconstructed signals when using only two measurements. In this paper, a new separation method using N strain and P velocity measurements is presented. It is based on the Maximum of Likelihood principle 2 ' 5 ' 6

•

Theory

Let us consider an L-long elastic or viscoelastic bar. In the case of single mode propagating longitudinal waves, the Fourier transform of stress, strain, displacement and velocity are expressed as follows :

f(x,m )= A(m )e-•~(m)x + B(m )e'Hm)x' O'(x,m )= E * (m) (A(m )e-•~(m)x + B(m )e'~(m)x ), 1 - _ CO(-A(co )e-i~(ru)x + B(co )e'~(ru)x) v(x,co)- ~(co) , - _ i (A(co )e-i~(ru)x -B(co )e'~(ru)x) u(x,co)- ~(co) ,
where A(co) and B(co) are the Fourier components of the ascendant and descendant waves at origin, respectively. E * (co) is the complex Young's modulus and ~(co)=k(co)+ia(co) is the complex wave number. The two parameters E*(co) and ~(co) are only related to the bar properties (geometry and material). In the following, it is assumed that they are known.

From strain and/or speed measurements, we want to recover A(co) and B(co) so that strain, stress, displacement and velocity can be calculated at any point of the bar, in particular at both ends. We perform N strain and P velocity measurements on the bar. The corresponding record is modelled as the superposition of the exact measurement and a Gaussian white noise:

fJ(t)=e(xJ,t)+WJ(t} J=I, .. ,N, vK(t)=v(xJ,t)+WJ(t} J=N+l, .. ,N+P

The N + P white noises are supposed to be two-by-two independent. The amplitudes of the noise concerning strain and velocity are denoted 1/ a~ and I I a~ , respectively.

In order to estimate the two functions A(co) and B(co), the Maximum Likelihood Method is used 2 .

We denote XJK• J=I, .. ,N+P and K=l, .. ,M, the random variable corresponding to the noise stored on the measurement made at the station J at the time t = K/ f.,h , where M is the maximum measured points and f.,h is the sampling frequency.

The likelihood function is given by :

V (t, (t);, (t) A(w )B(w ))~ {;:;~;(x • =W, (KIf~)) l
Since all the noises are white and two-by-two independent, the likelihood function is then expressed as follows :

v(e J (t) vJ (t) A(m ),B(m ))= II p(X JK =W J (K 1 J,c}, ))

Noises are also Gussiens, hence :

J=l ... ,N+P K=I, .. ,M
where v 1 = 1 I a 1 is the standard deviation and J1 1 is the mean of the noise W 1 •

This method consists in writing that what is measured corresponds to the most probable event (a particular application is the least-square method). This leads to maximize the function v(eAttv 1 {t)A(w~B(w)) which is equivalent to minimizing the following function: 1

F =I { t (a1 Y(i1 (t )-e(xJ' t))' + 1 ~1(a 1 ) (v 1 (t )-v(x 1 ,t ))' }dt
The function F is minimized when:

where: The validity of the method is checked using a nylon bar. A nylon striker is launched at the left end of the bar at a speed of 3.03 mls. The right end is free. Three strain and one-velocity measurements are recorded on the bar. We use the method developed in section 2. to reconstruct the stress at two ends of the bar and the displacement at the free end. The stress at the left end was almost zero as expected. At the right end, the stress became almost zero after the first incident wave. Compared to the amplitude of the impact stress, the error on the reconstructed stress was less than 3.5% (Fig 3). The reconstructed displacement was similar to the directly measured one. The relative error was less than 2.5% (Fig 3).

A( co)= h 2 (co )E, (co)-g(co)E 2 (co) h,(co)h 2 (co)-g(co)g(co) ' B(co) = h, (co)E 2 (co)-~~(co) h, (co )h 2 (co)-g(co)g(co) ' h,(co)= i(

Conclusion

A multi-point method (multi-strain and/or multi-velocity measurements) is presented for reconstructing one-dimensional waves in bars. This method is exact when used with the single-mode dispersive propagation model commonly applied to Hopkinson bars. It yields consistent results (the inaccuracy due to imprecise measurements does not increase with time). It is illustrated here by applying it successfully to the analysis of a real test on a Nylon bar. It provides a significant increase in the observation time available when using measuring techniques based on the use of bars such as SHPB set-ups. The method would make it possible to obtain precise measurements at

2 F

 2 = JI(aJ2ieJ(w)-A(w~-~~(m)x, -B(w~'~(m)x,l dw _.,., J=l + Ji (aJ 2 ~~1 (w )+ ~(A(w ~-tHmk -B(w ~~~(mh, f dw __ J=l ~(w)

  Figure2. E"or on displacement (a) N=Z and P=O-(b) N=3 and P=l -(c) N=3 and P=Z -(d) N=3 and P=O-(e) N=4 and P=O-(f) N=5 and P=O

.Figure 3 .

 3 Figure 3. Reconstructed stresses at the ends of the bar and displacement at the free end (The stress at the free end has been shifted down by 0.2 MPa to make the figure more readable).

Table 1 .

 1 •••. 3 Maximum error on strain and displacement

	p	0	0	0	0	lc•J > .'	2
	med(%) 11,90	3,50	1,80	1,50	t,;tl4fc	2,10
	meu(%) 71,00	74,00	57,00	56,00	, •f,'J;~c• 0,98

4 Application to a Nylon bar

Numerical simulation

In this section we propose to validate the method with a numerical test. The bar simulated is elastic. It is 3m long and 40 mm in diameter. The Young's modulus is E. = 70 GPa , the Poisson's ratio is v = 0.34, and volumic mass is p = 2800 kg/ m' . A I .2m long striker, having the same chracteristic as the bar, is launched at one end of the bar (x = 0) at a speed V, = 12 m/s. Five strain measurements at sections x, = 0.5m, x, = 1.02m, x, = 1.4m, x. = 1.78m, x, = 2.2m and two velocity measurements at sections x. = 0. 8m, x, = 1.4m are simulated.

Gaussian noise with amplitude 2 % of the maximum strain or the maximum velocity is added to each measurement. We suppose also that the mean of each noise on strain measurements is not zero and equals 5 %o of the maximum strain.

We compare results provided by the method developed in section 2. to exact simulated signals. We denote med the maximum relative error on strain and meu the maximum relative error of reconstructed displacements. Figs. 1 and2 compare the error on strain and displacement for different values of Net P. The results show that it is sufficient to use three strain and one velocity measurement to have good accuracy on reconstruct strain and displacement. For experimental application we choose this solution (Tab. 1 ).


C Gervet
email: gervetec@univ-savoie.fr

S Galichet
email: sylvie.galichet@univ-savoie.fr

On Combining Regression Analysis and Constraint Programming

Keywords: Data uncertainty, Constraint Programming, regression analysis

Uncertain data due to imprecise measurements is commonly specified as bounded interval parameters in a constraint problem. For tractability reasons, existing approaches assume independence of the parameters. This assumption is safe, but can lead to large solution spaces, and a loss of the problem structure. In this paper we propose to combine the strengths of two frameworks to tackle parameter dependency effectively, namely constraint programming and regression analysis. Our methodology is an iterative process. The core intuitive idea is to account for data dependency by solving a set of constraint models such that each model uses data parameter instances that satisfy the dependency constraints. Then we apply a regression between the parameter instances and the corresponding solutions found to yield a possible relationship function. Our findings show that this methodology exploits the strengths of both paradigms effectively, and provides valuable insights to the decision maker by accounting for parameter dependencies.

Introduction

Data uncertainty due to imprecise measurements or incomplete knowledge is ubiquitous in many real world applications, network design, renewable energy investment planning, and inventory management, to name a few. Regression analysis is one of the most widely used statistical techniques to model and represent the relationship among variables to describe or predict phenomena for a given context. Recently, models derived from fuzzy regression have been defined to represent incomplete and imprecise measurements in a contextual manner, using intervals [START_REF] Boukezzoula | A MidpointRadius approach to regression with interval data[END_REF]. Such models apply to problems in finance or complex systems analysis in engineering whereby a relationship between crisp or fuzzy measurements is sought.

Constraint Programming (CP) on the other hand, is a powerful paradigm used to solve decision and optimization problems in areas as diverse as planning, scheduling, routing. The CP paradigm models a decision problem using constraints to express the relations between variables, and propagates any information gained from a constraint onto other constraints. When data imprecision is present, forms of uncertainty modeling have been embedded into constraint models using bounded intervals to represent such parameters. For instance if we model traffic in a network, the flow over links between two routers cannot be measured with precision as it depends on the collected traffic volume data at each router which cannot be synchronized. As a result, the data information obtained is erroneous. We use the sigcomm4 network given in Fig. 1 as a running example taken from [START_REF] Medina | Traffic Matrix Estimation: Existing Techniques and New Directions[END_REF]. On link A → C, for example, the traffic volume might measure as 565 at A and as 637 at C, whereas the true value, equal at both nodes, is presumably somewhere in between. Thus, the flow between A and C will be specified by Traditional models either omit any routing uncertainty for tractability reasons, and consider solely the shortest path routing or embed the uncertain parameters but with no dependency relationships. Values for the flow variables are derived by computing bounded intervals, which are safe enclosing of all possible solutions. Such intervals enclose the solution set without relating to the various instances of the parameters. For instance, the traffic between A and C can also pass through the link A → B. Thus the flow constraint on this link also contains 0.3..0.7 * F AC . However, the parameter constraint stating that the sum of the coefficients of the traffic F AC in both constraints should be equal to 1 should also be present. Assuming independence of the parameters for tractability reasons, leads to safe computations, but at the potential cost of a very large solution set, even if no solution actually holds. The problem structure is lost. Also, there is not insight as to how the potential solutions evolve given instances of the data.

The question remains as to how can this information be embedded in a constraint model that would remain tractable. To our knowledge this issue has not been addressed in the general case. It is the purpose of this work.

In this paper we propose a new methodology and efficient process to account for data dependency constraints in decision problems. We aim to more closely model the actual problem structure, refine the solutions produced and add accuracy to the decision making process. We use regression analysis to show the relationship among various instances of the uncertain data parameters and the solutions produced. The basic process is to extract the parameter constraints from the model, solve them to obtain tuple solutions over the parameters. Then we run simulations on the constraint models using the parameter tuples as data instances that embed the dependencies. In the example above this would imply for the two constraints given, that if one parameter takes the value 0.3, the other one would take the value 0.7. A set of constraint models can thus be solved efficiently, matching a tuple of consistent parameters to a solution, to determine whether there are solutions once dependencies are taken into account or not. Finally, we run a regression analysis between the parameter values and solutions produced to determine the regression function, i.e. see how potential solutions relate to parameter variations.

The paper is structured as follows. Section 2 summarizes the related work and gives a small illustrative case study. Section 3 describes the approach and algorithms, and Section 4 gives an application study. A conclusion is given in Section 5.

Background and case study

The fields of regression analysis and constraint programming are both well established in computer science. While we identified both fields as complementary, there has been little attempt to integrate them together to the best of our knowledge. The reason is, we believe, that technology experts tackle the challenges in each research area separately. However, each field has today reached a level of maturity shown by the dissemination in academic and industrial works, and their integration would bring new research insights and a novel angle in tackling real-world optimization problems with measurement uncertainty. There has been some research in Constraint Programming (CP) to account for data uncertainty, and similarly there has been some research in regression modeling to use optimization techniques. We give an account of the state of the art against our main objective to integrate both paradigms.

CP is a paradigm within Artificial Intelligence that proved effective and successful to model and solve difficult combinatorial search and optimization problems from planning and resource management domains [START_REF] Rossi | Handbook of Constraint Programming[END_REF]. Basically it models a given problem as a Constraint Satisfaction Problem (CSP), which means: a set of variables, the unknowns for which we seek a value, the range of values allowed for each variable , and a set of constraints which define restrictions over the variables. Constraint solving techniques have been primarily drawn from Artificial Intelligence (constraint propagation and search), and more recently Operations Research (graph algorithms, Linear Programming). A solution to a constraint model is a complete consistent assignment of a value to each decision variable.

In the past 15 years, the growing success of constraint programming technology to tackle real-world combinatorial search problems, has also raised the question of its limitations to reason with and about uncertain data, due to incomplete or imprecise measurements, (e.g. energy trading, oil platform supply, scheduling). In the past 10 years, the generic CSP formalism has been extended to account for forms of uncertainty: e.g. numerical, mixed, quantified, fuzzy, uncertain CSP and CDF-interval CSPs [START_REF] Brown | Chapter 21: Uncertainty and Change Handbook of Constraint Programming[END_REF]. The fuzzy and mixed CSP [START_REF] Fargier | Mixed constraint satisfaction: A framework for decision problems under incomplete knowledge[END_REF] coined the concept of parameters, as uncontrollable variables, meaning they can take a set of values, but their domain is not meant to be reduced to one value during problem solving (unlike decision variables). Constraints over parameters, or uncontrollable variables, can be expressed and thus some form of data dependency modeled. However, there is a strong focus on discrete data, and the consistency techniques used are not always effective to tackle large scale or optimization problems.

Frameworks such as numerical, uncertain, or CDF-interval CSPs, extend the classical CSP to approximate and reason with continuous uncertain data represented by intervals; see the real constant type in Numerica [START_REF] Van Hentenryck | Numerica: a Modeling Language for Global Optimization The[END_REF] or the bounded real type in ECLiPSe [START_REF] Cheadle | An Introduction[END_REF]. Our previous work introduced the uncertain and CDFinterval CSP [START_REF] Yorke-Smith | Certainty Closure: Reliable Constraint Reasoning with Uncertain Data[END_REF][START_REF] Saad | Constraint Reasoning with Uncertain Data usingCDF-Intervals Proceedings of CP[END_REF]. The goal was then to derive efficient techniques to compute reliable solution sets that ensure that each possible solution corresponds to at least one realization of the data. In this sense they compute an enclosure of the set of solutions. Even though we identified the issue of having a large solution set, the means to relate different solutions to instances of the uncertain data parameters and their dependencies were not thought of. On the other hand, in the field of regression analysis, the main challenges have been in the definition of optimization functions to build a relevant regression model, and the techniques to do so efficiently. Regression analysis evaluates the functional relationship, often of a linear form, between input and output parameters in a given environment. Here we are interested in using regression to seek a possible relation between uncertain constrained parameters in a constraint problem, e.g. distribution of traffic among two routers on several routes and the solutions computed according to the parameter instances. We note also that methods such as sensitivity analysis in Operations Research allow to analyze how solutions evolve relative parameter changes. However, such models assume independence of the parameters. In the following case study we show how our approach can establish relationships with the solutions and uncertain parameters while accounting for dependencies.

Case study We present a small case study to give the intuition of our approach. The core element is to go around the solving of a constraint optimization problem with uncertain parameter constraints by first solving the parameter constraints alone. This way we handle uncertainty in an efficient and tractable manner. We then substitute solution tuples of these parameters to solve a set of constraint optimization problems (now without parameter constraints). Finally to provide insight to the solutions to the uncertain constraint problem, we run a regression between the solutions produced and the corresponding parameter tuple instances.

Consider the following fictitious constraint between two unknown positive variables, X and Y ranging in 0.0..1000.0, with uncertain data parameters A, B taking their values in the real interval [0.1..0.7]:

A * X + B * Y = 150
The objective is to compute values for X and Y in the presence of uncertain parameters (A, B). Without any parameter dependency a constraint solver based on interval propagation techniques with bounded coefficients, derives the ranges [0.0..1000.0] for both variables X and Y [START_REF] Cheadle | An Introduction[END_REF]. Let us add to the model a parameter constraint over the uncertain parameters A and B: A = 2 * B. Without adding this parameter constraint to the model, since it is not handled by the solver, we can manually refine the bounds of the uncertain parameters in the constraint model such that the parameter constraint holds over the bounds, thus accounting partially for the dependency. We obtain the constraint system: We now give the intuition of our approach. The idea is to first solve the parameter dependency constraints alone to obtain solution tuples, not intervals. To do so we use a traditional branch and bound algorithm. We obtain a set of tuples for A and B such that for each tuple the constraint A = 2 * B holds. The idea is to have a well distributed sample of solutions for this parameter constraint.

We obtain a set of tuples that satisfy the parameter constraint, in this case for instance (0.2, 0.1), (0.3, 0.15), (0.4, 0.2), (0.5, 0.25), (0.6, 0.3), (0.7, 0.35). We then substitute each tuple in the uncertain constraint model rendering it a standard constraint problem, and solve each instance. We record the solution matching each parameter instance. The issue now is that we have a set of solutions for each tuple of paramers. There is no indication how the solutions are related and evolve. The idea is to apply a regression analysis between both. The regression function obtained includes the solution bounds obtained by the standard approach, but mainly shows the trends between the data parameters and the solutions. In this small example we can visualize how the solution evolves with the data, see Fig. 2 on the right. In the case of much larger data sets, a tool like Matlab can be used to compute the regression function and display the outcome. The algorithm and complexity analysis are given in the next section.

Process and algorithms

Our methodology is a three-steps iterative process: 1) Extract the uncertain parameter constraints from the uncertain optimization problem and run branch and bound to produce a set of tuple solutions, 2) solve a sequence of standard constraint optimization problems where the tuples are being substituted to the uncertain parameters. This is a simulation process that produces, if it exists, one solution per tuple instance. And finally, 3) run a regression analysis on the parameter instances and their respective solution, to identify the relationship function showing how the solution evolves with consistent parameter constraints. The overall algorithmic process is given in Fig. 3, where the outcomes at each step are highlighted in italic bold. A constraint satisfaction and optimisation problem, or CSOP, is a constraint satisfaction problem (CSP) that seeks complete and consistent instantiations optimizing a cost function. We use the notion of uncertain CSOP, or UCSOP first introduced in [START_REF] Yorke-Smith | Certainty Closure: Reliable Constraint Reasoning with Uncertain Data[END_REF]. It extends a classical CSOP with uncertain parameters.

Uncertain CSOP and uncertain parameter constraints

Recall that a CSOP is commonly specified as a tuple (X , D, C, f ), where X is a finite set of variables, D is the set of corresponding domains, C = {c 1 , . . . , c m } is a finite set of constraints, and f is the objective function (min or max of a given expression over a subset of the variables).

Definition 1 (UCSOP). An uncertain constraint satisfaction and optimisation problem is a classical CSOP in which some of the constraints may be uncertain, and is specified by the tuple (X , D, C X , Λ, U, f ). The finite set of parameters is denoted by Λ, and the set of ranges for the parameters by U. A solution to a UCSOP is a solution space enclosing safely the set of solutions.

C 1 : X 1 > λ 1 , C 2 : X 1 = X 2 + λ 2 , C 3 : X 2 > 2, C 4 : λ 2 = λ 1 + 3 and the objective function to maximize f (X 1 , X 2 ) = X 1 + X 2 . Writing X = {X 1 , X 2 }, D = {D 1 , D 2 }, Λ = {λ 1 , λ 2 }, U = {U 1 , U 2 }, and C X = {C 1 , C 2 , C 3 }, then (X , D, C X , Λ, U, f
) is a UCSOP. Note that C 3 is a certain constraint; C 1 and C 2 are both uncertain constraints because they contain uncertain parameters. C Λ = {C 4 } is the set of parameter constraints.

Constraint simulation

We now account for the parameters constraints by transforming the UCSOP into a set of tractable CSOPs instances. More formally, consider a UCSOP (X ,

D, C X ∪ C Λ , Λ, U, f ).
Definition 2 (instance of UCSOP). We denote n the number of variables, m the number of uncertain parameters, p the number of parameter constraints, and inst(U i ) a value within the range of an uncertainty set. An instance of an UCSOP is a certain CSOP (X , D, C X ) such that for each uncertain constraint C i (X 1 ..X m , λ 1 , ..λ m ), we have λ j = inst(U j ), such that ∀k ∈ {1, .., p}, the pa-

rameter constraint C k (λ 1 , ..λ m ) is satisfied. Example 2.
Continuing example 1, the UCSOP has two possible instances such that the parameter constraint λ 2 = λ 1 + 3 holds, given that

λ 1 ∈ U 1 , λ 2 ∈ U 2 .
The valid tuples (λ 1 , λ 2 ) are (2, 5), and [START_REF] Brown | Chapter 21: Uncertainty and Change Handbook of Constraint Programming[END_REF][START_REF] Raedt | Constraint Programming meets Machine Learning and Data Mining Dagstuhl seminar[END_REF]. The CSOP instances are:

C 1 : X 1 > 2, C 2 : X 1 = X 2 + 5, C 3 : X 2 > 2 and C 1 : X 1 > 3, C 2 : X 1 = X 2 + 6, C 3 : X 2 > 2
with the same objective function to maximize f = X 1 + X 2 .

The generator of CSOP instances extracts the parameter constraints, polynomial in the number of constraints in the worst case, then produces a set of parameter tuples that satisfy the parameter constraints. We can use a branch and bound search on the parameter constraints of the UCSOP. The constraint simulation then substitutes the tuple solutions onto the original UCSOP to search for a solution to each optimization problem, that is each CSOP. This is polynomial in the complexity of the UCSOP. The process is depicted in Algorithm 1.

Application

We illustrate the benefits of our approach by solving an uncertain constraint optimization problem, the traffic matrix estimation for the sigcomm4 problem, given in Fig. 1. The topology and data values can be found in [START_REF] Medina | Traffic Matrix Estimation: Existing Techniques and New Directions[END_REF][START_REF] Yorke-Smith | Certainty Closure: Reliable Constraint Reasoning with Uncertain Data[END_REF]. Given traffic measurements over each network link, and the traffic entering and leaving the network at the routers, we search the actual flow routed between every pair of routers. To find out how much traffic is exchanged between every pair of routers, we model the problem as an uncertain optimization problem that seeks the min and max flow between routers such that the traffic link and traffic conservation constraints hold. The traffic link constraints state that the sum of traffic using the link is equal to the measured flow. The traffic conservation constraints, two per router, state that the traffic entering the network must equal the traffic originating at the router, and the traffic leaving the router must equal the traffic whose destination is the router.

We compare three models. The first one does not consider any uncertain parameters and simplifies the model to only the variables in bold with coefficient 1. The traffic between routers takes a single fixed path, as implemented in [START_REF] Medina | Traffic Matrix Estimation: Existing Techniques and New Directions[END_REF]. The second model extends the first one with uncertain parameters but without the parameter dependency constraints. The third one is our approach with the parameter dependency constraints added. A parameter constraint, over the flow F AB , for instance, states that the coefficients representing one given route of traffic from A to B take the same value; and the sum of coefficients corresponding to different routes equals to 1. Note that the uncertain parameter equality constraints are already taken into account in the link traffic constraints. The uncertain parameters relative to flow distributions are commonly assumed between 30 and 70 % [START_REF] Yorke-Smith | Certainty Closure: Reliable Constraint Reasoning with Uncertain Data[END_REF].

Link traffic constraints: We first run the initial model and reproduced the results of [START_REF] Yorke-Smith | Certainty Closure: Reliable Constraint Reasoning with Uncertain Data[END_REF] in constant time. By adding the uncertain prameters the solution bounds got much larger as the space of potential solutions expanded. However when we run simulations using our approach and the linear EPLEX solver, and we were not able to find any solution to the model with dependency constraints. This shows the importance of taking into account such dependencies, indicating that the data provided match a single path routing algorithm for the sigcomm4 topology. After enlarging the interval bounds of the input data we were able to find a solution with a 50 % split of traffic, but none with 40 -60 or other combinations. Our approach showed the effectiveness and strong impact of taking into account dependency constraints with simulations.

[λ1 AB , λ1

Conclusion

In this paper we introduced an approach to account for dependency constraints among data parameters in an uncertain constraint problem. The approach follows an iterative process that first satisfies the dependency constraints using a branch and bound search. The solutions are then embedded to generate a set of CSPs to be solved. However this does not indicate the relationship between the dependent consistent parameters and possible solutions. We propose to use regression analysis to do so. The current case study showed that by embedding constraint dependencies only one instance had a solution. This was valuable information on its own, but limited the use of regression analysis. Further experimental studies are underway with applications in inventory management, problems clearly permeated with data uncertainty. Even though our approach has been applied to traditional constraint problems in mind, its benefits could be stronger on data mining applications with constraints [START_REF] Raedt | Constraint Programming meets Machine Learning and Data Mining Dagstuhl seminar[END_REF].

  565.0..637.0. The mean values are shown in the figure. Such models are used to find the flow matrix between any pair of routers. Commonly flow distribution is considered between 30 ad 70 percent. Thus on the link A → C the flow constraint is specified by: 0.3..0.7 * F AC + 0.3..0.7 * F BC + 0.3..0.7 * F AB + 0.3..0.7 * F AD = 565.0..637.0. A variable F AD denotes the traffic (unknonwn) from router A to router D.

Fig. 1 .

 1 Fig. 1. Sigcomm4 network topology and mean values for link traffic

Fig. 2 .

 2 Fig. 2. Left: Solution space. Tight and certain bounds for the decision variables: [0, 750] [0, 1000]. Right: Solutions vectors of problem instances with consistent parameter solutions

Fig. 3 .Example 1 .

 31 Fig. 3. Process

Algorithm 1 : 6 Si 7

 167 Generate and solve CSOPs from one UCSOPInput: A UCSOP (X , D, CX ∪ CΛ, Λ, U, f ) Output: Solutions to the CSOPs 1 SolsT uples ← ∅ 2 extract(CΛ) 3 T uples ← solveBB(Λ, U, CΛ) 4 for Ti ∈ T uples do 5 substitute Λ with Ti in (X , D, CX , Λ, f ) ← solveOpt(X , D, CX , Ti, f ) SolsT uples ← SolsT uples ∪ {(Si, Ti)} 8 return SampleSols

  AC , λ1 AD , λ2 AB , λ2 AC , λ2 AD ] ∈ 0.3..0.7 A → B λ1 AB * F AB + λ1 AC * FAC + λ1 AD * FAD = 309.0..328.0 B → A F BA + F CA + F DA + λ1 BC * FBC = 876.39..894.35 A → C λ2 AC * F AC + λ2 AD * F AD + λ2 AB * FAB + λ1 BC * FBC = 591.93..612.34 B → C λ2 BC * F BC + F BD + λ1 AC * FAC + λ1 AD * FAD = 543.30..562.61 C → B λ2 AB * FAB + F CB + F CA + F DA + F DB = 1143.27..1161.06 C → D F CD + F BD + F AD = 896.11..913.98 D → C F DC + F DB + F DA = 842.09..861.35 Parameter constraints λ1 AB + λ2 AB = 1, λ1 AC + λ2 AC = 1, λ1 AD + λ2 AD = 1, λ1 BC + λ2 BC = 1 FCB + FCA = 908.28..924.58 C destination FDC + FBC + FAC = 862.53..878.83 D origin FDC + FDB + FDA = 842.0..859.0 D destination FCD + FBD + FAD = 891.0..908.0

	Traffic conservation constraints
	A origin	FAD + FAC + FAB = 912.72..929.02
	A destination FDA + FCA + FBA = 874.70..891.00
	B origin	FBD + FBC + FBA = 845.56..861.86
	B destination FDB + FCB + FAB = 884.49..900.79
	C origin	FCD +

This research was partly support by the Marie Curie CIG grant, FP7-332683