Royal Society Publishing

Robust bi-level optimization models in transportation science

Michael Patriksson


Mathematical programmes with equilibrium constraints (MPECs) constitute important modelling tools for network flow problems, as they place ‘what-if’ analyses in a proper mathematical framework. We consider a class of stochastic MPEC traffic models that explicitly incorporate possible uncertainties in travel costs and demands. In stochastic programming terminology, we consider ‘here-and-now’ models where decisions must be made before observing the uncertain parameter values and the responses of the network users; the objective is to minimize the expectation of the upper-level objective function. Such a model could, for example, be used to derive a fixed toll pricing scheme that provides the best revenue for a given network over a time period, where variations in traffic conditions and demand elasticities are described by distributions of parameters in the travel time and demand functions.

We present new results on the stability of globally optimal solutions to perturbations in the probability distribution, establishing the robustness of the model. We also discuss penalization and discretization algorithms, the latter enabling the use of standard MPEC algorithms, and provide many future research avenues.


1. Introduction and motivation

(a) Motivation

When addressing network design and pricing problems under user equilibrium, or any kind of traffic assignment model for that matter, in the form of a hierarchical (i.e. bi-level) optimization model (or mathematical programming problem with equilibrium constraints), it is almost always understood that data are certain or that uncertain data can be given some deterministic representation, such as a mean value. It is at the same time understood by all who develop or use traffic equilibrium or assignment models that this assumption is simplistic. Replacing a deterministic traffic equilibrium model by a stochastic one does not really solve the problem, because it also produces unique equilibrium solutions in general; hence the mapping from data to solution is not stochastic even in such models.

Since uncertainty in data is prevalent in traffic assignment models, and because bi-level models provide such an attractive modelling approach, there is a need for a bi-level model that can take into account the uncertainty in data. One possibility is to use a classic ‘multi-load’ approach, taken from the engineering sciences, in which several representative scenarios are included through an averaging in the upper-level objective function.

Inspiration for this work stems from work on structural optimization, the science of producing structures that carry loads optimally. Variations in, for example, loading conditions are often taken into account such that the effectiveness of a design is defined as the average value (or even the worst) of the effectiveness of several ‘load cases’. Owing to the anticipated fact that the ‘real’ probability model is never known, and the reported high sensitivity of solutions to stochastic structural optimization problems with respect to small changes in the probability measure, many probability-free worst-case (‘pessimistic’) models of uncertainty have been developed as alternatives to probabilistic ones (see further below).

This paper seeks to extend the scope of bi-level traffic models to take into account data variations in the form of a stochastic bi-level model, or a stochastic mathematical programme with equilibrium constraints (SMPEC). In order to do so, we must consider complications that do not arise in standard bi-level traffic models: SMPEC models are infinite-dimensional, so even the existence of optimal solutions is non-trivial to establish. The main focus of our study of the SMPEC traffic model of this paper is, however, one that, to some degree, can be used to validate the use of mathematical programme with equilibrium constraints (MPEC) models in network design applications and in particular multi-load approaches and discretizations: we wish to establish conditions under which optimal designs change continuously with the probability distribution. We say that such solutions are stable, and the model therefore is ‘robust’ in some sense. Establishing the robustness of the stochastic bi-level model to be developed in this paper is also an alternative to the approach taken in some papers, where robust models are produced through reformulation.

(b) Stochastic programming and robust optimization

The problem of data uncertainty has been recognized as important for quite some time in the operations research community. The most well-known technique for dealing with uncertainty is stochastic programming (e.g. Birge & Louveaux 1997). Typically, one wants to minimize the expected cost of decisions that must be made without the complete knowledge of data. In ‘here-and-now’ models decisions are made once, but in certain types of applications decisions can be made at one or several future recourse stages. The here-and-now decision then represents the first-stage decision which is made to properly hedge against future outcomes of the uncertain data. In these problems one assumes that the distribution of uncertainty is known, or, at least, can be well approximated.

The term ‘robust optimization’ (RO) has been and is used in a variety of contexts. An important aspect in most applications is the assumption that the distribution of data is known to be confined to certain (typically bounded) ‘uncertainty sets’. For particular problems, such as linear and convex quadratic programming, and particular uncertainty sets, RO offers computationally tractable (i.e. polynomially solvable) robust versions. Because feasibility is required for every realization of the data, the robust counterparts include a semi-infinite system of constraints (whence tractability is only possible to obtain in the above instances). Importantly, it is at the same time a worst-case type of modelling approach.

Through the above modelling technique one imposes robustness on a model. Our main interest is to investigate the robustness of SMPEC models, in the hope that a reformulation is not necessary. As we shall see, in some circumstances it is possible to establish the robustness of an SMPEC model.

(c) Stochastic mathematical programmes with equilibrium constraints

An MPEC is an optimization problem with two variable types: primary ones, or ‘design’ variables, and secondary variables, or ‘responses’. The responses are evaluated as part of the constraints of the problem, often in the form of a secondary optimization problem (then often referred to as the ‘lower-level problem’). The overall objective is optimized according to a criterion in terms of both design and response. In order to represent this framework in mathematical notation, suppose the design is represented by a vector Embedded Image and the response by a vector Embedded Image. If the objective is to minimize the function Embedded Image and the response can be described by the point-to-set mapping, Embedded Image, then we can describe the MPEC problem as that toEmbedded Imagewhere Embedded Image is the set of admissible designs and responses.

If the mapping Embedded Image describes the solution of a variational inequality (VI), parametrized by x, then the inclusion Embedded Image holds if and only ifEmbedded Image(1.1)where Embedded Image is the feasible set of the VI, Embedded Image is the VI cost mapping, and Embedded Image is the normal cone mapping associated with the set Y(x), all parametrized by x. We assume throughout that the set Y(x) is closed and convex, whence its normal cone is the standard one in convex analysis: for Embedded Image, Embedded Image, and for yY(x), Embedded Image. If Embedded Image for some C1 function Embedded Image, then (1.1) is the first-order optimality conditions for the parametrized optimization problem to Embedded Image. For general overviews of MPEC and VI models and their analysis, see Luo et al. (1996) and Facchinei & Pang (2003), respectively.

The existence of optimal solutions to the problem (MPEC) follows under standard assumptions that hark back to a version of the Weierstrass theorem: if the set of feasible solutions to (MPEC) is non-empty and closed, and the objective function is lower semi-continuous and weakly coercive (this combination of properties is called ‘inf-compact’), then there exists a closed and bounded set of optimal solutions (see Zhang 1994). In particular, closedness of the feasible set follows in general from a closedness assumption on the mapping S and of the set Z. In the examples to follow, generally stronger properties still will hold.

We focus here on traffic and communication networks, whence x is the vector of design parameters, while the mapping S describes the solution to a traffic equilibrium (or assignment) type model having y as the corresponding equilibrium traffic flows and (dis)utilities. The set Z could represent constraints on the available investments (or tolls, etc.), which then are independent on the response y (e.g. Marcotte 1986; Patriksson & Rockafellar 2002); it could also represent maximum allowed travel times, exhaust emissions, or constraints defined by equity measures in a multi-class model (e.g. Eliasson & Mattsson 2006; Stewart 2007), or equilibrium travel times (e.g. Sumalee et al. 2006), which are examples of joint upper-level constraints.

The subject of rate control in computer communication networks is also related to congestion control in traffic networks, although the intrinsic existence of link flow capacity constraints in the former enforces the need to rephrase the Wardrop principle (cf. Larsson & Patriksson 1994). Ralph (2008) establishes the equivalence of rate flow equilibria for a model of the transmission rate protocol (TCP; see Kelly et al. 1998) to a mixed complementarity problem; various design and control problems of the MPEC type are then discussed. Such robust models that determine good transmission rates in the light of uncertainties in, for example, link capacities, in the form of SMPECs are very natural extensions to study in the future.

We will briefly discuss in the following certain applications to structural (topology) optimization, wherein x refers to design variables describing an amount of material (thicknesses or volumes), while y refers to an equilibrium state (stresses and displacements); the equilibrium, described by the mapping S, corresponds to an energy minimization problem, parametrized by x. The set Z represents possible constraints on available material and/or on the (maximum) stresses. For an overview of structural (topology) optimization, see Bendsøe & Sigmund (2003).

The focus is on the analysis of a stochastic extension of the MPEC problem. It is known in the literature as stochastic MPEC, or SMPEC, a term coined in the paper by Patriksson & Wynter (1999). We suppose that (Ω, Θ, P) is a complete probability space. When considering the space Embedded Image we equip it always with the sigma algebra given by the product of the Borel sigma algebra of Embedded Image and Θ.

The SMPEC problem then is that toEmbedded Imagewhere Embedded Image is a random element of the probability space (Ω, Θ, P), Embedded Image is a point-to-set mapping representing the upper-level constraints, and Embedded Image defines the set of solutions to the lower-level parametric variational inequality problem,Embedded Image(1.2)The above lower-level problem is defined by a mapping Embedded Image and a feasible set mapping Embedded Image having closed convex images with Embedded Image denoting the normal cone mapping to the set Y(x, ω).

Patriksson & Wynter (1999) discuss toll setting problems under user equilibrium, as well as a pricing problem in a spatial-price equilibrium setting, where in both cases demand is stochastic. Evgrafov et al. (2002, 2003) analyse the continuously distributed case of topology optimization models. The paper by Evgrafov & Patriksson (2004) provides the first existence analysis for the general SMPEC model as well as an inexact penalty method, while Evgrafov & Patriksson (2003a,b) investigated stability issues in the context of topology optimization; the latter two references established that, in general, the optimal design cannot be expected to vary continuously with the probability measure, but that continuity indeed could be established in some special circumstances for convex problems. In this paper, we shall provide a corresponding analysis in the context of optimal design in networks, and reach stronger results in that they do not impose convexity on the model. Other applications of special cases of SMPEC include Stackelberg–Nash–Cournot equilibrium problems, in which case the lower-level problem is a nonlinear complementarity problem; the special SMPEC model is then referred to as stochastic programme with complementarity constraints (SMPCC).

Section 2 provides a basic existence result for the problem (SMPECΩ), taken from Evgrafov & Patriksson (2004, theorem 2.1). Section 3 then introduces our traffic SMPEC model. Section 4 establishes the main result of this paper: that in the absence of joint upper-level constraints the optimal designs are continuous in the probability distribution; hence, we can conclude that globally optimal design solutions are stable, and the SMPEC traffic model is robust. Section 5 establishes the convergence of solution approaches to the SMPEC problem at hand. The first is a classic inexact exterior penalty method in which either the lower-level problem or any joint upper-level constraints are penalized. The second is a natural approach for the continuously distributed problem (SMPECΩ): we consider a discretization approach known as the sample average approximation. A final section discusses some interesting future research topics.

2. Existence of optimal solutions

Let X denote the projection of the feasible set of the problem (SMPECΩ) onto the space of x variables: Embedded Image, and let Embedded Image. Let us also denote by Embedded Image the x-slice of the feasible set of (SMPECΩ), Embedded Image. The existence result is based on the measurability in ω for fixed x of this mapping. (A closed valued mapping Embedded Image is said to be measurable if Embedded Image for every closed set Embedded Image.) We shall assume throughout that Embedded Image and Y(x, ω) are measurable in ω for any Embedded Image; note that this continuity type of assumption is not very restrictive. According to Evgrafov & Patriksson (2004, lemma 2.1), if in addition F is continuous in y and measurable in ω (which is referred to as the ‘Carathéodory property’) for any x, and Y has closed convex images for any x and almost any ω, then the mapping S is measurable in ω for any x.

The following result, quoted from Evgrafov & Patriksson (2004, theorem 2.1), establishes the existence of optimal solutions to the problem (SMPECΩ). This theorem, in turn, generalizes existence results for (MPEC) in a natural manner.

Suppose that the mappings Zx(.) and S(x, .) are measurable for any x; the set Z(ω) and the mapping Embedded Image are closed for almost any ω∈Ω and any x; the function f is continuous in (x, y), measurable in ω, uniformly weakly coercive with respect to x over the set X,1 and bounded from below by a (Θ, P)-integrable function; for any x∈X, there is a neighbourhood Embedded Image such that the set Embedded Image is bounded for almost any ω∈Ω; and the set Embedded Image is non-empty for some x0∈X and almost any ω∈Ω. Then, the problem (SMPECΩ) has at least one optimal solution.

Clearly, the case of joint upper-level constraints is a complicating factor, and later discussions on robustness results and computations are discussed in a framework where Z is independent of y. A corollary to the above theorem illustrates how the analysis then simplifies.

Suppose that the upper-level feasible set Z is independent of y; it then can be written as Embedded Image. Then, the assumptions of the theorem can be replaced by the following: the mapping Embedded Image is measurable for any x; the set X is closed, and the mapping Embedded Image is closed for almost any ω∈Ω; the function f is continuous in (x, y), measurable in ω, uniformly weakly coercive with respect to x over the set X, and bounded from below by a (Θ, P)-integrable function; and the set S(x0, ω) is non-empty for some x0∈X and almost any ω∈Ω.

In this latter case where the upper-level constraints are defined only in terms of x, we can provide a simple interpretation of the problem (SMPECΩ). First, we recall that we select the response y for which we obtain the minimum value of the upper-level objective; we can then write the problem (SMPECΩ) as the problem toEmbedded Image(2.1)where the optimization is performed over all xX and all measurable selections y(ω)∈S(x, ω). Equivalently, we may write the problem as that to Embedded Image, where Embedded Image. Notice that if for a given xX the set S(x, ω) is empty with a positive probability, we define Embedded Image; implicitly, therefore, the optimization over x is performed such that the set S(x, ω) is non-empty for almost any ω∈Ω.

A comparison is finally made with the case of a finite support of Ω. Suppose that Ω={ω1, …, ωk} is finite with probabilities p1, …, pk. Then we may write the problem (2.1) as the problem toEmbedded Image

In the field of structural topology optimization, this is a classic modelling approach. If, for example, the external load is stochastic, then (SMPECK) represents a ‘multi-load case’ model where K load scenarios are incorporated into the same design optimization model, together with their probabilities, resulting in a minimum average design ‘cost’. We will return to this type of model later on when considering discretization approaches to the problem (SMPECΩ).

3. A representative SMPEC traffic model

(a) Traffic equilibrium

Let Embedded Image be a transportation network, where Embedded Image and Embedded Image are the sets of nodes and directed links, respectively. For certain ordered pairs of nodes, Embedded Image, where node p is an origin, node q is a destination, and Embedded Image is a subset of Embedded Image, there is a transport demand, which may be given by a function of the travel cost. We assume that the network is strongly connected, so that at least one route joins each origin–destination (OD) pair. Wardrop's user equilibrium principle states that for every OD pair Embedded Image, the travel costs of the routes used are equal and minimal for each individual user. We denote by Embedded Image the set of simple (loop-free) routes for OD pair (p, q), by hr the flow on route Embedded Image, and by cr the travel cost on the route as experienced by an individual user.

We introduce the design parameter Embedded Image. This parameter could be present in one or both of the travel cost and demand functions. We assume that the (continuous) travel cost function has the form Embedded Image given a value of x, where Embedded Image denotes the total number of routes in the network, and Embedded Image. Further, the demand function is given by Embedded Image. Regarding the latter function, we shall assume that either g is independent of the travel cost (hence a case of a fixed demand model) or is such that Embedded Image is (at least) strictly monotone for each x; in the latter case we can then use the standard VI formulation based on the inverse of Embedded Image.

We introduce the route–OD pair incidence matrix Embedded Image (i.e. the element Embedded Image is 1 if route r joins OD pair Embedded Image, and 0 otherwise). Then, demand-feasibility is described by the conditions that Embedded Image andEmbedded Image(3.1)holds, while the Wardrop equilibrium conditions for the route flows are thatEmbedded Image(3.2a)Embedded Image(3.2b)holds, where the value of Embedded Image is the minimal (i.e. equilibrium) route cost in OD pair Embedded Image. By the non-negativity of the route flows, the system (3.1), (3.2a) and (3.2b) can more compactly be written as the mixed complementarity problem (MCP)Embedded Image(3.3a)Embedded Image(3.3b)where Embedded Image, for two arbitrary vectors Embedded Image, means that Embedded Image. (By non-negativity, this implies that Embedded Image for all j.)

In general, we shall need to assume that the route cost is additive. For each link Embedded Image, the travel cost has the form Embedded Image, where Embedded Image is the vector of link flows. The route and link travel costs and flows are related through a route–link incidence matrix, Embedded Image, whose element Embedded Image equals one if route Embedded Image uses link Embedded Image, and zero otherwise. Route r has an additive route cost Embedded Image if Embedded Image. In short, then, Embedded Image. Also, implicit in this relationship is the assumption that the pair Embedded Image is consistent, in the sense that v equals the sum of the route flows: Embedded Image. In general, we shall assume that t is (at least) strictly monotone in v for any x. Notice, however, that it is in each of the results to follow possible for the function t to be only monotone for some values of v for any x, as long as it is strictly monotone around the equilibrium solution for any x; thus, so called ‘flat spots’ of the travel cost are allowed, again as long as these are not situated near an equilibrium.

A more familiar representation of the parametrized Wardrop conditions (3.3a) and (3.3b) is that of a variational inequality,Embedded Image(3.4)where Embedded Image, Embedded Image is a closed and convex set, Embedded Image is smooth, and where the normal cone mapping is as defined in §1. LettingEmbedded Image(3.5a)Embedded Image(3.5b)andEmbedded Image(3.5c)we obtain an equivalent VI formulation from (3.3a) and (3.3b), where F is parametrized by x. Solutions exist to the problem (3.4), (3.5a)–(3.5c) whenever Embedded Image is continuous and Embedded Image is non-negative and upper bounded by some non-negative vector (e.g. Marcotte & Patriksson 2007, theorem 4).

We remarked above that the demand function is assumed to be of either of two different forms. In the case when the corresponding variational inequality models define first-order optimality conditions for an optimization problem, the two corresponding optimization formulations illustrate an important feature of the lower-level traffic equilibrium problem that we use heavily: its constraints do not depend on the design vector x; hence the equilibrium problem always exhibits feasible solutions, and according to the properties of the cost and demand functions assumed, equilibria will therefore also always exist.

In order to produce a hierarchical traffic model, we introduce finally a continuous function Embedded Image, and a possible set of jointly feasible designs and responses, Embedded Image. The corresponding MPEC model then is toEmbedded Image

The existence of solutions to the problem (HTM) follows under standard arguments, as it is an instance of (MPEC). The mapping S is closed as soon as t and g are continuous, which we have assumed. We further assume that the set Z and the function f are so defined that there exist feasible solutions, and that f is inf-compact there. The most natural assumptions under which this is guaranteed to hold is that f is continuous, Embedded Image and Embedded Image are strictly monotone, and the set Z is independent of y and compact; indeed, in most applications it is simply a box in x corresponding to investment bounds.

(b) An SMPEC traffic model

We introduce a stochastic extension of this model. Consider the problem toEmbedded Imagewhere Embedded Image is a random element of a complete probability space Embedded Image, Embedded Image is a point-to-set mapping representing the upper-level constraints, and Embedded Image now defines the set of solutions to a lower-level parametric variational inequality problem of the formEmbedded Image(3.6)whereEmbedded Image(3.7)

In this model we take into account uncertainties in the modelling of the travel costs and/or demands when evaluating the upper-level objective function for a given value of the parameters in x; we take them into account by minimizing the expectation of these objective values over the uncertainty set.

Owing to the fact that we study stochastic network models, we rule out from consideration such classic cases as ‘first-best’ toll pricing, where a desired link flow is fixed and the only variables are the tolls to be set, typically on every link, in order to reproduce this flow as a traffic equilibrium one; see Marcotte & Patriksson (2007) for a select bibliography on link toll pricing, especially for obtaining system (or, social) optimal flows. Our model, in the context of link tolls, therefore belongs to the ‘second-best’ school, as discussed, for example, by Yang et al. (2005).

We restate theorem 2.1 in the context of this problem.

Suppose that the following assumptions are fulfilled: the mappings Embedded Image, Embedded Image and Embedded Image are measurable for any x; the set Embedded Image is closed for almost any Embedded Image; the function f is continuous in (x, y), measurable in ω, uniformly weakly coercive with respect to x over the set X, and bounded from below by a Embedded Image-integrable function; for any Embedded Image, there is a neighbourhood Embedded Image such that the set Embedded Image is bounded for almost any ω; and the set Embedded Image is non-empty for some Embedded Image and almost any ω. Then, the problem (SHTMΩ) has at least one optimal solution.

The absence of joint upper-level constraints makes life easier.

Suppose that the upper-level feasible set Z is independent of y, and hence can be written as Embedded Image. Then, the above assumptions can be replaced by the following: the mappings Embedded Image and Embedded Image are measurable for any x; the set X is closed; and the function f is continuous in Embedded Image, measurable in ω, uniformly weakly coercive with respect to x over the set X, and bounded from below by a Embedded Image-integrable function.

4. Solution stability

The question of the continuity of optimal solutions to (SMPECΩ) with respect to changes in the probability distribution is important. From the computational point of view, a positive answer to this question would allow us to solve the problem by approximating the underlying probability measure with a sequence of discrete probability measures, and hence approximating the original infinite-dimensional optimization problem with a sequence of finite-dimensional optimization problems. From the theoretical point of view, we would conclude the robustness of the resulting optimal solutions with respect to errors in the modelling of uncertainty.

As discussed in §1, the structural optimization community often uses probability-free worst-case (pessimistic) models of uncertainty as alternatives to probabilistic models. These approaches do yield stable structures, but do not take into account the probability of occurrence of the different scenarios, thereby often resulting in unnecessarily costly designs. There are example problems where the optimal solutions do not change continuously even if the probability distribution measure changes only locally (i.e. only the density of the probability measure changes; cf. Evgrafov et al. 2003). There are example models where no joint upper-level constraints are present, and whose optimal solutions are robust (Evgrafov et al. 2003), and there are also examples where a possible reformulation (i.e. relaxation) of a non-robust problem yields a robust model (Evgrafov & Patriksson 2003b).

Certain convex problems in stochastic programming have been proven robust (e.g. Römisch 2003), in some cases with quantitative stability measures. Since stochastic programming is an instance of (SMPECΩ) (e.g. Patriksson & Wynter 1999; Shapiro 2006), the latter clearly contains robust models. As remarked in Evgrafov & Patriksson (2004), however, no generic conditions on Z and S under which one can expect a continuous behaviour of the optimal solutions to non-convex models within the framework of (SMPECΩ) (or at least the continuous behaviour of the optimal values of the upper-level variables x) yet exist.

The main result in this section is that globally optimal solutions to (SHTMΩ) are stable under natural conditions when there are no joint upper-level constraints. Owing to space limitations, proofs of theorems will however be published elsewhere.

Consider a sequence {Pk} of probability measures defined on Embedded Image, together with the associated sequence of optimization problemsEmbedded ImageWe assume that each measure Pk has a density Embedded Image with respect to a Lebesgue measure on Ω and that the sequence Embedded Image converges to a density p(.) of P Lebesgue almost everywhere. The existence of densities is not a very restrictive assumption from the theoretical point of view.

In addition to the conditions of theorem 3.1 suppose that the mapping Embedded Image is strictly monotone for each Embedded Image and Embedded Image and that g is either a constant mapping in Embedded Image or Embedded Image is strictly monotone for each Embedded Image and Embedded Image. Suppose that the sequence Embedded Image of probability measures weakly converges to P and that Embedded Image solves Embedded Image for each k. Then, each limit point (and there is at least one) of the sequence Embedded Image is an optimal solution to Embedded Image.

5. Solution approaches

(a) Inexact penalization

Compared with one-level problems, bi-level optimization algorithms are much less straightforward to develop owing to the non-convex nature of the problem and the absence of constraint qualifications for nonlinear programming (Luo et al. 1996). One approach is to move the equilibrium constraint as a penalty into the objective function. For examples of penalty functions leading to algorithmic constructions to MPEC, see Luo et al. (1996) and Ralph (2008). In particular, exact penalties are of great importance, since they lead to exact solutions while they do not require the penalty parameter to tend to infinity. However, one cannot expect to be able to construct an exact penalty for SMPEC problems, given an exact penalty for each ω, as an example in Evgrafov & Patriksson (2004) illustrates. Again, the reason is the presence of the coupling upper-level constraints.

Evgrafov & Patriksson (2004, theorem 4.1) establish the convergence of an inexact penalization method wherein the lower-level equilibrium problem is penalized. This result can be immediately transferred to the current situation. However, we have argued that joint upper-level constraints imply complications and may therefore alternatively conclude that they in fact should be penalized, in order to turn the problem into a more ‘standard’ SMPEC model. (This has indeed been used; see Evgrafov & Patriksson 2003a.) Providing a general theory of such an approach is a quite interesting avenue for future research. For now, we present a result within the transportation domain. In what follows, the notation Embedded Image refers to the optimal objective value of the problem W.

Suppose the conditions of theorem 4.1 are satisfied. Let also the function Embedded Image be non-negative, continuous in (x, y) for almost any ω, measurable in ω for any Embedded Image, and such that Embedded Image. Then, the penalized problemEmbedded Imagehas an optimal solution for any Embedded Image andEmbedded ImageFurthermore, any limit point of the sequence of optimal solutions Embedded Image to Embedded Image (and there is at least one) is an upper-level optimal solution to (SHTMΩ).

(b) Discretization approaches

A popular method for solving a stochastic programming problem involving a non-discrete probability measure is to approximate it with a sequence of finite-dimensional problems with discrete measures. For SMPEC models, such techniques are known as the sample path method, sample average approximation, stochastic counterpart method and the simulated likelihood method (e.g. Robinson 1996; Gürkan et al. 1999; Shapiro & Xu 2005; Shapiro 2006; and references therein). Using K random samples of the random vector ω, a problem of the form (SMPEC), with Embedded Image for every k, is solved, for increased values of K.

Shapiro & Xu (2005) study the convergence of this method for (SMPCC)Ω under conditions that are fulfilled if Embedded Image is unique and continuous for almost any ω, X is non-empty and compact, and the function Embedded Image is bounded over X almost surely. Under additional conditions on S and f such that the expected value function is differentiable, it is also established that stationary points to discretizations converge to the set of stationary points to (SMPCC)Ω. Owing to the smoothing effect of the averaging operation, it is remarked that differentiability of the expected value function may hold in many more cases than for the non-deterministic problem (MPCC). We expect the same to hold for (SHTM)Ω. The stronger conditions imposed in the work of Gürkan et al. (1999), in particular, imply that the lower-level problem has strongly regular solutions (Robinson 1980), but on the other hand, the results quite immediately extend to inexact solutions of the approximate problems (SHTM)K.

In Birbil et al. (2006) the above sample path method was applied to a special case of (SMPCC)Ω modelling a toll pricing problem under fixed demand traffic equilibrium. Suppose that tolls are to be set during the beginning of a fairly long time period, during which time the tolls cannot be altered. The parameters of the BPR formula are considered stochastic in order to represent varying road conditions during this time period, and the model (SMPCC)Ω then represents a means to derive the best link tolls ‘on average’. A test case using the Sioux Falls network is reported; in this example the exact solution can be computed beforehand, making it possible to establish, in this particular case, convergence to an optimal solution.

The main interest in the above techniques is of course that SMPEC models can be solved through a sequence of MPEC models, for which relatively efficient algorithms exist (e.g. Fletcher et al. 2006; Ralph 2008; and references therein). Shapiro (2006) establishes that convergence in some cases is exponential, which implies that relatively few samples may be needed to reach at least a near-optimal (or, near-stationary) solution; numerical experiments in Shapiro & Xu (2005) and Birbil et al. (2006) confirm this belief at least in small-scale examples. Therefore, there is a hope that SMPEC traffic models can be approximately solved with a computational effort that is not several orders of magnitude larger than, for one instance, that of a discretized problem. In particular, a rough design solution that is at least a lot better than any individual MPEC solution can probably be achieved through the solution of one single problem of the form (SHTM)k or (SHTM)N, provided of course that the samples are well chosen. The analysis performed in this paper, in fact—to at least some degree—validates such a simple approach, through the combined results of theorem 4.1 and the convergence of discretization methods.

6. Final remarks and future research directions

While this work concerns a deterministic traffic equilibrium model, the above development can be performed in the context also of stochastic traffic equilibrium models. Indeed, the properties needed are not connected to the route–choice principles per se, but rather to the properties of the equilibrium solutions: that the lower-level optimal link flow and demand are closed, in some cases continuous, as a function of x and ω, which is a property present also for, say, the logit- and probit-based stochastic models. For a recent account of research on link tolling under stochastic user equilibrium (SUE), see Stewart (2007). As far as this author is aware, the present paper is the first that (essentially) covers an analysis of a stochastic MPEC model where the lower level model is a SUE model.

As has been mentioned already in §1c, congestion control in communication networks is a very important topic; its relationships to traffic MPEC models were also alluded to. Several parameters in the definition of the problem through whose solutions one determines the transmission rates are likely to be subject to random fluctuations and are also difficult to measure exactly, in particular the capacity of the links (in terms of flow rates). Therefore, it seems natural to study stochastic models of transmission control, which then would have the form of SMPEC problems.

A natural future research task is to investigate the possible convergence of inexact solutions to the subproblems in the algorithms investigated in this paper to (in)exact solutions to the original one. In this context, it is interesting to note a result of Gürkan et al. (1999), stating that the maximum number of samples (K) required to reach a given accuracy of the final solution, while also solving each subproblem inexactly, grows linearly with the number n of design parameters. Another interesting question is whether convergence is achieved for the natural combination of penalization and discretization, as previously applied and established in structural topology optimization by Evgrafov & Patriksson (2003a).

A related issue regards the stability of optimal solutions to SMPEC traffic models with joint upper-level constraints. We have described the unlikelihood of the existence of such a result for SMPEC traffic models in general, but we have also related to work that shows that certain relaxations of joint upper-level constraints may in fact induce robustness. Their form is naturally highly dependent on the type of constraints considered. In topology optimization such relaxation algorithms are now quite well known and established; see Guo et al. (2001) and Evgrafov & Patriksson (2003b) for work on the ‘stress singularity phenomenon’ and specially designed relaxation methods for stress constraints. In relation to the negative result in Evgrafov & Patriksson (2003b) that one cannot expect convergence of a scheme in which Embedded Image converges to P and the relaxation parameter tends to zero simultaneously, one must observe that in that application the objective function of the lower-level variational inequality is not everywhere finite; the situation in the SMPEC traffic context should be more favourable.

A possible relaxation of the constraint that Embedded Image holds is given by, for some Embedded Image, Embedded Image. This is the ‘probabilistic’ or ‘chance constraint’ of stochastic programming (e.g. Prékopa 2003) and the ‘reliability constraint’ from structural optimization. Whether interesting stability properties can be derived from an SMPEC model equipped with this relaxed joint upper-level constraint is an interesting future research question.

An interesting research issue related to the above is whether stability results extending that for globally optimal solutions can be verified also for locally optimal designs, and/or solutions to a suitably stated necessary condition for a local optimum. The latter conditions are interesting in their own right, as KKT-type optimality conditions for general SMPEC problems are not well developed yet.

Applications to toll pricing and design problems in traffic networks have been mentioned previously. SMPEC models can of course also be used to similarly model and analyse networks of other commodities. One example is optical data communication networks where, for example, revenue maximization models (known as stochastic traffic engineering) involving bandwidth provisioning in the face of stochastic elastic bandwidth demands are discussed by Mitra & Wang (2005). The analysis and numerical solution of this and other problems in communication networks within the framework of SMPEC make a fruitful research avenue.

Finally, it would be interesting to investigate whether, in the context of network design and/or pricing, the analysis of this paper may offer contributions to the study of reliability of traffic flows (e.g. Bell 2000; Clark & Watling 2005).


The work leading to this paper was performed in association with the Gothenburg Mathematical Modelling Centre (GMMC) at Mathematical Sciences (Chalmers University of Technology and Gothenburg University), whose main sponsor is the Swedish Foundation for Strategic Research (SSF). Five anonymous referees helped to improve the presentation.


  • One contribution of 16 to a Discussion Meeting Issue ‘Networks: modelling and control’.

  • That is, that the set Embedded Image is bounded for every Embedded Image.


View Abstract