Sahar Bsaybes
email: sahar.bsaybes@uca.fr

Alain Quilliot
email: alain.quilliot@uca.fr

Annegret K Wagler
email: annegret.wagler@uca.fr

Fleet management for autonomous vehicles using flows in time-expanded networks

Keywords:

Fleet management for autonomous vehicles using flows in time-expanded networks

The project VIPAFLEET [5] aims at contributing to sustainable mobility through the development of innovative urban mobility solutions by means of fleets of Individual Public Autonomous Vehicles (VIPA) allowing passenger transport in closed sites like industrial areas, medical complexes or airports.

A VIPA is an "autonomous vehicle" that does not require a driver nor an infrastructure to operate, developed by Easymile and Ligier thanks to innovative computer vision guidance technologies [START_REF] Royer | Outdoor autonomous navigation using monocular vision[END_REF][START_REF] Royer | Retour dexpérience après plus de 1000 Km en navette sans conducteur guidée par vision[END_REF].

A fleet of VIPAs shall be used in an industrial site to transport employees and visitors e.g. between parkings, buildings and from or to a restaurant. The fleet is distributed at specified stations to supply internal transportation, and a VIPA can operate in three different circulation modes:

• Tram mode: VIPAs continuously run on predefined cycles in a predefined direction and stop at a station if requested to let users enter or leave.

• Elevator mode: VIPAs run on lines and react to requests by changing their driving direction and moving to a station to let users enter or leave.

• Taxi mode: VIPAs run on a connected network to serve transport requests (from any start to any destination station within given time windows).

This leads to an Online Pickup-and-Delivery Problem in a metric space encoding the considered site, since transport requests are released over time. In [1], tram mode and elevator mode are treated, here we focus on the taxi mode as the most advanced circulation mode for VIPAs. As proposed in [1], we embed the VIPAFLEET management problem in the framework of a metric task system. We encode the studied site as a metric space M = (V, d) induced by a connected network G = (V, E), whose nodes correspond to stations, edges to their physical links in the site, and distances d between two nodes v i , v j ∈ V to the length of a shortest path from v i to v j . In V , we have a distinguished origin v o ∈ V , the depot of the system.

An operator manages a fleet of k VIPAs each with a capacity for Cap passengers. The fleet management shall allow the operator to decide when and how to move the VIPAs in the network, and to assign requests to VIPAs. Any request r j is defined as a 6-tuple r j = (t j , x j , y j , p j , q j , z j ) where • t j is the release date (i.e., the time when r j becomes known),

• x j ∈ V is the origin node, y j ∈ V the destination node,

• p j is the earliest start time, q j the latest possible arrival time,

• z j specifies the number of passengers, where t j ≤ p j , p j + d(x j , y j ) ≤ q j , as well as z j ≤ Cap needs to be satisfied.

The operator decides which requests can be accepted (note that some requests may have to be rejected if, e.g., more requests are specified for a same time window than VIPAs are available in the fleet), and creates tasks τ j = (t j , x j , t pick j , y j , t drop j , z j ) to serve accepted requests r j , indicating that z j passengers have to be picked up at station x j at time t pick j and delivered at station y j at time t drop j , where p j ≤ t pick j ≤ q j -d(x j , y j ) and p j + d(x j , y j ) ≤ t drop j ≤ q j must hold. In order to fulfill tasks, the operator creates tours Γ 1 , . . . , Γ k for the VIPAs to circulate in the network G and to pickup, transport and deliver users s.t.

• each accepted request r j is served (within the time window [p j , q j ]),

• each tour starts and ends in the depot and respects the VIPA capacity Cap. This leads to the following problem:

Problem 1 (Online Taxi Mode Problem (M, σ, p, T, k, Cap) (OTMP))
Given a metric space M = (V, d) induced by a connected network G = (V, E), a sequence of requests σ, profits p for accepted requests, a time horizon [0, T ] and k VIPAs of capacity Cap, determine a maximum subset σ A of accepted requests and find tours Γ 1 , . . . , Γ k of minimum total tour length to serve all requests in σ A .

In order to solve the OTMP, we propose a replan strategy that considers at each moment in time t the subsequence σ(t ) of currently waiting requests (i.e., already released but not yet served requests), determines which requests from σ(t ) can be accepted, and computes optimal (partial) tours to serve them, performs these tours until new requests are released and recomputes σ(t ) and the tours (keeping already accepted requests). Hereby, finding optimal (partial) tours corresponds to solving, in each replanning step, an optimal offline solution on the subsequence σ(t ) (i.e. an optimal solution under the condition that the whole sequence of requests is known in advance).

Algorithm 1 (REPLAN)

Input: (M, σ, p, T, k, Cap)

Output: σ A and tours Γ 1 , . . . , Γ k 1: initialize σ A = ∅, σ(t ) = {r j ∈ σ : t j = 0}, and Γ i = (v 0 , 0) for 1 ≤ i ≤ k 2: WHILE σ = ∅ DO: call OFFLINE(σ A , σ(t ), Γ 1 , . . . , Γ k )
perform the (modified) tours until new requests become known, update σ(t ) 3: return σ A and Γ 1 , . . . , Γ k To compute those optimal solutions for the subsequences σ(t ), we build a time-expanded request network G(t ) = (V , A ) based on σ(t ) and the original network G and consider a flow in G(t ) that corresponds to the studied (partial) tours. To construct G(t ) = (V , A ), we extract the possible start positions P (t ) and start times S(t ) for the VIPAs from the current tours Γ 1 , . . . , Γ k : if VIPA i is currently serving a request r j , then we have P (t ) i = y j and S(t ) i = t drop j ; otherwise, P (t ) i is the current position v of VIPA i and S(t

) i = t . The node set V = V + ∪ V x ∪ V y ∪ (v 0 , T ) is composed of
• the VIPAs start positions and times (P (t ) i , S(t

) i ) for 1 ≤ i ≤ k as sources in V + ,
• all possible origins (x j , t pick j ) of all r j ∈ σ(t ) and all p j ≤ t pick j ≤ q j -d(x j , y j ) in V x ,

• all possible destinations (y j , t drop j ) of all r j ∈ σ(t ) and all p j + d(x j , y j ) ≤ t drop j ≤ q j in V y ,

• a sink node (v 0 , T ) with T = max{t drop j , r j ∈ σ(t )}.

The arc set

A = A + ∪ A R ∪ A L ∪ A -is composed of • source arcs from all nodes (P (t ) i , S(t ) i ) ∈ V + to all reachable origins (x j , t pick j ) ∈ V x whith t + d(v, x j ) ≤ t pick j ,
• request arcs from each (x j , t pick j

) ∈ V x to (y j , t pick j + d(x j , y j )) ∈ V y in A R ,
• link arcs from all destinations (y j , t drop j ) ∈ V y to all reachable origins (y i , t pick i

) ∈ V x with t drop j + d(y j , x i ) ≤ t pick i in A L ,
• sink arcs from all destinations (y j , t drop j

) ∈ V y to (v 0 , T ) in A -.
To keep previously accepted requests, we partition σ(t ) into the subsequences

• σ A (t )

of previously accepted but not yet served requests and

• σ N (t ) = {r j ∈ σ : t j = t } of newly released requests, and partition the request arcs accordingly in A R A and A R N . Moreover, let A j R A , A j R N be the subsets of request arcs of the corresponding previously accepted request r j ∈ σ A (t ) resp. newly released request r j ∈ σ N (t ).

In G(t ), we solve the following max profit flow problem

+ (v,t) f (a) = k(v) ∀(v, t) ∈ V + (1b) a∈δ -(v,t) f (a) = a∈δ + (v,t) f (a) ∀(v, t) ∈ V x ∪ V y (1c) a∈A j R A f (a) = 1 ∀A j R A ⊆ A R A (1d) a∈A j R N f (a) ≤ 1 ∀A j R N ⊆ A R N (1e) f (a) ≥ 0 ∀a ∈ A (1f) f (a) ∈ Z ∀a ∈ A (1g)
where δ -(v, t) denotes the set of outgoing arcs of (v, t), δ + (v, t) the set of incoming arcs of (v, t) and k(v) the number of VIPAs initially situated in v. Constraints (1d) ensure that previously accepted requests are served whereas constraints (1e) allow to reject newly released requests. Source, flow conservation and nonnegativity constraints (1b), (1c), (1f) together give rise to a totally unimodular matrix, but due to (1d) and (1e) the entire constraint matrix is not totally unimodular s.t. integrality constraints (1g) are required.

From the computed flow f in the request network G(t ), it is straitforward to determine newly accepted requests (corresponding to request arcs a ∈ A R N with f (a) > 0) and to construct tours Γ 1 , . . . , Γ k for the VIPAs by standard flow decomposition techniques, see e.g. [START_REF] Schrijver | Theory of linear and integer progr[END_REF].

In the special case of tight time windows satisfying p j + d(x j , y j ) = q j (which clearly results in p j = t pick j and q j = t drop j ) for all r j ∈ σ, there is exactly one request arc per request s.t. the entire constraint matrix becomes totally unimodular which implies: Corollary 1 The Offline Taxi Mode Problem with tight time windows can be solved in polynomial time.

In the general case, this is not true, but experiments show that the running times to solve the Offline Taxi Mode Problem are still reasonable, see Table ??. Regarding the quality of the solutions obtained by REPLAN, we note that • in theory, REPLAN is not competitive since there is no finite c s.t. for all instances σ we have that REPLAN(σ) ≤ c OPT(σ),

• in practice, REPLAN provides solutions of good quality within reasonably short time for each recomputation step, see again Table ??.

Hence, we can conclude that REPLAN is a promising algorithm to handle the OTMP for the taxi mode in the studied VIPAfleet management system.

Algorithm 2 (

 2 OFFLINE) Input: σ A , σ(t ), Γ 1 , . . . , Γ k Output: modified σ A and tours Γ 1 , . . . , Γ k 1: determine VIPA start positions P (t ) and start times S(t ) from Γ 1 , . . . , Γ k 2: create the request network G(t ) 3: solve the max profit flow problem (1) on G(t ) 4: update σ A and Γ 1 , . . . , Γ k accordingly and return them

  a∈δ

This work was founded by the French National Research Agency, the European Commission (Feder funds) and the Région Auvergne in the Framework of the LabEx IMobS3.


Sahar Bsaybes

Alain Quilliot
email: alain.quilliot@uca.fr

Annegret K Wagler
email: annegret.wagler@uca.fr

Fleet management for autonomous vehicles using multicommodity coupled flows in time-expanded networks

VIPAFLEET is a framework to develop models and algorithms for managing a fleet of Individual Public Autonomous Vehicles (VIPA). We consider a homogeneous fleet of such vehicles distributed at specified stations in a closed site to supply internal transportation, where the vehicles can be used in different modes of circulation (tram mode, elevator mode, taxi mode). We treat in this paper a variant of the Online Pickup-and-Delivery Problem related to the taxi mode by means of multicommodity coupled flows in a time-expanded network and propose a corresponding integer linear programming formulation. This enables us to compute optimal offline solutions and to apply the well-known meta-strategy Replan to the online situation. As it turned out that Replan requires too long computation times, we devise a heuristic approach h-Replan based on the flow formulation. Finally, we evaluate the performance of Replan and h-Replan in comparison with the optimal offline solutions, both in terms of competitive analysis and computational experiments, showing that h-Replan computes reasonable solutions, so that it suits for the online situation.

Introduction

The project VIPAFLEET aims at contributing to sustainable mobility through the development of innovative urban mobility solutions by means of fleets of Individual Public Autonomous Vehicles (VIPA) allowing passenger transport in closed sites like industrial areas, medical complexes, campuses, or airports. This innovative project involves different partners in order to ensure the reliability of the transportation system [10]. A VIPA is an autonomous vehicle that does not require a driver nor an infrastructure to operate. It is developed by Easymile and Ligier [8,9] thanks to innovative computer vision guidance technologies [START_REF] Royer | Outdoor autonomous navigation using monocular vision[END_REF][START_REF] Royer | Retour dexprience aprs plus de 1000 km en navette sans conducteur guide par vision[END_REF], whereas the fleet management aspect is studied in [?].

A fleet of VIPAs shall be used in a closed site to transport employees, customers and visitors e.g. between parkings, buildings and from or to the restaurant at lunch breaks. The fleet is distributed at specified stations within the site. To supply internal transportation, a VIPA can operate in three different transportation modes:

• Tram mode: VIPAs continuously run on predefined cycles in a predefined direction and stop at a station if requested to let users enter or leave. • Elevator mode: VIPAs run on predefined lines and react to requests by moving to a station to let users enter or leave, thereby changing their driving direction if needed. • Taxi mode: VIPAs run on a connected network to serve transport requests (from any start to any destination station within the network within given time windows).

This leads to a Pickup-and-Delivery Problem (PDP) under special constraints in a metric space encoding the considered closed site, where a fleet of servers shall transport goods or persons from a certain origin to a certain destination. If persons have to be transported, we usually speak about a Dial-a-Ride Problem.

Many variants are studied in the literature, including the Dial-a-Ride Problem with time windows [START_REF] Deleplanque | Transfers in the on-demand transportation: the DARPT Dial-a-Ride Problem with transfers allowed[END_REF][START_REF] Fabri | Online dial-a-ride problem with time windows: an exact algorithm using status vectors[END_REF]. In our case, we are confronted with an online situation, where transportation requests are released over time [START_REF] Ascheuer | Online dial-a-ride problems: Minimizing the completion time[END_REF][START_REF] Berbeglia | Dynamic pickup and delivery problems[END_REF][START_REF] Cordeau | The dial-a-ride problem: models and algorithms[END_REF]. Problems of this type are known to be N P-hard, see e.g. [START_REF] Karel | Complexity of vehicle routing and scheduling problems[END_REF], which also applies to the problem variant considered here, see Section ?? for details. In [?], we focus on the economic aspect of the problem where the objective is to minimize costs; several algorithms are presented and evaluated w.r.t. minimizing the total tour length for the tram and elevator mode that handle the requests coming online, solve a PDP, and generate tours for the VIPAs in order to serve the transport requests.

The taxi mode is the most advanced circulation mode for VIPAs in the dynamic fleet management system. The transport requests are released over time and need to be served within a specified time window. Due the time windows, it is not always possible to serve all transport requests (e.g., if more requests are specified for a same time window than VIPAs are available in the fleet). Hence, the studied PDP is an admission problem as it includes firstly to accept/reject requests and secondly to generate tours for the VIPAs to serve the accepted requests. We are confronted with both the quality-of-service aspect of the problem (with the goal to accept as many requests as possible) and the economic aspect (with the goal to serve the accepted requests at minimum costs, expressed in terms of minimizing the total tour length of the constructed tours), see again Section ?? for details.

In [?,?], a variant of the PDP is studied where the tours are supposed to be nonpreemptive and at each time, (at most) one customer can be transported by a VIPA (note: one customer can be a group of people less than the capacity of the VIPA), and a VIPA cannot serve other requests until the current one is delivered. This leads to a load non-preemptive DARP with time windows or PDPTW and server capacity 1, where the goal is to accept as many requests as possible and to find a tour of minimal length to serve all accepted requests.

In order to solve this problem, three approaches are considered:

• a simple heuristic, the Earliest Pickup Heuristic, that incrementally constructs tours by always choosing from the subsequence σ(t ) of currently waiting requests this request with smallest possible start time and appending it to the tour with shortest distance from its current end to the requested origin; • the two well-known meta-strategies Replan and Ignore (which are proposed in [?] for the ??? problem and can be applied to any online problem in timestamp model, see e.g. [?,?,?]) that determine which requests from σ(t ) can be accepted, and compute optimal (partial) tours to serve them, where • Replan performs these tours until new requests are released, but • Ignore completely performs these tours before it checks for newly released requests.

It is natural to interpret the PDPTW by means of flows in a time expanded network [START_REF] Groß | Generalized maximum flows over time[END_REF][START_REF] Koch | Continuous and discrete flows over time[END_REF] as, e.g., proposed by [START_REF] Jr | Constructing maximal dynamic flows from static flows[END_REF] for PDPTW. In this work, we propose an approach for the taxi mode by flows in time expanded network where one request can be handled at a time by a vehicle and

• the time windows of the requests are restrictive so that if a customer wants to be picked up from a station u at time t u and delivered and station v at time t v where the shortest distance between u and v is d(u, v) we have precisely t u + d(u, v) = t v , maybe remove this since we don't model this in detail but we put a note at the of the IP for restrictive time windows

• the time windows of a request are large so that there is an interval of time (tight or not) when the customer can be picked up and another when the customer can be delivered and

t u + d(u, v) ≤ t v .
Based on these criterias, we model the taxi mode of the dynamic fleet management system with time windows which allow us to solve a max-profit flow problem to balance the profit of accepted requests against the cost for serving them, see Section 3. change this part after finalizing the second model, check whether we propose a heuristic for large time windows or still the computation time is reasonable... The constraint matrix of the resulting integer linear programming formulation is totally unimodular. This enables us to compute optimal offline solutions easily since the problem turns out to be polynomial in case the capacity of the vehicle is equal to one and the time windows are restrictive. This is not the case for the large time windows even with a vehicle capacity equal to 1, see Section 3. We, then, devise an approach based on the integer linear programming formulation and show experimentally that it computes reasonable solutions, so that it suits the online situation, see Section 4. We close with computational results and a discussion on the pros and cons of our approaches and future lines of research.


Silvia Bianchi
email: sbianchi@fceia.unr.edu.ar

Mariana Escalante
email: mariana@fceia.unr.edu.ar

Graciela Nasini
email: nasini@fceia.unr.edu.ar

Annegret K Wagler
email: wagler@isima.fr

Lovász-Schrijver PSD-Operator on Claw-Free Graphs

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The context of this work is the study of the stable set polytope, some of its linear and semi-definite relaxations, and graph classes for which certain relaxations are tight. Our focus lies on those graphs where a single application of the Lovász-Schrijver positive semi-definite operator introduced in [START_REF] Lovász | Cones of matrices and set-functions and 0-1 optimization[END_REF] to the edge relaxation yields the stable set polytope.

The stable set polytope STAB(G) of a graph G = (V, E) is defined as the convex hull of the incidence vectors of all stable sets of G (in a stable set all nodes are mutually nonadjacent). Two canonical relaxations of STAB(G) are the edge constraint stable set polytope

ESTAB(G) = {x ∈ [0, 1] V : x i + x j ≤ 1, ij ∈ E},
and the clique constraint stable set polytope

QSTAB(G) = {x ∈ [0, 1] V : x(Q) = i∈Q x i ≤ 1, Q ⊆ V clique}
(in a clique all nodes are mutually adjacent, hence a clique and a stable set share at most one node). We have STAB(G) ⊆ QSTAB(G) ⊆ ESTAB(G) for any graph, where STAB(G) equals ESTAB(G) for bipartite graphs, and QSTAB(G) for perfect graphs only [START_REF]On Certain Polytopes Associated with Graphs[END_REF].

According to a famous characterization achieved by Chudnovsky et al. [START_REF] Chudnovsky | The Strong Perfect Graph Theorem[END_REF], perfect graphs are precisely the graphs without chordless cycles C 2k+1 with k ≥ 2, termed odd holes, or their complements, the odd antiholes C 2k+1 . This shows that odd holes and odd antiholes are the only minimally imperfect graphs.

Perfect graphs turned out to be an interesting and important class with a rich structure and a nice algorithmic behavior [START_REF] Grötschel | Geometric Algorithms and Combinatorial Optimization[END_REF]. However, solving the stable set problem for a perfect graph G by maximizing over QSTAB(G) does not work directly [START_REF] Grötschel | The Ellipsoid Method and its Consequences in Combinatorial Optimization[END_REF], but only via a detour involving a geometric representation of graphs [START_REF] Lovász | On the Shannon capacity of a graph[END_REF] and a semi-definite relaxation TH(G) introduced in [START_REF] Grötschel | Geometric Algorithms and Combinatorial Optimization[END_REF].

For some N ∈ Z + , an orthonormal representation of a graph G = (V, E) is a sequence (u i : i ∈ V ) of |V | unit-length vectors u i ∈ R N , such that u i T u j = 0 for all ij ∈ E. For any orthonormal representation of G and any additional unit-length vector c ∈ R N , the orthonormal representation constraint is i∈V (c T u i ) 2 x i ≤ 1. TH(G) denotes the convex set of all vectors x ∈ R

|V | +

satisfying all orthonormal representation constraints for G. For any graph G,

STAB(G) ⊆ TH(G) ⊆ QSTAB(G)
holds and approximating a linear objective function over TH(G) can be done with arbitrary precision in polynomial time [START_REF] Grötschel | Geometric Algorithms and Combinatorial Optimization[END_REF]. Most notably, the same authors proved a beautiful characterization of perfect graphs:

G is perfect ⇔ TH(G) = STAB(G) ⇔ TH(G) = QSTAB(G). (1)
For all imperfect graphs, STAB(G) does not coincide with any of the above relaxations. It is, thus, natural to study further relaxations and to combinatorially characterize those graphs where STAB(G) equals one of them.

Linear relaxations and related graphs. A natural generalization of the clique constraints are rank constraints x(G ′ ) = i∈G ′ x i ≤ α(G ′ ) associated with arbitrary induced subgraphs G ′ ⊆ G. By the choice of the right hand side α(G ′ ), denoting the size of a largest stable set in G ′ , rank constraints are valid for STAB(G). A graph G is called rank-perfect by [START_REF] Wagler | Critical Edges in Perfect Graphs[END_REF] if and only if STAB(G) is described by rank constraints only.

By definition, rank-perfect graphs include all perfect graphs. By restricting the facet set to rank constraints associated with certain subgraphs, several wellknown graph classes are defined, e.g., near-perfect graphs [START_REF] Shepherd | Near-Perfect Matrices[END_REF] where only rank constraints associated with cliques and the whole graph are allowed, or t-perfect [START_REF]On Certain Polytopes Associated with Graphs[END_REF] and h-perfect graphs [START_REF] Grötschel | Geometric Algorithms and Combinatorial Optimization[END_REF] where rank constraints associated with edges, triangles and odd holes resp. cliques of arbitrary size and odd holes suffice.

As common generalization of perfect, t-perfect, and h-perfect graphs, the class of a-perfect graphs was introduced in [START_REF] Wagler | Antiwebs are rank-perfect[END_REF] as graphs G where STAB(G) is given by rank constraints associated with antiwebs. An antiweb A k n is a graph with n nodes 0, . . . , n -1 and edges ij if and only if k ≤ |i -j| ≤ nk and i = j. Antiwebs include all complete graphs K n = A 1 n , odd holes C 2k+1 = A k 2k+1 , and their complements C 2k+1 = A 2 2k+1 . Antiwebs are a-perfect by [START_REF] Wagler | Antiwebs are rank-perfect[END_REF].

A more general type of inequalities is obtained from complete joins of antiwebs, called joined antiweb constraints

i≤k 1 α(A i ) x(A i ) + x(Q) ≤ 1,
associated with the join of some antiwebs A 1 , . . . , A k and a clique Q. We denote the linear relaxation of STAB(G) obtained by all joined antiweb constraints by ASTAB * (G). By construction, we see that

STAB(G) ⊆ ASTAB * (G) ⊆ QSTAB(G) ⊆ ESTAB(G).
In [START_REF] Coulonges | Characterizing and bounding the imperfection ratio for some classes of graphs[END_REF], a graph G is called joined a-perfect if and only if STAB(G) coincides with ASTAB * (G). Besides all a-perfect graphs, further examples of joined a-perfect graphs are near-bipartite graphs (where the non-neighbors of every node induce a bipartite graph) due to [START_REF] Shepherd | Applying Lehman's Theorem to Packing Problems[END_REF].

A semi-definite relaxation and LS + -perfect graphs. In the early nineties, Lovász and Schrijver introduced the PSD-operator LS + (called N + in [START_REF] Lovász | Cones of matrices and set-functions and 0-1 optimization[END_REF]) which, applied to ESTAB(G), generates a positive semi-definite relaxation of STAB(G) stronger than TH(G) (see Section 2.1 for details). In order to simplify the notation we write LS + (G) = LS + (ESTAB(G)). In [START_REF] Lovász | Cones of matrices and set-functions and 0-1 optimization[END_REF] it is shown that

STAB(G) ⊆ LS + (G) ⊆ ASTAB * (G).
As in the case of perfect graphs, the stable set problem can be solved in polynomial time for the class of graphs for which LS + (G) = STAB(G). These graphs are called LS + -perfect, and all other graphs LS + -imperfect (note that they are also called N + -(im)perfect, see e.g. [START_REF] Bianchi | Near-perfect graphs with polyhedral N+(G)[END_REF]). In [START_REF] Bianchi | Near-perfect graphs with polyhedral N+(G)[END_REF], the authors look for a characterization of LS + -perfect graphs similar to the characterization (1) for perfect graphs. More precisely, they intend to find an appropriate polyhedral relaxation P (G) of STAB(G) such that

G is LS + -perfect ⇔ LS + (G) = STAB(G) ⇔ LS + (G) = P (G). (2)
A conjecture has been recently proposed in [START_REF] Bianchi | Lovász-Schrijver PSDoperator and a superclass of near-perfect graphs[END_REF], which can be equivalently reformulated as follows [START_REF] Escalante | Characterizing N+-perfect line graphs[END_REF]:

Conjecture 1 (LS + -Perfect Graph Conjecture). A graph G is LS + -perfect if and only if LS + (G) = ASTAB * (G).
The results of Lovász and Schrijver [START_REF] Lovász | Cones of matrices and set-functions and 0-1 optimization[END_REF] prove that joined a-perfect graphs are LS + -perfect, thus, the conjecture states that LS + -perfect graphs coincide with joined a-perfect graphs and that ASTAB * (G) is the studied polyhedral relaxation of STAB(G) playing the role of P (G) in [START_REF] Bianchi | Lovász-Schrijver PSDoperator and a superclass of near-perfect graphs[END_REF].

In addition, every subgraph of an LS + -perfect graph is also LS + -perfect. This motivates the definition of minimally LS + -imperfect graphs as these LS +imperfect graphs whose proper induced subgraphs are all LS + -perfect. The two smallest such graphs, found by [START_REF] Escalante | Minimal N+-rank graphs: Progress on Lipták and Tunçel's conjecture[END_REF] and [START_REF] Lipták | Stable set problem and the lift-and-project ranks of graphs[END_REF], are depicted in Figure 1. Conjecture 1 has been already verified for near-perfect graphs by [START_REF] Bianchi | Near-perfect graphs with polyhedral N+(G)[END_REF], for fsperfect graphs (where the only facet-defining subgraphs are cliques and the graph itself) by [START_REF] Bianchi | Lovász-Schrijver PSDoperator and a superclass of near-perfect graphs[END_REF], for webs (the complements W k n = A k n of antiwebs) by [START_REF] Escalante | Lovász and Schrijver N+-relaxation on web graphs[END_REF] and for line graphs (obtained by turning adjacent edges of a root graph into adjacent nodes of the line graph) by [START_REF] Escalante | Characterizing N+-perfect line graphs[END_REF], see Section 2.1 for details.

The LS + -Perfect Graph Conjecture for claw-free graphs. The aim of this contribution is to verify Conjecture 1 for a well-studied graph class containing all webs, all line graphs and the complements of near-bipartite graphs: the class of claw-free graphs (i.e., the graphs not containing the complete join of a single node and a stable set of size three).

Claw-free graphs attracted much attention due to their seemingly asymmetric behavior w.r.t. the stable set problem. On the one hand, the first combinatorial algorithms to solve the problem in polynomial time for claw-free graphs [START_REF] Minty | On maximal independent sets of vertices in claw-free graphs[END_REF][START_REF] Sbihi | Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoile[END_REF] date back to 1980. Therefore, the polynomial equivalence of optimization and separation due to [START_REF] Grötschel | Geometric Algorithms and Combinatorial Optimization[END_REF] implies that it is possible to optimize over the stable set polytope of a claw-free graph in polynomial time. On the other hand, the problem of characterizing the stable set polytope of claw-free graphs in terms of an explicit description by means of a facet-defining system, originally posed in [START_REF] Grötschel | Geometric Algorithms and Combinatorial Optimization[END_REF], was open for several decades. This motivated the study of claw-free graphs and its different subclasses, that finally answered this long-standing problem only recently (see Section 2.2 for details).

To verify the conjecture for claw-free graphs, we need not only to rely on structural results and complete facet-descriptions of their stable set polytope, but also to ensure that all facet-inducing subgraphs different from cliques, antiwebs or their complete joins are LS + -imperfect. A graph G is said to be facet-defining if STAB(G) has a full-support facet.

The paper is organized as follows: In Section 2, we present the State-of-the-Art on LS + -perfect graphs (including families of LS + -imperfect graphs needed for the subsequent proofs) and on claw-free graphs, their relevant subclasses and the results concerning the facet-description of their stable set polytopes from the literature. In Section 4, we verify, relying on the previously presented results, Conjecture 1 for the studied subclasses of claw-free graphs. As a conclusion, we obtain as our main result: Theorem 1. The LS + -Perfect Graph Conjecture is true for all claw-free graphs.

We close with some further remarks and an outlook to future lines of research.

2 State-of-the-Art

About LS + -perfect graphs

We denote by e 0 , e 1 , . . . , e n the vectors of the canonical basis of R n+1 (where the first coordinate is indexed zero), 1 the vector with all components equal to 1 and S n + the convex cone of (n × n) symmetric and positive semi-definite matrices with real entries. Given a convex set

K in [0, 1] n , let cone(K) = x 0 x ∈ R n+1 : x = x 0 y; y ∈ K .
Then, we define the polyhedral set

M + (K) = Y ∈ S n+1 + : Y e 0 = diag(Y ), Y e i ∈ cone(K), Y (e 0 -e i ) ∈ cone(K), i = 1, . . . , n} ,
where diag(Y ) denotes the vector whose i-th entry is Y ii , for every i = 0, . . . , n.

Projecting this lifting back to the space R n results in

LS + (K) = x ∈ [0, 1] n : 1 x = Y e 0 , for some Y ∈ M + (K) .
In [START_REF] Lovász | Cones of matrices and set-functions and 0-1 optimization[END_REF], Lovász and Schrijver proved that LS + (K) is a relaxation of the convex hull of integer solutions in K and that LS n

+ (K) = conv(K ∩ {0, 1} n ), where LS 0 + (K) = K and LS k + (K) = LS + (LS k-1 + (K)) for every k ≥ 1.
In this work we focus on the behavior of a single application of the LS +operator to the edge relaxation of the stable set polytope of a graph.

Recall that G LT and G EM N are the smallest LS + -imperfect graphs. Further LS + -imperfect graphs can be obtained by applying operations preserving LS +imperfection.

In [START_REF] Lipták | Stable set problem and the lift-and-project ranks of graphs[END_REF], the stretching of a node v is introduced as follows: Partition its neighborhood N (v) into two nonempty, disjoint sets A 1 and A 2 (so A 1 ∪ A 2 = N (v), and A 1 ∩ A 2 = ∅). A stretching of v is obtained by replacing v by two adjacent nodes v 1 and v 2 , joining v i with every node in A i for i ∈ {1, 2}, and subdividing the edge v 1 v 2 by one node w. In [START_REF] Lipták | Stable set problem and the lift-and-project ranks of graphs[END_REF] it is shown: Theorem 2 ( [START_REF] Lipták | Stable set problem and the lift-and-project ranks of graphs[END_REF]). The stretching of a node preserves LS + -imperfection.

Hence, all stretchings of G LT and G EM N are LS + -imperfect, see Figure 2 for some examples.

In [START_REF] Escalante | Characterizing N+-perfect line graphs[END_REF], the authors characterized LS + -perfect line graphs by showing that the only minimally LS + -imperfect line graphs are stretchings of G LT and G EM N and occur as subgraphs in all facet-defining line graphs different from cliques and odd holes: The proof relies on a result of Edmonds & Pulleyblank [START_REF] Edmonds | Facets of 1-Matching Polyhedra[END_REF] who showed that a line graph L(H) is facet-defining if and only if H is a 2-connected hypomatchable graph (that is, for all nodes v of H, H-v admits a perfect matching). Such graphs H have an ear decomposition H 0 , H 1 , . . . , H k = H where H 0 is an odd hole and H i is obtained from H i-1 by adding an odd path (ear) between distinct nodes of H i-1 . In [START_REF] Escalante | Characterizing N+-perfect line graphs[END_REF], it is shown that the line graph L(H 1 ) of any ear decomposition is a node stretching of G LT and G EM N and, thus, LS + -imperfect by [START_REF] Lipták | Stable set problem and the lift-and-project ranks of graphs[END_REF].

Again, using stretchings of G LT and G EM N and exhibiting one more minimally LS + -imperfect graph, namely the web W 2 10 , LS + -perfect webs are characterized in [START_REF] Escalante | Lovász and Schrijver N+-relaxation on web graphs[END_REF] as follows:

Theorem 4 ( [START_REF] Escalante | Lovász and Schrijver N+-relaxation on web graphs[END_REF]). A web is LS + -perfect if and only if it is perfect or minimally imperfect.

The proof shows that all imperfect not minimally imperfect webs with stability number 2 contain G EM N and all webs W 2 n different from W 2 7 , W 2 10 , some stretching of G LT . Furthermore, all other webs contain some LS + -imperfect W 2 n ′ and are, thus, also LS + -imperfect.

Finally, in [START_REF] Bianchi | Near-perfect graphs with polyhedral N+(G)[END_REF], there is another family of LS + -imperfect graphs presented that will play a central role in some subsequent proofs: Theorem 5 ( [START_REF] Bianchi | Near-perfect graphs with polyhedral N+(G)[END_REF]). Let G be a graph with α(G) = 2 such that Gv is an odd antihole for some node v. G is LS + -perfect if and only if v is completely joined to Gv.

About claw-free graphs

In several respects, claw-free graphs are generalizations of line graphs. An intermediate class between line graphs and claw-free graphs form quasi-line graphs, where the neighborhood of any node can be partitioned into two cliques (i.e., quasi-line graphs are the complements of near-bipartite graphs).

For this class, it turned out that so-called clique family inequalities suffice to describe the stable set polytope. Given a graph G, a family F of cliques and an integer p < n = |F|, the clique family inequality (F, p) is the following valid inequality for STAB(G)

(p -r) i∈W x i + (p -r -1) i∈Wo x i ≤ (p -r) n p (3)
where r = n mod p and W (resp. W o ) is the set of nodes contained in at least p (resp. exactly p -1) cliques of F. This generalizes the results of Edmods [START_REF] Edmonds | Maximum Matching and a Polyhedron with (0,1) Vertices[END_REF] and Edmonds & Pulleyblank [8] that STAB(L(H)) is described by clique constraints and rank constraints

x(L(H ′ )) ≤ 1 2 (|V (H ′ )| -1) (4)
associated with the line graphs of 2-connected hypomatchable induced subgraphs H ′ ⊆ H. Note that the rank constraints of type (4) are special clique family inequalities. Chudnovsky and Seymour [START_REF] Chudnovsky | The structure of claw-free graphs[END_REF] extended this result to a superclass of line graphs. They showed that a connected quasi-line graph G is either a fuzzy circular interval graph or STAB(G) is given by clique constraints and rank constraints of type (4).

Let C be a circle, I a collection of intervals in C without proper containments and common endpoints, and V a multiset of points in C. The fuzzy circular interval graph G(V, I) has node set V and two nodes are adjacent if both belong to one interval I ∈ I, where edges between different endpoints of the same interval may be omitted.

Semi-line graphs are either line graphs or quasi-line graphs without a representation as a fuzzy circular interval graph. Due to [START_REF] Chudnovsky | The structure of claw-free graphs[END_REF], semi-line graphs are rank-perfect with line graphs as only facet-defining subgraphs.

Eisenbrand et al. [START_REF] Eisenbrand | The stable set polytope of quasi-line graphs[END_REF] proved that clique family inequalities suffice to describe the stable set polytope of fuzzy circular interval graphs. Stauffer [START_REF] Stauffer | On the Stable set polytope of claw-free graphs[END_REF] verified a conjecture of [START_REF] Pêcher | Almost all webs are not rank-perfect[END_REF] that every facet-defining clique family inequality of a fuzzy circular interval graph G is associated with a web in G.

All these results together complete the picture for quasi-line graphs. However, there are claw-free graphs which are not quasi-line; the 5-wheel is the smallest such graph and has stability number 2. Due to Cook (see [START_REF] Shepherd | Applying Lehman's Theorem to Packing Problems[END_REF]), all facets for graphs G with α(G) = 2 are clique-neighborhood constraints

2x(Q) + x(N ′ (Q)) ≤ 2 (5)
where

Q ⊆ G is a clique and N ′ (Q) = {v ∈ V (G) : Q ⊆ N (v)}.
Therefore all non-trivial facets in this case are 1, 2-valued. This is not the case for graphs G with α(G) = 3. In fact, all the known difficult facets of claw-free graphs occur in this class. Some non-rank facets with up to five different non-zero coefficients are presented in [START_REF] Giles | On stable set polyhedra for K1,3 -free graphs[END_REF][START_REF] Liebling | On non-rank facets of the stable set polytope of claw-free graphs and circulant graphs[END_REF]. All of these facets turned out to be so-called co-spanning 1-forest constraints due to [START_REF] Pêcher | On facets of stable set polytopes of claw-free graphs with stability number three[END_REF], where it is also shown that it is possible to build a claw-free graph with stability number three inducing a co-spanning 1-forest facet with b different left hand side coefficients, for every positive integer b.

The problem of characterizing STAB(G) when G is a connected claw-free but not quasi-line graph with α(G) ≥ 4 was studied by Galluccio et al.: In a series of results [START_REF] Galluccio | Gear composition and the stable set polytope[END_REF][START_REF] Galluccio | The stable set polytope of claw-free graphs with stability number at least four. I. Fuzzy antihat graphs are W-perfect[END_REF][START_REF] Galluccio | The stable set polytope of claw-free graphs with stability number at least four. II. Striped graphs are G-perfect[END_REF], it is shown that if such a graph G does not contain a clique cutset, then 1,2-valued constraints suffice to describe STAB(G). Here, besides 5-wheels, different rank and non-rank facet-defining inequalities of the geared graph G shown in Fig. 3 play a central role.

In addition, graphs of this type can be decomposed into strips. A strip (G, a, b) is a (not necessarily connected) graph with two designated simplicial nodes a and b (a node is simplicial if its neighborhood is a clique). A claw-free strip containing a 5-wheel as induced subgraph is a 5-wheel strip. Given two node-disjoint strips (G 1 , a 1 , b 1 ) and (G 2 , a 2 , b 2 ), their composition is the union of G 1 \ {a 1 , b 1 } and G 2 \ {a 2 , b 2 } together with all edges between N G1 (a 1 ) and N G2 (a 2 ), and between N G1 (b 1 ) and N G2 (b 2 ) [START_REF] Chudnovsky | The structure of claw-free graphs[END_REF].

As shown in [START_REF] Oriolo | A new algorithm for the maximum weighted stable set problem in claw-free graphs[END_REF], this composition operation can be generalized to more than two strips: Every claw-free but not quasi-line graph G with α(G) ≥ 4 admits a decomposition into strips, where at most one strip is quasi-line and all the remaining ones are 5-wheel strips having stability number at most 3. There are only three "basic" types of 5-wheel strips (see Fig. 3) which can be extended by adding nodes belonging to the neighborhood of the 5-wheels (see [START_REF] Oriolo | A new algorithm for the maximum weighted stable set problem in claw-free graphs[END_REF] for details).

Note that a claw-free but not quasi-line graph G with α(G) ≥ 4 containing a clique cutset may have a facet-inducing subgraph G ′ with α(G ′ ) = 3 (inside a 5-wheel strip of type 3), see [START_REF] Pietropaoli | Some results towards the description of the stable set polytope of claw-free graphs[END_REF] for examples.

Taking all these results together into account gives the complete list of facets needed to describe the stable set polytope of claw-free graphs. 3 LS + -Perfect Graph Conjecture for claw-free graphs

In this section, we verify the LS + -Perfect Graph Conjecture for all relevant subclasses of claw-free graphs.

Graphs with α(G) = 2 play a crucial role. Relying on the behavior of the stable set polytope under taking complete joins [START_REF]On Certain Polytopes Associated with Graphs[END_REF] and the result on LS + -(im)perfect graphs G with α(G) = 2 (Theorem 5), we can prove: Theorem 6. All facet-inducing LS + -perfect graphs G with α(G) = 2 are odd antiholes or complete joins of odd antihole(s) and a (possibly empty) clique.

This shows that all facet-inducing LS + -perfect graphs G with α(G) = 2 are joined a-perfect, and we conclude: Corollary 1. The LS + -Perfect Graph Conjecture is true for graphs with stability number 2.

Quasi-line graphs partition into the two subclasses of semi-line graphs and fuzzy circular interval graphs.

Chudnovsky and Seymour [START_REF] Chudnovsky | The structure of claw-free graphs[END_REF] proved that the stable set polytope of a semiline graph is given by rank constraints associated with cliques and the line graphs of 2-connected hypomatchable graphs. Together with the result from [START_REF] Escalante | Characterizing N+-perfect line graphs[END_REF] (presented in Theorem 3), we directly conclude that the LS + -Perfect Graph Conjecture holds for semi-line graphs.

Based on the results of Eisenbrand et al. [START_REF] Eisenbrand | The stable set polytope of quasi-line graphs[END_REF] and Stauffer [START_REF] Stauffer | On the Stable set polytope of claw-free graphs[END_REF], combined with the characterization of LS + -imperfect webs from [START_REF] Escalante | Lovász and Schrijver N+-relaxation on web graphs[END_REF] (Theorem 4), we are able to show: Theorem 7. All facet-inducing LS + -perfect fuzzy circular interval graphs are cliques, odd holes or odd antiholes.

As a consequence, every LS + -perfect fuzzy circular interval graph is a-perfect. This verifies the LS + -Perfect Graph Conjecture for fuzzy circular interval graphs.

Since the class of quasi-line graphs partitions into semi-line graphs and fuzzy circular interval graphs, we obtain as direct consequence:

Corollary 2. The LS + -Perfect Graph Conjecture is true for quasi-line graphs.

Claw-free graphs that are not quasi-line are distinguished according to their stability number.

Relying on the behavior of the stable set polytope under clique identification [START_REF]On Certain Polytopes Associated with Graphs[END_REF] and the result on LS + -(im)perfect graphs from Theorem 5, we can prove:

Theorem 8. Every facet-defining claw-free not quasi-line graph G with α(G) = 3 is LS + -imperfect.
Hence, the only facet-defining subgraphs G ′ of LS + -perfect claw-free not quasi-line graphs G with α(G) = 3 have α(G ′ ) = 2 and are, by Theorem 6, cliques, odd antiholes or their complete joins. We conclude that LS + -perfect facet-defining claw-free not quasi-line graphs G with α(G) = 3 are joined aperfect and, thus, the LS + -Perfect Graph Conjecture is true for this class.

To treat the case of claw-free not quasi-line graphs G with α(G) ≥ 4, we rely on the decomposition of such graphs into strips, where at most one strip is quasi-line and all the remaining ones are 5-wheel strips [START_REF] Oriolo | A new algorithm for the maximum weighted stable set problem in claw-free graphs[END_REF]. By noting that 5-wheel strips of type 3 contain G LT and exhibiting LS + -imperfect line graphs in the other two cases, we are able to show: Theorem 9. Every facet-defining claw-free not quasi-line graph G with α(G) ≥ 4 is LS + -imperfect.

This together with Theorem 8 shows that the only facet-defining subgraphs G ′ of LS + -perfect claw-free not quasi-line graphs G with α(G) ≥ 4 have α(G ′ ) = 2 and are, by Theorem 6, cliques, odd antiholes or their complete joins. Thus, every LS + -perfect claw-free not quasi-line graph G with α(G) ≥ 4 is joined a-perfect and, thus, the LS + -Perfect Graph Conjecture holds true for this class.

Combining Corollary 1 with the above results shows that all LS + -perfect claw-free but not quasi-line graphs are joined a-perfect and we obtain: Corollary 3. The LS + -Perfect Graph Conjecture is true for all claw-free graphs that are not quasi-line.

Finally, we obtain our main result as direct consequence of Corollary 2 and Corollary 3: The LS + -Perfect Graph Conjecture is true for all claw-free graphs.

Conclusion and future research

The context of this work was the study of LS + -perfect graphs, i.e., graphs where a single application of the Lovász-Schrijver PSD-operator LS + to the edge relaxation yields the stable set polytope. Hereby, we are particularly interested in finding an appropriate polyhedral relaxation P (G) of STAB(G) that coincides with LS + (G) and STAB(G) if and only if G is LS + -perfect. An according conjecture has been recently formulated (LS + -Perfect Graph Conjecture); here we verified it for the well-studied class of claw-free graphs (Theorem 1).

Note further that, besides verifying the LS + -Perfect Graph Conjecture for claw-free graphs, we obtained the complete list of all minimally LS + -imperfect claw-free graphs. In fact, the results in [START_REF] Bianchi | Near-perfect graphs with polyhedral N+(G)[END_REF][START_REF] Escalante | Lovász and Schrijver N+-relaxation on web graphs[END_REF][START_REF] Escalante | Characterizing N+-perfect line graphs[END_REF] imply that the following graphs are minimally LS + -imperfect:

graphs G with α(G) = 2 such that Gv is an odd antihole for some node v, not completely joined to Gv, -the web W 2 10 , -LS + -imperfect line graphs (which are all node stretchings of G LT or G EM N ).

Our results from Section 3 on facet-defining LS + -perfect claw-free graphs imply that they are the only minimally LS + -imperfect claw-free graphs.

Finally, the subject of the present work has parallels to the well-developed research area of perfect graph theory also in terms of polynomial time computability. In fact, it has the potential of reaching even stronger results due the following reasons. Recall that calculating the value η + (G) = max 1 T x, x ∈ LS + (G) can be done in polynomial time for every graph G by [START_REF] Lovász | Cones of matrices and set-functions and 0-1 optimization[END_REF]. Thus, the stable set problem can be solved in polynomial time for a strict superset of perfect graphs, the LS + -perfect graphs, by α(G) = η + (G). Hence, our future lines of research include to find new families of graphs where the conjecture holds (e.g., by characterizing the minimally LS + -imperfect graphs within the class), -new subclasses of LS + -perfect or joined a-perfect graphs, -classes of graphs G where STAB(G) and LS + (G) are "close enough" to have α(G) = ⌊η + (G)⌋.

In particular, the class of graphs G with α(G) = ⌊η + (G)⌋ can be expected to be large since LS + (G) is a much stronger relaxation of STAB(G) than TH(G).

In all cases, the stable set problem could be solved in polynomial time in these graph classes by optimizing over LS + (G). Finally, note that LS + (P (G)) with STAB(G) ⊆ P (G) ⊆ ESTAB(G)

clearly gives an even stronger relaxation of STAB(G) than LS + (G). However, already optimizing over LS + (QSTAB(G)) cannot be done in polynomial time anymore for all graphs G by [START_REF] Lovász | Cones of matrices and set-functions and 0-1 optimization[END_REF]. Hence, in view of the polynomial time solvability of the stable set problem, LS + -perfect graphs or their generalizations satisfying α(G) = ⌊η + (G)⌋ are the most promising cases in this context.

Fig. 1 .

 1 Fig. 1. The graphs GLT (on the left) and GEMN (on the right).

Theorem 3 (

 3 [START_REF] Escalante | Characterizing N+-perfect line graphs[END_REF]). A facet-defining line graph G is N + -perfect if and only if G is a clique or an odd hole.

Fig. 2 .

 2 Fig.2. Some node stretchings (v1, w, v2 in black) of GLT and GEMN .

Fig. 3 .

 3 Fig. 3. The three types of basic 5-wheel strips.

⋆ This work was supported by an ECOS-MINCyT cooperation (A12E01), a MATH-AmSud cooperation (PACK-COVER), PID-CONICET 0277, PICT-ANPCyT 0586.


Pascal Halffmann
email: halffman@mathematik.uni-kl.de

Sven O Krumke
email: krumke@mathematik.uni-kl.de

Alain Quilliot
email: quilliot@isima.fr

Annegret K Wagler
email: wagler@isima.fr

Jan-Thierry Wegener
email: wegener@isima.fr

On the Online Min-Wait Relocation Problem

Keywords: relocation problem, competitive ratio, max/max ratio

In a carsharing system, a fleet of cars is distributed at stations in an urban area, customers can take and return cars at any time and station. For operating such a system in a satisfactory way, the stations have to keep a good ratio between the total number of places and cars in each station, in order to refuse as few customer requests as possible. This leads to the problem of relocating cars between stations. We consider the Online Min-Wait Relocation Problem, aiming at satisfying all customer requests with a minimal total waiting time, and show the non-existence of competitive online algorithms against several adversaries. Furthermore, we consider the max/max ratio, and show that this ratio cannot be used to theoretically evaluate online algorithms for the Online Min-Wait Relocation Problem either.

Introduction

Carsharing is a modern way of car rental, attractive to customers who make only occasional use of a car on demand. In a carsharing system, a fleet of cars is distributed at specified stations in an urban area, customers can take a car at any time and station and return it at any time and station, provided that there is a car available at the start station and a free place at the final station. To ensure the latter, customers do not book their requests in advance, but wait at a station until their request can be fulfilled. For operating such a system in a satisfactory way, the stations have to keep a good ratio between the total number of places and the number of cars in each station, in order to keep the waiting times for the customers as low as possible. This leads to the problem of balancing the load of the stations, called Relocation Problem: an operator has to monitor the load situations of the stations and to decide when and how to move cars from "overfull" stations to "underfull" ones.

Balancing problems of this type occur for any car-or bikesharing system, but the scale of the instances, possibility and time delay for prebookings and the possibility to move one or more vehicles in balancing steps differ. We consider an innovative carsharing system, where the cars are partly autonomous, which allows to build wireless convoys of cars lead by a special vehicle, such that the whole convoy is moved by only one driver (cf. [START_REF] El-Zaher | Vehicle platoon control with multi-configuration ability[END_REF]). This setting is similar to bikesharing, where trucks can simultaneously move several bikes during the relocation process [START_REF] Chemla | Bike sharing system: Solving the static rebalancing problem[END_REF][START_REF] Contardo | Balancing a dynamic public bike-sharing system[END_REF]. Since customers of our carsharing system do not book their requests in advance, the main goal is to guarantee a balanced system during working hours (online as in [START_REF] Contardo | Balancing a dynamic public bike-sharing system[END_REF][START_REF] Krumke | Models and algorithms for carsharing systems and related problems[END_REF]) or to set up an appropriate initial state for the morning (static situation as in [START_REF] Chemla | Bike sharing system: Solving the static rebalancing problem[END_REF][START_REF] Krumke | Models and algorithms for carsharing systems and related problems[END_REF]). Both, the online and the static versions are known to be N P-hard [START_REF] Chemla | Bike sharing system: Solving the static rebalancing problem[END_REF], and different heuristics have been developed, e.g., by partitioning the problem into subproblems with clustering techniques [START_REF] Schuijbroek | Inventory rebalancing and vehicle routing in bike sharing systems[END_REF], or by reducing the search space [START_REF] Krumke | Relocation in carsharing systems using flows in time-expanded networks[END_REF].

In this extended abstract, we address the online situation where cars can be transfered between stations during the working hours in order to satisfy the needs of the customers. Hereby, customers do not book their requests in advance as they do in [START_REF] Krumke | Relocation in carsharing systems using flows in time-expanded networks[END_REF] but wait at a station until their request can be fulfilled. We model the Relocation Problem in the framework of a metric task system. By [START_REF] Krumke | Models and algorithms for carsharing systems and related problems[END_REF] the studied carsharing system can be understood as a discrete event-based system, where the system components are the stations v 1 , . . . , v n , each having an individual capacity cap(v i ), a system state z t ∈ Z n specifies for each station v i its load z t i at a time point t and z t changes when customers or convoy drivers take or return cars at stations. Customers demanding a car at time t from a station u, keeping the car for δ time units before bringing it back to station v, are modeled by floating customer requests r = (t, u, v, δ). The time t is called release time, u the pickup station, v the drop station, and δ the occupation time of r. In our considered situation, all floating customer requests must be served, i.e., it must be ensured that at a finite point in time a customer can take a car from u to v. The time between the release time and the time when the floating customer request is served is called waiting time. Since (floating) customer requests may cause imbalances in the system, an operator has to monitor the system states and to decide when and how to move cars between the stations in order to fulfill all demands. For that, the operator monitors the evolution of system states over time, detects infeasible states (z t v < 0 or z t v > cap(v)) and creates tasks to move cars out of stations having an excess number of cars (z t v > cap(v)) into stations with a deficit number of cars (z t v < 0). To fulfill these tasks, tours have to be created for the convoys in order to perform the desired relocation process. For that, it is suitable to encode the urban area where the carsharing system is running as a metric space M = (V, d) induced by a weighted graph G = (V, E, w) with weight function w : E → R + . The nodes correspond to stations, edges to their physical links in the urban area, and the distance d between two points v i , v j ∈ V is the length of a shortest path from v i to v j . This yields a metric task system, a pair (M, T ) where M = (V, d) is the above metric space and T a set of tasks, as suitable framework to embed the tours for the convoys. A truck able to lead a convoy plays the role of a server. Each server has a capacity, corresponding to the maximum possible number of cars per convoy. A tour is assigned to every server, where the servers are instructed to move between stations and to add cars to (resp. remove cars from) the stations. A collection of tours, where every server has an assigned tour and that does not lead to infeasible system states is called a transportation schedule.

Problem 1.1 (Online Min-Wait Relocation Problem (M, R, k, L, x)) Given a metric space M , a sequence of floating customer requests R, k servers of capacity L, and x cars, find a transportation schedule with minimal total waiting time for the metric task system (M, T ), where T consists of tasks which are induced by R as above.

Competitive Ratio and Max/Max Ratio

Competitive analysis has become one standard way of measuring the quality of online algorithms, see e.g. [START_REF] Karp | On-line algorithms versus off-line algorithms: How much is it worth to know the future[END_REF]. The analysis can be viewed as a request/answer game, where an adversary generates a sequence of floating customer requests and an online algorithm tries to serve them. The performance of the online algorithm is then compared to that of an offline algorithm, which, in contrast to the online algorithm, has complete information about the whole request sequence in advance. Due to the advantage of having more information, the offline algorithm generally makes better decisions. However, the offline algo-rithm cannot serve any floating customer request before its release time. If the ratio between the values of the solutions produced by the online ONL(R) and the optimum offline algorithm OPT(R) is finite for all sequences R, i.e., ONL(R) ≤ c • OPT(R) for a c ∈ N, the online algorithm is called competitive.

We show that there does not exist a competitive online algorithm for the Online Min-Wait Relocation Problem even against restricted adversaries. We derive our results for the uniform metric space, where all distances are equal to one. Although the uniform metric space is a strong simplification of the general situation, in transportation problems within a small central urban area, the travel distance between two stations may be determined so much by the real distance, but by a general fixed setup time for loading and unloading.

First, we consider the standard adversary who knows the complete behavior of an online algorithm ONL and chooses a worst-case sequence for ONL. He is allowed to move convoys towards yet unreleased floating customer requests, but must not serve any request before its release time.

Theorem 2.1 There does not exist a competitive online algorithm for the Online Min-Wait Relocation Problem (M, R, k, L, x) on the uniform metric space even if there are only three nodes in M , and k = x = 1.

The basic idea of the proof is that the adversary releases a floating customer request with a high occupation time. The adversary waits until the online algorithm starts serving r 1 and then releases another floating customer request r 2 with occupation time 1. The adversary then serves r 2 before r 1 , while the online algorithm serves the requests in reversed order. Since we can select the occupation time of r 1 arbitrarily high, we can conclude that the ratio between the solutions produced by the online and the offline algorithm is arbitrarily high. Thus, there does not exist a competitive online algorithm for the Online Min-Wait Relocation Problem.

This proof motivates to restrict the set of floating customer requests the adversary can choose from. However, even when we restrict the adversary to select only from floating customer requests with an occupation time of 1 the situation does not change.

Theorem 2.2 There is no competitive online algorithm for the Online Min-Wait Relocation Problem (M, R, k, L, x) on the uniform metric space against an adversary which releases only floating customer requests with an occupation time of 1, even if there are only three nodes in M , and k = x = 1.

In terms of standard competitive analysis, the previous results show that one reaches the so-called triviality barrier [START_REF] Fiat | Online Algorithms: The State of the Art[END_REF]. With Yao's principle [START_REF] Borodin | On Randomization in On-Line Computation[END_REF], one can show that Theorem 2.1 and 2.2 holds for deterministic as well as randomized online algorithms. We now consider another method to analyze the efficiency of an online algorithm, the max/max ratio, which has been successfully applied to the k-server problem2 [START_REF] Wegener | A new measure for the study of online algorithms[END_REF][START_REF] Boyar | A comparison of performance measures for online algorithms[END_REF]. A downside of competitive analysis is that some (intuitive) improvements of some algorithms do not necessarily lead to a better competitive ratio. A famous example is that online algorithms with a finite lookahead usually do not have a better competitive ratio than their counterparts with no lookahead at all. However, in [START_REF] Wegener | A new measure for the study of online algorithms[END_REF] the authors could show, that applying the max/max ratio, there is a difference between algorithms with and without lookahead. One of the major motivations to try the max/max ratio on the Online Min-Wait Relocation Problem is that David and Borodin show in [START_REF] Wegener | A new measure for the study of online algorithms[END_REF] that a greedy strategy (which is not a competitive online algorithm against an oblivious adversary) has a finite max/max ratio for the k-server problem. However, it turns out that there does not exist a properly defined max/max ratio for the Online Min-Wait Relocation Problem.

Let ALG be an algorithm with costs ALG(R) on the input sequence R. The amortized costs M (ALG) are defined as M (ALG) := lim sup λ→∞ M λ (ALG), where M λ (ALG) := max |R|=λ ALG(R)/λ. The max/max ratio w M (ONL) of an online algorithm ONL vs. an optimal offline algorithm OPT is then defined as Theorem 2.3 On the uniform metric space with at least two points, it holds: for every λ ≥ 2 and for every C ∈ N there exists a sequence R, with |R| = λ, so that OPT(R) ≥ C. This holds even in the case that there are only three nodes in M , and k = x = 1.

The result can be proved similarly as Theorem 2.1. It implies that the value M (OPT) is not bounded. From M (ONL) ≥ M (OPT), we conclude that w M (ALG) = ∞/∞ is indeterminate. However, when we restrict the set of floating customer requests as before to requests with an occupation time of 1, it turns out that several standard online algorithms for the k-server problem as "first come first serve" or "replan" have a max/max ratio of 1, since the worst-case sequences for an optimal offline algorithm are equal to the worstcase sequences for these online algorithms.

Overall, it seems that neither the competitive ratio nor the max/max ratio are meaningful tools for evaluating the efficiency of online algorithms for the Online Min-Wait Relocation Problem. Thus, developing a concept which allows us to theoretically evaluate online algorithms for the Online Min-Wait Relocation Problem to reflect practical observations on the different performance of online algorithms remains a goal for the future.

w

  M (ONL) := lim sup λ→∞ M λ (ONL) M λ (OPT) = M (ONL) M (OPT) . The last equation of the definition of w M (ONL) is proved in [1, Lemma 4.2].

This work was founded by the French National Research Agency, the European Commission (Feder funds) and the Région Auvergne in the Framework of the LabEx IMobS3.

In the k-server problem, tours for a fleet of k servers have to be computed such that every released city is visited. Hereby, the goal is to minimize the total tour length.


Luis M Torres Modemat

Annegret K Wagler
email: wagler@isima.fr

Analyzing the dynamics of discrete deterministic systems

This work is based on an extension of the Petri net framework. Our model relies on the definition of a priority relation between conflicting transitions, which is encoded in a compact manner by orienting the edges of a transition conflict graph. The benefit is that this allows the use of a successor function for the study of dynamic processes from a global point of view, independent from a particular initial state and the (complete) construction of the reachability graph. We address the problem of gaining the information that allows to provide an appropriate priority relation governing the dynamic behavior of the studied system and discuss some further implications and generalizations of the studied approach.

I. INTRODUCTION

To model complex dynamic systems, Petri nets constitute a well-established framework that offers a variety of analysis techniques. Hereby, the structure of the systems is described by means of a network, while dynamic processes are usually represented in terms of state changes. Several fundamental issues concerning the dynamics of such systems can be addressed within this setting, either via theoretical analysis or computer simulation. Accordingly, Petri nets have a broad application range, including the design of asynchronous hardware circuits [START_REF] Yakovlev | Modelling, analysis and synthesis of asynchronous control circuits using Petri nets[END_REF], the analysis of production and workflow systems [START_REF] Adam | Modeling and analysis of workflows using Petri nets[END_REF], the analysis and control of batch processes [START_REF] Gu | A survey of Petri net applications in batch processes[END_REF], the design of distributed algorithms for networks of agents [START_REF] Reisig | Elements of distributed algorithms: modeling and analysis with Petri nets[END_REF], and the modeling and simulation of biological networks [START_REF] Hardy | Modeling and simulation of molecular biology systems using Petri nets: modeling goals of various approaches[END_REF], [START_REF] Koch | Petri nets[END_REF], [START_REF] Chaouiya | Petri net modelling of biological regulatory networks[END_REF], to cite only some prominent examples.

More formally, a network G = (P, T, A, w) reflects the involved components (like network elements, technical components, biological entities etc.) by places p ∈ P and their interactions (like transformations, causal dependencies, chemical reactions etc.) by transitions t ∈ T , linked by weighted directed arcs. Some places B ⊆ P may have bounded capacities, which are given by a positive integral vector u ∈ Z B + . Each place p ∈ P can be marked with an integral number x p of tokens (at most u p if p ∈ B). Any such marking defines a state of the system that can be represented as an integral nonnegative vector x ∈ Z P + . The potential state space of a capacitated network (G, u) is the set of all theoretically possible states X := {x ∈ Z P + : x p ≤ u p , ∀p ∈ B}, if no further conditions restrict X . Its size is at least exponential in |P | and is finite if B = P holds.

Dynamic processes are described as sequences x 0 , x1 , . . . , x k of consecutive system states 1 , where state x i+1 is obtained from x i by switching a transition t ∈ T . Thereby, t consumes w pt tokens from each place p with (p, t) ∈ A and produces w tp new tokens on each place p with (t, p) ∈ A. A transition t ∈ T is enabled at a state x ∈ X if switching t yields a valid successor state in X . We denote by T (x) the set of enabled transitions at state x and, accordingly, by X(t) the set of states at which transition t is enabled.

Usually, the dynamic behavior is the result of several conflicting as well as concurrent ongoing dynamic processes. A Petri net is a pair (G, x 0 ) consisting of a network G together with an initial state x 0 , and its state space X (x 0 ) is understood as the set of all further system states which can be reached from x 0 by switching or firing sequences of transitions, see e.g. [START_REF] Reisig | Petri nets: an introduction[END_REF] for more information. Describing the dynamics of a system might be done by model animation, i.e., by simulating the flow of tokens inside the network as transitions are switched. Given a network G and an initial state x 0 , some central problems are:

• Reachability: Determine whether the system may reach one of a set of target states after a finite sequence of transition switches.

• Boundedness: Determine if there are sequences of transition switches that lead to the accumulation of an unlimited number of tokens at some place.

• Liveness: Determine whether no sequence of transition switches can put the system into a state where some transition is permanently disabled.

These problems are in general hard from a computational complexity point of view. For instance, reachability was proven to require exponential space [START_REF] Lipton | The reachability problem requires exponential space[END_REF] and decidability of this problem could only be established some years later [START_REF] Mayr | An algorithm for the general Petri net reachability problem[END_REF], [START_REF]An algorithm for the general Petri net reachability problem[END_REF].

a) Partial versus global point of view on a system: Dynamic processes can be encoded as directed paths in a state digraph G where nodes represent states and there is a directed arc between two states x, x if x can be obtained from x by switching a single transition. It is common practice to use the term reachability or marking graph to refer to the subgraph G(x 0 ) of G induced by the set X (x 0 ) of nodes corresponding to those states that can be reached from the initial state x 0 of the network.

The marking graph G(x 0 ) allows only a partial view on the studied system which is, e.g., suitable for a technical system performing exactly one process. However, already a failure of one or several components can change the initial state, and a more global view is required to coherently model both normal and malfunction of the system, and to detect the faulty element(s) by an according failure analysis.

Similarly, the study of biological systems by performing experiments can be seen as putting the system in an initial state and observing the evolution of the system in terms of sequences of state changes. Due to the intrinsic complexity of biological systems, the dynamic behavior of such systems can rarely be understood by performing a single experiment so that, in general, several experiments starting from different initial states are required.

To study complex dynamic systems and processes therein from a more global point of view (independent from a particular initial state), we therefore suggest to consider the state digraph G on the potential state space X of the system, i.e., on the set of all theoretically possible states. b) Non-deterministic versus deterministic systems: While studying dynamic processes, a particular situation occurs when so-called dynamic conflicts are present at states, in which two transitions are enabled, but switching one disables the other. In this case, model animation does not allow definite conclusions about any system properties, as mentioned in [START_REF] Heiner | Petri nets for systems and synthetic biology[END_REF]. The reason is that the occurrence of dynamic conflicts is understood as alternative (branching) system behavior, where a decision between these alternatives is taken nondeterministically.

However, there are examples of systems that show a deterministic behavior despite the existence of dynamic conflicts. We call a dynamic system deterministic if any state x ∈ X has a unique successor state succ(x). For technical systems, a deterministic behavior is often crucial in order to guarantee the reliability of the performed processes.

In addition, also some biological systems are deterministic, as stimulating them in a certain way triggers always the same response (see e.g. the light-induced sporulation of Physarum polycephalum plasmodia or the phototaxis of halobacterial cells described in [START_REF] Marwan | The sequence of regulatory events in the sporulation control network of physarum polycephalum analysed by time-resolved somatic complementation of mutants[END_REF], [START_REF] Marwan | Theory of time-resolved somatic complementation and its use for the analysis of the sporulation control network of physarum polycephalum[END_REF], [START_REF] Marwan | Reconstructing the regulatory network controlling commitment and sporulation in physarum polycephalum based on hierarchical Petri net modeling and simulation[END_REF]). Petri nets, as originally defined, can be used to model such systems only in some trivial cases. c) A compact encoding for deterministic systems: To overcome the above mentioned difficulties, we propose to model deterministic systems from a global point of view (independent from a particular initial state). For that, a successor function succ : X → X can be defined which returns succ(x) for every potential state x ∈ X . Note that an explicit encoding of succ, for instance pointwise, is exponential in the size of the network G.

If the change from a state x ∈ X to its successor state succ(x) can always be explained by the switch of a single transition, the dynamics of a deterministic system can be alternatively expressed with the help of a transition selection function trans : X → T . This function assigns to every state x ∈ X a unique transition trans(x) ∈ T (x) that must be switched in order to reach succ(x).

In [START_REF] Marwan | A mathematical approach to solve the network reconstruction problem[END_REF], it was proposed to use priorities between the transitions2 of the network as additional activation rules to determine which transition from T (x) has to be selected as trans(x) in order to reach succ(x). In [START_REF] Torres | Encoding the dynamics of deterministic systems[END_REF], the following compact scheme for encoding trans based on such priorities was introduced. The transition conflict graph of (G, u) is an undirected graph K = (T, E) having as nodes the transitions from G, where two transitions t, t are joined by an edge if and only if there exists at least one state where both are enabled.

A directed graph D obtained by orienting the edges of K is a valid orientation for (G, u) if, for every state x ∈ X with T (x) = ∅, the node subset T (x) has a unique sink, and this sink coincides with trans(x). Observe that the size of

D is O(|T |
2 ), which is polynomial in the size of G, see Section II.

A valid orientation completely encodes the dynamic behavior of a deterministic system: given a state x ∈ X , determine the highest-priority transition trans(x) by searching for the unique sink in the subgraph of D induced by T (x); switching trans(x) yields the successor succ(x).

Computing successors is a key operation within simulation algorithms to study the dynamic behavior of a system and to address questions like reachability, boundedness or liveness. To the best of our knowledge, currently no algorithm for these problems is known, which does not rely on storing explicit descriptions of the state digraph or some equivalent structure to compute succ(x) at every state x, which limits the size of the networks that can be considered, due to the high memory requirements. Having, however, a valid orientation allows to determine succ(x) for each state x ∈ X . d) Experiment design to obtain such models: To benefit from the above mentioned properties, a valid orientation of a transition conflict graph needs to be obtained. This shall be done by observing dynamic processes in the underlying deterministic system: based on the knowledge of succ(x) at some states x ∈ X , we aim at finding a valid orientation that encodes the global dynamic behavior of the system since succ(x) can be determined for all states x ∈ X .

Querying succ(x) for a state x is typically done by performing experiments with the studied system. Since this can be expensive and time-consuming, it is worth to design the experiments in such a way that as few of them suffice to gain the required information. In this paper, we address a problem in this context posed in [START_REF]Model reconstruction for discrete deterministic systems[END_REF]: given a network G and an oracle for returning succ(x) for any state x ∈ X , we aim at determining D by calling the oracle as few times as possible. Thus, we shall design experiments (in terms of oracle calls) to deduce the global dynamic behavior of the system by providing enough transition priorities, encoded in D. In Section III, we formally state the problem, present some related concepts from [START_REF]Model reconstruction for discrete deterministic systems[END_REF] and propose an algorithm to solve the problem.

We close with some concluding remarks and a discussion on potential generalizations of our approach.

II. ENCODING VALID ORIENTATIONS

As observed in the previous section, one key issue for modeling the dynamic behavior of a deterministic system is the specification of a mechanism for the (unambiguous) resolution of dynamic conflicts between enabled transitions.

Recall that, given a capacitated network G = (P, T, A, w) with u ∈ Z B + , its transition conflict graph is an undirected graph K = (T, E) having as nodes the transitions from G, where two transitions t, t are joined by an edge if and only if there exists at least one state where both are enabled, i.e.,

tt ∈ E ⇔ X(t) ∩ X(t ) = ∅.
As the involved sets X(t) are boxes, K can be constructed in

O(|P | |T |
2 ) time using a straightforward algorithm to check for box intersections X(t) ∩ X(t ). A more efficient way of its computation is proposed in [START_REF] Torres | Encoding the dynamics of deterministic systems[END_REF].

It follows from the definition of K that, for every state x ∈ X , the set T (x) of enabled transitions induces a clique in K, i.e., a set of mutually adjacent nodes.

Remark 1: The converse is not necessarily true, as it is shown in [START_REF] Torres | Encoding the dynamics of deterministic systems[END_REF]. However, as the sets X(t) are boxes, it is possible to prove that at least the inclusion-wise maximal cliques in K are associated with states of the system.

Example 2: Consider the capacitated network (G, 1l), with G = (P, T, A, 1l), from Figure 1(a). It has X = {0, 1} 4 as set of potential system states, where for each

x i ∈ X , with 0 ≤ i < 16, it holds that i = x i 1 2 0 + x i 2 2 1 + x i 3 2 2 + x i 4 2 3 .
The sets X(t) for all transitions in T are as follows:

X(t 1 ) = x 1 , x 3 , x 5 , x 7 , X(t 2 ) =
x 2 , x 3 , x 6 , x 7 , X(t 3 ) =

x 5 , x 13 , X(t 4 ) =

x 4 , x 5 , x 6 , x 7 .

The resulting transition conflict graph K is shown in Figure 1(b). Note that (G, 1l) has four branching states and the following cliques of K are associated with them:

T (x 3 ) = {t 1 , t 2 }, T (x 5 ) = {t 1 , t 3 , t 4 }, T (x 6 ) = {t 2 , t 4 }, T (x 7 ) = {t 1 , t 2 , t 4 }.
T (x 5 ) and T (x 7 ) are the inclusion-wise maximal cliques of K. Moreover, there are five cliques of size two (edges), from which only two (t 1 t 2 and t 3 t 4 ) are associated with states.

K is a plausible candidate to embed priorities between transitions. This motivates the following definition. A directed graph D = (T, A) obtained by orienting the edges of K is valid for the system (G, u) if, for every state x ∈ X with T (x) = ∅, the subgraph induced by the nodes from T (x) has a unique sink, and this sink coincides with trans(x).

The existence of a valid orientation of K implicitly imposes a further requirement on the nature of a dynamic system: if two states x, x * ∈ X have the same set T (x) = T (x * ) of enabled transitions, then both induce the same subgraph of D and, therefore, trans(x) = trans(x * ) must hold. Moreover, if a transition t is enabled at two states x, x ∈ X and t is the highest-priority transition at x, then either t is also the highest-priority transition at x or trans(x ) ∈ T (x). The next result from [START_REF] Torres | Encoding the dynamics of deterministic systems[END_REF] shows that this condition is also sufficient for the existence of a valid orientation.

Theorem 3: A system (G, u) has a valid orientation if and only if the following consistency condition holds: For any pair of states x and x , if trans(x) ∈ T (x) ∩ T (x ) then either trans(x ) = trans(x) or trans(x ) ∈ T (x ) \ T (x).

Recognizing whether an orientation D of K is valid is hard in general, since it requires a test for every state x ∈ X , whether the corresponding clique T (x) in D has a unique sink.

Note that a clique cannot have more than one sink, and that every clique without a sink contains a directed cycle. Hence, if D is acyclic then every clique of the graph has a unique sink, and we immediately obtain:

trans(x 3 ) = t 2 in T (x 3 ), trans(x 5 ) = t 4 in T (x 5 ), trans(x 6 ) = t 4 in T (x 6 ), trans(x 7 ) = t 4 in T (x 7 ),
and the consistency condition from Theorem 3 is satisfied:

• trans(x 3 ) = t 2 belongs to the intersection of T (x 3 ) ∩ T (x 6 ) and T (x 3 ) ∩ T (x 7 ), but trans(x j ) = t 4 belongs to T (x j ) \ T (x 3 ) for j = 6, 7; • t 4 is the common highest-priority transition in T (x 5 ), T (x 6 ), T (x 7 ).

III. FINDING VALID ORIENTATIONS FOR A NETWORK

A relevant problem when modeling dynamic systems with our approach consists in inferring a valid orientation for the transition conflict graph from observations made on dynamic processes in the underlying deterministic system. Based on the knowledge of the values of succ(x) at some states x ∈ X , we aim at finding a valid orientation that allows to predict succ(x) for all states x ∈ X .

Given as input the capacitated network (G, u) and an oracle for returning the value of trans(x) at any state x ∈ X , we shall determine D by calling the oracle as few times as possible since in practice, a call to the oracle stands for the execution of an (expensive and time-consuming) experiment. A set X ⊆ X of states is a valid test set if the information about the corresponding highest-priority transitions {trans(x) : x ∈ X } is sufficient for inferring the direction of all arcs in D. We are interested in the following problem, formulated in [START_REF]Model reconstruction for discrete deterministic systems[END_REF].

Problem 6 (Minimum Valid Test Set Problem (MVTP)): Given a deterministic system together with an oracle for returning highest-priority transitions, find a valid test set of minimum cardinality.

In the following, we discuss and extend an approach from [START_REF]Model reconstruction for discrete deterministic systems[END_REF] to solve the MVTP iteratively, by alternating oracle calls and analyzing the gained information.

For that, suppose that we are in the situation of having already a partial orientation of a (mixed) graph D = (T, A , E ), obtained by fixing the direction for some edges of K (e.g. as result of previous calls to the oracle) with A being the set of the corresponding oriented arcs, and E the set of the remaining unoriented edges. A partial orientation is extendible if it is possible to choose directions for all unoriented edges in such a way that a valid orientation is obtained. Given an extendible partial orientation D = (T, A , E ), a yet unoriented edge tt ∈ E is said to be inferable as (t, t ) if the partial orientation (T, A ∪ {(t , t)}, E \ {tt }) is not extendible and dominated if for all states x with t, t ∈ T (x), trans(x) is already known to differ from t and t . Observe that the direction of dominated edges is irrelevant in our model, as these never provide information for computing highest-priority transitions. However, as we shall see later, the direction of dominated edges may be important in order to determine which of the other edges are inferable and which are not. We call D to be sufficient for inferring a valid orientation D = (T, A) if all edges in E are inferable as the corresponding arcs in A. This also shows that the optimal solution of MVTP may depend on the underlying valid (complete) orientation D, and not on the transition conflict graph alone.

Testing whether a partial orientation is extendible or not is computationally hard, for the same reason for which recognizing a valid orientation is hard in general. In the following, we focus on the particular case where the valid (complete) orientation D is known a priori to be acyclic. This is equivalent to assuming that there exists a partial orientation reflecting the priority relations among all transitions of the network, an assumption which is plausible in many practical applications. Furthermore, a partial orientation D is sufficient if, for every non-dominated edge tt ∈ E , the digraph (T, A ) contains either a directed path from t to t , or a directed path from t to t. Conversely, given a (complete) orientation D = (T, A), an arc a = (t, t ) ∈ A such that the digraph (T, A \ {a}) does not contain a directed path from t to t is either dominated or otherwise essential.

Observe that the direction of an essential arc a cannot be inferred in any partial orientation extendible to D, whereas the orientation of a dominated arc can be arbitrarily chosen.

Any sufficient partial orientation must therefore contain the set A * of all essential arcs from D. Furthermore, for any state x ∈ X , the information on succ(x) can be used to orient at most one essential arc among the set

A(x) = {(t, trans(x)) : t ∈ T (x), t = trans(x)}
of arcs whose directions are revealed by testing the system at x. As a consequence, the following result is obtained in [START_REF]Model reconstruction for discrete deterministic systems[END_REF] for systems satisfying the clique property: each clique of the transition conflict graph is associated with a state of the system.

Theorem 9: If a system satisfies the clique property, then

• the essential arcs of D form a sufficient partial orientation; • a valid test set X ⊆ X is optimal for MVTP if and only if A(x) ∩ A * = ∅ holds for every x ∈ X .

Here, we extend the results from [START_REF]Model reconstruction for discrete deterministic systems[END_REF] to the case that D is known a priori to be acyclic, but the clique property is not assumed to hold. Recall that this is reasonable to expect in practical instances.

Theorem 10: If the complete orientation D is acyclic, then

• the essential and the dominated arcs of D form a sufficient partial orientation; • a valid test set X ⊆ X is optimal for MVTP if A(x)∩ A * = ∅ holds for every x ∈ X .

Algorithm 1 shows an approach to determine a valid test set in this case. It computes as first step the set Q of all inclusionwise maximal cliques in K (to ensure that each clique in Q is associated to a state), then it alternates oracle calls and the analysis of the gained information.

Input: (G, u, trans) {deterministic system with oracle for computing trans} K {transition conflict graph} 3: Output: D {valid acyclic orientation} initialize Q as the set of all inclusion-wise maximal cliques in K while Q = ∅ do 6:

retrieve a clique Q from Q while Q contains more than one node and there is x ∈ X with T (x) = Q do call the oracle and determine t * := trans(x)

9:
orient the arcs {(t, t * ) : t ∈ T (x), t = t * } deduce orientations for inferable edges remove t * from Q 12:

end while if Q contains more than one node then compute

Q := {T (x) ⊂ Q : x ∈ X } 15:
remove from Q cliques that are not inclusion-wise maximal

Q := Q ∪ Q end if 18: end while D := (T, A , E
) is the partial orientation obtained so far while E = ∅ do 21:

deduce an orientation for all yet unoriented inferable edges choose an arbitrary orientation for a yet unoriented dominated edge end while Algorithm 1: Inferring an acyclic valid orientation.

Theorem 11: If the orientation of D is known to be acyclic, then Algorithm 1 determines a valid test set for inferring D.

Example 12: In order to determine a valid test set X ⊆ X to infer a valid orientation of the edges in K from Figure 1(b), we recall from Example 2 that the following cliques of K are associated with states:

T (x 3 ) = {t 1 , t 2 }, T (x 5 ) = {t 1 , t 3 , t 4 }, T (x 6 ) = {t 2 , t 4 }, T (x 7 ) = {t 1 , t 2 , t 4 }.
The set of all inclusion-wise maximal cliques in E is Q = {T (x 5 ), T (x 7 )}. Applying Algorithm 1 to K and Q yields:

For Q = Q(x 5
), we call the oracle in x 5 and receive succ(x 5 ) = x 9 . We conclude trans(x 5 ) = t 4 and, thus, t 4 > t 3 and t 4 > t 1 follows. After removing t 4 , the dominated edge t 1 t 3 remains. We compute Q = ∅, so no new cliques are added to Q.

For Q = Q(x 7 ), we call the oracle in x 7 and receive succ(x 7 ) = x 11 . We conclude trans(x 7 ) = t 4 and, thus, t 4 > t 2 and t 4 > t 1 follows. After removing t 4 , we obtain Q = {t 1 , t 2 }. This clique is associated with x 3 , so we call the oracle in x 3 and receive succ(x 3 ) = x 9 . We conclude trans(x 3 ) = t 2 and, thus, t 2 > t 1 . After removing t 2 , the remaining subclique has only one node.

The resulting partial orientation D is depicted in Figure 3 It is left to discuss the quality of the test set obtained by Algorithm 1. For that, we firstly note the following.

Lemma 13: Given a capacitated network (G, u) with acyclic orientation D, then the number of essential arcs of D (resp. branching states of (G, u)) is a lower (resp. an upper) bound for the cardinality of a minimum valid test set.

Example 14: Consider the two acyclic valid orientations D 1 in Figure 3(b) and D 2 in Figure 3(c). In both cases, t 1 t 3 is a dominated edge. The essential arcs are

• t 1 t 2 , t 2 t 4 , t 3 t 4 in D 1 ; • t 1 t 2 , t 2 t 4 in D 2 .
These essential arcs form together with the dominated edge t 1 t 3 the two sufficient partial orientations depicted in Figure 2(d) and Figure 2(c), respectively. For D 1 , the number of essential arcs equals the cardinality of the test set X obtained by Algorithm 1 (thereby verifying its optimality). D 2 shows that both bounds do not need to be tight (we have |A * 2 | = 2, but |X | = 3 and four branching states x 3 , x 5 , x 6 , x 7 ). This illustrates the difficulties for certifying optimality of a computed test set. However, we conjecture the following:

Conjecture 15: Given a capacitated network (G, u),

• any acyclic valid orientation D contains the partial acyclic orientation D , computed in the first part of Algorithm 1; • there is one acyclic valid orientation D * whose set of essential arcs equals D ; • if D * is the valid orientation encoding the dynamic behavior of (G, u), then the test set used by Algorithm 1 is optimal.

IV. DISCUSSION

In this paper, we have examined a new approach for encoding the dynamic behavior of certain deterministic discrete systems that relies on extending the familiar framework of Petri nets. Our encoding consists in a realization of the successorfunction succ as a valid orientation of the edges of the transition conflict graph K. This encoding is compact in the sense that the amount of space required for its storage is polynomial in the size of the network. Therefore, it is well-suited for being integrated into simulation algorithms like [START_REF] Heiner | Snoopy a unifying petri net tool[END_REF] to study the dynamics of large complex deterministic systems, and to address issues such as reachability, boundedness, existence of deadlocks, and liveness, among others.

To benefit from the above mentioned properties, a valid orientation of a transition conflict graph needs to be obtained. This shall be done by observing dynamic processes in the underlying deterministic system: based on the knowledge of succ(x) at some states x ∈ X , a valid test set, we aim at finding a valid orientation that encodes the global dynamic behavior of the system since succ(x) can be determined for all states x ∈ X . In this paper, we address the MVTP: given a network G and an oracle for returning succ(x) for any state x ∈ X , we aim at determining D by calling the oracle as few times as possible. Thus, we shall design experiments (in terms of oracle calls) to deduce the global dynamic behavior of the system by providing enough priorities, encoded in D. In Section III, we presented some related concepts from [START_REF]Model reconstruction for discrete deterministic systems[END_REF] and proposed an algorithm to solve the problem for systems where it is known that valid orientations are acyclic.

A possible interesting extension of our model concerns the study of dynamic systems where the concurrent switch of various transitions can occur. Throughout this paper we have assumed that a change from a state x ∈ X to its successor state succ(x) can always be explained by the switch of a single transition trans(x). However, there are deterministic systems where this does not hold, but a transition selection function trans : X → 2 T is required that assigns to each state x a subset of transitions to be switched in order to reach succ(x), see [START_REF]Model reconstruction for discrete deterministic systems[END_REF] for examples.

One way of dealing with these systems could be through the inclusion of pseudo-nodes in the transition conflict graph, to account for the simultaneous switching of various transitions. The advantage would be that all results from the previous sections directly carry over to the extended setting. The disadvantage of such a modification is, however, the dramatic increase in the size of the transition conflict graph, as the number of required pseudo-nodes may grow exponentially with respect to |T | (in the worst-case upto 2 |T | according to the number of subsets of T ).

An alternative approach consists in working on a slightly different transition conflict graph, where an edge between two transitions means that they are in dynamic conflict (i.e. when switching one transition disables the other). In this case, T (x) does not longer induce a clique in K. Yet we can now define an orientation to be valid if for any state x ∈ X the set T (x) of enabled transitions induces a subgraph containing at least one sink. These sinks reveal an anti-chain of transitions with maximal priorities, exactly the subset trans(x) ∈ 2 T , which have to be switched concurrently. Theorem 3 can be generalized to this new setting in a straightforward manner, characterizing which deterministic systems admit valid orientations. The advantage of this scheme is that it is still compact with respect to the size of the network G. However, as the sets T (x) do not induce cliques in the conflict graph, many of the combinatorial properties pointed out in Section II do not hold any more. Moreover, since all transitions that may switch concurrently are required to do so, it is again possible to construct examples of deterministic systems whose behavior cannot be modeled in this way. Hence, further research is necessary to propose a compact encoding of the successor function for general deterministic systems.

For a large number of such systems, however, the here presented results allow us already the use of such an oracle for the study of dynamic processes from a global point of view, independent from a particular initial state and the (complete) construction of the reachability graph.

Fig. 1 .

 1 Fig. 1. (a) A capacitated network of a dynamic system (places are represented by circles, transitions by squares, all place capacities and arc weights are assumed to be equal to one), (b) the corresponding transition conflict graph, (c) a valid orientation.

Observation 4 :Example 5 :

 45 Every acyclic orientation of K is valid. For the capacitated network (G, 1l) from Figure 1(a), the priority relation t 1 < t 2 , t 1 < t 3 , t 2 < t 4 , t 3 < t 4 induces an acyclic orientation D, depicted in Figure 1(c), of the transition conflict graph K from Figure 1(b). D is indeed a valid orientation: each of the cliques in D associated with (branching) states has a unique sink:

Fig. 2 .Observation 8 :

 28 Fig. 2. Different types of partial orientations: (a) non-extendible; (b) extendible, but non-sufficient; (c) and (d) sufficient.

Fig. 3 .

 3 Fig. 3. (a) The partial orientation D obtained by Algorithm 1; (b) and (c) valid orientations obtained by assigning any direction to the dominated edge t 1 t 3 .

Figure 3 (

 3 Figure 3(b) or D 2 in Figure 3(c) by assigning any direction to the dominated edge t 1 t 3 .

We use superindices to reference different states and subindices to specify places. Thus, x i p is the number of tokens assigned to place p at state x i .

These priority relations shall reflect the relative reaction rates of the (chemical) reactions represented by the transitions of the network with the idea that faster reactions have higher priorities and are taken. On the model side, priorities can be seen as a discrete extreme case of firing rates of transitions defined by probability distributions, where exactly one transition in T (x) (namely, the highest-priority transition trans(x)) has probability 1, and all other transitions in T (x) have probability 0.