Bernardetta Addis
email: bernardetta.addis@loria.fr

Giuliana Carello
email: giuliana.carello@polimi.it

Francesca De Bettin

Meihui Gao
email: meihui.gao@loria.fr

On a Virtual Network Function Placement and Routing problem: properties and formulations

Keywords: OR in telecommunications, Networks, Virtual Network Functions, ILP formulations 1

In recent years, the increasing diffusion of applications, both on computers and mobile devices, has yielded to an increasing demand for network services. So far, the network services, such as firewalls or tunneling, were provided by expensive hardware appliances, which could not keep up with the ever increasing demand nor allow new services to be embedded at a reasonable cost. Network Functions Virtualization has been recently proposed to overcome such issues: hardware appliances are replaced with Virtual Network Functions running on generic servers. Indeed, thanks to the Network Functions Virtualization paradigm, it is possible to flexibly, dynamically and cost-effectively manage network services. A key problem in implementing the Network Functions Virtualization paradigm is the so called Virtual Network Functions chaining problem: Virtual Network Function instances must be located on some network nodes. Demands must be routed so as to guarantee that each demand passes through the functions it requires. In this work we consider a particular case of the VNF chaining problem where each demand requires a single service and must be routed on a simple path. All the demands require the same service. Links and service instances are capacitated. The goal is to minimize the number of VNF instances installed. We investigate the problem properties and we compare two formulations inspired by the two main modeling strategies proposed in the literature.

Introduction

The mass diffusion of telecommunication networks and the possibility of accessing email, social networking or cloud computing from mobile devices is exponentially increasing the demand for network services. Network services were up to now provided by proprietary network appliances, such as firewalls, proxies or WAN optimizers, but it has become difficult to integrate and operate such hardware based appliances or to add new functionalities to keep up with the ever increasing demand at a reasonable cost. To cope with this challenge, the Network Functions Virtualization (NFV) paradigm has been recently proposed: hardware based appliances should be replaced by Virtual Network Functions (VNFs) running on generic servers, which will provide the required services in a cheaper and more flexible way.

A key problem arising in implementing the NFV paradigm is the VNF chaining problem: locating VNFs and routing demands so as to guarantee that each demand passes through a sequence (chain) of VNFs that provides the services it needs. The allocation of demands to VNF instances and the demand routing must satisfy quality requirements, such as delay, congestion, minimal resource utilization (CPU, energy, etc). We can schematically describe the VNF chaining problem as follows: we are given a telecommunication network, where the nodes can be connected to computing servers (and/or clouds). Each server is connected to one node, but in general a node can or cannot be connected to a server. Traffic demands must be routed on the network and must be served by a set of VNFs (services), which must be located on computing servers. For each demand, the VNFs must be traversed with a given (possibly partial) order or without any fixed order. Therefore a traffic demand that needs to access a VNF located in a given server must pass through the node that is directly connected to the computing server itself. Several constraints can be taken into account, such as the service order constraint, the VNF capacity constraint, and link capacity constraint, thus leading to several versions of the problem.

Different versions of the problem have been addressed in the telecommunication literature, which, however focuses mainly on the application and, to the best of our knowledge, properties have not been studied thoroughly (apart from the complexity of a particular version of the problem which has been addressed in [START_REF] Addis | On the complexity of a virtual network function placement and routing problem[END_REF]). Although different mathematical programming formulations have been proposed for the problem, they have not been compared. From an optimization point of view, the VNF chaining problem shares features with network design problems (for the demand routing part) and with facility location problems (for the VNF location and the server dimensioning). Both problems are widely studied in the literature, but the combination described by the VNF chaining problem represents a new challenge. The goal of the paper is to study the properties of a particular version of the problem and to compare two formulations derived from the main modeling strategies proposed in the literature. Further, additional inequalities to enrich such formulations are proposed. Formulations and valid inequalities are tested on a set of instances derived from the SNDLib ( [START_REF] Orlowski | SNDlib 1.0 -Survivable Network Design library[END_REF]).

We work under the (commonly used) hypothesis that the network link capacity is tighter than the capacity of the connection between computational servers and nodes. Therefore, as each server is connected directly to only one routing node, we use a compact representation where routing nodes and server nodes are collapsed, simply assigning the computational capacity of a server to the associated node. VNF instances are capacitated, as well as network connections. Further, each demand requires a single service, which is the same for all the demands, and must be routed on a simple path. The goal is to minimize the number of installed VNF instances.

This paper is organized as follows. In Section 2, we present the related work. In Section 3, we formally define the problem and investigate the problem properties. In Section 4, we introduce two problem formulations and describe the features of each of them and their relation. We present and analyze the results of computational experiments in Section 5. Section 6 concludes the paper.

Related work

NFV technology has received much attention from both industry and academia. A number of works on NFV have been published addressing challenging aspects spreading from the creation of NFV platforms [START_REF] Soares | Cloud4NFV: A platform for virtual network functions[END_REF], [START_REF] Hwang | Netvm: High performance and flexible networking using virtualization on commodity platforms[END_REF] to the optimization of VNF chaining with respect to, for instance, resource efficiency [START_REF] Luizelli | Piecing together the NFV provisioning puzzle: Efficient placement and chaining of virtual network functions[END_REF] or competitive goals [START_REF] Addis | Virtual network functions placement and routing optimization[END_REF]. We classify the literature on VNF optimization into two broad categories according to the modeling strategy. The first modeling strategy is based on the Virtual Network Embedding (VNE) paradigm [START_REF] Fischer | Virtual network embedding: A survey[END_REF]. In VNE a set of virtual networks is given that must be embedded into a physical one, mapping virtual nodes on physical nodes and virtual links on physical paths, while respecting capacity constraints. The second modeling strategy combines routing and location decisions.

Preliminary works on the optimization of VNF chains deployment tend to model the VNF chaining problem as a VNE problem. A virtual network is built for each demand representing the demand together with the chain of VNFs to serve it. The VNF instances location and demand routing are then defined according to the VNE mapping solution. In [START_REF] Guerzoni | A novel approach to virtual networks embedding for SDN management and orchestration[END_REF], authors introduce a VNE based MIP formulation. In [START_REF] Bari | On orchestrating virtual network functions[END_REF] a VNE based ILP formulation is proposed along with a dynamic programming based heuristic to deal with large size instances. Similarly, [START_REF] Mijumbi | Design and evaluation of algorithms for mapping and scheduling of virtual network functions[END_REF] proposes a VNE based representation of the problem and focuses on the online version of the VNF chaining problem: three greedy algorithms and a tabu-search based heuristic method are proposed to deal with the VNF online mapping and scheduling. The problem of embedding VNF chains is addressed also in [START_REF] Lukovszki | Online admission control and embedding of service chains[END_REF], where demands may be rejected and the subset of accepted demands must be maximized while limiting the number of service chains considered. In [START_REF] Luizelli | Piecing together the NFV provisioning puzzle: Efficient placement and chaining of virtual network functions[END_REF], the authors propose an ILP model based on the mapping of VNF chains on a physical network, although without naming it explicitly. Pre-computed paths for mapping are used. The ILP model is used as a step in a heuristic procedure based on a dichotomic search on the number of located VNFs.

From the optimization perspective, however, the VNF chaining problem differs from the general VNE problem. In VNE, virtual network nodes and virtual network links need to be mapped on the physical network, while in the VNF chaining problem, the VNFs are located on physical nodes, and the service demands must be assigned to their required VNF instances and routed to pass through them. In a sense, VNF chaining can be seen as a special case of VNE where the virtual networks to be embedded reduce to linear graphs whose both extreme nodes have a fixed location. However, the VNE based representation is possible only if the order of VNFs in the chain is fixed and fully determined. As a consequence, the VNE complexity results cannot be just extended to the VNF chaining problem as they are. Indeed, [START_REF] Addis | On the complexity of a virtual network function placement and routing problem[END_REF] shows that the VNF chaining problem is easier than the VNE in some particular case and for some network topologies.

The second modeling perspective, adopted by a handful of papers in the networking literature, exploits the fact that the VNF chaining problem shares features with both facility location and network design problems. Authors in [START_REF] Mehraghdam | Specifying and placing chains of virtual network functions[END_REF] define a model formalizing the VNF chaining problem using a context-free language and propose to use Mixed Integer Quadratically Constrained Program (MIQCP) for finding the optimal placement of VNFs and chaining them together. In [START_REF] Bouet | Cost-based placement of vDPI functions in NFV infrastructures[END_REF], the specific Deep Packet Inspection (DPI) VNF placement problem, where a single type of services is asked, is targeted and modeled as an adaptation of the multicommodity flow problem model. Small instances are solved with a standard ILP solver (GLPK) and for larger instances a centralitybased greedy algorithm is proposed: at each step a new VNF (vDPI) is located in the node that has the highest centrality until all the traffic flows are served or all nodes have a vDPI. In [START_REF] Addis | Virtual network functions placement and routing optimization[END_REF], authors provide a MILP formulation accounting for facility location and demand routing with a generic number of services and no fixed order in the chain, taking into account different latency regimes and traffic compression properties. Their work investigates the trade-off between a legacy traffic engineering (TE) related goal (namely maximum link utilization) and a combined TE-NFV goal (namely, the sequential optimization of the TE goal and of the VNF installing cost). An extension of the work [START_REF] Gao | Optimal orchestration of virtual network functions[END_REF] presents a model that takes into account also ordered (or partially ordered) chains. A math-heuristic is presented to speed up the solution phase and a numerical comparison with a VNE model approach is proposed. A model similar to [START_REF] Addis | Virtual network functions placement and routing optimization[END_REF] is proposed in [START_REF] Allybokus | Virtual function placement for service chaining with partial orders and anti-affinity rules[END_REF], where additional constraints are added to take into account the incompatibility of certain VNFs and thus imposing that they are located in different nodes. Furthermore, in this work, some demands can be rejected, therefore their routing and VNF assignment can be neglected. A greedy algorithm based on the decomposition of the problem into two steps (routing and location) is proposed. Flows are allocated one by one, and then the VNFs are located on the selected paths. Most of the works focus on developing heuristic methods to solve the problem within a reasonable computational time, and most of them decompose the problem into two steps.

Although the combined facility location and network design problem has been studied in optimization literature [START_REF] Contreras | General network design: A unified view of combined location and network design problems[END_REF], the VNF chaining problem specificities are still not explored in the optimization literature. To the best of our knowledge, we are among the first to investigate in detail the properties of the VNF chaining problem. We propose two different formulations that are representative of each modeling perspective presented in the literature (namely, VNE and routing and location based) and compare them theoretically and numerically.

Problem description and properties

In this work we focus on a VNF chaining problem where a single type of VNF is considered and any node can be equipped with a VNF. VNFs and links are capacitated and the number of installed VNF instances is minimized. Further, each demand must be served by an instance of the VNF and must be routed on a simple path. Let us denote the problem as Virtual Network Function Placement and Routing with Simple Path (VNF-PR SP ).

The network is represented by a graph G(N, A), where N represents the set of nodes and A represents the set of capacitated arcs (or links). Let u denote the arc capacity. An instance of the VNF can be installed on each node in N and can serve a limited amount of demand q. The network demands are represented by the set D: each demand k ∈ D is characterized by a source (origin) node o k a destination (terminal) node t k , a demand amount d k . The demand must be served (pass through) an instance of the VNF (service) 1 , but a demand can pass through a node without using a VNF installed on it2 . Demands cannot be split and must be routed on simple paths, i.e. the demand is not allowed to deviate from its path to "search" the VNF.

The problem is NP-complete even with only one type of capacity (either link or service capacity): in [START_REF] Luizelli | A fix-and-optimize approach for efficient and large scale virtual network function placement and chaining[END_REF] the problem is proved to be difficult if nodes are capacitated (the same approach can be used for the service capacity case), while in [START_REF] Addis | On the complexity of a virtual network function placement and routing problem[END_REF] it is proved to be difficult if only arc capacity is considered.

General remarks

We assume that one VNF type is available, however this assumption is not so restrictive. Indeed, the problem where all the demands ask for the same sequence (same types of VNF and same order) is equivalent to the case with a single VNF type, if VNFs capacity is uniform and a node can host an instance of each VNF type. Proposition 3.1. Let us consider two problems P 1 and P 2 that share the same features but the cardinality of the required chain of services: in P 1 each demand requires the same unique service a, while in P 2 a set of VNF types T is given, each VNF type in T has the same capacity of service a and all the demands require the same sequence of services, both in terms of service types and order.

If there exists an optimal solution for problem P 1 , then an optimal solution for P 2 can be derived by installing all the required services in the optimal sites selected by the solution of P 1 and routing the demands according to the optimal solution of P 1 .

Proof. An optimal solution for P 1 is given, that is to say a location solution for the instances of service a such that all the demands can be routed from their source node to their destination node passing through an instance of the service a, and respecting link capacity, service capacity and simple path constraints. Now, let us consider the problem P 2 . By installing an instance of each service type in T on the same nodes where instances of service a are located, and by keeping the same demand-service instance assignment as in the P 1 solution, we obtain a feasible solution for P 2 . In fact installing several VNF type instances on one node does not affect neither the link capacity constraints nor the routing constraints. Furthermore, as the VNF types have the same capacity, if a service {a} instance installed in a given node i can serve all the demands assigned to it, then any service instance installed on node i can serve the same set of demands.

As any feasible solution of P 1 can be extended to a feasible solution of P 2 with the same number of service instances per service type, if the P 1 solution location is optimal then it is optimal also for P 2 .

We can observe that under the hypothesis that the set of required service types is exactly the same, the two problems are equivalent even if they account for different service orders3 .

Impact of biconnected components and articulation points

A lower bound on the number of VNF instances (and thus on the objective function) can be obtained if the graph contains at least one articulation point.

Let us recall some definitions. Then, it is necessary to install a service inside each biconnected component with internal demand and single articulation point. Furthermore, if the instance is feasible,there exists an optimal solution where an instance of the service is located on each articulation point belonging to a biconnected component with internal demand and single articulation point.

Proof. Let us consider a biconnected component, a demand with both endpoints within it and a node i outside it. If the demand is served by a service installed on node i then its routing must pass first through the articulation point to reach the service and then it must pass again through the same articulation point to complete its routing, thus violating the simple path routing constraint. Thus, in a feasible solution, a service must be installed within a biconnected component to serve the demands whose source and destination belong to the biconnected component itself. Similarly, a demand with both endpoints outside the biconnected component cannot be served by a node in the biconnected component, if it is not the articulation point. Thus a solution where a service is installed in the articulation point is always at least as good as one in which the service is in the biconnected component but not in the articulation point. Therefore, the minimum number of service instances is equal to the number of biconnected components with internal demands.

Thanks to Property 3.2, it is possible to determine a lower bound of the number of VNFs to install combining the number and structure of the biconnected components with the source and destination of the demands. Furthermore, a partial solution can be built, installing services on articulation points. A preprocessing can be devised, which aims at 1. detecting the number of biconnected components with internal demand, thereby installing one service on each of their articulation points;

2. forbidding the assignment of a demand to the VNF which are out of the biconnected component the demand belongs to.

Mathematical formulation

As mentioned, in the telecommunication literature two main modeling perspectives have been proposed: the VNF Placement and Routing (VNF-PR) formulation [START_REF] Addis | Virtual network functions placement and routing optimization[END_REF] and the VNE formulation [START_REF] Bari | On orchestrating virtual network functions[END_REF]. In this section we present two formulations inspired by such perspectives. The first one is directly inspired by network design and facility location problems: a set of variables and constraints represent origin-destination routings and a set of variables and constraints represent the facility location part, connecting constraints are used to couple the two subproblems. It can be considered as the adapted version of the formulation presented in ( [START_REF] Addis | Virtual network functions placement and routing optimization[END_REF]) to our VNF-PR SP problem. The second one, the Split-Path (SP), is based on the decomposition of each demand path into several sub-paths, each associated with a service instance serving the demand. A similar model is presented in [START_REF] Bouet | Cost-based placement of vDPI functions in NFV infrastructures[END_REF] (also here a single VNF type is considered). We can observe that the SP formulation is very close to the VNE formulations. Indeed, the VNF chaining problem can be viewed as a VNE problem where the networks to embed are linear graphs. Nevertheless, the SP formulation is leaner than the VNE based formulation, because it is tailored to the problem. Furthermore, the simple path condition is not guaranteed in the VNE formulations.

In Table 1 the notation is summarized and the variables used by the two models are reported. As some variables are common to both models and some are model dependent, in the last column we report the model in which the parameter/variable is used.

In both models, binary variable y i represents the location of an instance of the VNF on node i ∈ N and binary variable z k i represents the assignment of demand k to the instance of the VNF located on node i. The two models differ in the way the routing is modeled. In both, arc binary variables are used, that are equal to one if a given arc is used by a given demand. In PR, these variables are x k ij . In SP, the path is explicitly divided into two sub-paths: the first from origin o k to the service node (described by variables x k1 ij ) and the second from the service node to the destination t k (described by variables x k2 ij ). As we want to enlighten the common points and differences between the two models, we present them in parallel, starting from the common part.

min i∈N y i ( 1
)
i∈N z k i = 1 ∀k ∈ D (2)
z k i ≤ y i ∀k ∈ D, i ∈ N (3) k∈D d k z k i ≤ q ∀i ∈ N (4)
The objective function (1) minimizes the sum of the opened services (i.e., instances of the VNF). Constraints [START_REF] Orlowski | SNDlib 1.0 -Survivable Network Design library[END_REF] impose that each demand is assigned to exactly one instance of the service. Inequalities [START_REF] Soares | Cloud4NFV: A platform for virtual network functions[END_REF]

y i 1 if a service is located on node i ∈ N both z k i 1 if demand k ∈ D uses the service on node i ∈ N both Routing variables (binary) x k ij 1 if arc (i, j) ∈ A is used by demand k ∈ D PR x k1 ij 1 if arc (i, j) ∈ A is used by demand k on sub-path 1 SP x k2 ij 1 if arc (i, j) ∈ A is used by demand k on sub-path 2 SP TSP-like labeling variables (continuous non-negative) π k i position of node i ∈ N in the path used by demand k ∈ D PR Table 1: Mathematical notation
VNF instance is installed on a node, then no demand can be assigned to it. Constraints (4) impose that each instance of the VNF can serve a maximum quantity q of demand.

The link capacity constraints are similar for the two models:

SP: k∈D d k (x k1 ij + x k2 ij ) ≤ u ∀(i, j) ∈ A (5)
PR:

k∈D d k x k ij ≤ u ∀(i, j) ∈ A (6)
We now present the constraints characterizing each formulation. The main difference is in the way the routing is managed, and, as a consequence, in how the models deal with the coherence between service assignment and routing. In short, in the SP formulation routing and assignment are implied by modified flow balance constraints, while in the PR formulation the routing is implied by the classical flow balance constraints and the consistency between assignment and routing is implied by coherence constraints and isolated loop elimination constraints.

Routing and assignment are modeled as follows:

SP: j:(i,j)∈A x k1 ij - j:(j,i)∈A x k1 ji = 1 -z k i if i = o k -z k i otherwise ∀k ∈ D, i ∈ N (7) j:(i,j)∈A x k2 ij - j:(j,i)∈A x k2 ji = z k i -1 if i = t k z k i otherwise ∀k ∈ D, i ∈ N (8) j:(j,i)∈A (x k1 ji + x k2 ji ) ≤ 1 ∀k ∈ D, i ∈ N (9) j:(i,j)∈A (x k1 ij + x k2 ij ) ≤ 1 ∀k ∈ D, i ∈ N (10)
Each demand is routed on two sub-paths: from the source node to the VNF node (equations ( 7)), then from the VNF node to the destination node (equations ( 8)). These two constraints impose that the routing of the demand passes through the VNF instance assigned to the demand itself, therefore ensure that the assignment is consistent.

Simple path routing5 is imposed by constraints ( 9) and ( 10): each demand can pass through a node at most once.

PR:

j:(i,j)∈A x k ij - j:(j,i)∈A x k ji =      1 if i = o k -1 if i = t k 0 otherwise ∀k ∈ D, i ∈ N (11)
z k i ≤ (j,i)∈A x k ji ∀k ∈ D, i ∈ N \ {o k } (12) π k j ≥ π k i + x k ij -|N | (1 -x k ij ) ∀k ∈ D, (i, j) ∈ A ( 13
)
Each demand is routed from its source to its destination with the classical flow balance constraints [START_REF] Lukovszki | Online admission control and embedding of service chains[END_REF] and it is forced to pass through a VNF instance by constraints [START_REF] Mehraghdam | Specifying and placing chains of virtual network functions[END_REF], that impose that a demand k can be assigned to a service located on node i only if the routing path of the demand passes through the given node. The simple path and the elimination of isolated cycles are enforced using the TSP-like labeling variables π and constraints (13): continuous variables π k i represents the position of node i in the routing path of demand k.

Both models can be generalized to take into account multiple service types, even hosted on different nodes. Nevertheless, SP model is able to manage the case where the order of services is fixed (as it explicitly split the path into sub-paths from source to service, service to next service, etc.) at the cost of increasing the number of routing variables and constraints, but it needs additional variables to manage the no ordered case (see A). This is due to the fact that the routing part and the location part are directly connected by the notion of sub-path, and new variables are needed to decouple them and generalize the model. Instead, PR model can be simply generalized to deal with any imposed order (full, partial, none). In fact, variables π can be used, together with additional constraints, to impose a given full or partial order of the services along the demand path (see [START_REF] Addis | Virtual network functions placement and routing optimization[END_REF]).

Relation between the two formulations

In this section we show that the SP formulation produces a continuous relaxation bound that is always not worse than the one produced by PR. The feasible region of SP can be partitioned into two subsets: in the first subset no isolated cycles exist while in the second one isolated cycles are present, but they cannot host a service (see Remark 4.1). Any solution of the second subset has an equivalent in the first one (see Proposition 4.2) and we prove that any solution of the first subset can be mapped into a solution of PR (see Theorem 4.1). Thus a solution of SP either is feasible also for PR or is equivalent to one that is. Instead, there exist solutions of PR that are not feasible for SP and for which the bound provided by SP is strictly better than the one provided by PR (see Proposition 4.3).

For any demand k, the flow in a feasible continuous solution can be divided into flow on simple paths and flow on cycles. Let us denote with P k the set of simple paths and with C k the set of cycles. We can distinguish between two type of cycles (see Figure 1): cycles sharing some nodes with a simple path (Figure 1a) and isolated cycles (Figure 1b). Remark 4.1. SP forbids demands to be served, even partially, by a VNF instance installed on an isolated cycle 6 . For example, let us consider an isolated cycle of two nodes A and B such that the demand is partially served by a node

A (z k A = α, α < 1)
. Summing up flow balancing constraints [START_REF] Fischer | Virtual network embedding: A survey[END_REF] leads to an inconsistency 0 = -α (analogously for subpath 2).

As a consequence, only three cases occur: Remark 4.2. Consider a feasible solution of the continuous relaxation of SP (x 1 , x 2 , y, z), a demand k and a cycle induced by such solution. Let us denote with N c the set of nodes of the cycle c that are not shared with any simple path:

N c = {i ∈ c : ∀p ∈ P k i ∈ p}.
Due to flow balance constraints ( 7)-( 8), we have only three possible cases for all nodes belonging to N c :

1. if a (partial) service instance is located in any of the nodes belonging to N c , the cycle is induced by variables of both semi-paths, and If a (partial) service is located on a node belonging to the cycle c ∈ C k , but not to the path p , the routing variables inducing the path and the cycle are fractional and their value is less than or equal to 1 2 , due to constraints ( 7)-( 8) and ( 9)- [START_REF] Mijumbi | Design and evaluation of algorithms for mapping and scheduling of virtual network functions[END_REF]. Proposition 4.2. Any solution such that no service instance is installed on a node belonging to a cycle but not to a simple path can be transformed in an equivalent solution (in term of cost, location and assignment) removing the cycles without service instances installed and the corresponding flow from the routing.

x k1 i = x k2 i 2. if
Theorem 4.1. Any solution of the continuous relaxation of SP such that no service instance is installed on a node belonging to a cycle but not to a simple path can be mapped into an equivalent solution of PR in terms of routing, location and assignment and therefore cost.

Proof. Opening variables y i and assignment variables z k i , the objective function and constraints (2), ( 3) and ( 4) are common to both formulations. SP routing variables can be easily mapped into PR ones as follows:

x k ij = x k1 ij + x k2 ij (14)
Thanks to constraints ( 9) and ( 10) the mapping guarantees also that x k ij ∈ [0, 1]. Further, link capacity constraints of SP (5) imply the link capacity constraint of PR [START_REF] Addis | Virtual network functions placement and routing optimization[END_REF]. Routing constraints of the SP formulation imply the routing constraints for the PR formulation. In fact, by summing equations ( 7)-( 8) and using the mapping [START_REF] Gao | Optimal orchestration of virtual network functions[END_REF], we obtain constraints [START_REF] Lukovszki | Online admission control and embedding of service chains[END_REF]. Now we show that SP routing constraints for the semi-path (7) imply routinglocation connecting constraints of PR [START_REF] Mehraghdam | Specifying and placing chains of virtual network functions[END_REF]. Let us consider the case i ∈ N, i = o k :

j:(i,j)∈A x k1 ij - j:(j,i)∈A x k1 ji = -z k i
reordering terms, we obtain:

j:(i,j)∈A x k1 ij + z k i = j:(j,i)∈A
x k1 ji As j:(i,j)∈A x k1 ij ≥ 0, we can derive:

z k i ≤ j:(j,i)∈A
x k1 ji Adding j:(i,j)∈A x k2 ij at the right side, as this term is always not negative, the inequality still holds:

z k i ≤ j:(j,i)∈A (x k1 ji + x k2 ij )
Then, using the routing variables mapping [START_REF] Gao | Optimal orchestration of virtual network functions[END_REF], we verify constraint [START_REF] Mehraghdam | Specifying and placing chains of virtual network functions[END_REF]:

z k i ≤ j:(j,i)∈A x k ji .
Finally, suitable values for π variables must be derived. Let us consider a demand k and its routing. We can build an induced graph as follows:

G k (N k , A k ) where (i, j) ∈ A k if x k1 ij + x k2 ij > 0 and ∃p ∈ P k : (i, j) ∈ p, i.e.
the arc belongs at least to one simple path. A node î belongs to N k if there exists an arc ((î, j) or (j, î)) in A k . For any arc (i, j) ∈ G k we define the following cost

c ij = x k1 ij + x k2 ij = x k ij .
As G k does not contain arcs that belong only to cycles in C k , the obtained graph is acyclic, thus we can define π k j as the longest path from node o k to node j:

• π k o k = 0 • π k j = max i:(i,)∈A k {π k i + x k ij }
Such values obviously satisfy constraints [START_REF] Bouet | Cost-based placement of vDPI functions in NFV infrastructures[END_REF] for the nodes belonging to the path.

The nodes that belong to a cycle and to a simple path (nodes from l to m in Figure 2) have already been assigned a suitable value π. We now need to determine a value of π for the nodes on the cycle N C that have been removed.

π k i = π k m + π k l 2 (15)
Now, we prove that such values of π always satisfy constraints [START_REF] Bouet | Cost-based placement of vDPI functions in NFV infrastructures[END_REF]. We can observe that x ij ≤ 1 in any feasible solution, therefore the values of π are bounded by |N | -1. As for the arcs in A \ A k , we have two cases.

1. Arcs whose endpoints both belong to the cycle but not the path (thus both endpoints are labelled according to equation ( 15)). Due to property 4.1, we can infer that for any arc belonging to the cycle but not the path, we have x k ij ≤ 1 2 . Therefore, the term:

x k ij -|N | (1 -x k ij ) is always non positive as |N | ≥ 2.
Therefore for any two nodes in the cycle, as they have the same value of π, the constraint is valid.

2. Arcs with one endpoint belonging to the cycle and the other one belonging both to the path and to the cycle, i.e. with one extreme in l or m.

Let consider the arc of the cycle entering node l: (i, l) (see Figure 2), we need to prove that:

π k l ≥ π k i + x k il -|N |(1 -x k il ), (16)
Let us denote with n the number of arcs in the path between node l and node m (n ≤ |N | -1), and with β ≤ 1 the value of the associated routing variable on the path, then we have that:

π k m = π k l + βn
and we obtain:

π k i = π k m + π k l 2 = π k l + βn 2 ≤ π k l + (|N | -1) 2
Thus, denoting with γ the right-hand side of equation ( 16), we get:

γ ≤ π k l + (|N | -1) 2 + x k il -|N |(1 -x k il )
and, rearranging the terms,:

γ ≤ π k l + x k il - 1 2 (|N | + 1)
and using x k il ≤ 1 2 (see Proposition 4.1):

π k l ≥ γ
A similar argument can be used to prove that the constraint is valid for the link belonging to the cycle and exiting the other extreme node m.

We now prove that the bound provided by PR is not better than the one of SP, by showing an instance in which the bound provided by SP is stricter than the one provided by PR. Further, we present three features that make a solution unfeasible for the SP continuous relaxation but are acceptable for the PR continuous relaxation.

Proposition 4.3. The bound provided by PR is not better than the one provided by SP.

Proof. Let us consider the symmetric graph in Figure 3a (in the following figures, each pair of the symmetric arcs is represented by the corresponding edge). The services are uncapacitated, and the link capacity is 5. There are 4 demands, whose characteristics are listed in Table 3b. The continuous relaxation provided by SP is equal to 2, while the continuous relaxation provided by PR is 1, for any value of the demands k 3 and k 4 in (0, 5].

We report the details of the solution of SP formulation in Table 2 and Figure 4, while the details of the solution of PR in Figure 5 and Table 3: the assignment of service to nodes is reported in bold in the tables and in gray in

f p node (i) z k i k 1 p 1 : 4 → 5 → 2 → 3 1 4 1 k 2 p 2 : 5 → 4 → 3 → 2 1 4 1 k 3 p 3 : 3 → 1 1 3 1 k 4 p 4 : 4 → 6 1 4 1 Installed services y 3 = 1 y 4 = 1
Table 2: Routing and assignment/location in the continuous relaxation of SP the figures. As for the SP formulation, one service is located on node 4 and one on node 3. Demands k 1 , k 2 and k 4 are served by the service located on node 4, while demand k 3 is served by the service located on node 3. As for the solution of PR, half service is installed on node 4 and the other half on node 5; each demand uses both services.

The difference between the two bounds is due to the fact that in the continuous relaxation of the PR formulation some routing solutions are feasible, while they are not for the SP formulation, because of the direct coupling of assignment and routing determined by constraints ( 7)-( 8) present in SP. Indeed, the example above is a representative of a family of solutions that are feasible for PR but not for SP: Remark 4.3. A solution where a source-destination path does not pass through any service node (see path p 1 for demand k 3 in 4.3) and an isolated loop hosts a (partial) service (see path p 2 for demand k 3 in 4.3) is feasible for PR but not for SP.

Such solutions may be profitable when the capacity of a cut is small and some demands cannot reach the services installed on the other side of the cut itself: The routing provided by the continuous relaxation of SP using a service on an isolated cycle is then the best option for PR. In the example described in Table 3b demands k 1 and k 2 saturate the cut {4, 5, 6} , {1, 2, 3} forcing SP to install a service in each side of the cut to serve also demands k 3 and k 4 . Instead, PR does not open two services, thus providing a weaker bound. The bound provided by SP is stricter even if the amount of flow of demands k 1 and/or k 2 decreases and thus the cut is not fully saturated, as long as the residual capacity on the cut {4, 5, 6} , {1, 2, 3} is not enough to allow the full demand k 3 to pass through it and back (or symmetrically demand k 4 for the reversed cut). A feasible solution is then selected by PR as described in Figure 6, where the demand is half routed (x = 0.5) on the path and is completely served by partially using the two services located in node i and j. Such solution is instead unfeasible for SP 7 , as proved by the following proposition.

z k i ( 17
)
where with succ(lm) we represent all the nodes that appear in the path p k not before arc (l, m) (node m is considered belonging to succ(lm)).

Proof. This property is a direct consequence of the modified flow balancing constraints ( 7)- [START_REF] Guerzoni | A novel approach to virtual networks embedding for SDN management and orchestration[END_REF]. See Figure 7 for a schematic illustration of this property.

Impact of the biconnected components

Network topology has an impact on the quality of the bounds produced by the two formulations. In fact, the SP formulation can produce a tighter bound in presence of biconnected components, even in the uncapacitated case, due to the simple path assumption.

Let us consider the graph in Figure 8a, and a set of three demands described in Table 8b. Service and link capacities are unbounded. The graph contains two articulation points (nodes 3 and 6) and 3 biconnected components:

BC 1 = {1, 2, 3}, BC 2 = {3, 4, 5, 6}, BC 3 = {6, 7, 8}.
The continuous relaxation bound obtained by the SP formulation for this instance is 4 3 , the one obtained by the PR formulation is the trivial bound 1. In Table 4, a solution 8 for the SP formulation is reported. For each path, the node where the (partially) used service is located is reported in bold. Partial services are installed on nodes 2, 5 and 8. Half for nodes 2 and 8 and one third for node 5. Demand k 1 (k 3 , respectively) is served by the half service installed on node 2 belonging to its connected component BC 1 (node 8 in BC 3 respectively) and by half service installed on node 8 in connected component BC 3 ( node 2 in BC 1 , respectively). Demand k 2 is split on three paths, and each of them is served by a (partial) service in a different connected component. i j 4: Routing and assignment/location in the continuous relaxation of SP for the biconnected components case example In Table 5 a solution for the PR formulation is reported. Each demand is routed on the direct arc connecting its origin to its destination, thus satisfying the flow balance constraints [START_REF] Lukovszki | Online admission control and embedding of service chains[END_REF]. To reach the service, both demand k 2 and k 3 use two isolated cycles each in the connected component BC 1 . It is worth to notice that a single cycle would not be enough to satisfy both the coherence constraints [START_REF] Mehraghdam | Specifying and placing chains of virtual network functions[END_REF] and the TSP-like cycle elimination constraints (13) (only fractional solutions can have cycles).

z i = α x 1 = ζ + α x 1 = ζ (a) flow balance on node i i j z j = β x 1 = δ + β x 1 = δ (b) flow balance on node j i j x 1 = δ + α + β x 1 = δ + β x 1 = δ (c) resulting feasible values for x 1
f p node (i) z k i k 1 p 1 1 : 1 → 2 0.5 2 0.5 p 1 2 : 1 → 3 → 6 → 8 → 6 → 3 → 2 0.5 8 0.5 k 2 p 2 1 : 4 → 5 1/3 5 1/3 p 2 2 : 4 → 3 → 2 → 3 → 6 → 5 1/3 2 1/3 p 2 3 : 4 → 3 → 6 → 8 → 6 → 5 1/3 8 1/3 k 3 p 3
k o k → t k d k 1 1 → 2 1 2 4 → 5 1 3 7 → 8 1 (b) Demands.

Figure 8:

The SP relaxation bound is strictly better than the one of PR: a numerical example with biconnected components demand paths fraction f p node (i)

z k i k 1 p 1 : 1 → 2 1 1 1 k 2 p 2 1 : 1 → 3 → 1 0.5 1 0.5 p 2 2 : 1 → 2 → 1 0.5 1 0.5 p 2 3 : 4 → 5 1 - k 3 p 3 1 : 1 → 3 → 1 0.5 1 0.5 p 3 2 : 1 → 2 → 1 0.5 1 0.5 p 3 3 : 7 → 8 1 - Installed services y 1 = 1
Table 5: Routing and assignment/location in the continuous relaxation of PR for the biconnected components case example

Valid inequalities

In this section, we describe some valid inequalities. We can rewrite the service capacity constraint (4): the total demand that can be served by the service located on the node i is limited not only by the service capacity, but also by the overall capacity of links that are incoming in the node (except for the demands served in the origin node i). A similar remark holds for the outgoing links capacity. We can calculate the maximal demand that can be served by a node as follow:

qi = min    q, max    (i,j)∈A u + k∈D:t k =i d k , (j,i)∈A u + k∈D:o k =i d k       (18)
Therefore, constraint (4) can be replaced by:

k∈D d k z k i ≤ qi ∀i ∈ N (19)
Both constraints (4) and constraints (19) can be strengthened using the service location variable y, obtaining:

k∈D d k z k i ≤ q y i ∀i ∈ N (20)
and

k∈D d k z k i ≤ qi y i ∀i ∈ N (21)
respectively.

When the capacity of a single VNF instance is not large enough to serve all the demands, a bound on the number of needed VNF instances can be calculated and introduced in a VI:

i∈N y i ≥ k∈D d k q (22)
Additionally, VIs inspired by cover inequalities can be added. As preliminary tests showed that adding all cover inequalities was not effective, we decide to select only the max-minimal cover. We define the max-minimal cover C 1 with respect to the service capacity as the minimal cover, i.e.

• k∈C1 d k > q • C 1 \ k is not a cover for any k ∈ C 1 such that |C 1 |
is maximal among all possible covers, namely the maximum number of demands that can be served by one service. We can find C 1 as follows: we order the set of demands in increasing order of bandwidth, and then select them until the total capacity is reached. Let us call M 1 = |C 1 | -1, then we introduce the following:

k∈D z k i ≤ M 1 ∀i ∈ N (23)
We can define in the same way a max-minimal cover C 2 for link utilization, changing the total demand condition as follows k∈C2 d k > u. Thus, if we call M 2 = |C 2 | -1, we get the following VIs:

For PR: k∈D x k ij ≤ M 2 ∀(i, j) ∈ A (24)
For SP:

k∈D (x k1 ij + x k2 ij ) ≤ M 2 ∀(i, j) ∈ A (25)

Computational Results

We tested the two formulations and the proposed valid inequalities on 16 networks (with minimum 10 nodes and maximum 28 nodes) from the SNDLib ( [START_REF] Orlowski | SNDlib 1.0 -Survivable Network Design library[END_REF]).

The topologies and the traffic demands (i.e., source, destination, amount of flow) are taken directly from SNDLib. Different capacity profiles were generated to analyze the impact of the VNF and link capacity. As for the links, two levels of capacity have been generated: low and high. The high capacity is such that all the demands can be routed on a single link, thus leading to uncapacitated link instances. The low capacity is computed as the minimum capacity such that a feasible routing exists, neglecting the services. As for the services, three levels of capacity are considered: low, medium and high. The high capacity is computed so as to guarantee that all the demands can be served by a single VNF (i.e., the VNF capacity is equal to the sum of the demand amount). Low VNF capacity is twice the total amount of the demands divided by the number of nodes, that is, we need to install a VNF in at least half of the nodes (for lower values many instances were not feasible). Medium capacity is the average between high and low. The obtained 96 instances are summarized in Table 6, where each row refers to a network topology. Columns two to four report the network features from SNDLib (number of nodes, number of links and number of demands). Column five gives the sum of the demand amount based on the SNDLib values. Such value is also the high capacity value both for links and VNFs. The last three columns give the values of capacity of VNFs and links: the first two report the medium and low capacity values for the VNFs and the last one reports the low capacity value for the links. In the following, we denote with h, m and l the high, medium and low capacity level respectively. Models are implemented with AMPL and instances are solved with IBM ILOG CPLEX 12.7.1.0 on an Intel Xeon, CPU E5-1620 v2 (4 cores), 3.7 GHz with 32 GB of RAM. A time limit of 3600s and a tree memory limit of 3000 MB are set.

First we present the results of continuous relaxation (Section 5.1), then we report about the integer problem (Section 5.2).

Continuous Relaxation Results

We first compare the results of the two formulations on the continuous relaxation, then we evaluate the impact of the valid inequalities described in Section 4.

Summarized results on the continuous relaxations of the two formulations are reported in and aggregated values over the 16 topologies are reported. As we proved in Section 3, the SP formulation produces a bound that is never worse than the PR formulation, therefore, (in the first group of columns) we report about the improvement obtained by the SP continuous relaxation upon the PR one. In the second column the number of instances where SP obtains a better bound than PR is given. The third and fourth columns report the average and maximum percentage of the improvement, calculated as 100% * CR SP -CR P R

CR

, where CR SP and CR denote the continuous relaxation of SP and , respectively. The average value is computed based on the instances where SP improves upon PR. The last four columns report the average and the maximum computational times (in seconds) for the two formulations. The best average computational time is reported in bold.

As expected by the theoretical results, SP formulation always provides a continuous relaxation bound that is better than or equal to the one provided by PR. When the link capacity is high SP improves upon PR just in one or two instances, but the improvement in the bound can be quite significant (up to around 150% for the l h case) and the average and maximum computational times are smaller (at least one third less). When link capacity is low, the number of instances where the SP formulation produces a better bound increases greatly (11-12 cases over 16) and the average and maximum improvement is more significant (up to 350%). The improvement is obtained at the price of a longer computational time, and SP cannot find a feasible solution within the time limit (3600s) for one instance, norway l l, while PR does. We run tests on the valid inequalities introduced in Section 4. In Table 8, we report summarized qualitative results. In the first column we report the equation corresponding to the VI. Constraints (21) are enhanced versions of the VNF capacity constraint, so they replace the VNF capacity constraint (4). In the second and the third columns the change obtained by adding the VI, in terms of bound and computational time, is qualitatively described. In the following, we discuss in detail the most effective valid inequalities in terms of bound improvement and/or computational time reduction, i.e. the enhanced capacity equation (21) (in the following VI1) and the lower bound on the minimum number of VNFs: equation ( 22) (in the following VI2). We consider them singularly and together (VI1+2).

VI

We compare the continuous relaxation bound obtained by the two formulations with the best upper bound known to evaluate its overall quality. The comparison is reported in Table 9. Results are reported in aggregated form, grouping instances based on the capacity level, for the case with noVI, and with VI1, VI2 and VI1+2. For each case, three columns are reported: the number of instances where the continuous relaxation bound is equal to the best UB and the average and maximum gap for the cases where they are not equal (calculated as best UB-CR LB best UB

). No integer solution can be found for the instance norway l l, therefore in this case we cannot calculate any gap with the best UB case. By the way, SP cannot even find a CR value for such instance: indeed the instance has the greatest number of demands, thus suggesting that SP may experience some issues with the increasing number of demands.

SP continuous relaxation is equal to the best upper bound in all the uncapacitated instances (h h). continuous relaxation is equal to the best upper bound in all the h h instances but one, france, where an articulation point is present. In this case, as we proved in Section 4.1.1, is weaker than SP. We can infer that for the uncapacitated case, we cannot expect an improvement in terms of bound from the VIs, and the only possible improvement can be in terms of computational time, if any.

Adding VI1 does not increase the number of cases where the CR bound is equal to the best UB, but reduces in general the gap for the cases where they are not equal. Adding VI2 provides a larger impact both for the SP and formulation. This is not surprising, since VI2 imposes a lower bound on the number of installed VNFs, that is also a lower bound on the objective function and in the high capacity link case such bound is often tight. Combining VI1 and VI2 reduces a little more the gap for the cases where the CR bound and the best UB do not coincide. 10 shows the average computational times for the SP and the formulations with and without the addition of VIs. The smallest computational time for each capacity case is reported in bold. The VI2 in general provides very good computational times, with few exceptions. Instead, VI1 always increases the computational times of both formulations, without improving the bound (which already coincides with the integer optimal solution).

Finally, we compare the CR of SP and when VIs are added. Figure 9 reports the percentage difference between the two continuous relaxation bounds for each VI (calculated as 100% *

CR SP V I i -CR V I i CR SP V I i
). As expected VI2 reduces the difference between the two continuous relaxations only when the service capacity is medium or low, while it provides the naive bound (at least one service) when the service capacity is high. If the service capacity is medium and low, adding VIs reduces the difference between the continuous relaxations. We can observe that adding VIs reduces the computational time of while improving its bound, which is then similar to the SP one.

ILP results

Let us now compare the behavior of the two formulations when solving the integer problem. In Figures 10a -10c (and respectively Figures 10b -10d), the number of optimal and integer feasible solutions found by the SP (respectively ) formulation are reported. SP performs better than , in fact SP finds the optimal solution when the link capacity is high. When it is low, SP cannot find the optimal solution for five instances out of 16 when no VIs are added, but this number improves adding VIs. The number of feasible solutions is similar to the number of optimal solutions, indeed if SP can find a feasible solution it can almost always prove its optimality. When SP cannot prove optimality, the gap is still reasonable (around 27% for janos us instance with h l and m l capacities). Adding VIs increases the number of feasible solutions that can be found when the link capacity is low. can find the optimal solution in more than half of the instances for the h h case and the l h case. For all the other capacity cases, it can solve to optimality less than half of the instances. The number of feasible solutions found is slightly higher than the number of optimal solutions.

Adding VIs not always improves the performance, for example in the h l Figure 9: Average percentage difference between SP model and model case the number of optimal (and feasible integer) solutions is reduced. The low link capacity makes the instances more challenging for both formulations.

In Table 11, computational times (in seconds) are reported. In the first block, the average times when the optimality is proved are reported, in the second block the average computational time including the cases where the time limit (3600s) is reached are summarized. The SP formulation in general performs better than the formulation, and adding both valid inequalities seems to produce the best results, reducing in almost all cases the total computational time.

In Table 12 we report about the UB and the LB of each combination of formulation and VIs w.r.t. the best known. Each group of columns refers to a VI case. The following data are reported: in the first column, the number of cases where the bound is equal to the best known, in the second column, the number of cases where the bound cannot be found and in the third column, the average gap with respect to the best known bound (when the gap is not null). The SP formulation with the VI1+2 shows the best performance among all possible variants, producing the best bounds (UB and LB) in the largest number of instances.

Articulation point based preprocessing

We tested the articulation point preprocessing on 3 network topologies of SNDLib which contain at least one articulation point: france, ta2 and zib54. Instance and 1069, respectively). The preprocessing is quite fast (few seconds) and its addition can improve the continuous relaxation, especially for the formulation where otherwise often the naive relaxation -one service -is found. As for the integer problem, its addition reduces almost always the computational time and allows solving to optimality, despite their big size, instances for which no feasible solution can be found without preprocessing (ta2 and zib54 for the l h capacity case and the zib54 for the l l capacity case). Nevertheless, in some capacity cases (all the h l and m l cases) no feasible solution can be found even using the preprocessing. However, as it needs negligible computational time and is beneficial for some instances, although not for all, the articulation point based preprocessing is worth performing.

Conclusions

This paper addresses a Virtual Network Function Placement and Routing problem, where each demand can be routed only through a simple path. The same service is required by all the demands and the number of needed service instances is minimized.

We first prove some problem properties: -the single service case is equivalent to the multiple service one, when the sequence of services is the same for all the demands and there is no limit on the number of service instances installed on a node; -an instance of the service must be installed on the articulation points that belong to biconnected components with internal demands.

Then two formulations are compared which are inspired by the two main modeling strategies proposed in the literature. The first modeling strategy (SP) is based on splitting each demand path into two sub-paths, one connecting the source with the service, the second one connecting the service with the destination. The second one () uses arc flow variables and forbids cycles exploiting node labels. We discuss the relation between the formulations and prove that SP always provides a better bound than . Valid inequalities are also proposed and their impact evaluated.

As expected from the theoretical results, computational tests show that stand alone SP improves upon , which in turn benefits more from the VIs and seems to suffer less from the increasing number of demands.

We are currently extending and SP formulations to the multi-service and multi-sequence case. SP and models apply different modeling strategies to guarantee the simple path routing of each demand. Indeed, other modeling approaches have been proposed in the literature to forbid non simple paths, although for different problems: for instance in [START_REF] Ibrahim | A strong flowbased formulation for the shortest path problem in digraphs with negative cycles[END_REF] a flow based formulation is proposed for the shortest path problem with negative cost. As future work, the possibility of applying alternative modeling techniques to the VNF-PR SP is worth analyzing.

The resulting extended models is:

min i∈N f ∈F y if i∈N z k if = 1 ∀k ∈ D, f ∈ F : V N F k f = 1 z k if ≤ y if ∀k ∈ D, i ∈ N, f ∈ F k∈D s∈1..n k +1 d k x ks ij ≤ u ∀(i, j) ∈ A k∈D:V N F k f =1 d k z k if ≤ q f ∀i ∈ N, f ∈ F j:(i,j)∈A
x k,s ijj:(j,i)∈A

x k,s ji = z k i,f k (s-1) -z k i,f k (s)
∀k ∈ D, i ∈ N, s ∈ 2..n k j:(i,j)∈A

x k,1 ijj:(j,i)∈A

x k,1 ji = 1 -z k i,f k (1) if i = o k -z k i,f k (1) otherwise ∀k ∈ D, i ∈ N j:(i,j)∈A x k,n k +1 ij - j:(j,i)∈A x k,n k +1 ji = z k i,f k (n k ) -1 if i = t k z k i,f k (n k ) otherwise ∀k ∈ D, i ∈ N s∈1.
.n k +1 l:(j,i)∈A

x ks ji ≤ 1 ∀k ∈ D, i ∈ N s∈1..n k +1 j:(i,j)∈A

x ks ij ≤ 1 ∀k ∈ D, i ∈ N

To extend the model for the case with unordered services, it is necessary to decouple the sub-paths description and the services assignment to nodes (originally both represented by variable z). We keep variables z to represent the location of services, while the new variables w will be used to describe the flow balance for sub-paths: and additional consistency constraints must be added to link z and w variables:

f ∈F :V N F k f =1 z k if = s∈1..n k +1 w k,s i ∀k ∈ D, i ∈ N

  (a) Cycle sharing nodes with a simple path (b) Isolated cycle

Figure 1 :

 1 Figure 1: Examples of cycle sharing nodes and of isolated cycle

Figure 2 :

 2 Figure 2: An example of a cycle sharing some nodes with a simple path Let us consider the two nodes l and m, corresponding to the smallest (π k l ) and largest (π k m ) value of variables π on the cycle N C , respectively. For all the nodes i ∈ N c , we impose:

Figure 3 :

 3 Figure 3: The SP relaxation bound is strictly better than the one of PR: a numerical example demand paths f p node (i) z k

1 (

 1 a) Routing of demand k1.

2 (

 2 b) Routing of demand k2.

3 (

 3 c) Routing of demand k3.

4 (

 4 d) Routing of demand k4.

Figure 4 :

 4 Figure 4: The routing provided by the continuous relaxation of SP

Proposition 4 . 4 .y 4

 444 Let us consider a feasible solution for the continuous relaxation of SP formulation where a fraction of a demand k is routed on a path p k . Let us consider the services located along this path and the corresponding assignment variables z k i , and suppose that such services are not used by demand k along demand paths f p node (i) = 0.5 y 5 = 0.5

Figure 5 : 5 Figure 6 :

 556 Figure 5: The routing solution of continuous relaxation of the PR

Figure 7 :

 7 Figure 7: Relation between routing and assignment variables in the SP formulation demand paths fraction f p node (i) z k

2 : 7 → 6 → 3 → 2 → 3 → 6 y 2

 27632362 = 0.5 y 5 = 1/3 y 8 = 0.5 Table

3 (

 3 a) Topology and demands distribution.

  (a) Number of optimal solutions SP. (b) Number of optimal solutions . (c) Number of feasible solutions SP. (d) Number of feasible solutions .

Figure 10 :

 10 Figure 10: Number of optimal and integer feasible solutions found

- 1

 1 -w ks i ∈ {0, 1} if demand k ∈ D uses the s -th service on node i ∈ N Only the flow balancing constraints are affected by this change: if i = t k w k,n k i otherwise ∀k ∈ D, i ∈ N

  An articulation point of a graph G is a vertex v such that G \ v has more connected components than G.

	Definition 3.3. The following property can be stated.
	Proposition 3.2. Let us consider a VNF-PR SP problem defined on a graph G
	containing biconnected components and suppose that there exists at least one
	demand whose origin and destination nodes are both in the same biconnected
	component. Further, suppose that such biconnected component has only one
	articulation point. Let us refer to such biconnected components as biconnected
	components with internal demands and single articulation point.
	Definition 3.1. A graph is biconnected if removing any node the graph remains
	connected 4 .
	Definition 3.2. Given a graph G(N, A), a biconnected component is a maximal
	induced biconnected subgraph of G.
	Biconnected components are connected to each other at shared vertices called
	cut vertices or articulation points.

  guarantee that if no

		Notation	Model
		Sets
	N	set of nodes	both
	A	set of arcs	both
	D	set of demands	both
		Capacities (Network and Services)
	u	arc capacity	both
	q	service capacity	both
		Demand parameters
	o k	origin of demand k ∈ D	both
	t k	destination of demand k ∈ D	both
	d k	bandwidth of demand k ∈ D	both
		Variables common to both models (binary)

Table 3 :

 3 Routing and assignment/location solution in the continuous relaxation

	of PR
	other paths. Then:
	x k1 lm ≥
	i∈p

k :i=succ(lm)

Table 7 .

 7 The instances are grouped based on the capacity levels

		Data from SNDLib			Capacity
	Network	|N | |L| |D|	k∈D d k (high cap) medium Service	low	Link low
	abilene	12	15 132	3000002 1750001 500000 829282
	atlanta	15	22 210	136726	77478	18230	19404
	dfn-bwin	10	45	90	548388	329032 109677	55916
	di-yuan	11	42	22	53	31		9	5
	france	25	45 300	99830	53908		7986	9413
	geant	22	36 462	2999992 1636359 272726 359868
	janos-us	26	42 650	80000	43076		6153	7624
	newyork	16	49 240	1774	997		221	66
	nobel-eu	28	41 378	1898	1016		135	214
	nobel-germany 17	26 121	660	368		77	74
	nobel-us	14	21	91	5420	3097		774	486
	norway	27	51 702	5348	2872		396	358
	pdh	11	34	24	4621	2730		840	384
	polska	12	18	66	9943	5800		1657	995
	sun	27	51	67	476	255		35	53
	ta1	24	51 396	10127249 5485593 843937 819678

Table 6 :

 6 Instance details

Table 7 :

 7 Comparison between the continuous relaxations

			Improvement	Computational times (s)
	cap		SP vs. PR		SP		PR
		#	avg	max	avg	max	avg	max
	h h	1	100.00 100.00	0.77	4.13	5.23	46.79
	h l	12 143.00 349.38 136.67 1502.60	83.13 698.42
	m h	2	62.00 100.00	1.35	7.89	7.24	61.48
	m l	12 143.00 349.38 116.32 1240.33	96.27 513.98
	l h	2	109.7 152.66 10.41	52.35	29.42 134.35
	l l	11	131.92 270.54 138.41 1153.76 111.91 875.50

Table 8 :

 8 Adding valid inequalities to continuous relaxation: qualitative behavior

		Bound	Runtime
	Eq.(21)	almost always better	almost always increased
	Eq.(22)	almost always better	almost always decreased
	Eq.(23)	always unchanged	unchanged/increased
	Eq.(24) ()	always unchanged	unchanged/increased
	Eq.(25) (SP)	always unchanged	almost always unch./decr.

Table 9 :

 9 Comparison of the CR bound with respect of the best UB

			Continuous relaxation bound for the SP formulation
			noVI			VI1			VI2			VI1+2
	cap	#	gap		#	gap		#	gap		#	gap
		opt avg	max opt avg	max opt avg	max		avg	max
	h h 16	-	-	16	-	-	16	-	-	16	-	-
	h l	2 35.35 50.00	2 33.21 48.93	2 35.35 50.00 2 33.21 48.93
	m h	1 49.2 50.00	1 10.94 16.67 16	-	-	16	-	-
	m l	0 37.79 50.00	0 20.01 42.79	7 28.9 45.03 7 28.53 42.79
	l h	0 87.57 93.33	0 8.08 16.67 16	-	-	16	-	-
	l l	0 78.96 91.67	0 8.37 16.67 15	-	-	15	-	-
			Continuous relaxation bound for the formulation
			noVI			VI1			VI2			VI1+2
	cap	#	gap		#	gap		#	gap		#	gap
		opt avg	max opt avg	max opt avg	max		avg	max
	h h 15 50.00 50.00 15 50.00 50.00 15 50.00 50.00 15 50.00 50.00
	h l	2 61.82 80.00	2 49.19 60.60	2 61.82 80.00 2 49.19 60.60
	m h	0 50.00 50.00	0 10.72 16.67 16	-	-	16	-	-
	m l	0 60.00 80.00	0 27.71 59.54	7 43.33 60.00 7 42.81 59.54
	l h	0 88.90 93.33	0 8.08 16.67 16	-	-	16	-	-
	l l	0 88.67 93.33	0 8.37 16.67 15	-	-	15	-	-
	Table

Table 10 :

 10 Computational time with and without VIs for SP and formulations

		Computational times for the SP formulation continuous relaxation
	cap	avg	noVI max	avg	VI1	max	avg	VI2	max	avg	VI1+2 max
	h h	0.77	4.13	0.85		4.64	4.35	26.02	7.4	78.91
	h l 136.67	1502.6 137.83		1603.9 73.04 792.81 106.95 1268.05
	m h	1.35	7.89	20.62		130.63	5.03	36.63	7.16	56.01
	m l 116.32 1240.33 140.31		1555.4	64.9 759.71	76.57	805.44
	l h	10.41	52.35	39.13		278.51	3.37	31.44	2.86	19.66
	l l 354.69 3598.88	71.92		597.26	6.55	75.62	7.82	78.92
		Computational times for the formulation continuous relaxation
	cap	avg	noVI max	avg	VI1	max	avg	VI2	max	avg	VI1+2 max
	h h	5.23	46.79	9.96		82.29	8.87	85.5	12.14	131.3
	h l	83.13	698.42 163.46 2002.48	66.01 515.51 30.68	293.53
	m h	7.24	61.48	43		285.57	7.00	51.12	18.11	148.33
	m l	96.27	513.98 143.75		2008.5 33.88 273.42 108.31 1125.63
	l h	29.42	134.35	39.46		297.89	0.79	4.08	1.19	10.46
	l l 111.91	875.5	61.92		483.14	6.54	72.25	5.6	60.22

Table 11 :

 11 .89 2212.81 1812.10 1670.79 m l 1605.13 1396.10 1243.67 1228.73 3388.13 2705.17 2754.96 2942.03 l h 120.04 53.77 7.15 5.16 1474.12 1167.35 1581.80 1588.63 l l 1420.11 1569.64 445.12 369.82 1864.82 1704.02 1665.86 1703.43 Average computational times (in seconds) for the ILP

		Average computational time when optimal integer solution is found
	cap	noVI	VI1	SP	VI2	VI1+2	noVI	VI1	VI2	VI1+2
	h h	2.46	2.54		6.46	6.79	256.85 254.23	442.72	453.55
	h l 586.58 615.06 256.13	533.93	481.80 2386.38 1156.05 383.09
	m h 351.03	63.77		53.10	10.53	481.69	21.14	23.04	6.27
	m l 766.31 408.06		270.33 233.91	219.88	458.82 161.16 1548.00
	l h 120.04	53.77		7.15	5.16	83.08	48.38	13.02	25.30
	l l	429.55 647.06		17.74	10.22	358.12	616.65	73.58	117.17
		Total average computational time considering also timelimit (3600s)
	cap	noVI	VI1	SP	VI2	VI1+2	noVI	VI1	VI2	VI1+2
	h h	2.46	2.54		6.46	6.79 1679.58 1681.81 1919.80 1928.85
	h l 1528.01 1427.23 1026.41 1294.09 2936.61 3198.52 3087.09 3034.33
	m h 351.03	63.77		53.10	10.53 2301

Table 12 :

 12 Comparison of UB and LB found for the different formulations (with and without VIs) with respect to the best known UB and LB

In the following we will use the two terms interchangeably.

In the real application, the demand uses the routing node, but it does not use the server connected to it.

We recall that it is always possible to schedule the services allocated on the same sever in any order, and that in the application problem this order is determined by a suitable scheduling algorithm performed at the server/cloud level

i.e. there is a path between every pair of vertices

Isolated cycles with no service can be part of a feasible solution. Such cycles can be removed obtaining a cycle-free equivalent feasible solution.

Instead accepts solutions with an isolated cycle and a partial service installed on it, but routing variable values (on the cycle) cannot be greater than|N |m+|N | (where m is the length of the cycle) due to the isolated loop elimination constraints[START_REF] Bouet | Cost-based placement of vDPI functions in NFV infrastructures[END_REF].

The larger the fraction of demand k 3 that can pass the cut, the smaller the gap between the two continuous relaxation bounds.

For both formulations several equivalent solutions exist, both for location and routing. For the sake of clarity, we chose to show a "compact" solution for both formulations privileging symmetric, less fractional solutions, with short routings and a reduced number of isolated cycles.

A Extended SP model for multiple services

We now consider to have multiple services and that each demand can ask for a different number of services among the available ones. We need to introduce the following notation:

• F : set of VNFs types

• n k : number of services asked by demand k

indicator parameters, equal to 1 if demand k asks for service of type f Furthermore, if the chain order is given, we need to define:

• f k (s) : 1..n k → F : integer indicator map, type of service at position s for demand k, 0 if the service is not requested Decision variables must be extended accordingly:


domain: math shs

text:
Yannis Liakos
email: ioannis.liakos@uia.no

Mathematical modeling and competencies for biology students

Keywords: Mathematical modeling, mathematical competencies, tasks, progression

The research aims at introducing modeling tasks with an ultimate goal to engage students more actively into learning mathematics through tasks that are biologically 'colored'. My focus is on the individual progression (if any) of students' mathematical competencies during a sequence of modeling sessions as part of their first year mathematics. My goal is to explore the nature of progression within the competency profile of participating student, the relation between modeling processes and this progression and what transformations are applied in these sets of competencies.

Short description of the research topic

The literature provides documentation of learning benefits by engaging students in mathematical modeling: educational benefits [START_REF] Kaiser | Towards a didactical theory for mathematical modeling[END_REF]; students engaged in modeling may develop a deep understanding of the content and an ability to solve novel problems and that it can bring students into alignment with the epistemic aims of science and help them develop more sophisticated ideas within the area of study they are focused on. I adopt a design based research approach in which an iterative process of design, implementation and analysis takes place.

The research questions

RQ_1

) What is the nature of progression in a student's competency profile through the course of the mathematical modeling unit? RQ_2) Considering a set of competencies (competency profile) as a body of knowledge, what transformations are applied in the course of the modeling sessions?

Theoretical and methodological framework

My theoretical approach is informed by the anthropological theory of the didactic [START_REF] Bosch | Introduction to the Anthropological Theory of the Didactic (ATD)[END_REF] and, in particular, by the distinction between four bodies of knowledge: scholarly knowledge; knowledge to be taught; knowledge taught; and knowledge learnt. A significant work on mathematical and modeling competencies has been done by many researchers (e.g. [START_REF] Maaß | What are modelling competencies?[END_REF][START_REF] Blum | Vergleichende empirische Untersuchungen zu mathematischen Anwendungsfähigkeiten von englischen und deutschen Lernenden[END_REF] while [START_REF] Niss | Mathematical competencies and the learning of mathematics: The Danish KOM project[END_REF] created an 8-fold (KOM project) system of mathematical competencies. I decided to proceed to an adaptation of the KOM model adjusted to the above mentioned literature and the specific context I am working on: students of a Biology Department. Part of my analysis will be based a 3-D (radius of action, degree of coverage and technical level) model of progression for each competency from Niss and Højgaard (2011). I have also constructed a coding system in order to "attach" specific students' expressions to a certain mathematical competency. These constructs form a first set of tools for data collection and analysis.

The context and methods for data generation and analysis

The context (or arena) of this study is the Biology Department of a Norwegian university and a mathematics course for first year Biology students. My main study took place with first year Biology students. Modeling sessions occur weekly during the first semester. These sessions (for groups of 3 to 4 students) are 50 minute in length and supplement lectures to the whole cohort of students. Tasks in the sessions are designed in five 2-week blocks focused on a subset of mathematical competencies that students should bring into action in order to complete the task.

To address RQ_1 I will, as above, explore selected students' small group discourse activity. Data were collected through audio-visual recordings of students working on tasks synchronized with their writing (using Smartpens which records audio and visual data accompanying written data). At RQ_2 I am addressing the question: what is the "offered body of competencies" (an a-priori analysis). For the next three steps I will use my data to provide answers or useful directions. A task-design analysis, for example, can provide what the existing literature provides on population dynamics and exponential growth (scholarly knowledge) but also which task was finally decided to be presented (knowledge to be taught) and this will happen for every different modeling block.

Potential significance and contribution

My research will contribute to the following areas (1) dynamic competencies profiles for students, (2) a critique of Niss' (2003) 8-fold system of mathematical competencies, and (3) a description, in the context of mathematical modeling in the Biological Science, of ATD's four bodies of knowledge.

Proceedings of CERME10


text:
Peter Stender

Gabriele Kaiser
email: gabriele.kaiser@uni-hamburg.de

The use of heuristic strategies in modelling activities

Keywords: Mathematical modelling activities, heuristic strategies, modelling example. Thematic Working Group 06

For students working on realistic modelling problems as autonomously as possible the support by a tutor is indispensable. However, how this support can be realised is still not a sufficiently answered question. In the paper we describe a study in which students worked on complex, realistic, authentic modelling problems over three days supported by tutors. The tutors participated in a teacher training prior to the modelling activity. The focus of the study is the usage of heuristic strategies by students within modelling activities and the promotion of strategic help provided by the tutors. Based on videotaping of ten groups while they were working on the modelling problem of the optimal placement of a bus stop, the study could show that heuristic strategies are an indispensable basis for adequate decisions in the modelling process. Their promotion by the tutors seems to be highly adequate in order to foster modelling competencies under a broader perspective.

Introduction

Modelling and applications are receiving increasing attention all over the world, modelling competencies are required internationally by many curricula. However, the complexity of real world examples and the according modelling process to tackle the problem leads to a strong discrepancy between the high relevance of these kinds of activities in curricula and their factual relevance in school. In the following we will present a study, which examines how tutors can foster the tackling of complex and authentic modelling problems by students in special learning environments, the socalled modelling days. We will in particular focus on heuristic strategies from the problem solving discussion and their possible usage in modelling classrooms.

Theoretical framework

Mathematical modelling and modelling cycle

In our research modelling is understood as a process where a 'real situation' from the 'Rest of the World' [START_REF] Pollak | The interaction between mathematics and other school subjects[END_REF] comes up and needs to be understood and simplified and transferred into a realworld model. The real world model is transformed into the world of mathematics, i.e. the formulated mathematical problem is (partly) solved and the solution is validated according to the real world situation. Often the first results do not answer the primary problem adequately, so the modelling cycle is run through again with an adjusted real world model. This process is repeated until a solution is produced which is adequate for the real situation from the standpoint of the modeller. The according process can be visualized with the following modelling cycle (figure 1).

Mathematical model

Mathematical result

Real world model

Real situation

Real world meaning of result

Fostering student's independent modelling activities in cooperative learning environments

If it is intended that students work as independent as possible on the modelling task in cooperative learning environments self-directed learning environments as required by many scholars in the modelling discussion (e.g. [START_REF] Kaiser | Complex modelling problem in cooperative learning environments selfdirected learning environments[END_REF], for an overview see [START_REF] Blum | Modelling and applications in mathematics education[END_REF], the support by a tutor has to be adaptive. We use the definition given by [START_REF] Leiss | Hilf mir es selbst zu tun[END_REF] of an adaptive intervention:

Adaptive teacher interventions are defined as those kinds of assistance by the teacher to the student, which supports the individual learning and problem solving process of students minimally, so that students can continue to work at a maximal independent level. (Leiss, 2007, p. 65, own translation) As guidelines for teachers supporting students who need help in their work, we refer to a framework developed [START_REF] Zech | Grundkurs Mathematikdidaktik[END_REF], who suggests a five step approach to realise adaptivity: (1) motivate, e.g. 'You will make it'; (2) feedback, e.g.: 'Go on like this!'; (3) strategic help based on strategy what to do next, e.g. 'Simplify the situation by making it as symmetric as possible!"; (4) content-related strategic help gives a strategic help with additional information to the problem, e.g. which aspect should be described as symmetric; (5) content-related help shows the students aspects of concrete steps to work on.

If motivational and feedback support are not sufficient to enable the students to continue their work, strategic help is according to this framework the next step to support the students, as the students only get a possible way how to go on, but the students themselves still have to realise the work by their own. Important strategic helps are based on references to the steps of the modelling cycle: 'Simplify the situation!', 'Try to transfer this into a formula!', 'What does the mathematical result mean in the real world?', 'Does the result answers the real world situation meaningfully?' More specific support is offered by the use of heuristic strategies.

Heuristic strategies

The usage of heuristic strategies is a well-known approach in mathematical problem solving (e.g. [START_REF] Pólya | How to solve it. A new aspect of mathematical methods[END_REF], that can be used while tackling modelling problems as well. Based on the work of Pólya and others we distinguish the following heuristic strategies, which were formulated in the frame of ongoing empirical research in mathematical modelling (for details see [START_REF] Stender | Scaffolding in complex modelling situations[END_REF]:

 organise your material / understand the problem: change the representation of the situation if useful, try out systematically, [START_REF] Pólya | How to solve it. A new aspect of mathematical methods[END_REF] use simulations with or without computers, discretize situations,  use the working memory effective: combine complex items to supersigns, which represent the concept of 'chunks' [START_REF] Miller | The magical number seven, plus or minus two: Some limits on our capacity for processing information[END_REF], use symmetry, break down your problem into subproblems),  think big: do not think inside dispensable borders, generalise the situation [START_REF] Pólya | How to solve it. A new aspect of mathematical methods[END_REF],  use what you know: use analogies from other problems, trace back new problems to familiar ones, combine partial solutions to get a global solution, use algorithms where possible [START_REF] Pólya | How to solve it. A new aspect of mathematical methods[END_REF],  functional aspects: analyse special cases or borderline cases [START_REF] Pólya | How to solve it. A new aspect of mathematical methods[END_REF], in order to optimise you have to vary the input quantity,  organise the work: work backwards and forwards, keep your approachchange your approachboth at the right moment [START_REF] Pólya | How to solve it. A new aspect of mathematical methods[END_REF].

Although these heuristic strategies are well-known in the problem solving discussion, there is only little empirical research known, how these heuristic strategies can be implemented in classroom teaching and how far these heuristic strategies can be transferred to other mathematical activities such as mathematical modelling.

Research Question

In our research study we aim to evaluate, how far heuristic strategies developed in the problem solving discussion can be transferred into the teaching and learning of mathematical modelling. Furthermore, we examine how far these heuristic strategies are appropriate strategic interventions for the tutoring of students who are working on complex, realistic and authentic modelling problems.

Design of the Empirical Study Modelling Days as learning environment

As this kind of work is not very common in usual classes we established modelling projects in schools as learning environment, called modelling days and offer these to schools as special, project-oriented activity organised in their school. The problems, on which the students work, are developed by the university research group. The tutoring of the students, who work in groups of four to six, is organised either by the teachers or future teachers within their master studies. Both groups receive a special training, in which they become acquainted with complex modelling examples and how to support students during their modelling activities. During the modelling days students of grade 9 (15 years old at the end of lower secondary level) work on one modelling problem for three full days in school.

The students can choose the problem out of three problems presented by the research group.

In the following we describe one example and describe exemplarily one possible solution.

Modelling problem: The Bus Stop Problema possible solution

We used the bus stop problem in two different versions within various modelling days: the more complex one asks for the best positions of the bus stops for the entire public transport system of the city of Hamburg. The simplified (but still complex) version only asks for the bus stops of one single bus line.

A solution for the more complex version is based on the idea of covering the city with circles of the same diameter in a regular pattern where the centres of the circles are the bus stops. In a second step a rule is developed based on the adjustment of the bus stops to the requirements of the city-map. The diameter of the circles has to be calculated, which leads to the distance of two bus stops by a certain bus line. For this problem there are a lot of possible aspects that can be considered. One possible approach is to reduce the bus line to a straight line, where the bus stops all have the same distance to the next stop.

Figure 2: Bus line

In this solution the following aspects were taken into consideration: the average walking time from and to the bus station (velocity vF), the time the bus drives (velocity vB) over the distance s and the extra time (TH) each stop causes in between. An optimal bus stop distance shall minimize the total travel time T(x).

This leads to the function and setting the derivation as zero yields the following solution These formulae now can be interpreted according to the situation, e.g. in respect of the influence of the distance s or the walking velocity. Students usually will not receive this general result using variables, but with set numbers and they often produce a graph like figure 3. For a more detailed version of this solution see [START_REF] Stender | The Bus Stop Problem[END_REF].

Data collection and data evaluation

Within our study we videotaped ten groups of students who were working in five rooms at higher track school in Hamburg (so-called Gymnasium), overall about 40 students participated in the study. Over three days the students worked around 15 hours on this modelling problem. We transcribed the phases during which the tutor communicated with the students, including a short time before, so that we could identify the causes leading to the contact and a few minutes after the communication so it was possible to analyse the effect of the tutors' intervention. In total 238 contacts between tutors and individual groups were transcribed and coded using qualitative content analysis [START_REF] Mayring | Qualitative content analysis: Theoretical background and procedures[END_REF]. Based on the analysis of the codes for the phases before, during and after the intervention the success of the interventions could be determined. Detailed findings were presented in [START_REF] Stender | Scaffolding in complex modelling situations[END_REF]. Interventions that were not successful or gave too strong content-related help were subject to a more detailed examination. In these cases we tried to formulate alternative strategic interventions for use in further teacher training. The solution processes of the students were reconstructed based on the work of different groups and hereby an idealised modelling process could be reconstructed (for more details see [START_REF] Stender | The Bus Stop Problem[END_REF].

Results of the study

The reconstructed and idealised modelling process is in the first part of the results section used in order to identify, which heuristic strategies students used either intuitively or by referring explicitly to the modelling cycle, to which they had been introduced explicitly using the example of the length of traffic light phases. All students had worked on this example as introduction. The second part of the results section identifies possible interventions by tutors, introducing the students to the usage of heuristic strategies or by using these heuristic strategies by themselves in order to support the students.

Reconstruction of heuristic strategies in the solution process

In the following we analyse this reconstructed idealised solution regarding the use of heuristic strategies, which are highlighted in italic.

The first step of every modelling process is the exploration of the situation, that means as heuristic strategy organise your material / understand the problem. The students explored public transport maps and collected important places like schools or hospitals. It took a longer time to change this point of view to a more abstract representation of the situation, where the bus line is a straight line and special places do not matter. In this situation the more abstract representation is less complex as a lot of details from reality (traffic lights, curves, crossings, hills, …) are missing. So, here a heuristic strategy derived from the modelling cycle is applicable: simplify the situation as much as possible at the beginning! Describing the representation of a bus line as a straight line needs another heuristic strategy, namely to construct the situation symmetrically. Using this strategy leads to the assumption that the distance between two contiguous bus stops should be all the same. Figure 2 shows that even more aspects are symmetrical in this model. The transfer from the complete public transport system to one single bus line, that is used later to reconstruct the whole transport-system, uses as heuristic strategy to break down your problem into sub-problems! This is another way to simplify the situation.

To understand the problem of the simple straight bus line two extreme cases should be analysed, a powerful heuristic strategy: If there are few bus stops, the bus can drive fast without being interrupted by time consuming boarding, but the walk to the next bus stop will be very long for many passengers, which leads to a high total travel time. The other extreme situation has many bus stops, e.g. every 50 m. Now the walking time to the bus stop will be short for all passengers, but the bus will need a long time for a certain distance, because it is stopping every 50 m. So it becomes clear that between these two extremes there is an optimal distance between two bus stops that minimises the total travel time.

For the students the situation was still too complex and they were not able to formulate a functional based approach as they did not have enough experience with these kinds of problems. Now several heuristic strategies were employed: use analogies, break down your problem into sub-problems, try out systematically or work on special cases. As already mentioned all groups had worked on the length of traffic light phases as introductory example, they therefore knew the formulae 2 1 () 2 s t at  and () v t at  and how to calculate acceleration processes. They reduced complexity again by the heuristic strategy simplify in the modelling cycle setting the distance between two bus stops a x = 500 m. This heuristic strategy is related to the heuristic strategy of working backwards as x should be the result of the calculation but is used here as if the result is already achieved. Then the students calculated the driving time between the two bus stops using certain values for the acceleration and the velocity of the bus and using analogies from the traffic light problem as heuristic strategy. This can be described again as using the heuristic strategy of break down into sub-problems as the calculation was not done for the whole bus line, but only for the part between two bus stops. As the choice of x = 500 m was made as ad hoc decision it can be described as heuristic strategy of trying out a special case. The calculation itself that led to a certain driving time includes several steps and is mathematically challenging, but was achieved due to the use of the analogy from the traffic light problem. The result of this approach was the calculation of a certain traveling time that unfortunately was not the answer to the question of the best distance between two bus stops. So, in a second loop through the modelling cycle the students calculated the time for a longer distance of 12 km with a bus stop every 500m combining the partial results from above. Again this shows an interesting result but no answer to the initial question.

The next step was to vary the number of bus stops on the 12 km journey using a heuristic strategy for optimisation you have to vary the input quantity. The travel time was calculated in the same way as before so an analogy was used. The calculation was realised using a spreadsheet and used the heuristic strategy trying out systematically different distances. This approach yields the result that with increasing number of bus stops the traveling time increases proportionally. This was expectable as one of the crucial aspectsthe walk to the bus stopwas not considered up to now.

Based on this insight an average walking time to the bus stop was included in the calculation while the rest of the calculation was analogue to the previous one. This led to a result similar to figure 3, but the students still used as variable the number of bus stops, not the distance between two bus stops.

With the heuristic strategy of a change of representation the students switched to the more meaningful variable, again the new calculation was analogue to the previous one. Still everything was calculated with a spreadsheet so it had the character of a simulation or just trying out special cases. Only few students were able to realise the next change of representation and combined the single steps of the calculation into one formula. They developed one function T(x) that included several steps of the calculation in one single mathematical term and T(x) works as a supersign, which is another, less discussed heuristic strategy. This approach opened the way to use the derivate and calculate a solution like it is shown above. This was done with concrete numbers instead of parameters (vF, vB, TH, s, r) by one group of students, but in another group there were students able to use parameters instead of concrete numbers, which again means the use of supersigns as each character stands for an infinite amount of numbers.

The results from different traveling distances s were compared and it became clear as meaningful result that on shorter trips the bus stops may be closer together. This result was validated, a heuristic strategy from the modelling cycle, by analysing the map of the public transport in Hamburg. Near the city, where people often use the bus only for the short distance to the next metro station, the bus stops were much closer than in the outer parts of Hamburg. The calculated distances matched very well to the distances in the map.

The subsequent step was to go back to the public transport network and cover the city with circles of a certain diameter. Now the results from the single bus line were used, which uses the heuristic strategy to combine partial solutions to get a global solution in order to choose meaningful diameters. These diameters were not the same over the whole city according to the previous results and in opposition to the initial idea.

To summarise, the analyses of the modelling activities by the students showed an intensive usage of heuristic strategies, partly referring to the various phases of the modelling cycle and partly as intuitive usage.

Heuristic strategies as strategic interventions

The heuristic strategies that were used quite often intuitively by the students in the modelling process can be transferred into strategic interventions by tutors, if the students are not able to continue their work on their own. In the following examples for these activities are described, which were shortly included in the teacher training beforehand and which were used by the tutors, but not as intensively as wished, probably due to their low importance in teacher training.

In each situation, where an analogue acting to previous work occurs, the following hints are possible: "This work is analogue to something you have done bevor!" or "Calculate this in the same way you did in the traffic light problem".

While constructing the real model the simplification of the situation is essential. "In your first approach build the real model as simple as possiblefor this, it's a good idea to describe the model as symmetric as possible!"

The idea to break down the problem into sub-problems can be initiated by "For this problem you have to work on several stepstry to solve only one simple part at the beginning and then try to use these result for the next steps!"

The idea of using special cases can be implemented as follows: "If you have no idea how to go on, select specific numbers and work with them! Just work on special cases in the beginning!" As shown above this strategic intervention is a powerful mean for modelling activities.

The heuristic strategy For optimisation you have to vary the input quantity can be helpful for students who are not familiar with functional thinking. The following hints can be given: "You calculated with 23 bus stops. What happens if you use more or less bus stops?" "Vary the number of bus stops!" "If you look for an optimal solution you have to make sure that a nearby situation is less good!"

To summarise, these examples show how a heuristic strategy can be used to create a strategic intervention. Depending on the work of the students, more or less information on the concrete modelling problem can be included in the intervention in order to give a less abstract input to the students if necessary.

Summary and conclusions

The empirical study displays a great variety of heuristic strategies used by the students within their modelling activities, a few were developed intuitively, a few derived from the description of the modelling cycle introduced beforehand.

An important result of the study is that strategic interventions often were successful when a tutor supported students working on complex modelling problems, because the usage of these heuristic strategies is not self-evident. Because the usage of adequate strategic interventions by tutors is very hard, it often only will be possible if prepared beforehand. In order to react on the students in class in an adaptive way the tutor needs a deep insight into the modelling process, the modelling problem, possible solutions as well as heuristic strategies and strategic interventions.

  Figure 1: Modelling cycle (Kaiser & Stender, 2013, p. 279)

Figure 3 :

 3 Figure 3: T(x): Travel time depending on the bus stop distance

Proceedings of CERME10