N Ha Hoang
email: ha.hoang@hcmut.edu.vn

F Couenne
email: couenne@lagep.univ-lyon1.fr

Y Le Gorrec
email: yann.le.gorrec@ens2m.fr

C L Chen

B Erik Ydstie
email: ydstie@cmu.edu

Passivity-based nonlinear control of CSTR via asymptotic observers 1

Keywords: CSTR, Asymptotic observers, Hamiltonian systems, Nonlinear control, Lyapunov function, Passivity

This work makes use of a passivity-based approach (PBA) and tools from Lyapunov theory to design a nonlinear controller for the asymptotic stabilization of a class of non isothermal Continuous Stirred Tank Reactors (CSTR) around any desired stationary point. The convergence and stability proofs are derived in the port Hamiltonian framework. Asymptotic observers that do not require knowledge of reaction kinetics are also proposed for a system with incomplete state measurement. Numerical simulations are given to illustrate the application of the theoretical results to a CSTR with multiple steady states.

Introduction

Lyapunov theory [START_REF] Khalil | Nonlinear systems[END_REF], or more generally the Passivity Based Approach (PBA) [START_REF] Willems | Dissipative dynamical systems. Part I: General theory[END_REF][START_REF] Van Der Schaft | L 2 -gain and passivity techniques in nonlinear control[END_REF][START_REF] Brogliato | Dissipative systems analysis and control[END_REF] combined with generalized energetic arguments as expressed through a Hamiltonian function, is one of the most efficient ways to investigate stability and design controllers for nonlinear dynamical systems [START_REF] Ortega | Putting energy back in control[END_REF][START_REF] Ortega | Power shaping: A new paradigm for stabilization of nonlinear RLC circuits[END_REF][START_REF] Jeltsema | An energy-balancing perspective of interconnection and damping assignment control of nonlinear systems[END_REF].

The key idea of the PBA in the Port Hamiltonian framework [START_REF] Ortega | Interconnection and damping assignment passivity-based control of port-controlled Hamiltonian Systems[END_REF] is to define transformations (by means of control input or shaped dynamics) to obtain a certain structured representation of the original system by rendering it passive with respect to a given storage function. The PBA was first proposed and successfully applied for stability analysis and control design for the electromechanical systems [START_REF] Van Der Schaft | Port-controlled Hamiltonian systems: Towards a theory for control and design of nonlinear physical systems[END_REF][START_REF] Maschke | Energy based Lyapunov functions for forced Hamiltonian systems with dissipation[END_REF]. In these systems the connections between the energy and the dynamical behaviour of the system are well established by the fact that the system reaches its stable state if and only if the total energy is at its minimum. As a consequence, a Lyapunov function candidate can be assigned to the total energy and passivity can then be related to energy dissipation due to friction or resistance. Unfortunately, the link between Lyapunov stability theory and the energy of chemical reactive systems is far from being understood at present [START_REF] Alvarez | Energy shaping plus damping injection control for a class of chemical reactors[END_REF][START_REF] Favache | Power-shaping of reaction systems : the CSTR case study[END_REF]. This topic has therefore been an active research area [START_REF] Hangos | Hamiltonian view on process systems[END_REF][START_REF] Ramírez | On the control of non-linear processes: An IDA-PBC approach[END_REF][START_REF] Hoang | Lyapunov-based control of non isothermal continuous stirred tank reactors using irreversible thermodynamics[END_REF][START_REF] Hudon | Dissipativity-based decentralized control of interconnected nonlinear chemical processes[END_REF].

The Continuous Stirred Tank Reactors (CSTRs) [START_REF] Luyben | Process modeling, simulation, and control for chemical engineers[END_REF] provide a benchmark both in chemical engineering and in dynamical systems theory due to their highly nonlinear dynamics. CSTRs may exhibit non-minimum phase behaviour [START_REF] Niemiec | Nonlinear model-state feedback control for a nonminimum-phase processes[END_REF], instability and multiple steady states [START_REF] Viel | Global stabilization of exothermic chemical reactors under input constraints[END_REF][START_REF] Favache | Power-shaping of reaction systems : the CSTR case study[END_REF]. Studies on CSTRs have investigated control synthesis for stabilization [START_REF] Georgakis | On the use of extensive variables in process dynamics and control[END_REF][START_REF] Hoang | The Port Hamiltonian approach to modeling and control of Continuous Stirred Tank Reactors[END_REF][START_REF] Hoang | Lyapunov-based control of non isothermal continuous stirred tank reactors using irreversible thermodynamics[END_REF][START_REF] Favache | Power-shaping control: writing the system dynamics into the Brayton-Moser form[END_REF][START_REF] Alvarez | Energy shaping plus damping injection control for a class of chemical reactors[END_REF] and state observer design [START_REF] Gibon-Fargeot | Nonlinear observers for chemical reactors[END_REF][START_REF] Soroush | Nonlinear state-observer design with application to reactors[END_REF][START_REF] Alvarez-Ramírez | Observers for a class of continuous tank reactors via temperature measurement[END_REF][START_REF] Dochain | Enthalpy based modelling and design of asymptotic observers for chemical reactors[END_REF]. The combination of these is an important field of research.

The underlying motivation for nonlinear control of the CSTRs is that industrial chemical reactors may have to be operated at unstable operating conditions [START_REF] Bruns | Process operation near an unstable steady state using nonlinear feedback control[END_REF]. Numerous control strategies have been developed to achieve this objective. Input/output feedback linearization [START_REF] Viel | Global stabilization of exothermic chemical reactors under input constraints[END_REF] for control under constraints, nonlinear PI control [START_REF] Alvarez-Ramírez | PI control of continuously stirred tank reactors: stability and performance[END_REF], direct Lyapunov based control [START_REF] Antonelli | Continuous stirred tank reactors: easy to stabilise?[END_REF], (pseudo) Hamiltonian framework [START_REF] Hangos | Hamiltonian view on process systems[END_REF][START_REF] Ramírez | On the control of non-linear processes: An IDA-PBC approach[END_REF][START_REF] Dörfler | An introduction to interconnection and damping assignment passivity-based control in process engineering[END_REF][START_REF] Hoang | The Port Hamiltonian approach to modeling and control of Continuous Stirred Tank Reactors[END_REF], power/energy-shaping control [START_REF] Favache | Power-shaping of reaction systems : the CSTR case study[END_REF][START_REF] Alvarez | Energy shaping plus damping injection control for a class of chemical reactors[END_REF], inventory control [START_REF] Farschman | Process systems and inventory control[END_REF] and dissipativity based decentralized control of interconnected chemical reactors [START_REF] Hudon | Equivalence to dissipative Hamiltonian realization[END_REF][START_REF] Hudon | Dissipativity-based decentralized control of interconnected nonlinear chemical processes[END_REF] provide some examples. Thermodynamics/physics based control has also been proposed to the stabilization of chemical reactors in [START_REF] Georgakis | On the use of extensive variables in process dynamics and control[END_REF][START_REF] Ydstie | Process systems and passivity via the Clausius-Planck inequality[END_REF] and more recently in [START_REF] Hoang | Lyapunov-based control of non isothermal continuous stirred tank reactors using irreversible thermodynamics[END_REF] using the availability function as its point of departure.

State estimation for CSTRs has attracted the attention of researchers for a long time. Papers [START_REF] Dochain | State and parameter estimation in chemical and biochemical processes: A tutorial[END_REF][START_REF] Kravaris | Advances and selected recent developments in state and parameter estimation[END_REF] and references therein provide good overviews of recent developments. Strategies have been developed for industrial applications since on-line measurements of all reactant concentrations are difficult and/or quite expensive to implement and the reactor temperature is in some cases the only measurement available online [START_REF] Gibon-Fargeot | Nonlinear observers for chemical reactors[END_REF][START_REF] Alvarez-Ramírez | Observers for a class of continuous tank reactors via temperature measurement[END_REF]. The missing state variables can be estimated by different tools [START_REF] Gibon-Fargeot | Nonlinear observers for chemical reactors[END_REF][START_REF] Soroush | Nonlinear state-observer design with application to reactors[END_REF][START_REF] Alvarez-Ramírez | Observers for a class of continuous tank reactors via temperature measurement[END_REF][START_REF] Dochain | Asymptotic observers for stirred tank reactors[END_REF][START_REF] Dochain | Enthalpy based modelling and design of asymptotic observers for chemical reactors[END_REF]. The results given in the papers referred above relate to systems where feedback is not imposed. Closed loop stability can therefore not be guaranteed in general.

In this work we focus on the combined control and state estimation problems. First, we propose a passive nonlinear controller for the stabilization of the fully actuated CSTR with chemical reactions around a steady state which may be unstable. This approach is based on the passive Hamiltonian concepts defined in [START_REF] Brogliato | Dissipative systems analysis and control[END_REF][START_REF] Van Der Schaft | L 2 -gain and passivity techniques in nonlinear control[END_REF][START_REF] Maschke | Energy based Lyapunov functions for forced Hamiltonian systems with dissipation[END_REF]. The shaped Hamiltonian storage function is chosen by using the techniques in [START_REF] Viel | Global stabilization of exothermic chemical reactors under input constraints[END_REF][START_REF] Farschman | Process systems and inventory control[END_REF][START_REF] Hoang | Lyapunov-based control of non isothermal continuous stirred tank reactors using irreversible thermodynamics[END_REF] such that the resulting state feedback is admissible [START_REF] Hoang | Lyapunov-based control of non isothermal continuous stirred tank reactors using irreversible thermodynamics[END_REF]. Second, we assume that only the reactor temperature and a subset of concentrations are available online. Following the same concepts used for the passivity-based control, we propose a state estimation strategy based on chemical reaction invariants via the so-called asymptotic observers [START_REF] Dochain | Asymptotic observers for stirred tank reactors[END_REF][START_REF] Dochain | Enthalpy based modelling and design of asymptotic observers for chemical reactors[END_REF]. We show, analytically and/or with simulations, that exponential convergence of the estimated state variables and closed loop stability of the CSTR are guaranteed.

This paper is organized as follows. The passivity based approach is introduced and the state feedback control law is derived in section 2. The dynamical model of the CSTR case study is presented and preliminary results are presented in section 3. Section 4 is devoted to the design of a passive nonlinear controller within the port Hamiltonian framework. It is shown that the resulting control is asymptotically stable and admissible in terms of the amplitude and variation rate as long as the chosen closed loop Hamiltonian function is appropriate. The results generalize previous ones [START_REF] Viel | Global stabilization of exothermic chemical reactors under input constraints[END_REF] without constraint on control input. Furthermore, they allow to rewrite the closed loop system dynamics into a port Hamiltonian representation. A state reconstruction method is then proposed via the so-called asymptotic observers [START_REF] Dochain | Asymptotic observers for stirred tank reactors[END_REF][START_REF] Dochain | Enthalpy based modelling and design of asymptotic observers for chemical reactors[END_REF]. The theoretical developments are then illustrated by simulation studies reported in section 5. Conclusions and future perspectives of the work are given in section 6.

The Passivity Based Approach (PBA)

Let us consider nonlinear systems that are affine in the control input u and whose dynamics is given by the following set of ordinary differential equations (ODEs) [START_REF] Khalil | Nonlinear systems[END_REF]:

dx dt = f (x) + g(x) u (1)
where x = x(t) ∈ R n is the state vector, f (x) ∈ R n is a smooth nonlinear function with respect to x, g(x) ∈ R n×m is the input-state map and u ∈ R m is the control input. The purpose of the PBA is to find a static state-feedback control u = β(x) such that the closed loop dynamics becomes a dissipative Port Controlled Hamiltonian (PCH) system [START_REF] Maschke | Energy based Lyapunov functions for forced Hamiltonian systems with dissipation[END_REF][START_REF] Ortega | Interconnection and damping assignment passivity-based control of port-controlled Hamiltonian Systems[END_REF]. The dynamics can then be written:

dx dt = Q d (x) ∂H d (x) ∂x (2)
where the controlled Hamiltonian storage function H d (x) has a strict local minimum at the desired equilibrium x d ; and

Q d (x) = [J d (x) -R d (x)]
is the difference of a skew-symmetric matrix J d (x) and a symmetric one R d (x) so that:

J d (x) = Q d (x)-Q d (x) T 2 , R d (x) = -Q d (x)+Q d (x) T 2 (3)
Furthermore, the damping matrix R d (x) in equation (3) fulfills:

R d (x) = R d (x) T ≥ 0 (4)
The system (2) is then dissipative in the sense that the time derivative

dH d (x) dt = - ∂H d (x) ∂x T R d (x) ∂H d (x) ∂x (5)
is always negative and the Hamiltonian H d (x) is bounded from below [START_REF] Van Der Schaft | L 2 -gain and passivity techniques in nonlinear control[END_REF][START_REF] Brogliato | Dissipative systems analysis and control[END_REF]. Consequently, it plays role of Lyapunov function for stabilization at the desired equilibrium x d . The following matching equation2 that follows from equations ( 1) and (2) has to be solved to find u = β(x):

f (x) + g(x)β(x) = Q d (x) ∂H d (x) ∂x (6)
We assume that there exists a full rank left annihilator of g(x) denoted g(x) ⊥ such that g(x) ⊥ g(x) = 0. If J d (x), R d (x) and H d (x) are chosen such that:

g(x) ⊥ f (x) = g(x) ⊥ Q d (x) ∂H d (x) ∂x (7)
then the control variable is deduced from the state feedback β(x) given by [START_REF] Ortega | Interconnection and damping assignment passivity-based control of port-controlled Hamiltonian Systems[END_REF]:

β(x) = g(x) T g(x)g(x) T -1 Q d (x) ∂H d (x) ∂x -f (x) (8)
Thus, a general methodology for the PBA in the port Hamiltonian framework is derived from equations (3)( 4) and ( 6)- [START_REF] Ortega | Interconnection and damping assignment passivity-based control of port-controlled Hamiltonian Systems[END_REF]. Three different guidelines can be considered:

(i) We first choose an appropriate Hamiltonian storage function H d (x). The matrix Q d (x) fulfilling (3)(4) has to be found by considering [START_REF] Jeltsema | An energy-balancing perspective of interconnection and damping assignment control of nonlinear systems[END_REF]. The feedback u is then synthesized using (8) [START_REF] Ramírez | On the control of non-linear processes: An IDA-PBC approach[END_REF][START_REF] Hoang | Passivity based controller and observer for exothermic chemical reactors[END_REF].

(ii) We choose an appropriate matrix Q d (x) fulfilling (3)(4). The Hamiltonian storage function H d (x) remains to be found by considering [START_REF] Jeltsema | An energy-balancing perspective of interconnection and damping assignment control of nonlinear systems[END_REF]. From this the feedback u is obtained using (8) [START_REF] Hoang | The Port Hamiltonian approach to modeling and control of Continuous Stirred Tank Reactors[END_REF].

(iii) The matrix Q d (x) fulfilling (3)(4) and the Hamiltonian storage function H d (x) are simultaneously solved by considering [START_REF] Jeltsema | An energy-balancing perspective of interconnection and damping assignment control of nonlinear systems[END_REF]. The feedback u is then given by (8) [START_REF] Dörfler | An introduction to interconnection and damping assignment passivity-based control in process engineering[END_REF]. This guideline becomes quite difficult to implement as degrees of freedom increase [START_REF] Ortega | Interconnection and damping assignment passivity-based control of port-controlled Hamiltonian Systems[END_REF].

In what follows, we shall show that the PBA is useful, not only for controller synthesis but also asymptotic observers design of a class of the non isothermal CSTR with chemical reactions. The use of the PBA with the guideline (i) is applied.

The CSTR case study with chemical transformation

The CSTR modelling

Consider a CSTR with n r chemical reactions 3 with n c active components C i of molar mass M i (i = 1, 2, . . . , n c ). Such a reaction network is character-ized by the following reaction invariant :

nc j=1 ν ij M i = 0, i = 1, 2, . . . , n r (9)
where ν ij is the signed stoichiometric coefficient of species j as it enters in reaction i [START_REF] Srinivasan | Reaction and Flow Variants/Invariants in Chemical Reaction Systems with Inlet and Outlet Streams[END_REF][START_REF] Hoang | The Port Hamiltonian approach to modeling and control of Continuous Stirred Tank Reactors[END_REF]. For modelling purposes, we make the following hypotheses :

(H1) The fluid mixture is isobaric, ideal and incompressible.

(H2) The heat flow from the jacket to the reactor is given by :

QJ = λ(T J -T ) ( 10
)
where λ > 0 is the heat exchange coefficient. The jacket temperature T J is the only control variable.

(H3) The reactor is fed by the species k (k = 1, 2, . . .) at a fixed temperature T I and dilution rate d. The specific heat capacities c pk (k = 1, 2, . . .) are assumed to be constant.

Remark 1. Any reversible reaction l (l ∈ {1, . . . , n r }) of the network (9) can be considered to be irreversible [START_REF] Couenne | Bond graph modelling for chemical reactors[END_REF] when we define the reduced reaction rate:

r l = r l (f ) -r l (r) (11)
where r l (f ) and r l (r)

are the forward and reserve reaction rates respectively.

Under (H1), the energy balance is written using the enthalpy H. Hence the material and energy balances are finally given as follows [START_REF] Favache | Power-shaping control: writing the system dynamics into the Brayton-Moser form[END_REF][START_REF] Favache | Power-shaping of reaction systems : the CSTR case study[END_REF][START_REF] Hoang | Lyapunov-based control of non isothermal continuous stirred tank reactors using irreversible thermodynamics[END_REF][START_REF] Luyben | Process modeling, simulation, and control for chemical engineers[END_REF]:

                           dN 1 dt = d(N 1I -N 1 ) + nr j=1 ν 1j r j dN 2 dt = d(N 2I -N 2 ) + nr j=1 ν 2j r j . . . dNn dt = d(N ncI -N nc ) + nr j=1 ν nj r j dH dt = d(H I -H) + QJ (12)
where:

• N i is mole number of species i (i = 1, . . . , n c );

• H and r j represent the total enthalpy and the reaction rate of the reaction j (j = 1, . . . , n r );

• d stands for the dilution rate which is assumed to be constant. The subscript I written in equation ( 12) denotes "Inlet".

Remark 2. Species N ot that are Inert and/or Catalyst can be added to the dynamics by setting:

dN ot dt = d(N otI -N ot ) ( 13
)
where N ot is a vector containing all these species. But we can easily check that the differential equation ( 13) is stable and the states converge to 0. We shall therefore only consider the dynamics of n c active species (12) from the point of view of chemical reaction. However, the presence of Inert and/or Catalyst should be considered in the energy balance since the total enthalpy H in definition [START_REF] Ramírez | On the control of non-linear processes: An IDA-PBC approach[END_REF], the total heat capacity C p in definition [START_REF] Luyben | Process modeling, simulation, and control for chemical engineers[END_REF] and the total mass m t depend not only on (N 1 , . . . , N nc ) but also N ot .

Remark 3. The total enthalpy H of the reaction system is given by:

H = i h i (T )N i ( 14
)
with h i (T ) = c pi (T -T ref ) + h iref
where T ref and h iref are the reference values. By using the local equilibrium hypothesis, the energy balance dH dt in (12) can be rewritten in terms of temperature [START_REF] Hoang | Lyapunov-based control of non isothermal continuous stirred tank reactors using irreversible thermodynamics[END_REF] so that:

dT dt = r j=1 -∆H Rj r j C p + d(T I -T ) C pI C p + 1 C p QJ ( 15
)
where

∆H Rj = nc i=1 ν ij h i (T ) (16)
represents the enthalpy of the chemical reaction j (j = 1, . . . , n r ) and,

C p = i c pi N i ( 17
)
is the total heat capacity.

The system dynamics with state variables (H, N 1 , . . . , N nc ) given by equation ( 12) or (T, N 1 , . . . , N nc ) defined by equations ( 15) and ( 12) are mathematically equivalent due to definition [START_REF] Ramírez | On the control of non-linear processes: An IDA-PBC approach[END_REF]. The dynamical representation corresponding to the state vector (T, N 1 , . . . , N nc ) given by ODEs ( 12) and ( 15) will be used for controller synthesis. Asymptotic observer design will be solved with the dynamics corresponding to the state vector (H, N 1 , . . . , N nc ) in equation [START_REF] Favache | Power-shaping of reaction systems : the CSTR case study[END_REF]. The transient behaviour of the differential equation ( 13) is considered for the energy balance in both cases.

Example 1. We consider the production of cyclopentenol C 5 H 7 OH from cyclopentadiene C 5 H 6 by sulfuric acid-catalyzed addition of water in a dilute solution [START_REF] Niemiec | Nonlinear model-state feedback control for a nonminimum-phase processes[END_REF]. The total mass of the liquid phase mixture m t is assumed to be constant. The process is described by the Van de Vusse reaction system [START_REF] Van De Vusse | Plug-Flow Type Reactor Versus Tank Reactor[END_REF]. The stoichiometry is written as in [START_REF] Van Der Schaft | Port-controlled Hamiltonian systems: Towards a theory for control and design of nonlinear physical systems[END_REF] with n r = 3 and n c = 5:

C 5 H 6 M 1 + H 2 O M 5 H + --→ C 5 H 7 OH M 2 + H 2 O M 5 H + --→ C 5 H 8 (OH) 2 M 3 2 C 5 H 6 M 1 - → C 10 H 12 M 4 (18)
The system dynamics (12) with 5 active species is given by:

               dN 1 dt = d(N 1I -N 1 ) -r 1 -2r 3 dN 2 dt = d(N 2I -N 2 ) + r 1 -r 2 dN 3 dt = d(N 3I -N 3 ) + r 2 dN 4 dt = d(N 4I -N 4 ) + r 3 dN 5 dt = d(N 5I -N 5 ) -r 1 -r 2 dH dt = d(H I -H) + QJ (19)
Note that sulfuric acid is present as a catalyst. From Remark 2, we therefore have:

dNot dt = d(N otI -N ot ) (20)
In differential equations [START_REF] Viel | Global stabilization of exothermic chemical reactors under input constraints[END_REF] and (20), we have d = qm mt and N iI = x iI mt M i where i

x iI = 1 and q m is the mass flow rate. Finally, the energy balance dH dt in equation ( 19) is written in terms of the temperature T (see Remark 3) so that:

dT dt = 3 j=1 -∆H Rj r j C p + d(T I -T ) C pI C p + 1 C p QJ ( 21
)
where:

   ∆H R1 = -h 1 -h 5 + h 2 > 0 ∆H R2 = -h 2 -h 5 + h 3 < 0 ∆H R3 = -2h 1 + h 4 < 0 (22)
and,

C p = c p1 N 1 + c p2 N 2 + c p3 N 3 + c p4 N 4 + c p5 N 5 + c pot N ot (23)

Preliminaries

The following assumptions are now made to characterise the dynamical behaviour of the system ( 12): (A1) The reaction rates r j (j = 1, . . . , n r ) are described by the mass action laws,

r j = k j (T )F j (N |ν 1j | 1 , N |ν 2j | 2 , . . .), j = 1, . . . , n r (24)
where F j (j = 1, . . . , n r ) are nonlinear functions with respect to their arguments and k j (T ) (j = 1, . . . , n r ) are reaction rate constants fulfilling the condition that k j (T ) is monotone, non-negative and bounded in accordance to thermodynamic principles [START_REF] Luyben | Process modeling, simulation, and control for chemical engineers[END_REF][START_REF] Favache | Power-shaping of reaction systems : the CSTR case study[END_REF][START_REF] Hoang | Lyapunov-based control of non isothermal continuous stirred tank reactors using irreversible thermodynamics[END_REF] so that: lim

T →0
k j (T ) = 0 and lim

T →+∞ k j (T ) = k j max (25)
The Arrhenius law

k j (T ) = k 0j exp -k 1j T ( 26
)
where k 0j is the kinetic constant and k 1j is the activation temperature, is compatible with the limits in equation ( 25).

(A2) The temperature and mole numbers are non-negative.

Assumption (A2) describes measurable physical quantities [START_REF] Antonelli | Continuous stirred tank reactors: easy to stabilise?[END_REF] and implies that the CSTR is a positive system. In what follows, we first present the following results which are instrumental in proving the main results of this work.

Boundedness of material dynamics

Lemma 1 generalizes the results of Theorem 2.1 (i) presented in [START_REF] Viel | Global stabilization of exothermic chemical reactors under input constraints[END_REF] by considering multi-component homogeneous mixtures.

Lemma 1. The domain Ω = N 1 , . . . , N nc 0 ≤ nc i=1 M i N i ≤ nc i=1 M i N iI is positively invariant. Proof. Define η = nc i=1
M i N i . By using the mass conservation property given by equation ( 9), we obtain from equation [START_REF] Favache | Power-shaping of reaction systems : the CSTR case study[END_REF]:

dη dt = d nc i=1 M i N iI -η η(t) ≤ nc i=1 M i N iI for all η(t = 0) ≤ nc i=1 M i N iI since d > 0. Using (A2), one
gets η(t) ≥ 0. The latter completes the proof.

Stability of the isothermal dynamics

Let (N 1d , N 2d , . . . , N N d , T d ) be the steady state of the reaction system defined by equations ( 12) and [START_REF] Hoang | Lyapunov-based control of non isothermal continuous stirred tank reactors using irreversible thermodynamics[END_REF]. Let us note that possible steady states are calculated by considering that all time derivatives vanish and that there may be more than one stationary solution to the problem [START_REF] Favache | Power-shaping of reaction systems : the CSTR case study[END_REF]. An additional assumption (used in [START_REF] Viel | Global stabilization of exothermic chemical reactors under input constraints[END_REF][START_REF] Alvarez-Ramírez | PI control of continuously stirred tank reactors: stability and performance[END_REF][START_REF] Antonelli | Continuous stirred tank reactors: easy to stabilise?[END_REF] or recently [START_REF] Favache | Power-shaping of reaction systems : the CSTR case study[END_REF]) is considered: (A3) For the isothermal dynamics (T = T d ), the system dynamics (12) admits a single equilibrium point (N 1d , . . . , N nd ) which is globally asymptotically stable.

From a control point of view, we can show by means of Lyapunov converse theorems [START_REF] Khalil | Nonlinear systems[END_REF] together with the above assumption, that there exists a positive function V(N 1 , . . . , N nc ) with dV dt < 0 along the isothermal dynamics. Several industrial chemical reaction processes verify this assumption. Let us illustrate with the Van de Vusse reaction system in Example 1.

Example 2. We rewrite the isothermal dynamics derived from equation [START_REF] Viel | Global stabilization of exothermic chemical reactors under input constraints[END_REF] into the explicit form using (A1) so that:

           dN 1 dt = d(N 1I -N 1 ) -k 1 (T d )N 1 -2k 3 (T d )N 2 1 dN 2 dt = d(N 2I -N 2 ) + k 1 (T d )N 1 -k 2 (T d )N 2 dN 3 dt = d(N 3I -N 3 ) + k 2 (T d )N 2 dN 4 dt = d(N 4I -N 4 ) + k 3 (T d )N 2 1 dN 5 dt = d(N 5I -N 5 ) -k 1 (T d )N 1 -k 2 (T d )N 2 (27)
The existence of the positive-definite function V(N 1 , . . . , N nc ) is derived by considering the separable dynamics of [START_REF] Dochain | Enthalpy based modelling and design of asymptotic observers for chemical reactors[END_REF]. Indeed the dynamics on N 1 [START_REF] Dochain | Enthalpy based modelling and design of asymptotic observers for chemical reactors[END_REF] can be rewritten as follows:

dN 1 dt = -2k 3 (T d ) N 1 -N 1d N 1 -N1d ( 28
)
where N 1d > 0 and N1d < 0 are roots of the second-order polynomial equation that follow by setting dN 1 dt = 0 in equation ( 27):

   N 1d = (d+k 1 (T d ))- √ (d+k 1 (T d )) 2 +8 d k 3 (T d ) N 1I -4k 3 (T d ) N1d = (d+k 1 (T d ))+ √ (d+k 1 (T d )) 2 +8 d k 3 (T d ) N 1I -4k 3 (T d ) (29)
Lemma 1 shows that there exits a positive constant > 0 so that (28) can be rewritten as follows:

dN 1 dt ≤ -2 k 3 (T d ) N 1 -N 1d (30)
It is now clear that the positive-definite function

V 1 (N 1 ) = 1 2 (N 1 -N 1d
) 2 is a Lyapunov function candidate for the stabilization of (30) at N 1d . The same argument sequentially applies to N 2 , N 3 , N 4 and N 5 . Finally, the (global) Lyapunov function of the isothermal dynamics [START_REF] Dochain | Enthalpy based modelling and design of asymptotic observers for chemical reactors[END_REF] is defined so that:

V(N 1 , . . . , N nc ) = 5 k=1 V k (N k ) (31)
In the following we focus our attention on nonlinear control and state estimation problems of non isothermal CSTR [START_REF] Dochain | Enthalpy based modelling and design of asymptotic observers for chemical reactors[END_REF]. These two problems will be effectively solved in the framework of the passivity theory.

Main results

Controller design

For controller synthesis, it is convenient to let the state vector x = (N 1 , . . . , N nc , T ) represent the reaction system dynamics (15) [START_REF] Favache | Power-shaping of reaction systems : the CSTR case study[END_REF]. The dynamics ( 1) is then obtained with:

f (x) =                          d(N 1I -N 1 ) + nr j=1 ν 1j r j d(N 2I -N 2 ) + nr j=1 ν 2j r j . . . d(N ncI -N nc ) + nr j=1 ν nj r j V nr j=1 -∆H Rj rj -λT Cp + d(T I -T ) C pI Cp                          , g(x) =                0 0 . . . 0 λ Cp                and u = T J (32)
The PBA with the guideline (i) (in Section 2) will be used to design a passive nonlinear controller for the stabilization of the reaction system (1) with (32) at a given desired state x d . The problem first consists of choosing an appropriate closed loop Hamiltonian storage function H d (x). Let us note that in previous works [START_REF] Viel | Global stabilization of exothermic chemical reactors under input constraints[END_REF][START_REF] Alvarez-Ramírez | PI control of continuously stirred tank reactors: stability and performance[END_REF], a Lyapunov function candidate based on thermal deviation 1 2 (T -T d ) 2 is considered for the temperature stabilization problem. Farschman and coworkers in [START_REF] Farschman | Process systems and inventory control[END_REF] have proposed an inventory-based quadratic storage function 1 2 (x -x d ) 2 for control of chemical process systems. In [START_REF] Hoang | The Port Hamiltonian approach to modeling and control of Continuous Stirred Tank Reactors[END_REF][START_REF] Hoang | Lyapunov-based control of non isothermal continuous stirred tank reactors using irreversible thermodynamics[END_REF], the thermodynamic availability and its individual contributions have been used as the desired closed loop storage functions. We now show that the matrix Q d (x) can be found using the PBA with the Hamiltonian function:

H d (x) = H d (T, N 1 , . . . , N nc ) = (T -T d ) 2 2 1 + nc i=1 K i (N i -N id ) 2 (33)
where K i ≥ 0. One consequence of definition [START_REF] Hudon | Equivalence to dissipative Hamiltonian realization[END_REF] is that sufficient damping is introduced to allow the stabilization problem to be accomplished with a smooth control law in terms of the amplitude and variation rate. The proposed controller therefore generalizes the one obtained from [START_REF] Viel | Global stabilization of exothermic chemical reactors under input constraints[END_REF] which uses input constraints and non-smooth controls. It also allows us to rewrite the closed loop dynamics (1) with [START_REF] Farschman | Process systems and inventory control[END_REF] in a port Hamiltonian representation as seen in Proposition 1 below.

Proposition 1. The reaction system described by equations (1) and ( 32) is exponentially stabilized at the desired state x d = (N 1d , . . . , N nd , T d ) with the following state feedback control law:

T J = T + 1 λ C p -∂H d ∂T -1 nc i=1 ∂H d ∂N i dN i dt -K T ∂H d ∂T - nr j=1 -∆H Rj r j + d(T I -T )C pI (34)
where K T > 0 is a tuning parameter. Furthermore, the closed loop dynamics are represented in the passive Hamiltonian format so that:

dx dt = [J d (x) -R d (x)] ∂H d (x) ∂x (35)
where:

J d (x) =                0 . . . 0 ∂H d ∂T -1 dN1 dt . . . . . . . . . . . . 0 . . . 0 ∂H d ∂T -1 dNn c dt -∂H d ∂T -1 dN1 dt . . . -∂H d ∂T -1 dNn c dt 0                (36) R d (x) =      0 . . . 0 0 . . . . . . . . . . . . 0 . . . 0 0 0 . . . 0 K T      (37)
and H d (x) is given by [START_REF] Hudon | Equivalence to dissipative Hamiltonian realization[END_REF].

Proof. By using the PBA as described in Section 2, we have

Q d (x) = q ij (x) i,j=1...(nc+1)
and g ⊥ (x) = diag 1, . . . , 1, 0 ∈ R (nc+1)×(nc+1) .

The matching equations from [START_REF] Jeltsema | An energy-balancing perspective of interconnection and damping assignment control of nonlinear systems[END_REF] give the following partial differential equations :

     q 11 (x) ∂H d ∂N 1 + . . . + q 1nc (x) ∂H d ∂Nn c + q 1(nc+1) (x) ∂H d ∂T = dN 1 dt . . . q nc1 (x) ∂H d ∂N 1 + . . . + q nn (x) ∂H d ∂Nn c + q nc(nc+1) (x) ∂H d ∂T = dNn c dt
The number of equations equals n c with n c ×(n c +1) unknown variables q ij (x).

Hence this system has an infinite number of solutions. A simple solution is found using the negative definiteness of the matrix Q d (x) as follows:

(a) set q ij (x) = q ji (x) = 0 for i, j = 1 . . . n c ;

(b) then set q i(nc+1

) (x) = -q (nc+1)i (x) = ∂H d ∂T -1 dN i dt for i = 1 . . . n c ;
(c) and finally choose q (nc+1)(nc+1) (x) = -K T .

It follows that q i(nc+1) (x), i = 1 . . . n c is well defined in the limit ∂H d ∂T → 0 (refer to equation (41) below). The structure matrices J d (x) [START_REF] Kravaris | Advances and selected recent developments in state and parameter estimation[END_REF] and R d (x) (37) are computed by using (3). Finally, the feedback law is derived from (8) with J d (x) defined in equation [START_REF] Kravaris | Advances and selected recent developments in state and parameter estimation[END_REF], R d (x) defined in equation ( 37) and H d (x) given in equation [START_REF] Hudon | Equivalence to dissipative Hamiltonian realization[END_REF]:

C p -∂H d ∂T -1 ∂H d ∂N 1 dN 1 dt -. . . -∂H d ∂T -1 ∂H d ∂Nn c dNn c dt -K T ∂H d ∂T - nr j=1 -∆H Rj r j + d(T I -T )C pI = QJ
Using (H2) with u = T J leads to the feedback law [START_REF] Ydstie | Process systems and passivity via the Clausius-Planck inequality[END_REF]. Let us note that the feedback law ( 34) is well-defined when H d (x) is defined by equation [START_REF] Hudon | Equivalence to dissipative Hamiltonian realization[END_REF].

The function H d (x) is positive definite and its time derivative satisfies

dH d (x) dt = -K T ∂H d ∂T 2 < 0, ∀T = T d (38)
From Lemma 1 and equation [START_REF] Hudon | Equivalence to dissipative Hamiltonian realization[END_REF] it follows that there exists ς > 0 so that:

dH d (x) dt ≤ -ςH d (x) (39)
The stability proof immediately follows invoking La Salle's invariance principle [START_REF] Khalil | Nonlinear systems[END_REF] and (A3). We now develop some important limiting properties of the closed loop system to show that the control law proposed in equation ( 34) is well-defined. First, it follows from the development above that the closed loop dynamics of the temperature T with the feedback law given in equation ( 34) can be rewritten as follows:

dT dt = - ∂H d ∂T -1 dN 1 dt ∂H d ∂N 1 -. . . - ∂H d ∂T -1 dN nc dt ∂H d ∂N nc -K T ∂H d ∂T (40)
Second, we note that it follows from the definition of H d (x) in equation ( 33) that:

∂H d ∂T → 0 ⇔ T → T d and, lim T →T d ∂H d ∂N i → 0, i = 1, . . . , n c
From (33) we also have:

H d (T = T d , N 1 , . . . , N nc ) = 0 and dH d dt (T =T d ,N 1 ,...,Nn c ) = 0
We have shown that H d (x) is a Lyapunov function with [START_REF] Couenne | Bond graph modelling for chemical reactors[END_REF] for the stabilization of the reactor temperature T . As a consequence, we obtain lim

T →T d dT dt = lim ∂H d ∂T →0
dT dt = 0 and thus we deduce from [START_REF] Moreno | Global observability and detectability analysis of uncertain reaction systems and observer design[END_REF]:

             lim ∂H d ∂T →0 ∂H d ∂T -1 dN 1 dt < ∞ . . . lim ∂H d ∂T →0 ∂H d ∂T -1 dNn c dt < ∞ (41)
The latter completes the proof.

Remark 4. The feedback law [START_REF] Ydstie | Process systems and passivity via the Clausius-Planck inequality[END_REF] becomes similar to the one proposed by Viel and coworkers [START_REF] Viel | Global stabilization of exothermic chemical reactors under input constraints[END_REF] when the constraints are ignored and K 1 = . . . = K nc = 0 in H d (x) as defined by equation [START_REF] Hudon | Equivalence to dissipative Hamiltonian realization[END_REF]. In this case, the stabilization is dominated by the regulation of the thermal part in accordance with the Assumption (A3). In the general case ( nc i=1 K i = 0), we may use the gains to shape the amplitude and variation rate of the control input through the presence of the material balances given by equations ( 33) and (34).

Asymptotic observers

We now consider a situation where only the reactor temperature T and a subset of the concentrations are measured. In this case we have to design an observer to reconstruct other missing variables within the mixture. We also need to find a method to determine how many and which concentrations need to be measured. The main feature of the proposed observer is that it is independent of the system kinetics and is called asymptotic observers. These asymptotic observers were first proposed in [START_REF] Dochain | Asymptotic observers for stirred tank reactors[END_REF] for simplified CSTR models and developed further in [START_REF] Dochain | Enthalpy based modelling and design of asymptotic observers for chemical reactors[END_REF] for more general CSTR models. However, feedback law was not considered in these contributions and there is a question whether the use of the estimated states in feedback gives stable control. In what follows we show, analytically and/or simulations, that the estimated state variables exponentially converge to their exact values with and without feedback. Let us reconsider the original system [START_REF] Favache | Power-shaping of reaction systems : the CSTR case study[END_REF] and rewrite it into the following form:

Σ    dH dt = d(H I -H) + QJ dN dt = d(N I -N ) + νr (42)
where N = (N 1 , . . . , N nc ) T is the vector of mole numbers. ν = ν ij i=1...nc j=1...nr is the matrix of stoichiometric coefficients and r = (r 1 , . . . , r nr ) T is the vector composed of chemical reaction rates. The following additional assumption is made [START_REF] Dochain | Asymptotic observers for stirred tank reactors[END_REF][START_REF] Dochain | Enthalpy based modelling and design of asymptotic observers for chemical reactors[END_REF]: (A4) The reaction network [START_REF] Van Der Schaft | Port-controlled Hamiltonian systems: Towards a theory for control and design of nonlinear physical systems[END_REF] with n r < n c is independent so that, rank(ν) = n r And (n r -1) concentrations and the reactor temperature T are assumed to be available for the online measurement 4 .

We have the following lemma. Lemma 2. There exists an n c × n c matrix Θ so that:

Θ = υ nr×nc ν ⊥ (nc-nr)×nc nc×nc ( 43
)
where the following equalities hold:

υ ν = I nr×nr ( 44
)
and ν ⊥ ν = 0 (nc-nr)×nr ( 45
)
where I nr×nr and 0 (nc-nr)×nr are the identity and the zero matrices respectively.

Proof. The proof immediately follows using Assumption A4. Indeed it can be shown that the matrix Θ is directly derived by Gauss elimination.

Example 3. Let us consider the Van de Vusse reaction system given Example 1. Its dynamics (19) can be re-expressed as (42), where:

ν =       -1 0 -2 1 -1 0 0 1 0 0 0 1 -1 -1 0       and r = (r 1 , r 2 , r 3 ) T
After some manipulation we have:

Θ =       0 1 1 0 0 0 0 1 0 0 -1 2 -1 2 -1 2 0 0 1 2 1 2 1 2 1 0 0 1 2 0 1       = υ 3×5 ν ⊥ 2×5 5×5
and Θ verifies equations (44) and (45). 4 That means that n r values are assumed to be measured.

As a consequence of Lemma 2, We state Proposition 2.

Proposition 2. The map from R nc to R nc-nr , Z = ν ⊥ N , reduces the dynamics for N defined by equation (42) to:

dZ dt = d(Z I -Z) (46)
where Z I = ν ⊥ N I and ν ⊥ are given in equation (43). Furthermore, the reduced dynamics are independent of the chemical reaction kinetics.

Proof. The proof immediately follows by multiplying equation ( 42) with ν ⊥ defined by equation (43) (see also [START_REF] Dochain | Asymptotic observers for stirred tank reactors[END_REF][START_REF] Dochain | Enthalpy based modelling and design of asymptotic observers for chemical reactors[END_REF]).

In the remaining of the paper, we let N = {1, . . . , n c } be the set of indices for chemical species of the mixture described by the invariant (9) and the differential equations (42). It is worth noting that there exists a disjoint partitioning I, J ⊂ N with (n r -1) and (n c -n r + 1) elements respectively so that:

I ∩ J = ∅ I ∪ J = N (47)
where I and J refer to the subsets of (n r -1) measured mole numbers5 and (n c -n r + 1) remaining mole numbers to be estimated respectively. As a consequence, we can write from definition [START_REF] Ramírez | On the control of non-linear processes: An IDA-PBC approach[END_REF] and Proposition 2:

     H = h T I N I + h T J N J + h T ot N ot Z = ν ⊥ I N I + ν ⊥ J N J (48) where ν ⊥
O =    h T J ν ⊥ J    (nc-nr+1)×(nc-nr+1) (49)
fulfills the following condition,

rank(O) = n c -n r + 1 (50)
then the states of the system Σ defined by equation (42) are asymptotically reconstructed with the asymptotic observer Σ :

Σ    d Ĥ dt = d(H I -Ĥ) + QJ d Ẑ dt = d(Z I -Ẑ) (51)
The convergence rate of each Nj , ∀j ∈ J defined from Σ to the exact value is exponential with the time constant τ = 1 2d . Furthermore, the results above hold whether the system is operated in open or closed loop. -nr+1) . By subtracting (51) to (42), we get:

Proof. Let us define (t) =   H Z   =   Ĥ -H Ẑ -Z   ∈ R (nc
d dt = -d I (nc-nr+1)×(nc-nr+1)   H Z   (52)
with d > 0. The dynamics of is then presented in the port Hamiltonian format (2) where J( ) = 0, R( ) = d I (nc-nr+1)×(nc-nr+1) and the Hamiltonian storage function H( ) = 1 2 T ≥ 0. H( ) plays a role of a Lyapunov function for the stability of the zero dynamics of because:

dH( ) dt = - ∂H( ) ∂ T R( ) ∂H( ) ∂ < 0
Furthermore, it can be rewritten as follows:

dH( ) dt = -d T = -2d H( ) ⇒ H( (t)) = H( (t = 0)) exp -t 1 2d
H( (t)) exponentially converges to 0 with the time constant τ = 1 2d since d > 0. As a consequence, we have (t) → 0, e.g. Ĥ → H and Ẑ → Z. Using equation (48) together with equation ( 13), we obtain:

O NJ -N J = 0
where the matrix O is defined by equation (49). With condition (50), we conclude: NJ = N J

The estimated values NJ are then calculated from the asymptotic observer Σ defined in equation (51) using equations ( 48) and ( 13):

NJ = O -1    Ĥ -h T I N I -h T ot Not Ẑ -ν ⊥ I N I    (53)
It is important to notice that the convergence does not depend on the feedback strategy. The latter completes the proof.

Remark 5. The estimates Not of the states N ot used in equation (53) are derived by using the differential equation (13) so that:

d Not dt = d(N otI -Not ) (54)
We note that the observability matrix (49) and the full rank condition (50) can be regarded as feasibility conditions for the asymptotic observer [START_REF] Moreno | Global observability and detectability analysis of uncertain reaction systems and observer design[END_REF]. The condition (50) is fulfilled only if the reactions are independent [START_REF] Dochain | Asymptotic observers for stirred tank reactors[END_REF][START_REF] Dochain | Enthalpy based modelling and design of asymptotic observers for chemical reactors[END_REF], and more precisely if the states to be estimated in J have intrinsically been involved in the same reactions. Hence the proposed result generalizes and completes the analysis given in [START_REF] Dochain | Asymptotic observers for stirred tank reactors[END_REF][START_REF] Dochain | Enthalpy based modelling and design of asymptotic observers for chemical reactors[END_REF]. Let us illustrate this statement via the following example. We can easily check that O is not full rank because it is not necessarily true that det(O) = h 2 -

(O) = 1 2 (h 1 - h 2 + h 5 ) = -1
2 ∆H R1 < 0 as seen from equation (22).

Illustrative example

Let us consider a CSTR with one exothermic reaction involving 2 active chemical species A and B (e.g. n c = 2 and n r = 1) with the stoichiometry:

ν A M A → ν B M B ( 55
)
The reactor is fed by species A, B and an inert with a fixed inlet temperature T I . The balance equations are (see also [START_REF] Favache | Power-shaping of reaction systems : the CSTR case study[END_REF]):

           dN A dt = d(N AI -N A ) + ν A r dN B dt = d(N BI -N B ) + ν B r dH dt = d (H I -H) + QJ (56)
As previously mentioned, the energy balance in equation ( 56) can be rewritten in terms of temperature as follows:

C p dT dt = -∆H R r + d(T I -T )C pI + QJ (57)
where ∆H R = (ν B h B (T ) + ν A h A (T )) < 0 is the heat of reaction and C p = c pA N A + c pB N B + c pInert N Inert is the total heat capacity. Finally the dynamics of inert is given by:

dN Inert dt = d(N InertI -N Inert ) ≡ 0 ( 58
)
The numerical values are given in Table 1 [START_REF] Hoang | Passivity based controller and observer for exothermic chemical reactors[END_REF]. The exothermic reaction (55) is considered with ν A = -1 and ν B = 1. The open and closed loop simulations are carried out with respect to two different initial conditions, (C1) with T 0 = 340 (K), N A0 = 0.04 (mol), N B0 = 0.001 (mol) and (C2) with T 0 = 300 (K), N A0 = 0.15 (mol), N B0 = 0.03 (mol) .

Open loop simulation

Figure 1 shows that the system (56) has three steady states indicated with P 1 , P 2 and P 3 under the input:

T I = T J = 298 (K), N AI = 0.18 (mol), N BI = 0 (mol), N InertI = 3.57 (mol) (59)
The intermediate steady state P 2 is unstable whereas P 1 and P 3 are (locally) stable. In the next subsection, we operate the reaction system at the unstable state P 2 using the feedback law defined by equation [START_REF] Ydstie | Process systems and passivity via the Clausius-Planck inequality[END_REF] for the jacket temperature T J .

Closed loop simulation

In the first case we assume that all state variables are measured. In this case we can use the state feedback law [START_REF] Ydstie | Process systems and passivity via the Clausius-Planck inequality[END_REF]. We choose K T = 0.001, K A = 0 Figure 2 shows the closed loop response with phase plane. We see, for both of the considered initial conditions, that the system converges to the desired operating point P 2 . Figure 2 also shows that the control variable input T J (34) is admissible in terms of amplitude and dynamics.

The Hamiltonian H d (x) [START_REF] Hudon | Equivalence to dissipative Hamiltonian realization[END_REF] plays the role of a global Lyapunov function for any choice of admissible initial conditions and consequently it converges to 0 as shown in Figure 3.

ν ⊥ J = (ν B -ν A ), h T J = (h A (T ) h B (T )) and det(O) = -ν A h A (T ) - ν B h B (T ) = -∆H R > 0.
It follows that the observability matrix O is full rank and the asymptotic observer is feasible.

For the sake of simplicity, the initial condition (C2) is used for the system. The initial conditions of the asymptotic observer are ( Ĉ1) with Ĥ(0) = 0.98H(T 0 , N A0 , N A0 ), N (0) = 0.75N (N A0 , N B0 ) and ( Ĉ2) with Ĥ(0) = H(0.85T 0 , N A0 , N B0 ), N (0) = 0.95N (N A0 , N B0 ) where the numerical values of T 0 , N A0 and N B0 are given with the initial condition (C2). The open loop convergence of the estimates generated by the asymptotic observer (51) is illustrated in Figure 4. With the initial condition (C2), the system converges to the stable point P 1 . The closed loop simulations are given in Figures 5 and6 with the initial conditions, (C2) and ( Ĉ1), (C2) and ( Ĉ2) respectively. The stabilization at the unstable state P 2 of the controlled reaction system via the asymptotic observer is guaranteed. Furthermore, the dynamics of the control input T J remains admissible as seen in Figure 5

Conclusion

We have shown, by means of the passivity-based approach in the port Hamiltonian framework, how to synthesize a nonlinear controller for the stabilization and how to design an asymptotic observer of a class of CSTRs. The results can be applied to non isothermal CSTRs operated under multiple steady states. The resulting state feedback developed in the paper generalizes the one proposed by [START_REF] Viel | Global stabilization of exothermic chemical reactors under input constraints[END_REF] in the sense that we do not add a constraint on the control input. The closed loop convergence of the system is theoretically shown. The use of an asymptotic observer provided the rank condition on the observability matrix. This condition is fulfilled by appropriate choice of measured states. Finally, numerical simulations show that convergence objective is satisfied for a simple case study. The state feedback law on the jacket temperature T J is implementable and gives finite amplitude and admissible rate of variation. Open questions concern the structure of the observability matrix (with respect to traditional definition for linear systems); and the performance/robustness of the control law with respect to perturbations and parameters uncertainty.

IProposition 3 .

 3 and ν ⊥ J are submatrices of the matrix ν ⊥ formed by selecting columns corresponding to the marked mole numbers. The convergence of the estimates Nj , ∀j ∈ J to their exact values is shown in Proposition 3. If the square matrix defined by

Example 4 .

 4 Example 3 showed that N = {1, 2, 3, 4, 5} and If we choose I = {1, 3} and J = {2, 4, 5} then we get O =

1 2 h 4

 4 + 1 2 h 5 = 0 for non isothermal reactors. Otherwise, if we choose I = {3, 4}, J = {1, 2, 5} then we get O = latter is full rank because the species N 1 , N 2 and N 5 are effectively involved in the first chemical reaction of the network (18) and thus det

3 Figure 1 :

 31 Figure 1: The representation of the open loop phase plane

Figure 2 :Figure 3 :

 23 Figure 2: Representation of the closed loop phase plane (the point P 3 outside the frame) and the feedback law T J for two different initial conditions (C1) and (C2)

  (b) and Figure 6(b).

Figure 4 :

 4 Figure 4: N A , N B and their estimates in the open loop case -(a) for the initial conditions (C2) and ( Ĉ1) -(b) for initial conditions (C2) and ( Ĉ2)

Figure 5 :

 5 Figure 5: N A and its estimate with the asymptotic observer in the closed loop case -(a) for the initial conditions (C2) and ( Ĉ1) -(b) the control input T J with the asymptotic observer

Figure 6 :

 6 Figure 6: N A and its estimate with the asymptotic observer in the closed loop case -(a) for the initial conditions (C2) and and ( Ĉ2) -(b) the control input T J with the asymptotic observer

Table 1 :

 1 Parameters of CSTR

		Numerical value
	c pA	221.9 (JK -1 mol -1 )	Heat capacity of species A
	c pB	128.464 (JK -1 mol -1 ) Heat capacity of species B
	c pInert	21.694 (JK -1 mol -1 )	Heat capacity of Inert
	E a	73.35 (KJmol -1 )	Activation energy
	h Aref	-5.8085 10 5 (Jmol -1 ) Reference enthalpy of A
	h Bref	-6.6884 10 5 (Jmol -1 ) Reference enthalpy of B
	h Inertref -3.3 10 5 (Jmol -1 )	Reference enthalpy of Inert
	k 0	2.58 10 9 (s -1 )	Kinetic constant
	R	8.314 (JK -1 mol -1 )	Gas constant
	T ref	298 (K)	Reference temperature
	λ	0.75 (W K -1 )	Heat transfer coefficient
	d	0.0070 (s -1 )	Dilution rate

A partial differential equation (PDE)[START_REF] Ortega | Interconnection and damping assignment passivity-based control of port-controlled Hamiltonian Systems[END_REF].

Without loss of generality, we assume that all considered reactions are irreversible.

It does not include the temperature.

ACKNOWLEDGMENTS

This work is supported by the Vietnam's National Foundation for Science and Technology Development (NAFOSTED) under research proposal number 101.01-2013. 23. The first author wish to thank Prof. Denis Dochain for helpful discussions and comments on asymptotic observers during his stay in CESAME, UCL, Belgium. The scientific responsibility rests with its authors.


Giorgio Lucarelli
email: lucarelli@lamsade.dauphine.fr

Ioannis Milis
email: milis@aueb.gr

On the approximability of the Max Edge-Coloring problem

The max edge-coloring problem asks for a proper edge-coloring of an edge-weighted graph minimizing the sum of the weights of the heaviest edges in each color class. This problem arises in optical communication systems and has been well studied during last years. However, no algorithm of approximation ratio 2 -δ, for any constant δ > 0, is known for general or bipartite graphs, while the complexity of the problem on trees remains an open question. In this paper we present new approximation results towards these questions. In fact, we present a PTAS for trees and an 1.74-approximation algorithm for bipartite graphs; we also adapt the last algorithm to one for general graphs of the same, asymptotically, approximation ratio.

Introduction

In several communication systems messages are to be transmitted directly from senders (input ports) to receivers (output ports) through direct connections established by an underlying switching network (e.g., SS/TDMA [START_REF] Gopal | Minimizing the number of switchings in a SS/TDMA system[END_REF], IQ switch architectures [START_REF] Kesselman | Nonpreemptive scheduling of optical switches[END_REF]). Any node of such a system cannot participate in more than one transmissions at the same time, while messages between different pairs of senders and receivers can be transmitted simultaneously. A scheduler establishes successive configurations of the switching network, each one routing a non-conflicting subset of the messages from senders to receivers. Given the transmission time of each message, the transmission time of each configuration equals to the longest message transmitted. The aim is to find a sequence of configurations such that all the messages are transmitted and the total transmission time is minimized.

It is easy to see that this situation corresponds directly to the following generalized coloring problem: Given a graph G = (V, E) and a positive integer weight w(e), for each edge e ∈ E, we seek for a proper edge-coloring of G, M = {M 1 , M 2 , . . . , M k }, where each color class (matching) M i ⊆ E is assigned the weight of the heaviest edge in this class, i.e., w i = max{w(e)|e ∈ M i }, 1 ≤ i ≤ k, and the sum of all color classes' weights, W = ∑ k i=1 w i , is minimized. In fact, senders and/or receivers correspond to the vertices of the graph G, (transmission times of) messages correspond to (weights of) edges of G and configurations correspond to matchings. Although the graph G obtained is originally a weighted directed multi-graph it can be considered as an undirected one, since the directions of its edges do not play any role in the objective function.

The above coloring problem is known as the Max Edge-Coloring (MEC) problem; clearly, for unit edge weights it reduces to the classical edge-coloring problem. The analogous weighted generalization of the classical vertex-coloring problem has been also addressed in the literature as Max (Vertex-)Coloring (MVC) problem [START_REF] Pemmaraju | Buffer minimization using max-coloring[END_REF][START_REF] Pemmaraju | Approximation algorithms for the max-coloring problem[END_REF].

Remark that the MEC problem on a general graph, G, is equivalent to the MVC problem on the line graph, L(G), of G. Thus, the results for the MVC problem on a graph G apply also to the MEC problem on the graph L(G) and vice versa, if both G and L(G) are in the same graph class. Note, however, that this is true for general graphs and chains, but not for the most other special graph classes, including bipartite graphs and trees, since they are not closed under line graph transformation (e.g., the line graph of a bipartite graph is not anymore a bipartite one).

The MEC problem can be also viewed as a parallel batch scheduling problem with conflicts between jobs [START_REF] Demange | Time slot scheduling of compatible jobs[END_REF][START_REF] Finke | Batch processing with interval graph compatibilities between tasks[END_REF]. According to the standard three field notation for scheduling problems, the MEC problem is equivalent to 1 | pbatch, E(G) | C max : Jobs correspond to the edges E(G) of a weighted graph G and edge weights to processing times of jobs. The graph G describes incompatibilities between jobs, i.e., jobs corresponding to adjacent edges cannot be scheduled (resp., colored) in the same batch (resp., by the same color).

Related work.

It is well known that for general graphs it is NP-hard to approximate the classical edge-coloring problem within a factor less than 4/3 [START_REF] Holyer | The NP-completeness of edge-coloring[END_REF]; for bipartite graphs the problem becomes polynomial [START_REF] König | Über graphen und ihre anwendung auf determinantentheorie und mengenlehre[END_REF]. The MEC problem is known to be non approximable within a factor less than 7/6 even for cubic planar bipartite graphs with edge weights w(e) ∈ {1, 2, 3}, unless P=NP [START_REF] De Werra | Weighted coloring on planar, bipartite and split graphs: Complexity and approximation[END_REF]. It is also NP-complete for complete graphs with bi-valued edge weights [START_REF] Bourgeois | Approximating the maxedge-coloring problem[END_REF]. On the other hand, the MEC problem is known to be polynomial for a few special cases including bipartite graphs with edge weights w(e) ∈ {1, t} [START_REF] Demange | Time slot scheduling of compatible jobs[END_REF], chains [START_REF] Escoffier | Weighted coloring: further complexity and approximability results[END_REF][START_REF] Halldorsson | Batch coloring flat graphs and thin[END_REF][START_REF] Kavitha | Max-coloring paths: Tight bounds and extensions[END_REF], stars of chains [START_REF] Lucarelli | On the max-weight edge coloring problem[END_REF] and bounded degree trees [START_REF] Bourgeois | Approximating the maxedge-coloring problem[END_REF]. It is interesting that the complexity of the MEC problem on trees remains open.

Concerning the approximability of the MEC problem, a natural greedy 2approximation algorithm for general graphs has been proposed in [START_REF] Kesselman | Nonpreemptive scheduling of optical switches[END_REF]. For bipartite graphs of maximum degree ∆ = 3, an algorithm that attains the 7/6 inapproximability bound has been presented in [START_REF] De Werra | Weighted coloring on planar, bipartite and split graphs: Complexity and approximation[END_REF]. For bipartite graphs of small maximum degrees, algorithms which improve the 2 approximation ratio have been also presented. However, the ratios of these algorithms either exceed 2 [START_REF] Escoffier | Weighted coloring: further complexity and approximability results[END_REF] or tend asymptotically to 2 [START_REF] Lucarelli | On the max-weight edge coloring problem[END_REF][START_REF] Bourgeois | Approximating the maxedge-coloring problem[END_REF] as the maximum degree of the input graph increases. In [START_REF] Bourgeois | Approximating the maxedge-coloring problem[END_REF] has been also presented a 3/2-approximation algorithm for trees, and an asymptotic 4/3-approximation algorithm for general graphs with bi-valued edge weights and arbitrarily large maximum degree ∆.

The MVC problem has been also studied extensively during last years. It is known to be non approximable within a factor less than 8/7 even for planar bipartite graphs, unless P=NP [START_REF] Demange | Time slot scheduling of compatible jobs[END_REF][START_REF] Pemmaraju | Approximation algorithms for the max-coloring problem[END_REF]. This bound is tight for general bipartite graphs as an 8/7-approximation algorithm is also known [START_REF] De Werra | Weighted coloring on planar, bipartite and split graphs: Complexity and approximation[END_REF][START_REF] Pemmaraju | Approximation algorithms for the max-coloring problem[END_REF]. For the MVC problem on trees a PTAS has been presented in [START_REF] Pemmaraju | Approximation algorithms for the max-coloring problem[END_REF][START_REF] Escoffier | Weighted coloring: further complexity and approximability results[END_REF], while the complexity of this case is open. Other results for the MVC problem on several graph classes have been also presented in [START_REF] Demange | Time slot scheduling of compatible jobs[END_REF][START_REF] De Werra | Weighted coloring on planar, bipartite and split graphs: Complexity and approximation[END_REF][START_REF] Pemmaraju | Buffer minimization using max-coloring[END_REF][START_REF] Pemmaraju | Approximation algorithms for the max-coloring problem[END_REF][START_REF] Escoffier | Weighted coloring: further complexity and approximability results[END_REF][START_REF] Epstein | On the max coloring problem[END_REF][START_REF] Kavitha | Max-coloring paths: Tight bounds and extensions[END_REF].

Our results and organization of the paper. The two most interesting open questions about the MEC problem concern the existence of an approximation algorithm of ratio 2 -δ, for any constant δ > 0, for general or bipartite graphs, and the complexity of the problem on trees. In this paper we present substantial improvements towards these questions. In the next section we present a PTAS for the MEC problem on trees; recall that the situation for the MVC problem on trees is the same: a PTAS is known while its complexity remains unknown. In Section 3, we succeed to beat the longstanding 2 approximation ratio for the MEC problem in bipartite graphs by presenting an 1.74-approximation algorithm. In addition, in Section 4, we adapt our algorithm for bipartite graphs to general graphs yielding an approximation ratio which also tends asymptotically to 1.74 as the maximum degree of the input graph increases. Finally, we conclude in Section 5.

Notation. In the following, we consider the MEC problem on an edge-weighted graph

G = (V, E), |V | = n, |E| = m,
where a positive integer weight w(e) is associated with each edge e ∈ E. We denote by

M = {M 1 , M 2 , . . . , M k } a proper k-edge-coloring of G of weight W = ∑ k i=1 w i , where w i = max{w(e)|e ∈ M i }, 1 ≤ i ≤ k. By M * = {M * 1 , M * 2 , . . . , M * k * }

A PTAS for trees

In [START_REF] Bourgeois | Approximating the maxedge-coloring problem[END_REF] a 2-approximation algorithm (Algorithm Trees) for the MEC problem on trees has been presented. This algorithm in conjunction with the 2approximation algorithm for general graphs [START_REF] Kesselman | Nonpreemptive scheduling of optical switches[END_REF] has led to a 3 2 ratio for trees. In this section we also exploit Algorithm Trees to derive a PTAS.

Next proposition is proven in [START_REF] Bourgeois | Approximating the maxedge-coloring problem[END_REF].

Proposition 1. Algorithm Trees constructs a solution of exactly ∆ matchings in O(|V | • ∆ • log ∆) time.
For the weights of the matchings in this solution it holds that w 1 = w * 1 and

w i ≤ w * i-1 , 2 ≤ i ≤ ∆.
To obtain our scheme we shall use a transformation of our problem to the following list edge-coloring problem.

List Edge-Coloring ( LEC) problem

Instance: A graph G = (V, E), a set of k colors and a list of colors ϕ(e) ⊆ {1, 2, . . . , k} for each e ∈ E. Question: Is there a k-edge-coloring of G such that each edge e is assigned a color in its list ϕ(e)?

The MEC and LEC problems are strongly related: Given an edge-weighted graph G = (V, E), consider a combination of k edges' weights

w 1 ≥ w 2 ≥ • • • ≥
w k and answer to the following LEC problem on G: is there a k-edge-coloring of G such that each edge e ∈ E is assigned a color in ϕ(e) = {i : w(e) ≤ w i , 1 ≤ i ≤ k}? Then, a "yes" answer to this question corresponds to a feasible solution for the MEC problem of weight W = ∑ k i=1 w i . There are O(|E| k ) combinations of weights to be considered and an optimal solution to the MEC problem corresponds to the combination where W is minimized.

It is known that the LEC problem can be solved in O(|E| • ∆ 3.5 ) time for trees [START_REF] De Werra | Restrictions and preassignments in preemptive open shop scheduling[END_REF], while it becomes NP-complete for bipartite graphs even for three colors (k = 3) [START_REF] Kubale | Some results concerning the complexity of restricted colorings of graphs[END_REF].

Therefore, the next proposition follows.

Proposition 2. For a fixed number of matchings k the MEC problem on trees is polynomial.

Our scheme splits a tree G = (V, E), into subgraphs G[E 1,j ] and G[E j+1,m ] induced by the j heaviest and the n -j lightest edges of G, respectively (by convention, we consider G[E 1,0 ] as an empty subgraph). Our scheme depends on a parameter p such that all the edges of G of weights w * 1 , w Proof. Consider the iteration j, j ≤ m, of the algorithm where the weight of the heaviest edge in G[E j+1,m ] equals to the weight of the i-th matching of an optimal solution, i.e. w(e j+1 ) = w * i , 1 ≤ i ≤ p. The edges of G[E 1,j ] are a subset of those appeared in the i -1 heaviest matchings of the optimal solution. Thus, an optimal solution for G[E 1,j ] is of weight

OP T 1,j ≤ w * 1 + w * 2 + . . . + w * i-1 .
The edges of G[E j+1,m ] are a superset of those appeared in the k * -(i -1) lightest matchings of the optimal solution. The extra edges of G[E j+1,m ] are of weight at most w * i and appear in an optimal solution into at most i-1 matchings. Thus, an optimal solution for G[E j+1,m ] is of weight

OP T j+1,m ≤ w * i + w * i+1 + . . . + w * k * + (i -1) • w * i = i • w * i + w * i+1 + . . . + w * k * .
By Proposition 1, Algorithm Trees returns a solution for

G[E j+1,m ] of weight W j+1,m ≤ OP T j+1,m + w * i -w * ∆ ≤ i • w * i + w * i+1 + . . . + w * k * + w * i ≤ (i + 1) • w * i + w * i+1 + . . . + w * k * .
Therefore, the solution found in this iteration j for the whole graph G is of weight

W i = OP T 1,j + W j+1,m ≤ w * 1 + w * 2 + . . . + w * i-1 + (i + 1) • w * i + w * i+1 + . . . + w * k * .
As the algorithm returns the best among the solutions found, we have p bounds on the weight W of this best solution, i.e.,

W i ≤ w * 1 + w * 2 + . . . + w * i-1 + (i + 1) • w * i + w * i+1 + . . . + w * k * , 1 ≤ i ≤ p.
To derive our ratio we denote by c ji , 1 ≤ i, j ≤ p, the coefficient of the weight w * j in the i-th bound on W and we find the solution of the system of linear equations C • x T = 1 T . Using the standard Gaussian elimination method, we get the following solution:

x i = 1 i • (H p + 1) , 1 ≤ i ≤ p.
By multiplying both sides of the i-th, 1 ≤ i ≤ p, inequality by x i and adding up all of them we have

( p ∑ i=1 1 i • (H p + 1) ) •W ≤ OP T , that is W OP T ≤ H p + 1 H p = 1 + 1 H p .
Algorithm Scheme(p) iterates |E| times. In each iteration: (i) an optimal solution, if any, with at most p-1 matchings for G[E 1,j ] is found by Proposition 2 in ). Consequently, we have a PTAS for the MEC problem on trees, that is an approximation ratio of 1+ 1 Hp = 1+ϵ within time O

O(|E| p-1 •|E|•∆ 3.
( |E| ( |V | • ∆ • log ∆ + |E| p • ∆ 3.5 )) . ⊓ ⊔

Beating the 2-approximation ratio for bipartite graphs

A promising idea in order to create an approximation algorithm for the MEC problem on bipartite graphs is to repeatedly partition the input graph into a number of edge induced subgraphs and then to find a solution for each of them independently. In fact, this is the idea behind the known approximation algorithms of ratios less than 2 for the MEC problem on bipartite graph [3, 7, 2], as well as the 8/7-approximation algorithm for the MVC problem on bipartite graphs [START_REF] De Werra | Weighted coloring on planar, bipartite and split graphs: Complexity and approximation[END_REF][START_REF] Pemmaraju | Approximation algorithms for the max-coloring problem[END_REF]. However all known algorithms for the MEC problem that follow this idea achieve ratios which either exceed 2 or tend asymptotically to 2 as the maximum degree of the input graph increases. In this section we exploit the same idea and we are able to show an 1.74-approximation ratio for the MEC problem on bipartite graphs. Consider an ordering ⟨E⟩ = ⟨e 1 , e 2 , . . . , e m ⟩ of the edges of G. Let us denote by (p, q), 0

≤ p < q ≤ m, a partition of G into subgraphs G[E 1,p ], G[E p+1,q ]
and G[E q+1,m ]; by convention, we define E 1,0 = ∅ and E 0,q = E 1,q . By ∆ 1,q we denote the maximum degree of the subgraph G[E 1,q ]. For a partition (p, q) of G, we define a critical set of edges

A ⊆ E p+1,q , such that each vertex u ∈ V of degree d 1,q (u) > ∆ 1,p has degree d 1,q (u) -∆ 1,p ≤ d A (u) ≤ ∆ 1,q -∆ 1,p .
The proposed algorithm relies on the existence of such a critical set of edges A: a solution for the subgraph G[E 1,q ] is found by concatenating a ∆ 1,p -coloring solution for the subgraph G[E 1,q \ A] and a (∆ 1,q -∆ 1,p )-coloring solution for the subgraph G[A], if A exists, and by a ∆ 1,q -coloring of the subgraph G[E 1,q ], otherwise. For each partition (p, q), the algorithm computes a solution for the input graph G by concatenating a solution for G[E 1,q ] and a ∆-coloring solution for G[E q+1,m ]. The algorithm computes also a ∆-coloring solution for the input graph and returns the best among them.

The following lemma shows that the check in Line 4 of Algorithm Bipartite can be done in polynomial time.

Lemma 1. For a partition (p, q) of a graph G = (V, E), a critical set of edges A, if any, can be found in

O(|V | 3 ) time. Proof. A (g, f )-factor of a graph G is a spanning subgraph F such that g(u) ≤ d F (u) ≤ f (u), for all u ∈ V . Recall that A ⊆ E p+1,q and consider the subgraph G[E p+1,q ]. For each vertex u of G[E p+1,q ] we define g(u) = max{0, d 1,q (u)-∆ 1,p } and f (u) = ∆ 1,q -∆ 1,p .
Then, there exists a critical set of edges A ⊆ E p+1,q if and only if there exists a (g, f )-factor in G[E p+1,q ]. It is known that such a factor, if any, can be found in O(|V | 3 ) time [START_REF] Anstee | An algorithmic proof of Tutte's f -factor theorem[END_REF].

⊓ ⊔ Theorem 2. Algorithm Bipartite achieves an 1.74-approximation ratio for the MEC problem on bipartite graphs.

Algorithm Bipartite 1: Find a ∆-coloring solution for G; 2: for p = 0 to m -1 do 3: for q = p + 1 to m do 4:

Find, if any, a critical set of edges A in G[Ep+1,q]; 5:

if A exists then 6:

Find a ∆1,p-coloring solution for G[E1,q \ A]; 7:

Find a (∆1,q -∆1,p)-coloring solution for G[A]; 8: else 9:

Find a ∆1,q-coloring solution for G[E1,q]; 10:

Find a ∆-coloring solution for G[Eq+1,m]; 11:

Find a solution for G by concatenating the solutions found either in Lines 6,7 or in Line 9 with the one found in Line 10; 12: Return the best among the solutions found in Lines 1 and 11;

Proof. The solution obtained by a ∆-coloring of the input graph computed in Line 1 of the algorithm is of weight

W 1 ≤ ∆ • w * 1 . Consider the partition (p, q) of G where w(e p+1 ) = w * ⌈ i 2 ⌉ and w(e q+1 ) = w * i , for 2 ≤ i ≤ ∆ (recall that w * 1 ≥ w * 2 ≥ • • • ≥ w * k * and k * ≥ ∆).
In such an iteration, all the edges in E 1,p belong to

⌈ i 2 ⌉ -1 ≥ ∆ 1,
p matchings of an optimal solution M * , and all the edges in E 1,q belong to i-1 ≥ ∆ 1,q colors of an optimal solution M * .

If ∆ 1,q = ∆ 1,p then the set A does not exist. Hence, a ∆ 1,q -coloring of G[E 1,q ] yields a solution of weight at most

(⌈ i 2 ⌉ -1 ) • w * 1 for this subgraph. If ∆ 1,q > ∆ 1,p then a critical set of edges A exists. Indeed, in this case the matchings M * ⌈ i 2 ⌉ , M * ⌈ i 2 ⌉+1
, . . . , M * i-1 of M * always contain some edges from E p+1,q , for otherwise all the edges in E 1,q belong to ⌈ i 2 ⌉ -1 matchings of M * , a contradiction; these edges of E p+1,q could be a critical set of edges A for the partition (p, q). Thus, a ∆ 1,p -coloring solution of G[E 1,q \ A] and a (∆ 1,q -∆ 1,p )coloring solution for G[A] yield a solution for the subgraph

G[E 1,q ] of weight at most ∆ 1,p • w * 1 + (∆ 1,q -∆ 1,p ) • w * ⌈ i 2 ⌉ ≤ (⌈ i 2 ⌉ -1 ) • w * 1 + ⌊ i 2 ⌋ • w * ⌈ i 2 ⌉
, since

∆ 1,p ≤ ⌈ i 2 ⌉ -1, ∆ 1,q ≤ i -1 and w * 1 ≥ w * ⌈ i 2 ⌉
.

Finally, a ∆-coloring solution for G[E q+1,m ] is of weight at most ∆ • w * i . Hence, for such a partition (p, q) the algorithm finds a solution for the whole input graph of weight

W i ≤ (⌈ i 2 ⌉ -1 ) • w * 1 + ⌊ i 2 ⌋ • w * ⌈ i 2 ⌉ + ∆ • w * i , 2 ≤ i ≤ ∆.
As in the case of trees, the algorithm returns the best among the solutions found. Hence, we have ∆ bounds on the weight W of this best solution, i.e.,

W 1 ≤ ∆ • w * 1 , if i = 1, and
W i ≤ (⌈ i 2 ⌉ -1 ) • w * 1 + ⌊ i 2 ⌋ • w * ⌈ i 2 ⌉ + ∆ • w * i , if 2 ≤ i ≤ ∆.
Solving again the system of linear equations C•x T = 1 T , where c ji , 1 ≤ i, j ≤ ∆, is the coefficient of the weight w * j in the i-th bound on W , we get the following solution for the case where the maximum degree of the graph is a power of 2:

xi =                ⌊ log ∆ i ⌋ ∑ j=0   - ( -1 ∆ ) j+1 2 j ∑ y=1   j ∏ z=1 ( 2 z-1 (i -1) + ⌈ y 2 j-z+1 - 1 2 ⌉)     , if ∆ ≥ i ≥ 2 1 ∆   1 -x2 - ∆ ∑ j=3 (⌈ j 2 ⌉ -1 ) xj   , if i = 1.
For the case where the maximum degree of the input graph is not a power of 2 the solution of the system becomes more complicated:

xi = ⌊ log ∆ i ⌋ ∑ j=0   - ( -1 ∆ ) j+1 2 j ∑ y=1   j ∏ z=1 ( 2 z-1 (i -1) + ⌈ y 2 j-z+1 - 1 2 ⌉)     - ( -1 ∆ ) ⌊ log ∆ i ⌋ +2  ∆-i+1- ∑ ⌊ log ∆ i ⌋ r=0 ((i-1)2 r )   ∑ y=1     ⌊ log ∆ i ⌋ +1 ∏ z=1 ( 2 z-1 (i -1) + ⌈ y 2 ⌊ log ∆ i ⌋ +2-z - 1 2
⌉)    
while x 1 is the same as in the previous case.

For both cases, it holds that

W OP T ≤ 1 ∑ ∆ i=1 x i
. Using Mathematica, we computed the above ratio for quite large values of ∆, and it is found to tend to 1.74 (see Table 1 in our concluding section).

⊓ ⊔

It is an interesting question is whether a close formula for this ratio can be computed.

An adaptation for general graphs

The idea of splitting the input graph into three edge induced subgraphs and creating a ∆-coloring solution for each of them can be also exploited for general graphs. However, in this case, it is NP-complete to find, if any, a ∆-coloring solution of the input graph [START_REF] Holyer | The NP-completeness of edge-coloring[END_REF]. Instead of this, a (∆ + 1)-coloring solution can be found in polynomial time [START_REF] Gabow | Algorithms for edge-coloring graphs[END_REF]. Note that Lemma 1 holds for general graphs, and hence a critical set of edges A, if any, can be found in polynomial time. Theorem 3. There is an asymptotic 1.74-approximation ratio for the MEC problem on general graphs.

Proof. The analysis is almost the same as in the bipartite case. Considering the partition (p, q) where w(e p+1 ) = w * ⌈ i 2 ⌉

and w(e q+1 ) = w * i ; the difference is that if the set A exists then at most (i) a

⌈ i 2 ⌉ -coloring solution is created for G[E 1,q \A], (ii) a (⌊ i 2 ⌋ + 1 ) -coloring solution is created for G[A], and (iii) a (∆ + 1)-coloring solution is created for G[E q+1,m ].
Therefore, as in the previous case we have ∆ bounds on the weight W of this best solution, i.e.,

W 1 ≤ (∆ + 1) • w * 1 , if i = 1, W 2 ≤ w * 1 + (∆ + 1) • w * 2 , if i = 2, W 3 ≤ w * 1 + w * 2 + (∆ + 1) • w * 3 , if i = 3, W 4 ≤ w * 1 + 3w * 2 + (∆ + 1) • w * 4 , if i = 4, and
W i ≤ ⌈ i 2 ⌉ • w * 1 + (⌊ i 2 ⌋ + 1 ) • w * ⌈ i 2 ⌉ + (∆ + 1) • w * i , if 5 ≤ i ≤ ∆.
Note that, for i = 2, 3 or 4, the subgraph G[E 1,q \ A] is of maximum degree at most one, and hence an optimal solution of one matching is created in this case. Analogous remark can be done for the subgraph G[A] for i = 3.

Solving the adapted system of linear equations as in the proof of Theorem 2, we find a solution x i , 1 ≤ i ≤ ∆, such that

W OP T ≤ 1 ∑ ∆ i=1 x i
. For the case where the maximum degree of the graph is a power of 2, this solution is:

xi =                    ∑ ⌊ log ∆ i ⌋ j=0
( -

( -1 ∆+1 ) j+1 ∑ 2 j y=1 ( ∏ j z=1 ( 2 z-1 (i -1) + ⌈ y 2 j-z+1 + 1 2 ⌉)) ) , if ∆ ≥ i ≥ 5 1-4x 7 -5x 8 ∆+1 , if i = 4 1-3x 5 -4x 6 ∆+1 , if i = 3 1-x 3 -3x 4 ∆+1 , if i = 2 1 ∆+1 ( 1 -x2 -x3 -x4 - ∑ ∆ j=5 ⌈ j 2 ⌉ xj ) , if i = 1.
Using again Mathematica we computed this ratio which tends asymptotically to 1.74 as ∆ increases (see Table 1

below).

⊓ ⊔

Conclusions

We presented new results towards two open questions for the MEC problem; its complexity on trees, and the existence of an approximation algorithm for general and bipartite graphs of ratio 2 -δ, for any constant δ. We decrease the approximability gaps for both questions by presenting a PTAS for trees (improving the known 3/2 approximation ratio), and an 1.74-approximation algorithm for bipartite and general graphs (see Table 1). To explain the behavior of our approximation ratios it is worth to observe that the ratio for bipartite graphs increases with ∆, while for general graphs decreases with ∆. This is because we use (∆ + 1)-colorings for general graphs, instead of ∆-colorings for bipartite graphs. Recall that the standard ∆+1 ∆ -approximation ratio for the classical edge-coloring problem (implied by Vizing's Theorem) also decreases with ∆.

  we denote an optimal solution to the MEC problem on the graph G of weight OP T = ∑ k * i=1 w * i . By d G (u) (or simply d(u)) we denote the degree of vertex u ∈ V and by ∆(G) (or simply ∆) the maximum degree of the graph G. For a subset of edges of G, E ′ ⊆ E, |E ′ | = m ′ , we denote by G[E ′ ] the subgraph of G induced by the edges in E ′ and by ⟨E ′ ⟩ = ⟨e 1 , e 2 , . . . , e m ′ ⟩ an ordering of the edges in E ′ such that w(e 1 ) ≥ w(e 2 ) ≥ • • • ≥ w(e m ′ ).

  5 ) time and (ii) Algorithm Trees of complexity O(|V |•∆•log ∆) is called for G[E j+1,m ]. Choosing p such that ϵ = 1 Hp we get p = O(2 1 ϵ

  We obtain a solution for the whole graph by concatenating an optimal solution of at most p -1 colors for G 1,j , if there is one, and the solution obtained by Algorithm Trees for G[E j+1,m ]. Algorithm Scheme(p) is a PTAS for the MEC problem on trees.

	5:	Find an optimal solution for G[E1,j] with at most p -1 matchings;
	6:	Run Algorithm Trees for G[Ej+1,m];
	7:	Concatenate the two solutions found in Lines 5 and 6;
	8: Return the best solution found;
	Theorem 1.

* 2 , . . . , w * p-1 are in a subgraph G[E 1,j ]. Algorithm Scheme(p) 1: Let ⟨E⟩ = ⟨e1, e2, . . . em⟩; 2: for j = 0 to m do 3: Split the graph into two edge induced subgraphs: -G[E1,j] induced by edges e1, e2, . . . , ej -G[Ej+1,n] induced by edges ej+1, ej+2, . . . , em 4: if there is a solution for G[E1,j] with at most p -1 matchings then

Table 1 .

 1 Bipartite graphs 1.60188 1.71809 1.73409 1.73612 1.73637 1.73640 General graphs 1.99605 1.78855 1.74345 1.73730 1.73652 1.73642 Approximation ratios for the MEC problem on general and bipartite graphs for different values of ∆.

	∆	2 3	2 6	2 9	2 12	2 15	2 18

Acknowledgement. We would like to thank Professor Paris Vassalos for his help on linear algebra methods used in this paper.