Introduction

• Imitation across typologically distinct dialects  Requires approximating phonetic details of phonological structures not in the D1 system  D1-D2 imitation is not limited by strong category assimilation as in D1-D1 [START_REF] Cole | The phonology and phonetics of perceived prosody: What do listeners imitate[END_REF] or high cognitive demand as in L1-L2 [2]  Reveals the type and granularity of phonetic detail that can be accessed/implemented by the production system from recently experienced speech events

• D'Imperio & German (2015) [3]:
 Singapore English (SgE) speakers imitated early F0 peak timing of stress-initial American English (AmE) target words utterance-initially in declaratives  No phonetically similar pattern in SgE inventory

• Contour shape marks intonational contrasts in some varieties (Neapolitan Italian [START_REF] D'imperio | The interplay between tonal alignment and rise shape in the perception of two Neapolitan rising accents[END_REF], German [START_REF] Niebuhr | Are there "shapers" and "aligners"? Individual differences in signaling pitch accent category[END_REF],)

• Y/N questions in Singapore English vs. Am. English  Phonetic similarity: Final rising pattern  Contour shape: SgE has later rise with no dip (lacks L*), no inflection (i.e, concave versus s-shape)

Issues

• Contour shape: Can the contour shape of recently experienced tokens be accessed/implemented by the production system?

• Perceptual assimilation: Compared to peak timing, does phonetic similarity of Y/N contours limit speakers' ability to match phonetic detail of AmE targets?

Methods

•

  Tasks: Baseline reading (D1) + Imitation of AmE speaker • Target words: trisyllabic, initial stress, sentence-final • Participants: 18 males, bilingual in SgE/Mandarin • Measures: Mean F0 of 12 intervals within each target word • Comparison 1: F0 at timestep X condition • Comparison 2: Curvature (deg. of inflection) -3 rd coefficient of a 3 rd order polynomial regression-fitted to F0 timeseries

Figure 2 :Figure 3 :Figure 1 :

 231 Figure 2: Average F0 by time-normalized increment for AmE model, SgE baseline, and imitation task

Figure 4 :

 4 Figure 4: F0 plots of target items for the AmE speaker (red) and one SgE speaker (ID122) in the Baseline (green) and Imitation (blue) tasks

Figure 5 :

 5 Figure 5: Average by-item difference in coefficient (Imitation-Model) by self-reported weekly exposure to AmE.

Like a Square Peg in a Round Hole: Why Contour Shape Matters for Learning New Intonation Patterns

Mariapaola D'Imperio 1,2 & James Sneed German

Discussion

• Perceptual assimilation: Speakers imitated phonetic details of F0 scaling in different regions despite superficial phonetic similarity between D1/D2 contours • Contour shape is not immediately accessible by the production system  Speakers may not perceive differences in shape due to effects of perceptual assimilation  Producing complex contours may require articulatory practice

• Suggests that imitated tokens are variants of a D1 category whose scaling parameters have been adjusted to provide a better phonetic match to the AmE targets

• Recruitment of native categories does not preclude the imitation of phonetic details as suggested by [START_REF] Cole | The phonology and phonetics of perceived prosody: What do listeners imitate[END_REF]

Results

• F0 scaling (Comparison 1): At each timestep, speakers modified F0 towards the AmE targets (task x time interaction: est.max=26.1, tmax=7.83, p<0.0001)

• Curvature (Comparison 2): Speakers produced more highly inflected contours during imitation (est.=-4.52, t=2.35, p<0.05), high degree of overlap with baseline

• Item-by-item accuracy of curvature depends on selfreported exposure to AmE (r 2 =0.0755, p=0.14)


Keywords: optimization, discrete-event simulation, simulation optimization, routing problem. Résumé

When using optimization techniques based on mathematical models, we often need to make important simplifications. The solution thus provided, even if proven to be theoretically one of the best, might not be so good in practice. Simulation can be used to evaluate the actual performance of the solution. We propose here a coupling between optimization and simulation that tries to improve the solution provided by a mathematical model. This approach, named "model enhancement" here, still focuses on optimizing the theoretical objective function, contrary to the common optimization-simulation coupling that focuses on improving the objective function evaluated from simulation. We propose to illustrate this approach on a routing problem, and present numerical results on the quality of the solution and the efficiency of both coupling approaches.

Lorsqu'on utilise des techniques d'optimisation qui reposent sur des modèles mathématiques, on est souvent obligé de faire d'importantes simplifications. La solution ainsi produite, même s'il est théoriquement prouvé qu'elle est l'une des meilleures, peut ne pas être si bonne que cela en pratique. La simulation peut être employée pour évaluer la performance véritable de la solution. Nous proposons ici un couplage entre optimisation et simulation qui tente d'améliorer la solution produite par un modèle mathématique. Cette approche, nommée "enrichissement de modèle" ici, se concentre toujours sur l'optimisation de la fonction objectif théorique, contrairement au couplage optimisation-simulation classique qui se concentre sur l'amélioration de la fonction objectif évaluée par simulation. Nous proposons d'illustrer cette approche sur un problème de routage, et présentons des résultats numériques sur la qualité de la solution et l'efficacité des deux approches de couplage.

Mots clés : optimisation, simulation à événements discrets, couplage optimisation-simulation, problème de routage.

Introduction

The goal of this paper is to discuss a way to improve the practical quality of a solution provided by an optimization process. There are several advanced optimization techniques (mixed integer programming: branch-and-bound, branch-and-cut... [START_REF] Nemhauser | Integer and Combinatorial Optimization[END_REF], decomposition methods: Benders, Dantzig-Wolfe... [START_REF] Lasdon | Optimization Theory for Large Systems[END_REF]) that can solve efficiently problems formalized with mathematical models. Major results have been stated to prove the optimality or the quality of the solution (approximation algorithms can ensure the solution found to be close to the optimal solution according to a given precision [START_REF] Hochbaum | Approximation Algorithms for NP-Hard Problems[END_REF]), and to ensure the efficiency of the techniques (their complexity, their speed to converge to a solution...).

However, these methods have significant drawbacks when looking for their practical implementation. First, they are not robust to changes in the structure of the problem: adding a new kind of constraints might make the problem unsolvable with the previous optimization technique (e.g. linear constraints, solved with the simplex method, that become non-linear). Secondly, and more of concern in this paper, major simplifications on the modeling of the problem often have to be considered. As a result, a solution that is optimal in theory may not be so good in practice.

Therefore, we propose an optimization-simulation coupling called model enhancement, that attempts to reinforce the mathematical model in order to make the solution more adapted to practice than a straightforward optimization. Section 1 recalls the common optimization-simulation coupling sketch, usually called simulation optimization, and formalizes the problem that we propose to discuss in this article. Section 2 explains what straightforward optimization implies on the formulation and the solutions of the problem. Section 3 finally presents the idea of model enhancement, its goal and sketch. This proposition is illustrated in Section 4 through a routing problem. The approaches presented in the previous sections are implemented for this problem, and the quality of their solution and their computational efficiency are compared.

Simulation Optimization

An optimization problem can be expressed as finding the best solution x to a real problem (P r ), i.e. minimizing or maximizing a function f r (x). A solution x fits problem (P r ) if it satisfies a set of constraints that defines the space C r of feasible solutions.

(P r )    optimize f r (x) subject to x ∈ C r
During the modeling phase, the real problem (P r ) must be approximated. The common formulation of simulation optimization is expressed by problem (P s ). The fact that a function (resp. a space of solutions) a is approximated by another function (resp. another space of solutions) b is denoted b ∼ a.

(P s )        optimize f s (x) = g(x, λ), f s ∼ f r subject to x ∈ C s λ ∈ Λ s (x) ∼ C r
C s represents constraints on a solution x. It usually defines the basic structure of a feasible solution (for instance, the solution must be a cycle in a graph). λ is a vector of measures that is returned by the simulation for a solution x (cf. Figure 1).

Optimization Method Solution x

Simulation Evaluation

Estimation λ of performances Λ s (x) is the set of feasible solutions for λ, according to a given solution x. It is defined by implicit constraints of the simulation model (given a solution x, the simulation returns the estimation λ), and by explicit constraints on some performance measures (e.g. estimated delay must not exceed a given limit, or simply the solution is acceptable). That means Λ s (x) contains either one solution (x is feasible based on the simulation evaluation), or no solution (x is not feasible based on the simulation evaluation).

The objective function f r of the real problem is approximated by f s . We propose to parameterize this function on vector λ: f s (x) = g(x, λ). For instance, λ can represent estimated delays for solution x, and g(x, λ) an estimation of the quality of service of solution x according to these delays.

Simulation optimization explores the set of solutions C s to optimize f s . For each solution x, the simulation estimates vector λ. If λ satisfies all the constraints in Λ s (x), the solution x is accepted, and the objective function g(x, λ) is evaluated.

Several methods are proposed to solve problem (P s ). A classification in four major approaches can be found in [START_REF] Merkuryev | A Survey of Optimization Methods in Discrete Systems Simulation[END_REF] and [START_REF] Azadivar | A Tutorial on Simulation Optimization[END_REF]: gradient based search, stochastic approximation, response surface and heuristic search. These methods are robust to changes in the objective function or in the constraints of the problem. However, they only represent a few optimization techniques and their efficiency and convergence are not always ensured.

Straightforward Optimization

Optimization techniques, independent of simulation, usually need a mathematical model. This representation is also an approximation of the real problem (P r ).

(P o )    optimize f o (x), f o ∼ f r subject to x ∈ C o , C o ∼ C r
However, we can reasonably assume that the simulation optimization problem (P s ) is closer to the real problem than the straightforward optimization problem (P o ). For the purpose of model enhancement, we now make some assumptions on the structure of (P o ).

(P o )        optimize f o (x) = g(x, λ) subject to x ∈ C o ⊃ C s λ ∈ Λ o (x), Λ o ∼ Λ s
• The constraints C s describe the basic structure of a feasible solution. Hence, we can reasonably assume that the constraints defining C o are approximations, and even relaxations, of the constraints defining

C s . It means that C o ⊃ C s .
• We consider that the objective functions f o and f s are identical: f o (x) = g(x, λ). However, we assume that the space of solutions Λ o is an approximation of the space of solutions Λ s , which implicitly makes f o an approximation of f s .

Depending on the structure of the problem, various optimization techniques can be considered to solve (P o ). However, once a particular method m has been chosen to solve the problem, it is difficult to deal with changes on the kind of constraints of the problem. For model enhancement purpose, we consider changes only on the constraints that describe Λ o . Let us denote K m the set of all the families of constraints that can be managed by method m. That means problem

(P o ) is solvable by method m only if Λ o ∈ K m .

Model Enhancement

From the previous assumptions, if Λ o (x) is never empty, all solutions x in C o are feasible solutions of problem (P o ). As C o ⊃ C s , any solution of the simulation optimization problem (P s ) is a feasible solution of (P o ). In particular, any optimal solution x * s of (P s ) is a feasible solution of (P o ). The idea of model enhancement is to find the family of constraints Λ o ∈ K m such that the optimal solution x * o of (P o ) is one of the optimal solutions x * s of (P s ). We can state the model enhancement problem (P e ) as follows.

(P e )            optimize f s (x * o ) = g(x * o , λ s ) subject to Λ o ∈ K m , Λ o ∼ Λ s (x * o ; λ * o ) optimal solution of (P o ) λ s ∈ Λ s (x * o )
(P e ) is a very hard problem. However, one way to find a good solution to the problem may be to approximate Λ s by Λ o as precisely as possible. Thus, λ s and λ * o will have similar values and the theoretical evaluation g(x * o , λ * o ) of the optimal solution x * o of problem (P o ) will be close to its simulation evaluation g(x * o , λ s ). Algorithm 1 and Figure 2 describe a heuristic approach for model enhancement that iteratively modifies Λ o , based on the simulation evaluation λ s of an optimal solution of (P o ).

Constraints Λ o Solution x o Solution (x o ,λ o ) Optimization Method Solution (x * ,λ * ) Simulation Evaluation Constraints Λ k Model Enhancement Solution x * Estimation λ s of performances

Algorithm 1 Model enhancement heuristic.

k ← 0; let n be the maximal number of iterations; let Λ k o be an approximation of Λs;

repeat let (x * o , λ * o )
be an optimal solution of (Po) with Λo = Λ k o ; let λs be the simulation evaluation of

x * o ; Λ k+1 o ← h(Λ k o , λs); k ← k + 1; until |g(x * o , λ * o ) -g(x * o , λs)| < ε or k ≥ n;
Function h represents the way to modify Λ o at each iteration. It needs to be defined more precisely for any specific problem. In the next section, we propose to illustrate this heuristic on a bus routing problem.

Study of a Routing Problem

We propose now to study a bus routing problem in order to illustrate the discussion of the previous sections. We detail the simulation optimization method, a straightforward optimization approach and the model enhancement heuristic for this problem. We also present a practical comparison of these three approaches.

Problem Presentation

We focus on the following problem: let us consider a public transportation company in an urban network, such as a bus company. Basically, this company needs to design low cost bus routes while satisfying potential customers.

Let us consider a directed graph G = (V, E) where V is the set of vertexes and E the set of edges. Each vertex represents a potential bus stop or a crossroad in the real-life network. Each edge represents a road between two stops or crossroads.

We assume the customer demands are known, i.e. there is a description of the moves the customers need to perform in the urban network In this article, we limit the problem to find a transportation system Γ that meets the following requirements:

• Γ is a set of directed cycles in graph G (for clarity reasons, we consider further only one bus cycle);

• the length of the bus route, i.e. the time it takes to the bus to move along the route, must be less than a given threshold T ;

• Γ should maximize the satisfaction of the customers.

Let us denote t d the time it takes to a customer with demand d to travel through the network. His satisfaction can be represented by a function φ d (t d ) defined as follows: if t d ≤ 2t min d then the customer is fully satisfied and φ d (t d ) = 1; if t d ≥ 2t max d then the customer is not satisfied at all and φ d (t d ) = 0 ; and between these two limits, the closer to the minimum, the better the customer is satisfied. Figure 3 illustrates the satisfaction function. Finally, we define w i the time customers are waiting at a bus stop i. Back to our notations of the previous sections, λ is the vector of all the t d and the w i values. λ o will be their theoretical estimation (from optimization) and λ s their practical estimation (from simulation).

Let us denote x a solution to the problem, i.e. x e = 1 if edge e is part of the bus route, and x e = 0 otherwise. The objective is to maximize the satisfaction of the customers, i.e. function g(x, λ)

= d∈D Q d Φ d (t d ).

Simulation Optimization

We propose to solve the problem using the tabu search metaheuristic in the simulation optimization sketch (P s ). The tabu search was first introduced by [START_REF] Glover | Tabu Search[END_REF][START_REF] Herz | Tabu Search[END_REF]. It searches for a good solution x in the space of solutions C s . C s represents bus routes with their length below T . Moreover, we force the structure of the bus routes in C s to be a geodesic (the search is thus facilitated). A geodesic is a directed cycle defined by a given number of points called control points. Each control point is connected to its successor in the cycle by a shortest path (cf. Figure 4). Neighborhood structures for the heuristic rely on moving, adding or deleting a control point. The tabu list contains the control points that have been modified in the last few iterations. We have implemented a two-level heuristic using aspiration criteria (accepting a tabu move under some conditions) and diversification strategy (exploring another area of the space of solutions).

For a given solution x of the simulation optimization problem (P s ), simulation estimates the time of travel t d of the customers with demand d and their waiting time w i at bus stop i (reminder: all these values are stored in vector λ). Besides the implicit constraints of simulation, we consider no additional constraints in Λ s that can discard a solution x based on its estimation λ. That means any solution x ∈ C s is a feasible solution of (P s ) (it is a necessary condition for model enhancement to work).

We consider now a graph with 109 vertexes and 392 edges that represents Clermont-Ferrand downtown (cf. Figure 5), with 12 customer demands. Table 1 presents numerical results for the simulation optimization on this instance. In order to test various problem structures, the number of control points in a geodesic varies. We also consider several maximal length T for the bus route. The tabu search has been implemented with C++ and the simulation model with the B++ Simulator framework 3 Execution times can be more than a day. As our purpose here is only to know good practical solutions to compare with model enhancement's ones, we choose to limit the number of diversifications. Notice that the number of simulation evaluations to solve (P s ) is high, and without our restriction, it can reach more than 100000 evaluations. Hence, the solutions provided here are not always the best ones that simulation optimization can provide.

Straightforward Optimization

Our bus routing problem is strongly related to the well-known Vehicle Routing Problem (VRP) class. Several straightforward optimization techniques can be considered to solve the problem [START_REF] Toth | The Vehicle Routing Problem[END_REF]. Especially, [START_REF] Yon | Distance Minimization in Public Transportation Networks with Elastic Demands: Exact Model and Approached Methods[END_REF] propose a mixed integer programming formulation. They show that the tabu search (as defined in the previous section) can provide solutions very close to the optimal solution (when known) or to the best known solution (when it takes to much time or memory to get an optimal solution using mixed integer programming). Thus, we prefer to choose the tabu search as our method m to solve the optimization problem (P o ). It still searches a good solution x, but this time in the space of solutions C o . With mixed integer programming, C o would be larger than C s (C o ⊃ C s ), because instead of forcing the solution to be a geodesic, it would look for any directed cycle. With tabu search, it is easier to keep the geodesic structure, so

C o = C s .
Λ o is an approximation of Λ s . The implicit constraints of simulation that define Λ s are replaced by constraints to estimate the time of travel t d of the customers with demand d. Other constraints fix the waiting times w i to zero for any bus stop i, due to the assumption that there will be enough buses on the bus route for the waiting times to be insignificant. To sum up, Λ o approximates the way to estimate the travel times and sets the waiting times to zero.

Under the same conditions than problem (P s ), tests have been performed for (P o ). The problem is solved with tabu search. Table 2 shows the theoretical evaluation f o (x * o ) of the best solutions x * o found for (P o ), and their simulation evaluation f s (x * o ). The resolution is quite fast (around 10 seconds) compared to simulation optimization (several hours), but the solutions do not always have good simulation evaluations. Inside parenthesis is indicated the relative difference

(f s (x * o ) -f s (x * s ))/f s (x * s ).

Model Enhancement

Simulation optimization provides good practical solutions, but needs a very long time to execute. At the opposite, straightforward optimization is very fast, but provides poor practical solutions.

We describe now the model enhancement heuristic (as proposed in Section 4) applied to our bus routing problem, in order to improve the constraints defining Λ o so problem (P o ) provides good practical solutions.

In problem (P o ), we assumed that the waiting times w i are set to zero at any bus stop i. These constraints may make Λ o a poor approximation of Λ s . As the method used to solve (P o ) can deal with any constant waiting times w i = 0, we propose to modify these theoretical waiting times at each iteration of model enhancement (in order to make Λ o a better approximation of Λ s ).

Let us denote w k

i the waiting times for problem (P o ) at iteration k, and λ s = (w t), composed of vectors w = (w i ) i∈V (the estimated waiting times) and t = (t d ) d∈D (the estimated travel times), the simulation evaluation of the current theoretical solution x * o . If w i = 0, that means i was effectively used as a bus stop during the simulation. Thus, we propose to tend w k+1 i to w i as follows:

w k+1 i ← w k i + ∆(w i -w k i ).
If w i = 0, that means i is a vertex where customers never stop. However, we propose to tend w k+1 i to the mean M of the waiting times (estimated since the start of the algorithm) as follows:

w k+1 i ← w k i + ∆(M -w k i )
. ∆ < 1 is a progression step that needs to be tuned. One can choose ∆ either constant, or variable according to the number of iterations (in order to ensure some convergence). For this routing problem, we chose a constant ∆ = 0.1 and decide to stop the model enhancement after n = 100 iterations, or when there is some convergence, i.e. the difference between the theoretical evaluation f o (x * o ) = g(x * o , λ * o ) and the simulation evaluation f s (x * o ) = g(x * o , λ s ) is less than ε = 0.01. Algorithm 2 summarizes the model enhancement heuristic for our bus routing problem.

Under the same conditions than problems (P s ) and (P o ), tests have been performed for model enhancement. Table 3 indicates the theoretical evaluation of the best solutions x * e found. It shows that it is very close to the simulation evaluation of the same solution. In parenthesis, it indicates the relative improvement of the practical quality of the solution compared to straightforward optimization:

(f s (x * e ) -f o (x * o ))/f s (x * o ).
The number of iterations of the model enhancement process is also provided.

Algorithm 2

Model enhancement heuristic for bus routing problem.

k ← 0; for each vertex i ∈ V do w k i ← 0; repeat k ← k + 1; solve (Po) with waiting times w k i , i ∈ V ; let (x * o , λ * o )
be an optimal solution of (Po); let λs = (w t) be the simulation evaluation of x * o ; update mean M of the estimated waiting times;

for each vertex i ∈ V do if wi = 0 then w k+1 i ← w k i + ∆(wi -w k i ); else w k+1 i ← w k i + ∆(M -w k i ); end for; until |g(x * o , λ * o ) -g(x * o , λs)| < ε or k ≥ n; x * e ← x * o ;
The resolution is slower than straightforward optimization, but is really faster that simulation optimization. In fact, few calls to simulation evaluation are required, contrary to simulation optimization that needs a large amount of evaluations. The quality of the solution provided by model enhancement is usually close to the one provided by simulation optimization, and always improves the solution provided by straightforward optimization. Figure 6 shows the evolution and the convergence of both theoretical and simulation evaluations of solution x * o at each iteration k of the model enhancement process, for the search of a 10-points geodesic with T = 1000000. The convergence seems to be achieved quite easily in this case. However, Figure 7 shows the same kind of evolution for the search of a 7-points geodesic with T = 1000000. As shown in this figure, the heuristic sometimes oscillates between several good solutions, thus the convergence is more difficult to achieve.

Conclusion

Simulation optimization provides good practical solutions. However, it may take a long time to execute, with lots of simulation evaluations. At the opposite, for some problems, like the routing problem presented here, efficient theoretical approaches can efficiently solve simplified formulations. But, usually, they find solutions that are not so good in practice.

We propose in this article an approach called model enhancement that still focuses on the theoretical problem, and tries to improve its formulation in order to take into account practical aspects (estimated by simulation). The final goal is for the theoretical approach to provide good practical solutions.

We formalize model enhancement as problem (P e ) which, in some conditions, should provide the best practical solution (according to simulation evaluation). This problem seems actually very hard to solve. It proposes nevertheless a different way to think of optimization and simulation coupling. Therefore, we present a quite simple heuristic for model enhancement, illustrated on a routing problem. Experimental results show the potential of model enhancement, which needs further investigation.

Figure 1 :

 1 Figure 1: Simulation optimization sketch.

Figure 2 :

 2 Figure 2: Model enhancement heuristic.

Figure 3 :

 3 Figure 3: Satisfaction function for demand d.

Figure 4 :

 4 Figure 4: An example of 3points geodesic.

Figure 5 :

 5 Figure 5: Graph modeling Clermont-Ferrand (France) downtown.

Figure 6 :

 6 Figure 6: Solution estimation evolution with model enhancement, case 1.

Figure 7 :

 7 Figure 7: Solution estimation evolution with model enhancement, case 2.

  . A customer demand d ∈ D is defined by a tuple (o d ; s d ; Q d ; t min d ; t max d ), where o d ∈ V is the origin of the move, s d ∈ V the destination, Q d the throughput of customers for this demand. t min is the time it takes to a vehicle (such as a bus) to move from o d to s d ; and t max d is the time of travel of a pedestrian from o d to s d .

	d	and t max d	are reference times for the demand: t min d

Table 1 :

 1 . The tests have been performed on a Pentium Centrino 1.7 GHz with G++ 3.2 compiler. Simulation optimization numerical results.

	Control Length Bound Best Evaluation Number of CPU Time
	Points	T	f s (x * s )	Evaluations	(hours)
	5	700000	10.33	3793	5h04
	5	800000	10.30	5203	7h04
	5	900000	10.32	4807	6h08
	5	1000000	10.32	7573	9h44
	7	700000	10.32	8201	10h44
	7	800000	10.34	6092	8h16
	7	900000	10.32	6749	8h56
	7	1000000	10.31	7883	10h28
	10	700000	10.32	8843	11h20
	10	800000	10.33	9706	10h12
	10	900000	10.31	10732	13h52
	10	1000000	10.34	8812	11h04
	15	700000	10.31	6074	8h20
	15	800000	10.32	8759	10h08
	15	900000	10.33	10699	11h16
	15	1000000	10.33	10302	11h08

Table 2 :

 2 Straightforward optimization numerical results.

		Length	Straightforward Optimization	Simulation Optimization
	Control	Bound	Theoretical Eval. Simulation Eval.	Best Evaluation	CPU Time
	Points	T	f o (x * o )	f s (x * o )	f s (x * s )	(seconds)
	5	700000	11.99	10.29 (-0.4%)	10.33	5.0
	5	800000	11.99	10.25 (-0.5%)	10.30	5.0
	5	900000	11.99	9.62 (-6.8%)	10.32	5.1
	5	1000000	11.99	10.08 (-2.4%)	10.32	5.3
	7	700000	11.99	10.31 (-0.1%)	10.32	6.8
	7	800000	11.99	9.92 (-4.1%)	10.34	7.1
	7	900000	11.98	9.79 (-5.1%)	10.32	7.5
	7	1000000	12.00	9.43 (-8.5%)	10.31	7.6
	10	700000	11.97	10.18 (-1.4%)	10.32	7.7
	10	800000	11.99	9.92 (-4.0%)	10.33	8.9
	10	900000	11.99	10.05 (-2.5%)	10.31	9.4
	10	1000000	12.00	9.33 (-9.8%)	10.34	10.3
	15	700000	11.99	10.29 (-0.2%)	10.31	8.0
	15	800000	11.99	10.01 (-3.0%)	10.32	9.0
	15	900000	11.99	9.85 (-4.6%)	10.33	9.8
	15	1000000	12.00	9.56 (-7.5%)	10.33	10.8

Table 3 :

 3 Model enhancement numerical results.

Information available at http://frog.isima.fr/bruno/?doc=bpp_library+ch=simulator.

Acknowledgements / Remerciements

We would like to thank Antoine Mahul, PhD Student at Blaise Pascal University, Clermont-Ferrand, France, for his invaluable advice to formalize model enhancement.


Keywords: minimum cost tension, binary costs, two-terminal series-parallel graphs tension de coût minimum, coûts binaires, graphes série-parallèles

The aggregation technique, dedicated to two-terminal series-parallel graphs (or TTSP-graphs) and introduced lately to solve the minimum piecewise linear cost tension problem, is adapted here to solve the minimum binary cost tension problem (or BCT problem). Even on TTSP-graphs, the BCT problem has been proved to be NP-complete. As far as we know, the aggregation is the only algorithm, with mixed integer programming, proposed to solve exactly the BCT problem on TTSP-graphs. A comparison of the efficiency of both methods is presented here.

Introduction

The study of tension problems in graphs is motivated here by synchronization problems in hypermedia documents [START_REF] Bachelet | Modélisation et optimisation de problèmes de synchronisation dans les documents hypermédia[END_REF]. These documents are composed of various media objects such as audio, video, text, image, applet... Authors need powerful tools to schedule automatically the temporal specifications of these objects in a document. Any media object u has an ideal duration o u and an interval [a u ; b u ] in which its effective (i.e. scheduled) duration can vary. The author also specifies temporal constraints in order to express the way the presentation of the document should happen. The problem is finally to schedule the duration of each media object so that it satisfies both the tolerance intervals and the temporal constraints. This problem can be interpreted as a minimum cost tension problem (or MCT problem) in a graph [START_REF] Berge | Programmes, jeux et réseaux de transport[END_REF]. Let G = (X; U ) be a graph, with X the set of nodes, U the set of arcs, m = |U | and n = |X|. The nodes represent events in the hypermedia presentation (i.e. the start or end of presentation of a media object), and the arcs express temporal constraints between two events (i.e. precedence and duration between two events). Let π : X -→ R be a function that assigns a potential to each node of the graph. It represents the date scheduled for each event. Hence, the tension θ u of an arc u = (x; y), which is the difference of potentials θ u = π yπ x , is the duration between events x and y, and is constrained to θ u ∈ [a u ; b u ] ⊂ R. The minimum cost tension problem can finally be modeled as:

(P M CT )                minimize u∈U c u (θ u ) with π y -π x = θ (x;y) , ∀(x; y) ∈ U a u ≤ θ u ≤ b u , ∀u ∈ U
To measure the quality of a document, many proposals were made for c u . The first studies consider piecewise linear costs, with a minimum for o u [START_REF] Buchanan | Specifying Temporal Behavior in Hypermedia Documents[END_REF][START_REF] Kim | Multimedia Documents with Elastic Time[END_REF][START_REF] Bachelet | Modélisation et optimisation de problèmes de synchronisation dans les documents hypermédia[END_REF]. The problem is thus expressed as a linear program, and many polynomial algorithms were developed for this specific problem [START_REF] Hadjiat | A Strongly Polynomial Algorithm for the Minimum Cost Tension Problem[END_REF][START_REF] Ravindra | Solving the Convex Cost Integer Dual Network Flow Problem[END_REF]. [START_REF] Bachelet | Minimum Convex-Cost Tension Problems on Series-Parallel Graphs[END_REF] proposed an aggregation method to solve the minimum convex piecewise linear cost tension problem (or CPLCT problem) on two-terminal series-parallel graphs (or TTSP-graphs). It was shown to be competitive on this class of graphs with the best dual cost-scaling algorithms [START_REF] Ravindra | Solving the Convex Cost Integer Dual Network Flow Problem[END_REF].

However, the number of objects that need to be modified (i.e. that are not scheduled at their ideal duration) is also relevant for hypermedia synchronization [START_REF] Medina | Automatic Scheduling of Hypermedia Documents with Elastic Times[END_REF]. Altering the duration of a media object is CPU consuming, thus in a real time context, minimizing this operation is important. We propose here to develop an aggregation method for the minimum binary cost tension problem (or BCT problem) on TTSP-graphs, where the cost functions are defined as:

c u (θ u ) = 0, if θ u = o u 1, if θ u = o u (1)
Due to its discrete nature, this problem is NP-complete [START_REF] Kumar | An Efficient Scheme to Solve Two Problems for Two-Terminal Series Parallel Graphs[END_REF]. Lately, it was also proved that it is NP-complete on TTSP-graphs [START_REF] Celso | On the Complexity of Scheduling with Elastic Times[END_REF]. Our interest in this class of graphs is explained by the specific structure of the temporal constraints used in hypermedia synchronization, which leads us to manipulate graphs that are very close to TTSP-graphs [START_REF] Bachelet | Minimum Convex-Cost Tension Problems on Series-Parallel Graphs[END_REF].

Section 2 proposes an overview of the TTSP-graphs and the aggregation approach. Section 3 explains how to adapt the method to the BCT problem. Then, comparative numerical results with mixed integer programming are presented in Section 4. Section 5 shows that the aggregation algorithm can be used to solve the BCT problem on any elementary cycle, a subproblem that can be significant to solve the BCT problem on any graph (i.e. without any specific structure) [START_REF] Bachelet | Hypermedia Synchronization: Modeling and Optimization with Graphs[END_REF]. We conclude with a discussion on some leads to solve the BCT problem on quasi-k series-parallel graphs and maybe on any graph, using the aggregation technique.

Aggregation Method

Two-Terminal Series-Parallel Graphs

A common definition of TTSP-graphs is based on a recursive construction of the graphs (e.g. [START_REF] Eppstein | Parallel Recognition of Series-Parallel Graphs[END_REF], or [START_REF] Valdes | The Recognition of Series Parallel Digraphs[END_REF] with the edge series-parallel digraphs) that is very intuitive and close to the way synchronization constraints are built in a hypermedia document. A digraph G is two-terminal series-parallel, also called TTSP-graph, if it is obtained from a graph with only two nodes linked by an arc, applying recursively the two following operations:

• The series composition, applied upon an arc u = (x; y), creates a new node z and replaces u by two arcs u 1 = (x; z) and u 2 = (z; y) (cf. Figure 1a). We call series the relation that binds u 1 and u 2 and denote it u 1 + u 2 .

• The parallel composition, applied upon an arc u = (x; y), duplicates u by creating a new one v = (x; y) (cf. Figure 1b). We call parallel the relation that binds u and v and denote it u//v. The series and parallel relations are gathered under the term SP-relations. During the construction process, a SP-relation that binds two arcs can become a relation between two TTSPsubgraphs. The SP-relations are binary operations, so we can represent a TTSP-graph by a binary tree called decomposition binary tree [START_REF] Kumar | An Efficient Scheme to Solve Two Problems for Two-Terminal Series Parallel Graphs[END_REF] or SP-tree, as illustrated by Figure 2. [START_REF] Valdes | The Recognition of Series Parallel Digraphs[END_REF][START_REF] Schoenmakers | A New Algorithm for the Recognition of Series Parallel Graphs[END_REF][START_REF] Eppstein | Parallel Recognition of Series-Parallel Graphs[END_REF][START_REF] Bachelet | Minimum Convex Piecewise Linear Cost Tension Problem on Quasi-k Series-Parallel Graphs[END_REF] propose different ways to find such a tree in linear time. For the CPLCT problem, numerical results in [START_REF] Bachelet | Minimum Convex-Cost Tension Problems on Series-Parallel Graphs[END_REF] show that linear programming and the outof-kilter method take advantage of the particular structure of the TTSP-graphs and behave really better on this class of graphs than on non-specific graphs. However, the dual cost-scaling approach does not work that well on these instances, whereas it proves to be the most efficient for nonspecific graphs. Finally, the aggregation is the method that presents the best performance on TTSP-graphs.

Aggregation Method

The aggregation method, that allows to solve minimum cost tension problems only on TTSPgraphs, has been introduced in [START_REF] Bachelet | Minimum Convex-Cost Tension Problems on Series-Parallel Graphs[END_REF]. The algorithm works on a SP-tree T of the TTSP-graph G and is recursive: considering a SP-relation in T , it assumes that the optimal tensions of the two subgraphs implied in the relation are known, and from them, it is possible to quickly build the optimal tension of the whole SP-relation. Hence, starting from the leaves of T , the optimal tension of each SP-relation is built to finally reach the root of the tree T .

From the definition of a TTSP-graph, it is obvious that a TTSP-graph has only one source node (i.e. without any predecessor) and only one target node (i.e. without any successor). Hence, the main tension θ of a TTSP-graph is defined as the tension between its source s and target t, i.e. θ = π tπ s . To get an efficient algorithm, the minimum cost function C G of a TTSP-graph G must be defined. This function represents the cost of the optimal tension where the main tension is forced to a given value:

C G (x) = min{ u∈U c u (θ u ) | θ a tension, θ = x}
Let us consider two TTSP-subgraphs G 1 and G 2 , and suppose that their minimum cost functions C G 1 and C G 2 are known. The minimum cost function

C G 1 +G 2 of the SP-relation G 1 + G 2 is: C G 1 +G 2 (x) = min x=x 1 +x 2 C G 1 (x 1 ) + C G 2 (x 2 ) Thus, C G 1 +G 2 is the inf-convolution C G 1 C G 2 . The minimum cost function C G 1 //G 2 of the SP-relation G 1 //G 2 is: C G 1 //G 2 (x) = C G 1 (x) + C G 2 (x)
If all the functions c u are convex, as in the CPLCT problem, the minimum cost function C G is convex. From this assessment, a simple recursive algorithm [START_REF] Bachelet | Minimum Convex-Cost Tension Problems on Series-Parallel Graphs[END_REF] for the CPLCT problem has been proposed to build the minimum cost function C G of a TTSP-graph G.

Aggregation for the BCT Problem

In the BCT problem, the minimum cost functions have no specific properties, they are neither convex, nor continuous. Moreover, for each aggregation, the minimum cost functions of the subgraphs must be entirely expressed, because any part may be of interest in the whole process. As we know that the problem is NP-complete, it should be expected that the size to store the detail of a minimum cost function will grow exponentially (in theory) with the size of the graph. To sum up, computing the minimum cost function can be done the rough way and can lead to an explosion in time and space of the algorithm. That justifies the modeling we choose here to represent a minimum cost function.

We consider a minimum cost function C G as a set of cases, a case e being a set of arcs S e of G scheduled at their ideal value. Let I G = [M IN G ; M AX G ] be the interval in which C G is defined, and W G the maximum value of C G . With each case e is associated the feasibility interval i e = [min e ; max e ] (of the main tension θ) in which e can occur, and its cost c e . As an example, we suppose a single arc u. Its minimum cost function C u is defined as follows:

C u    W u = 1 ; I u = [a u ; b u ] Case 1: S 1 = {u} ; c 1 = 0 ; i 1 = [o u ; o u ]
As shown in Figure 3a, the value of C u is usually W u = 1 (the worst case). If case 1 occurs, i.e. θ u = o u , then the cost is 0.

Parallel Aggregation

In this section, we explain how to build the minimum cost function C G of a graph G that is the parallel relation G 1 //G 2 where G 1 and G 2 are two TTSP-subgraphs with their minimum cost functions C 1 and C 2 respectively. But first, let us consider G 1 and G 2 as single arcs u and v with their minimum cost functions C u and C v defined as above for u and as follows for v (cf. Figure 3b): We define now the minimum cost function C u//v of the parallel aggregation of u and v. In the general case, the cost of the function is W u + W v = 2 (the sum of the general cases of both arcs). Then we must identify all the particular cases:

C v    W v = 1 ; I v = [a v ; b v ] Case 2: S 2 = {v} ; c 2 = 0 ; i 2 = [o v ; o v ] o v b v a v 1 θ v C v o u b u a u 1 θ u C u b u a v 1 θ u // v o u o v C u // v 2 (a) (b) (c)
• Case 1': Case 1 for u and general case for v. The cost is c 1 + W v and the case is feasible only when both cases occur, i.e. when the main tension θ u//v ∈ i 1 ∩ I v .

• Case 2': General case for u and case 2 for v. The cost is W u + c 2 and the case is feasible when θ u//v ∈ I u ∩ i 2 .

• Case 3: Case 1 for u and case 2 for v. The cost is c 1 + c 2 and the case is feasible when

θ u//v ∈ i 1 ∩ i 2 .
To sum up, the minimum cost function C u//v is defined as follows (see also Figure 3c):

C u//v            W u//v = W u + W v ; I u//v = I u ∩ I v Case 1': S 1 = {u} ; c 1 = c 1 + W v ; i 1 = i 1 ∩ I v Case 2': S 2 = {v} ; c 2 = c 2 + W u ; i 2 = i 2 ∩ I u Case 3 : S 3 = {u; v} ; c 3 = c 1 + c 2 ; i 3 = i 1 ∩ i 2
The idea here is to check all the possible cases and determine their feasibility and their cost. Algorithm 1 explains the general process to build the minimum cost function However, just from the simple example above, it is obvious that for practical instances, lots of combinations of cases will not be possible in parallel (their feasibility interval will be empty). For instance, it seems reasonable to think that case 3 happens rarely in practice.

C 1//2 of the parallel relation G = G 1 //G 2 , from the minimum cost functions C 1 and C 2 of its TTSP-subgraphs G 1 and G 2 . Algorithm 1 Parallel aggregation. if I 1 ∩ I 2 = ∅ then W 1//2 ← W 1 + W 2 ; I 1//2 ←

Cases Redundancy and Overlapping

Moreover, the number of cases might be virtually overestimated: it is possible, in the same minimum cost function, to get two cases with the same interval. In order to avoid this redundancy (and later useless combinations of cases), one of the cases must be removed: the one with the worst cost (if they are equal, it does not matter which one to eliminate). For instance, if we suppose in the example above that o u = o v , then cases 1' and 2' become redundant with case 3, so both of them must be removed.

We choose to detect redundancy each time a case e is added to the minimum cost function of a series or parallel relation. We oppose the case e with each case f already in the minimum cost function of the SP-relation. There are three possibilities:

• if c e ≥ c f and i e ⊆ i f , there is redundancy of the cases, then case e is not added;

• if c e ≤ c f and i e ⊇ i f , there is redundancy of the cases, then case f is removed and e is added;

• otherwise, there may be overlapping of the cases, but e is added.

Notice that we do not attempt to build a minimal set of cases for a SP-relation, i.e. a set of disjoint, i.e. non-overlapping, cases (remark: this is not the set with the minimal number of cases; if you look at Figure 3c, the minimal set would have 5 pieces, whereas C u//v , as we build it, has only 3 pieces). As it seems difficult to maintain this minimal set (that is not even the set with the minimum number of pieces), we decide to deal with cases that are overlapping (e.g. cases like e and f where i e ∩ i f = ∅, but neither i e ⊆ i f nor i f ⊆ i e ).

Series Aggregation

In this section, we explain how to build the minimum cost function C G of a graph G that is the series relation G 1 + G 2 where G 1 and G 2 are two TTSP-subgraphs with their minimum cost functions C 1 and C 2 respectively. But first, let us consider G 1 and G 2 as single arcs u and v with their minimum cost functions C u and C v defined as previously. We define then the minimum cost function C u+v of the series aggregation of u and v. In the general case, the cost of the function is W u + W v = 2 (the sum of the general cases of both arcs). Then we must identify all the particular cases:

• Case 1': Case 1 for u and general case for v. The cost is c 1 + W v and the case is feasible on the interval of case 1 "plus" the interval of the general case for v, i.e. when the main tension

θ u+v ∈ [min 1 + M IN v ; max 1 + M AX v ].
• Case 2': General case for u and case 2 for v. The cost is W u + c 2 and the case is feasible when

θ u+v ∈ [M IN u + min 2 ; M AX u + max 2 ].
• Case 3: Case 1 for u and case 2 for v. The cost is c 1 + c 2 and the case is feasible when

θ u+v ∈ [min 1 + min 2 ; max 1 + max 2 ].
To sum up, the minimum cost function C u+v is defined as follows (see also Figure 4):

C u+v                            W u+v = W u + W v ; I u+v = [M IN u + M IN v ; M AX u + M AX v ] = [a u + a v ; b u + b v ] Case 1': {u} ; c 1 = c 1 + W v ; i 1 = [min 1 + M IN v ; max 1 + M AX v ] = [o u + a v ; o u + b v ] Case 2': {v} ; c 2 = c 2 + W u ; i 2 = [min 2 + M IN u ; max 2 + M AX u ] = [a u + o v ; b u + o v ] Case 3: {u; v} ; c 3 = c 1 + c 2 ; i 3 = [min 1 + min 2 ; max 1 + max 2 ] = [o u + o v ; o u + o v ]
The idea here is similar to the parallel aggregation. It is to enumerate all the cases and determine their cost (they are always feasible). Algorithm 2 explains the general process to build the minimum cost function C 1+2 of the series relation G = G 1 + G 2 , from the minimum cost functions C 1 and C 2 of its TTSP-subgraphs G 1 and G 2 . At the opposite of the parallel aggregation, all the cases are possible. However, it is still possible to detect redundant cases to remove. As an indication, on a practical instance of TTSPgraph with 20 nodes and 40 arcs, we observe more than 2 million cases in the final minimum cost function, if we keep the redundant cases. With the constant elimination of these cases, we observe less than a hundred cases in the final minimum cost function (cf. Table 1).

a u + o v a u + a v o u + o v o u + b v o u + a v b u + o v b u + b v 1 2 C u + v θ u + v
Algorithm 2 Series aggregation.

W 1+2 ← W 1 + W 2 ; I 1+2 ← [M IN 1 + M IN 2 ; M AX 1 + M AX

Conclusion Proposition 3

The aggregation method, for the BCT problem, generates a minimum cost function with at most 2 m -1 cases, and requires O(2 m ) operations.

Proof. We can establish that for a TTSP-graph G k with k arcs, at most 2 k -1 cases compose the minimum cost function C k of G k . For k = 1, it is obvious. Assume now that the property is true for any TTSP-graph with at most k arcs, and consider a TTSP-graph G k+1 with k + 1 arcs. By definition of TTSP-graphs, it is either a series or a parallel composition of two TTSP-graphs G p and G q , with p and q arcs respectively, such that p + q = k + 1. From propositions 1 and 2, the minimum cost function of G k+1 has (2 p -1) + ( 2

q -1) + (2 p -1)(2 q -1) = 2 p+q -1 = 2 k+1 -1 cases.
Also from propositions 1 and 2, each composition i needs O(2 k i ) operations, where k i is the number of arcs in the composition i. As there are m -1 SP-relations in the TTSP-graph [START_REF] Bachelet | Minimum Convex-Cost Tension Problems on Series-Parallel Graphs[END_REF], the whole aggregation method finally requires O( m-1 i=1 2 k i ) operations (we suppose that the compositions are numbered in the same order they are performed in the aggregation process). It is known that m i=1 2 i < 2 m+1 , and it can be verified by recurrence that m-1 i=1 2 k i ≤ m i=1 2 i , thus the whole aggregation method requires O(2 m ) operations.

Numerical Results

As the complexity presented in the previous section represents worst case situations, we must study the practical behavior of the algorithm. As far as we know, the only other method that solves the BCT problem is mixed integer programming. As proposed in [START_REF] Medina | Automatic Scheduling of Hypermedia Documents with Elastic Times[END_REF], the BCT problem can be modeled as a mixed integer program (P BCT ). It is based on the generic (P M CT ) program defined in Section 1, with the binary cost functions c u defined by formula (1). These c u functions are modeled with binary variables y u and additional constraints (a), (b) and (e).

(P BCT )                                minimize u∈U y u with -θ u -(o u -a u )y u ≤ -o u , ∀u ∈ U (a) θ u -(b u -o u )y u ≤ o u , ∀u ∈ U (b) π y -π x = θ (x;y) , ∀(x; y) ∈ U (c) a u ≤ θ u ≤ b u , ∀u ∈ U (d) y u ∈ {0, 1}, ∀u ∈ U (e)
The following tables present a practical comparison of the aggregation technique with mixed integer programming, which is always difficult and questionable due to all kinds of biases. But the goal here is to get an idea of how the methods behave on TTSP-graphs. Results are expressed in seconds on an Intel Xeon 2.4 GHz processor under a Gentoo Linux operating system. We used GNU C++ 3.3 compiler and its object-oriented features to implement the methods, linked to the CPLEX 8.0 Callable Library for mixed integer programming.

Results are based on series of 30 tests on randomly generated graphs 3,4 . To generate an instance, the following parameters must be given: the number of nodes n, the number of arcs m and the tension bound A = max u∈U b u . A TTSP-graph structure with n nodes and m arcs is randomly built, based on the constructive definition of TTSP-graphs in Section 2. Then, using the topological order of the nodes, a potential π x is affected to each node x, such that θ u = π yπ x < A for each arc u = (x; y). The bounds a u and b u are randomly chosen to satisfy 0

≤ a u ≤ θ u ≤ b u ≤ A. Finally, the ideal tension o u is randomly chosen in the [a u ; b u ] interval.
Table 1 shows results where the size of the graphs varies, with A = 1000. Each value in columns "CPLEX" and "Aggregation" is the mean of a series of tests, and the number in parentheses is the associated standard deviation. Due to the combinatorial aspect of the problem, the time to solve an instance can vary significantly in a same series. However, these results allow to catch the general evolution of the computation time for each method. In order to compare the methods, we propose two last columns in the table to present the relative time difference between the methods. We denote t aggregation and t CP LEX the resolution times of the aggregation and linear programming respectively. The first column is the mean of where linear programming is faster than the aggregation. We choose to present the relative time difference instead of a time ratio like time CP LEX time aggregation to compare the methods, because extreme situations like a very short time for the aggregation and a long time for CPLEX on the same instance makes the mean estimation useless. If the relative difference is close to 0, that means the resolution times tend to be similar. At the opposite, if the difference is close to 1, that means the resolution times tend to be infinitely different. We also indicate into parentheses the number of times a method is faster than the other. Notice that when the resolution times are identical, it is considered that linear programming is faster.

With these informations, it appears that the aggregation is faster than mixed integer programming for most of the instances. The fact that linear programming is faster in some cases is due to the fact that the aggregation can not deal very efficiently with a chain of series compositions: in a parallel relation, there are cases that can immediately be detected infeasible, whereas in a series relation, all the cases are potentially feasible, but many of them will be eliminated later in the aggregation process. Thus, even if its theoretical complexity is exponential, the aggregation provides a quite efficient way to solve the BCT problem on TTSP-graphs with a size far above what is requested in hypermedia authoring: a 50 nodes and 100 arcs graph is already considered a large instance.

Even in the same series, some instances are easier to solve. If we look at the number of cases generated by the aggregation, there is also a significant variation among the instances of a same series. However, the number of cases is not clearly related to the resolution time. As the number of non-redundant cases is not significant to determine the complexity of an instance, we think that the aggregation explores more redundant cases in the difficult instances. Identifying precisely the reasons of this behavior is not that obvious. Intuitively, the ideal tension is crucial: for instance, there are situations where the tension can not be fixed to its ideal value. The aggregation and mixed integer programming have their own mechanism (the redundancy detection for the aggregation) to detect some situations more easily than others.

To show that the tension data are significant in the resolution time of both methods, Table 2 proposes results where the tension bound A varies. The aggregation method is still more efficient than mixed integer programming in most cases, but the difficulty to solve the instances, for both methods, increases with A. [START_REF] Bachelet | Hypermedia Synchronization: Modeling and Optimization with Graphs[END_REF] explains that solving the BCT problem on an elementary cycle C of a graph G can be useful to find cuts to add in the mixed integer program that models the BCT problem on the whole graph G. However, in this article, the problem was solved using mixed integer programming. We propose here to use the aggregation technique to solve exactly, and more efficiently than linear programming, the BCT problem on an elementary cycle. The idea is simply to transform the cycle C (Figure 5a) into a TTSP-graph H (Figure 5b), making the BCT problem (P ) on H equivalent to the BCT problem (P ) on C. To perform the transformation, the orientation of some arcs of C must be changed so the cycle becomes two directed paths P 1 and P 2 in parallel, e.g. H = P 1 //P 2 (cf. Figure 5). Thus, H is two-terminal series-parallel and in order to make (P ) equivalent to (P ), the tension data of any arc u that has been reversed must be modified as follows (cf. Figure 5): its interval [a u ; b u ] becomes [-b u ; -a u ] and its ideal tension o u becomes -o u .

BCT Problem on an Elementary Cycle

It is easy to check that the constraints and the objective functions of both problems are equivalent. Numerical results for elementary cycles (not introduced in this paper because very similar to those presented for TTSP-graphs in the previous section) show that this method to solve the BCT problem on an elementary cycle is more efficient in practice than mixed integer programming.

Conclusion

This article provides a first alternative to mixed integer programming in solving the BCT problem on TTSP-graphs. Moreover, the practical efficiency of the aggregation method is far above mixed integer programming. It can thus be useful in the resolution of the BCT problem on non-specific graphs: as shown in Section 5, it provides a way to solve the problem on an elementary cycle, which is relevant to generate cuts for the linear program of the BCT problem [START_REF] Bachelet | Hypermedia Synchronization: Modeling and Optimization with Graphs[END_REF]. We also hope to find better cuts with the aggregation algorithm: the BCT problem can be solved optimally and quite quickly for TTSP-subgraphs of any graph, which provides bounds for new constraints.

The aggregation method results in more than just an optimal tension. As presented in this article, it provides aggregated information, which allows to adapt optimally the tension of a TTSPgraph to any main tension in polynomial time 5 . It is the idea of the reconstruction technique that solves the CPLCT problem on quasi-k series-parallel graphs (or k-QSP graphs) [START_REF] Bachelet | Minimum Convex Piecewise Linear Cost Tension Problem on Quasi-k Series-Parallel Graphs[END_REF]. A graph is k-QSP if the removal of a minimal subset of arcs (of size k) makes the remainder of the graph twoterminal series-parallel. For the CPLCT problem, the out-of-kilter technique can use efficiently the aggregated information provided by the aggregation technique on TTSP-subgraphs. For the BCT problem, no equivalent method actually exists. However, as the aggregation technique is really efficient for the BCT problem, the study of a reconstruction approach for k-QSP graphs seems interesting.

2 Figure 1 :

 21 Figure 1: Series and parallel compositions.

Figure 2 :

 2 Figure 2: Example of SP-tree.

Figure 3 :

 3 Figure 3: An example of parallel aggregation.

Figure 4 :

 4 Figure 4: An example of series aggregation.

Figure 5 :

 5 Figure 5: Transformation of an elementary cycle into a TTSP-graph.

  I 1 ∩ I 2 ; for all cases e in C 1 such that ie ∩ I 2 = ∅ do [All the cases of G 1 combined with the general case of G [All the cases of G 1 combined with all the cases of G 2 ] for all pairs of cases e in C 1 and f in C 2 such that ie ∩ i f = ∅ do let e be a new case of C 1//2 ; S Let n 1 and n 2 be the numbers of cases in C 1 and C 2 respectively. The number of cases of C 1//2 can not exceed n 1 + n 2 + n 1 × n 2 , and the parallel aggregation G 1 //G 2 requires O(n 1 × n 2 ) operations.Proof. Algorithm 1 considers n 1 + n 2 + n 1 × n 2 cases (the single cases + the combinations of the cases).

	f ;
	end for;
	end if;
	Proposition 1

2 ] let e be a new case of C 1//2 ; S e ← Se; c e ← ce + W 2 ; i e ← ie ∩ I 2 ; end for; for all cases e in C 2 such that ie ∩ I 1 = ∅ do [All the cases of G 2 combined with the general case of G 1 ] let e be a new case of C 1//2 ; S e ← Se; c e ← ce + W 1 ; i e ← ie ∩ I 1 ; end for; e ← Se ∪ S f ; c e ← ce + c f ; i e ← ie ∩ i

  for all cases e in C 2 do [All the cases of G 2 combined with the general case of G 1 ] let e be a new case of C 1//2 ; S e ← Se; c e ← ce + W 1 ; i e ← [mine + M IN 1 ; maxe + M AX 1 ]; end for; for all pairs of cases e in C 1 and f in C 2 do [All the cases of G 1 combined with all the cases of G 2 ] let e be a new case of C 1+2 ; S e ← Se ∪ S f ; c e ← ce + c f ; i e ← [mine + min f ; maxe + max f ]; end for;

2 ]; for all cases e in C 1 do [All the cases of G 1 combined with the general case of G 2 ] let e be a new case of C 1+2 ; S e ← Se; c e ← ce + W 2 ; i e ← [mine + M IN 2 ; maxe + M AX 2 ]; end for;

Table 1 :

 1 Numerical results, graph size influence.

	Nodes	Arcs	CPLEX		Aggregation			Time Difference
	n	m		Time		Time	Cases	Aggregation	CPLEX
	10	20	0.01	(0.01)	0.01	(0.01)	32.3	(35.9)		(0/30)	0.000	(30/30)
	20	40	0.03	(0.03)	0.01	(0.01)	86.4	(68.2)	0.637	(24/30)	0.000	(6/30)
	30	60	0.09	(0.14)	0.01	(0.02)	143	(157)	0.749	(26/30)	0.396	(4/30)
	40	80	0.43	(0.92)	0.03	(0.03)	231	(264)	0.861	(25/30)	0.290	(5/30)
	50	100	4.2	(14.9)	0.08	(0.13)	342	(365)	0.841	(27/30)	0.447	(3/30)
	60	120	9.1	(18.5)	0.19	(0.35)	498	(577)	0.884	(27/30)	0.571	(3/30)
	70	140	276	(1049)	0.29	(0.58)	445	(574)	0.900	(27/30)	0.842	(3/30)
	80	160	982	(5027)	0.22	(0.3)	464	(467)	0.957	(28/30)	0.175	(2/30)
	90	180	3172	(6153)	0.9	(1.4)	844	(730)	0.963	(28/30)	0.158	(2/30)
	100	200	8490	(19298)	1.1	(3.2)	783	(904)	0.976	(28/30)	0.492	(2/30)

Table 2 :

 2 Numerical results, tension scale influence.

Tool available at http://frog.isima.fr/bruno/?doc=bpp_library+ch=build_graph.

Instances available at http://frog.isima.fr/bruno/retrieve.htm?archive=bct_instances.