Josette Ayoub
email: josetteayoub@hotmail.com

Michael Poss
email: michael.poss@lirmm.fr

Decomposition for adjustable robust linear optimization subject to uncertainty polytope

Keywords: Adjustable robust optimization, Uncertainty polytope, Benders decomposition, Mixed-integer linear programming, Network design

We present in this paper a general decomposition framework to solve exactly adjustable robust linear optimization problems subject to polytope uncertainty. Our approach is based on replacing the polytope by the set of its extreme points and generating the extreme points on the fly within row generation or column-and-row generation algorithms. The novelty of our approach lies in formulating the separation problem as a feasibility problem instead of a max-min problem as done in recent works. Applying the Farkas lemma, we can reformulate the separation problem as a bilinear program, which is then linearized to obtained a mixed-integer linear programming formulation. We compare the two algorithms on a robust telecommunications network design under demand uncertainty and budgeted uncertainty polytope. Our results show that the relative performance of the algorithms depend on whether the budget is integer or fractional.

Introduction

Robust Optimization is now a well-developed paradigm to tackle optimization problems under uncertainty. The framework has experienced its revival in the late nineties independently by [START_REF] Ben-Tal | Robust convex optimization[END_REF]; El Ghaoui et al (1998); [START_REF] Kouvelis | Robust Discrete Optimization and its Application[END_REF], and has witnessed an increasing attention in the past twenty years. Its essence lies in the use of convex sets to model uncertainty that can arise when solving optimization problems. In the robust counterpart of an optimization problem, the constraints involving uncertain parameters must be feasible for all values of the uncertain parameters in the convex sets. In particular, the optimization variables are fixed independently of the values taken by the uncertain parameters; it is not possible to adjust them after the uncertainty is known. When the problem constraints are linear, this approach leads to tractable optimization problems. For instance, the robust counterparts of linear constraints subject to polyhedral uncertainty are still linear constraints.

The framework can fail to model design problems that involve actions that are delayed in time, such as network design problems or facility location problems, among many others. In each of these optimization problem, we must take part of the decisions today, e.g. implantation of new links or building facilities. Then, when the new links or facilities are operational, we must choose how to use them optimally to provide a service to the customers. In these problems, the demand of the customers is usually not known with precision until the links or the facilities are constructed.

Adjustable robust optimization has been introduced by Ben-Tal et al ( 2004) to improve over static robust optimization by allowing a subset of variables to account for the uncertainty. Namely, the framework partitions the optimization variables into two sets: part of them must fix their values before the uncertainty is revealed while the rest of them can adjust themselves according to the values taken by the uncertain parameters. These variables become functions defined on the uncertainty set. [START_REF] Ben-Tal | Adjustable robust solutions of uncertain linear programs[END_REF] prove that adjustable robust optimization is untractable in general, so that they focus on approximations that restrict the adjustable variables to affine functions of the uncertainty, yielding the so-called affine decision rules. The main advantage of affine decision rules is their tractability, since they lead to robust optimization problems with the structure of classical robust counterparts. The properties of affine decision rules have been studied in subsequent papers: Bertsimas et al (2011b) and [START_REF] Iancu | Supermodularity and affine policies in dynamic robust optimization[END_REF] study conditions in which affine decision rules are optimal, while [START_REF] Bertsimas | On the power and limitations of affine policies in two-stage adaptive optimization[END_REF] study the suboptimality of affine decision rules from a worst-case perspective. Authors have also studied more complex decision rules that offer more flexibility than affine decision rules while providing tractable optimization problems. Among others, [START_REF] Chen | A linear decision-based approximation approach to stochastic programming[END_REF] introduce deflected linear and segregated linear decision rules, [START_REF] Chen | Uncertain linear programs: Extended affinely adjustable robust counterparts[END_REF] propose to define affine decision rules on extended descriptions of the uncertainty set, [START_REF] Goh | Distributionally robust optimization and its tractable approximations[END_REF] introduce complex piece-wise linear decision rules defined through liftings and projections, and Bertsimas and Georghiou (2015) propose piece-wise affine decision rules having fixed number of affine pieces. Alternatively, [START_REF] Bertsimas | Finite adaptability in multistage linear optimization[END_REF] dynamically partition the uncertainty set and use constant decision rules in each set of the partition. The performance guarantee of the latter scheme is studied theoretically by Bertsimas et al (2011a). This idea has been revived recently by [START_REF] Bertsimas | Design of near optimal decision rules in multistage adaptive mixed-integer optimization[END_REF] and [START_REF] Postek | Multi-stage adjustable robust mixed-integer optimization via iterative splitting of the uncertainty set[END_REF] who extend it to multi-stage linear mixed-integer linear programs and test it numerically on different problems.

To assess numerically the quality of the aforementioned approximations, one needs to compute the (exact) optimal solutions, at least on small instances. Hence, in contrast with approximations approaches, some authors have tried to solve exactly the adjustable problems. Indeed, when the robust constraints are linear and the uncertainty set is a polytope, we know that the latter can be replaced by the finite set of its extreme points. This reformulation as such is not very useful because the number of extreme points is usually prohibitive. However, recent works have proposed decomposition algorithms that generate the extreme points on the fly. The first work in that line of research was carried out by [START_REF] Bienstock | Computing robust basestock levels[END_REF] who propose cutting plane algorithms (denoted RG in the following) for computing optimal base-stock levels in a supply chain. Similar approaches have been used subsequently by [START_REF] Mattia | The robust network loading problem with dynamic routing[END_REF] who study a network design problem with integer link capacities under demand uncertainty, by [START_REF] Gabrel | Robust location transportation problems under uncertain demands[END_REF] who study a facility location problem under demand uncertainty, and by [START_REF] Bertsimas | Adaptive robust optimization for the security constrained unit commitment problem[END_REF] who study a unit commitment problem under nodal injection uncertainty. In these four papers, the uncertainty is limited to the right-hand side of the constraints and problem specific algorithms are proposed. [START_REF] Zeng | Solving two-stage robust optimization problems by a constraint-and-column generation method[END_REF] improved over the previous papers by proposing a row-and-column generation algorithm (denoted RCG in the following) and comparing the latter numerically to RG. Their results show that RCG can be up to three order of magnitudes faster than RG. The idea behind RCG has also been combined with RG heuristically by [START_REF] Bertsimas | Adaptive robust optimization for the security constrained unit commitment problem[END_REF]. More general problems (based on algorithm RG) have also been considered by [START_REF] Billionnet | 2-stage robust MILP with continuous recourse variables[END_REF].

This papers contributes to this line of research, proposing an alternative approach to solve exactly two-stage robust linear programs with continuous second stage variables. We implement cutting plane algorithms and row-andcolumn generation algorithms very close to those proposed by [START_REF] Zeng | Solving two-stage robust optimization problems by a constraint-and-column generation method[END_REF], with the difference that we consider the separation problem as a feasibility problem instead of a min-max problem as done by [START_REF] Zeng | Solving two-stage robust optimization problems by a constraint-and-column generation method[END_REF]. Using the Farkas' lemma, we can reformulate the feasibility problem into a bilinear program. Whenever the uncertainty set can be obtained as an affine projection of a 0 -1 polytope, which is the case for the budgeted uncertainty polytope from [START_REF] Bertsimas | The price of robustness[END_REF], the bilinear program can be linearized to obtain a mixed-integer linear program. We assess our algorithms on a difficult telecommunication network design problem that has previously been studied in the literature by [START_REF] Poss | Affine recourse for the robust network design problem: between static and dynamic routing[END_REF], comparing our results with the affine decision rules.

Problem overview

We consider in this paper the following type of two-stage robust optimization problems:

min c • x (1) s.t. x ∈ S (P ) T (ξ)x + W y(ξ) ≥ h, ξ ∈ Ξ (2)
where u • v denotes the scalar product between any pair of vectors u and v,

c ∈ R |I| , W ∈ R |M |×|J| , h ∈ R |M | , S ⊂ R |I| denotes the first-stage feasibility polyhedron, Ξ ⊂ R |K| denotes the uncertainty polytope, T (ξ) ∈ R |M |×|I|
denotes the realization of the uncertain first-stage coefficient matrix, and y(ξ) denotes the second-stage decision vector. We follow a classical assumption from the robust optimization literature and suppose that T depends affinely on uncertain parameter ξ. Hence, there exists matrices T 0 and T 1k with the same dimensions as T such that

T (ξ) := T 0 + k T 1k ξ k .
One readily sees that (P ) encompasses more general problems where (i) h depends affinely on ξ and (ii) second stage variables y have fixed costs given by vector k. Similarly, the approaches presented in this paper can be applied (with minor modifications) to problems where set S is the intersection of Z |I1| × R |I2| and a polyhedron. When Ξ is not a singleton, problem (P ) is a linear program that contains an infinite number of variables, since y is defined for each ξ ∈ Ξ, as well as an infinite number of constraints (2). The ideas presented in this paper rely on considering only the extreme points of Ξ, which is formalized in the result below (whose proof can be found in [START_REF] Ben-Tal | Robust optimization methodology and applications[END_REF], among others).

Lemma 1 Let vert(Ξ) be the set of extreme points of Ξ and x ∈ R |I| a given vector. Vector x can be extended to an optimal solution (x, y) to (P ) if and only if it can be extended to an optimal solution (x, y ) to

min c • x s.t.
x ∈ S (P )

T (ξ)x + W y (ξ) ≥ h ξ ∈ vert(Ξ). (3)
We provide next an example showing that Lemma 1 may not hold if the recourse matrix W depends on the uncertainty parameters ξ, which implies that our approach cannot handle problems with random recourse. Consider a unique robust constraint defined by

W (ξ) = -1 + 2ξ, T (ξ) = -2 + 3ξ, h = 0,
and Ξ = [0, 1], and consider x * = 1. The constraint becomes:

ξ = 0 ⇒ 2 -y(0) ≥ 0 (4) ξ = 0.5 ⇒ -0.5 ≥ 0 (5) ξ = 1 ⇒ 1 + y(1) ≥ 0. (6)
Constraints ( 4) and ( 6) are feasible while constraint ( 5) is infeasible. Hence, x * is feasible for the constraints induced by each ξ ∈ vert([0, 1]) but infeasible for ξ = 0.5, providing a counter-example to Lemma 1 when W is an affine function of ξ.

Let K denote the projection of the set defined by (3) on variables x. Set K is a polyhedron. Hence, if a vector x does not belong to K, there exists a separating hyperplane between x and K. We study in the following section how to find such a hyperplane and how to use it to solve (P ).

Solution approach

We propose in this section an algorithmic framework to solve (P ) by generating scenarios in vert(Ξ) on the fly. First, we provide in Section 3.1 a mathematical program for the following separation problem: does x belong to K? Then, assuming that the separation problem can be solved adequately, we describe in Section 3.2 two algorithms for addressing (P ).

Separation

A naive approach to the separation problem would enumerate all elements of vert(Ξ). This is not suitable for practical problems since Ξ is likely to have a very large number of extreme points. We propose instead to address the problem by solving a mathematical program. The next result is based on Farka's lemma.

Theorem 1 Let x * ∈ R n be given. Vector x * belongs to K if and only if the optimal solution of the following optimization problem is non-positive

max (h -T (ξ)x * ) • π (7) (SP ) s.t. ξ ∈ Ξ W T π = 0 1 • π = 1 π ≥ 0.
Before proving the Theorem, we introduce without proof a well-known property of bilinear optimization.

Lemma 2 Let P be a polytope, Q a closed and bounded set, and f (p, q) a bilinear function. It holds that {max f (p, q) s.t. p ∈ P, q ∈ Q} = {max f (p, q) s.t. p ∈ vert(P), q ∈ Q}.

Proof (Proof of Theorem 1) Consider a given vector x * ∈ R n . Because x * is fixed, constraints (3) become separable for each ξ ∈ vert(Ξ). Hence, for each ξ ∈ vert(Ξ), vector y(ξ) must satisfy to

W y(ξ) ≥ h -T (ξ)x * . ( 8
)
Let π(ξ) be the dual multipliers associated to constraints (8). Using Farkas' Lemma, we know that constraints (8) have a solution if and only if

(h -T (ξ)x * ) • π(ξ) ≤ 0
for all π(ξ) that satisfy

W T π(ξ) = 0 (9) π(ξ) ≥ 0. ( 10
)
Notice that the coefficients of constraints ( 9) and ( 10) do not depend on ξ.

Hence, considering Farkas' conditions for all ξ ∈ vert(Ξ) simultaneously, we obtain that constraints (8) for each ξ ∈ vert(Ξ) are consistent if and only if the optimal solution of max

(h -T (ξ)x * ) • π (11) s.t. ξ ∈ vert(Ξ) (12) W T π = 0 π ≥ 0 is non-positive. Adding normalization constraint 1 • π = 1
to the problem above does not impact the sign of the optimal solution of the above optimization problem. Finally, we can replace (12) by ξ ∈ Ξ because objective ( 11) is bilinear in ξ and π and the constraints of ξ and π are independent from each other, so that Lemma 2 holds.

The objective function of (SP ) is bilinear so that (SP ) belongs to a class of problems NP-hard to solve exactly [START_REF] Matsui | Np-hardness of linear multiplicative programming and related problems[END_REF]. Unreported results show that algorithms based on spatial branching [START_REF] Ryoo | Global optimization of multiplicative programs[END_REF] are unable to cope with (SP ) even for small instances. Hence, we propose to address (SP ) through mixed-integer linear reformulations, see Section 4.

Algorithms

We propose in this section two solution algorithms for (P ), denoted by RG and RCG, assuming that we can solve (SP ) through a black-box method. The algorithms are both based on generating dynamically a subset Ξ ⊂ vert(Ξ). Both algorithms start by solving the following master problem min c • x

(M P ) s.t. x ∈ S.
Given an optimal solution to (M P ), the algorithms solve the separation problem (SP ), yielding an optimal solution (ξ * , π * ). The two algorithms differ then by the way they include more information to (M P ) when the solution cost of (SP ) is positive. Algorithm RG is a classical Benders' decomposition approach that adds a violated Benders' cut to the master problem

(h -T (ξ * )x) • π * ≤ 0. ( 13
)
The drawback of RG is that a single cut is added to the master problem at each iteration, facing the risk that many iterations may be required before obtaining a feasible solution for (P ). To incorporate more information to the master problem at each iteration, Algorithm RCG adds to (M P ) all constraints and variables associated to

ξ * T (ξ * )x + W y(ξ * ) ≥ h. (14)
For completeness, both algorithms are described formally in Algorithm 1.

Algorithm 1: RG and RCG repeat solve (M P ); let x * be an optimal solution; solve (SP ); let (ξ * , π * ) be an optimal solution and z * be the optimal solution cost; if z * > 0 then RG: add constraint ( 13) to (M P ); RCG: add constraint ( 14) to (M P );

until z * > 0;
4 Mixed-integer programming reformulations

In this section, we propose two mixed-integer linear reformulations for (SP ).

Recall that a polytope Ω is called a 0 -1 polytope if each of its extreme points is a binary vector. Our first mixed-integer linear formulation for (SP ) is based on reformulating Ξ as the affine mapping of a 0 -

1 polytope Ω ⊂ R |K | of (a) Ξ (0, 1) (1, 0) (b) Ω = a(Ξ)
Fig. 1 Example of affine mapping such that Ω = a(Ξ) and Ω is a 0 -1 polytope.

reasonable dimension |K |. Notice that such a mapping always exists since we can represent Ξ as the set of all convex combinations of the vectors in vert(Ξ). This example is useless, however, because the associated polytope Ω would be the unit simplex of dimension | vert(Ξ)|. A more useful example of pair of polytopes Ξ and Ω is given in Figure 1.

Theorem 2 Let x * ∈ R |I| be given and suppose that we know a 0 -1 polytope Ω ⊂ R |K | and an affine mapping a(ω) = Aω + b such that Ξ = a(Ω). Vector x * belongs to K if and only if the optimal solution of the following optimization problem is non-positive

max (h -T 0 x * ) • π - k∈K ( T 1k x * ) • v k (SP L) s.t. ω ∈ Ω W T π = 0 1 • π = 1 v k m ≥ π m -(1 -ω k ) k ∈ K , m ∈ M (15) v k m ≤ ω k k ∈ K , m ∈ M (16) π, v k m ≥ 0, ω ∈ {0, 1} |K | where T 1k = h∈K T 1h A hk for each k ∈ K and T 0 = T 0 + k∈K T 1k h∈K A kh b k .
Proof The proof consists of two steps. First, we take (SP ) and make the change of variable ξ = a(ω):

max (h -T (ω)x * ) • π (17) s.t. ω ∈ Ω (18) W T π = 0 1 • π = 1 π ≥ 0.
Then, using Lemma 2, we replace constraint (18) by ω ∈ vert(Ω). Because Ω is a 0 -1 polytope, we can add binary restrictions ω ∈ {0, 1} |K | to the problem. Hence, each product ω k π m involved in objective function ( 17) can be reformulated by introducing auxiliary variables v k m and using big-M coefficients. Finally, the big-M coefficients can be set to 1, because 0 ≤ π m ≤ 1, which yields constraints ( 15) and ( 16).

An interesting example of non-bijective affine mapping arises with the budgeted uncertainty set introduced in [START_REF] Bertsimas | The price of robustness[END_REF]:

Ξ Γ ≡ ξ ∈ [0, 1] |K| s.t. k∈K ξ k ≤ Γ .
Polytope Ξ Γ is a 0 -1 polytope only when Γ is integer. Nevertheless, Ξ Γ for fractional values of Γ can be obtained as the affine transformation of the following polytope

Ω Γ ≡ (ω 1 , ω 2 ) ∈ [0, 1] 2|K| s.t. ω 1k + ω 2k ≤ 1, k ∈ K, k∈K ω 1k ≤ Γ , k∈K ω 2k ≤ 1 , using mapping a(ω) = ω 1 + (Γ -Γ )ω 2 . One readily sees that Ω Γ is a 0 -1 polytope.
A different approach has been used by [START_REF] Mattia | The robust network loading problem with dynamic routing[END_REF] for a specific network design problem. The result below generalizes the one of [START_REF] Mattia | The robust network loading problem with dynamic routing[END_REF] in two aspects: we do not assume that S has a specific form, and we allow the firststage constraint matrix to depend on the uncertainties (while [START_REF] Mattia | The robust network loading problem with dynamic routing[END_REF] only considers right-hand-side uncertainty).

Theorem 3 Let x * ∈ R n be given and let Ξ = {ξ ∈ R |K| s.t. Bξ ≤ b, ξ ≥ 0}. Vector x * belongs to K if and only if the optimal solution of the following optimization problem is non-positive

max (h 0 -T 0 x * ) • π + b • γ s.t. W T π = 0 1 • π = 1 π ≥ 0 B T γ ≥ k∈K u k (T 1k x * ) Bξ ≤ b γ ≥ 0 ξ ≥ 0 -B T γ -M µ ≥ -M 1 - k∈K u k (T 1k x * ) ξ -M µ ≤ 0 γ + M ν ≤ M 1 -Bξ -M ν ≤ -b µ ∈ {0, 1} n , ν ∈ {0, 1} m Proof Introducing notations τ 0 (x * ) := h 0 -T 0 x * and τ 1k (π, x * ) := (T 1k x * ) • π for each k ∈ K, (h -T (ξ)x * ) can be rewritten as τ 0 (x * ) • π + τ 1 (π, x * ) • ξ, (19)
where only the second term of ( 19) depends on ξ. Hence, for any polyhedron Π, we have that max π∈Π,ξ∈Ξ

τ 0 (x * ) • π + τ 1 (π, x * ) • ξ = max π∈Π τ 0 (x * ) • π + max ξ∈Ξ τ 1 (π, x * ) • ξ
so that we can rewrite (SP ) as a bilevel program sending ξ to the follower's decisions:

max τ 0 (x * ) • π + τ 1 (π, x * ) • ξ (20) s.t. W T π = 0 1 • π = 1 π ≥ 0 ξ ∈ argmax τ 1 (π, x * ) • ξ ξ ∈ Ξ
Recall that Ξ is described by {ξ : Bξ ≤ b, ξ ≥ 0}. Because Ξ is bounded and non-empty, we know by linear programming duality that

{max τ 1 (π, x * ) • ξ : Bξ ≤ b, ξ ≥ 0} = {min b • γ : B T γ ≥ τ 1 (π, x * ), γ ≥ 0}.
Then, replacing the follower's problem by its dual and substituting the bilinear term τ 1 (π, x * ) • ξ in the objective function ( 20) with the objective function of the dual, b • γ, we obtain:

max τ 0 (x * ) • π + b • γ s.t. W T π = 0 1 • π = 1 π ≥ 0 γ ∈ argmax -b • γ (21) B T γ ≥ τ 1 (π, x * ) γ ≥ 0.
The result finally follows from applying the mixed-integer reformulation from (Audet et al, 1997, Corollary 3.2) to the bilevel problem above.

Notice that in spite of its generality, the reformulation from Theorem 3 can be very hard to solve to optimality [START_REF] Mattia | Private communication[END_REF]. Hence, it should be combined with heuristic separation of violated extreme points as done by [START_REF] Mattia | The robust network loading problem with dynamic routing[END_REF] for a network loading problem.

Application to telecommunications network design

We illustrate in this section the performance of Algorithm 1 on an adjustable robust optimization problem previously studied in the literature.

Problem description

Telecommunications networks have evolved quickly, especially in the last two decades. This is due to the expansion of the Internet, on-line gaming, instant messaging, file sharing and plenty of other applications requiring fast and reliable communication technologies. This has resulted in increasing demands for higher bit-rates. Network operators are then under constant pressure to design high speed networks with larger capacities such as to satisfy the growing need for fast connections with no interruptions and latency. However, network operators also tend to design networks while minimizing capital costs and taking into account that resources are limited. Given a directed graph (V, A) and a set of point-to-point commodities K, network design can be defined as a planning process that involves setting up link capacities x a for each a ∈ A and traffic routing y k a for each a ∈ A and k ∈ K in order to route data packets for each commodity k ∈ K from its source s k to its destination t k . Its goal is to minimize the total capacity cost a∈A c a x a while satisfying all traffic demands d k for k ∈ K.

Traditional models for network design ignored demand uncertainty and overestimated demand values to avoid blockages. This led to a waste in network capacities and investments. In order to obtain a more robust and efficient network, demand fluctuation has to be taken into consideration throughout the design procedure. As a result, the idea of demand uncertainty must be included in the mathematical program that models the planning process of the network.

Robust network design considers that the vector of demands d is uncertain and depends affinely on the uncertain parameters ξ that can take any value in a predetermined uncertainty polytope. The problem becomes an adjustable robust optimization problem: capacities x are first-stage decision variables while routings y are second-stage decision variables. Let δ + v and δ - v be the sets of outgoing arcs and incoming arcs, respectively, for each v ∈ V . The mathematical program for the problem is given below.

min a∈A c a x a (22) (RN D) s.t. a∈δ - v y k a (ξ) - a∈δ + v y k a (ξ) =    -d k (ξ) if v = s k d k (ξ) if v = t k 0 otherwise v ∈ V, k ∈ K (23) k∈K y k a (ξ) ≤ x a a ∈ A (24)
x ≥ 0, y ≥ 0.

Objective function ( 22) minimizes the total capacity installation cost subject to flow balance constraints ( 23) and capacity constraints (24). The above optimization problem has been studied previously by [START_REF] Poss | Affine recourse for the robust network design problem: between static and dynamic routing[END_REF]. [START_REF] Poss | Affine recourse for the robust network design problem: between static and dynamic routing[END_REF] solves (RN D) by enumerating the extreme points of Ξ using Lemma 1. This approach is of course restricted to uncertainty polytopes having limited number of extreme points and they address larger problems by applying affine decision rules to routing variables y:

y k (ξ) = f 0k + h∈K f hk ξ h , k ∈ K. ( 25
)
Other approximations of (RN D) have been considered in the literature, see [START_REF] Poss | A comparison of routing sets for robust network design[END_REF] and the references therein. Among them, static routing which enforces y k to depend linearly on ξ k by adding constraints

y k (ξ) = f k ξ k , k ∈ K (26)
to (RN D), where f are non-negative optimization variables. It must be said that (RN D) with static or affine routing is much easier to solve than (RN D) because the problem can then be reformulated as a static robust optimization problem, which can be solved by dualizing the robust constraints.

In the next section, we apply the two versions of Algorithm 1 to the instances studied by [START_REF] Poss | Affine recourse for the robust network design problem: between static and dynamic routing[END_REF].

Numerical results

We consider three realistic networks from SNDlib [START_REF] Orlowski | SNDlib 1.0-Survivable Network Design Library[END_REF] : janosus, sun, and giul-39. These networks have 26/27/39 nodes and 84/102/172 arcs, respectively. The networks are originally undirected and we direct them by replacing each edge by two arcs with opposite directions. To reduce the size of the formulations and to be able to do a series of runs, we considered the largest 20-50 commodities with respect to the mean value of d k . Our uncertainty set is based on the budgeted uncertainty polytope from [START_REF] Bertsimas | The price of robustness[END_REF]. Namely, d k (ξ) = d k + ξ k dk where the deviation dk is set to 0.4d k , and

Ξ ≡ {ξ ∈ R |K| s.t. k∈K ξ k ≤ Γ, 0 ≤ ξ k ≤ 1 for each k ∈ K}.
Polytope Ξ is a 0 -1 polytope so that we can reformulate the subproblem as (SP L) from Theorem 2. Notice that our uncertainty set does not consider downward deviations. Hence, Ξ corresponds to D σ + used in [START_REF] Poss | Affine recourse for the robust network design problem: between static and dynamic routing[END_REF]. We consider two sets of instances. In the first set, Γ is integer and belongs to {1, 2, . . . , 6}. In the second set, Γ is fractional and belongs to {1.5, 2.5, . . . , 5.5}. Our algorithms have been coded using the Concert Technology library for JAVA from CPLEX 12.6 (IBM-ILOG, 2015) on a 64-bit 2.53Ghz Quad-Core CPU with 6GB of memory and 16 threads. CPLEX is called with its default parameters and we have set a time limit of T seconds of CPU time for every individual run and our computing times are presented in seconds. of the profiles should be considered as approximations of the true relative performance of the algorithms. Despite this, one can observe from the profiles that RG and RCG behave differently on the two sets of instances. Namely, when Γ is integer, RCG clearly outperforms RG, and the performance of RCG is close to the one of affine routing. In contrast, when Γ is fractional, RCG is outperformed by RG and both algorithms behave much worse than affine routing. This behavior can be explained by the following observations. First, the solution times of (SP L) is usually higher when Γ is fracional (see below). Second, algorithm RCG generates much more extreme points when Γ is fractional. Hence, the time spent solving (M P ) increases, making it an important part of the total solution time. In contrast, the time spent solving (M P ) is insignificant for RG, which concentrates all of its effort on solving (SP L). We present the extensive computational results on Tables 1 and2. The columns of these tables report the number of commodities (K), the value of Γ , the optimal solution cost for static routing (opt stat ), the cost reduction (gap af f ) when using affine routing constraints (25) instead of static routing constraints (26), the cost reduction (gap dyn ) for the true optimal solution of (RN D), the time required by RCG (t RCG ) and RG (t RG ), the number of iterations of both algorithms (iter), and the time that they spent solving (SP L) as a percentage of the total solution time (t SP L (%)). We also report the solution times spent to solve the problem with affine routing (t af f ) and to solve the problem that contains all extreme points (t P ), although this last model very often consumes all memory available. Time and memory hits are denoted by T and M, respectively. Table 1 confirms the results summarized in Figure 2(a); that is, RCG is more efficient than RG on instances with integer values of Γ , solving the instances faster than the latter. In contrast Table 2 shows that RCG can solve only two instances with fractional values of Γ , while RG can solve roughly half of them. The tables also show that both algorithms spend most of their time in the solution of (SP L) apart from RCG for the instances with high numbers of iterations. Figure 3 reports the arithmetic averages of the solution times for solving (SP L) for each instance, which are based on the separations problems that were solved to optimality. Figure 3(a) and Figure 3(b) show that for the instances janos-us and sun, the solution times of (SP L) is much higher for fractional values of Γ than for the integer ones. In contrast, Figure 3(b) shows the opposite behavior for sun, particularly when K = 50.

Conclusion

We propose in this paper decomposition algorithms to solve adjustable robust linear programs under polytope uncertainty by generating the extreme points of the uncertainty polytope on the fly. We discuss algorithmic frameworks for decomposing the robust problem and solution algorithms to address the subproblem. Our numerical results show that the relative efficiency of row generation and row-and-column generation algorithms depends on the type of polytope considered. In any case, the bottleneck of these algorithms lies in finding the extreme point of the polytope that is mostly violated by the current solution, which amounts to solve a mixed-integer linear program (MIP).

Aknowledgements

We would like to thank Sara Mattia for fruitful discussions on the topic of this paper. We also thank the editors and the referees for useful remarks and suggestions that helped in improving the presentation and the content of the paper.

  (a) Integer values of Γ . (b) Fractional values of Γ .

Fig. 2

 2 Fig. 2 Performance profiles comparing the solution times of RG, RCG, and af f .

Figure 2

 2 Figure2shows performance profiles[START_REF] Dolan | Benchmarking optimization software with performance profiles[END_REF] that compare the solution times of algorithms RG and RCG as well as affine routing (denoted af f ). Figure2(a) reports the profile for Γ ∈ {1, 2, . . . , 6} while Figure 2(b) reports the profile for Γ ∈ {1.5, 2.5, . . . , 5.5}. Notice that the solution times of unsolved instances have been set to T seconds, so that the right part

Fig. 3

 3 Fig. 3 Average solution times in seconds for (SP L) for each value of K ∈ {20, . . . , 50}. Integer and fractional values of Γ are reported in gray and black, respectively.

Table 1

 1 Results for Γ integer.

	instance	K	Γ	optstat	gap dyn (%) gap af f (%)	t RCG	t SP L (%) iter	t RG	t SP L (%) iter	t P	t af f
		20 1.0	4,65E5	7.2	7.2	9	81	10	29	100	73	2	84
		20 2.0	5,12E5	6.5	6.2	36	70	18	61	100	67	7	78
		20 3.0	5,12E5	2.5	0.9	33	67	18	76	100	84	55	68
		20 4.0	5,12E5	0.0	0.0	40	63	20	57	100	70	293	47
		20 5.0	5,12E5	0.0	0.0	21	80	13	34	100	55	M	44
		20 6.0	5,12E5	0.0	0.0	22	71	15	37	100	59	M	37
		30 1.0	6,12E5	7.5	7.5	30	89	12	77	100	85	7	345
		30 2.0	6,72E5	8.7	8.4	85	82	19	170	100	86	22	490
		30 3.0	6,99E5	7.0	6.6	137	85	21	235	100	82	307	401
		30 4.0	6,99E5	2.9	2.4	245	81	27	474	100	92	M	371
		30 5.0	6,99E5	0.7	0.0	276	83	27	587	100	87	M	290
	janos-us	30 6.0 40 1.0	6,99E5 6,72E5	0.0 8.2	0.0 8.2	139 52	83 80	22 14	335 130	100 100	84 90	M 34	252 567
		40 2.0	7,32E5	8.8	8.4	205	76	22	376	100	91	63	988
		40 3.0	7,63E5	7.6	6.7	432	82	25	747	100	88	M	1490
		40 4.0	7,66E5	4.1	2.9	977	80	32	2231	100	98	M	1865
		40 5.0	7,66E5	1.5	0.2	1300	80	35	2186	100	100	M	2427
		40 6.0	7,66E5	0.0	0.0	1036	77	34	1372	100	89	M	1213
		50 1.0	7,32E5	8.4	8.4	90	81	15	251	100	95	103	2511
		50 2.0	7,93E5	8.9	8.5	464	76	25	794	100	98	122	4494
		50 3.0	8,27E5	8.2	7.3	1836	91	28	2776	100	101	M	5454
		50 4.0	8,39E5	6.0	4.9	4188	93	33	10093	100	104	M	4419
		50 5.0	8,41E5	3.2	2.2	4079	88	39	T	100	96	M	3529
		50 6.0	8,41E5	0.8	0.1	6309	78	50	T	100	99	M	4866
		20 1.0	4,31E2	9.9	9.9	22	88	12	215	100	152	1	50
		20 2.0	4,67E2	9.2	8.9	90	81	23	429	100	160	8	58
		20 3.0	4,82E2	6.4	5.5	207	84	29	586	100	149	74	63
		20 4.0	4,87E2	3.5	2.0	230	85	29	730	100	161	439	82
		20 5.0	4,88E2	1.8	0.7	326	82	34	826	100	156	M	36
		20 6.0	4,88E2	1.0	0.2	234	85	29	595	100	145	M	34
		30 1.0	5,56E2	9.3	9.3	55	93	13	766	100	200	5	224
		30 2.0	6,03E2	10.5	10.1	347	83	31	1413	100	190	22	248
		30 3.0	6,3E2	9.6	8.8	1790	90	43	4009	100	174	319	293
		30 4.0	6,4E2	6.9	5.7	4921	98	36	T	100	161	M	282
		30 5.0	6,47E2	5.2	3.2	T	98	41	T	100	137	M	259
	sun	30 6.0 40 1.0	6,49E2 6,69E2	4.2 8.6	1.9 8.6	T 119	100 97	24 12	T 1908	100 100	104 227	M 12	311 867
		40 2.0	7,23E2	10.7	10.3	770	93	30	4313	100	209	54	840
		40 3.0	7,58E2	10.9	10.2	10038	98	42	T	100	138	1126 1028
		40 4.0	7,78E2	10.3	8.9	T	100	18	T	100	89	M	975
		40 5.0	7,91E2	11.6	7.2	T	100	9	T	100	78	M	1152
		40 6.0	7,96E2	11.4	5.5	T	100	8	T	100	62	M	1421
		50 1.0	7,34E2	8.0	8.0	139	98	11	2437	100	207	22	3059
		50 2.0	7,92E2	10.4	10.1	1498	97	27	9056	100	199	108	3539
		50 3.0	8,3E2	11.1	10.4	T	100	22	T	100	100	M	3347
		50 4.0	8,53E2	12.7	9.6	T	100	9	T	100	64	M	3828
		50 5.0	8,7E2	13.1	8.6	T	100	7	T	100	50	M	3487
		50 6.0	8,81E2	14.9	7.4	T	100	5	T	100	44	M	2927
		20 1.0	8,97E1	4.8	4.8	33	93	9	166	100	85	3	56
		20 2.0	9,93E1	6.2	6.2	62	95	10	383	100	93	13	64
		20 3.0	1,04E2	5.1	4.5	177	94	15	696	100	92	94	59
		20 4.0	1,07E2	3.1	2.3	338	95	18	973	100	102	735	83
		20 5.0	1,09E2	1.3	0.3	401	95	19	985	100	99	M	78
		20 6.0	1,09E2	0.8	0.0	571	95	21	731	100	96	M	46
		30 1.0	1,42E2	6.1	6.1	111	96	9	837	100	131	19	416
		30 2.0	1,52E2	7.4	7.4	366	95	14	2655	100	144	58	501
		30 3.0	1,61E2	7.9	7.7	2588	99	18	T	100	117	927	446
		30 4.0	1,68E2	7.3	7.2	10718	100	18	T	100	83	M	405
		30 5.0	1,72E2	6.0	5.1	T	100	14	T	100	92	M	407
	giul-39	30 6.0 40 1.0	1,73E2 1,9E2	3.2 6.9	2.3 6.9	T 469	100 94	18 16	T 3081	100 100	72 188	M 31	554 4372
		40 2.0	2,04E2	8.4	8.4	1480	97	18	T	100	181	119	3000
		40 3.0	2,15E2	10.4	8.6	T	100	11	T	100	67	M	3376
		40 4.0	2,22E2	12.6	8.1	T	100	6	T	100	31	M	2231
		40 5.0	2,27E2	21.7	7.2	T	100	2	T	100	13	M	2728
		40 6.0	2,3E2	12.6	5.3	T	100	5	T	100	5	M	3184
		50 1.0	2,21E2	8.0	8.0	900	96	16	5767	100	188	82	9680
		50 2.0	2,38E2	10.3	9.8	5982	99	20	T	100	139	221	7390
		50 3.0	2,49E2	13.6	9.8	T	100	8	T	100	63	M	7324
		50 4.0	2,57E2	18.6	9.8	T	100	3	T	100	13	M	6574
		50 5.0	2,63E2	23.8	9.1	T	100	2	T	100	7	M	5526
		50 6.0	2,68E2	-	7.9	T	100	1	T	100	1	M	5852


Tomas Ohlin
email: tomas@telo.se

Birth of Internet Ethics

Keywords: Ethics, Internet, moral, network, videotex, Minitel, Teleguide

Communication on the open networks during the first half of the 1980s was more factual than personal. However, the expanding use of electronic mail increased the personal and individual character of this type of communication. Personal and emotional content became more and more common. This increased content interest. Branch organizations formulated ethical principles, and it was created around the balance between market control and legal control.

At the time, legal regulation concerned the balance between public openness and personal integrity. Sweden was a country in the forefront. The number of concerns within the concept of content "control" increased.

This text discusses the occurrence of ethical control on the networks of the 1980s. Many of these were videotex networks that were not technically standardized, they could rather be considered as technologically defined market islands. However, a certain "ethical standardization "appeared, which was to become important later, when the Internet arrived.

Background

In this text, the concepts "ethics" and "codes of conduct" are used in similar conceptual environments.

Codes of conduct for creators of computerized systems had started to be discussed in the 1970s. The early often centralized data base oriented systems were often built with a concern primarily for top-down efficiency, and discussion of effects on and by users was not apparent and frequent. However, such user concern was asked for increasingly, and codes of conduct for system creators were believed to be able to help. This was early observed by Kerstin Anér, liberal Member of Swedish Parliament, who in her visionary book "Datamakt" [START_REF] Anér | Datamakt[END_REF] asks citizens to observe openness and moral for system creators. She discusses "ethical codes for computer system workers", referring to UK and US proposals from 1973 where such codes were suggested, much in line with ethical codes for legal experts and medical doctors. It was mentioned here that sanctions might be applied against misuse. She also explicitly refers to a Japanese report ("Plan for Information Society 1985") where it is noted that:

"The ethics of the future should not be of the modest type which only avoids to harm others, but should state that each individual strongly should contribute to societal wellbeing and development through intellectual creativity" ([2] pp 318, translated by this author).

Thereafter, ethics for system creators successively came to be observed in larger circles, although these circles in the beginning had small radius. It took time until Kerstin Anér´s thoughts reached out.

Through the arrival of computer conferencing, including electronic mail, the border between system creators and system users turned less and less sharp. ( [START_REF] Ohlin | Border effects in videotex networks[END_REF] pp 1) Consequently, ethical concerns for communication systems creators slowly came to be observed in larger circles.

The use of early public computer based networks in the late 1970s showed analysis and communication with only little "personal" communication but with much more factual and "measurable" content. As time passed, however, network content contained communication elements that became more and more personal and, often, emotional. This became evident as electronic mail started to be used in larger circles in the 1980s. Interest then smoothly shifted to ethical principles applied on and inside these new types of communication.

This development was foreseen by the pioneers of computer communication systems, professors Starr Roxanne Hiltz and Murray Turoff. In their "The Network Nation", first published already in 1978, they note:

"In public computer conferences, operators should state clearly what, if any, are the policies on censorship of the material. On material that is not subject to censorship, the operators should recognize individual rights of ownership to individual entries…. Items should not be copied to others by receivers without the permission of the owner or the awareness of the group" ([3] pp 506-507).

Observation of such interests, evident as they may look today, came slowly to be demanded on the early communication networks.

This evidently was way before the arrival of the Internet. However, the dawning ethical concerns and interests on early computer communication systems and on the videotex networks of the 1980s had an influence on later communication on the Internet.

As uses of services over time more and more began to contain items of personal nature, the concept "codes of conduct" became complemented by "ethical concern", and regulation increasingly observed information content.

The videotex networks of the 1980s were not technically unified and standardized. On the contrary, different countries used quite different types of technical communication standards (ref 4). As these standards met and at times collided at the national borders, for instance when the French Télétel standard met the German CEPT videotex standard, or met the English Prestel standard, market oriented "battles" arose (ref 1). But these battles built on technology. However, the applications learned from each other. The French advance invited several other countries to implement similar applications that increasingly concerned customers and private users.

However, the English Viewdata system (later called Prestel) was probably first in offering nationally public videotex network services. Already in 1980 the UK Post Office presented an astonishingly complete Code of Practice handbook, with detailed specifications concerning use of many types of services. It contained chapters including rules about Information and Advertising concerning Children, Consumer Credits, Financial, Sales, Medicine, Body, Alcohol, Tobacco, Slimming, Betting, Direct sale. This was, as can be seen, a for its time fairly complete catalogue.

In spite of this UK move, during several years of the 1980s, by quantity the (packet switched) French Télétel network with its Minitel terminals dominated European network concerns for videotex expansion. The French network combined centralized terminal definition and production with a business model with ingenious and highly decentralized (for organization and payment) market structure definition (Ref 1, p 169) Before being "defeated" by TCP/IP, this French communication standard was used by as many as 7 million Minitel users, which was a true success. Competing networks in other countries, and there were many, could at best only show cultures of hundreds of thousands of users. The influence from the French codes of conduct was therefore probably mostly restrained by language.

User Cultures

On all of the separate videotex networks (French, English, German, American, Nordic, Japanese ….) electronic mail successively became a central application. These systems were of public as well as private nature. Electronic market applications were tried in the 1980s, by banks, postal concerns, commercial branches, game providers etc, but the lack of standardized payment routines made wide spread market use difficult. This type of service needed time to mature. The Swedish TeleGuide system, which in the middle of the 1980s tried to copy the French Minitel success, introduced payment with smart cards (for which the need for codes of conduct was observed). But the methods to handle this, especially by service providers, were not mature. TeleGuide reached, as a maximum, approx. only 22 000 users (ref 5)..

During the beginning of the 1980s pornographic material started to appear on the French Télétel network (via the Minitel terminals). After some time, the phone number to the main and most low-cost French Minitel service database (kiosk), 3615, became looked upon as a "soft number" (where the user easily could find pornographic services). Such pornographic services via Minitel were advertised privately, and for some years in the 1980s, they generated quite a lot of profitable traffic. This development was criticized in the public debate. A representative of France Telecom in 1987 excused himself by saying: "…. but this "Messagerie rose" at the time only generates 5% of our télématique traffic income" (personal communication). One can note the word "only" here.

Similar types of mail-type usage was observed in other countries. In the EIES system in New Jersey, USA, certain material turned soft and personal, resembling "soap operas" with "light relations" (ref 3, p 204).

This type of systems behaviour also has been observed at the introduction of other types of technology. It can be remembered that video technology introduction generated a strong debate in the 1990s, for similar reasons. Effects of this type have later turned out to be strong in the beginning, but smoother as time passes.

Other types of as it seemed unethical services also started to appear on public networks during the first half of the 1980s. Increasing amounts of this raised many questions about responsibility and personal integrity.

Market Reactions

This development created a discussion among information providers about possible regulation. General public legislation was at the time mostly not fully applicable for this new type of communication medium. Therefore, regional branchwise regulation was discussed, and in certain environments created. As an example, US concern (for services based on the technological videotex NAPLPS standard) introduced development of certain ethical "standards" organized by the Office of Fair Trading already in 1980.

In Sweden, Informationsproducentföreningen (Information Providers´ Organization) that was created in autumn 1983, quite soon showed concern for codes of conduct and ethical principles on the Swedish networks of the time.

Some of these would touch legal structures, others would be more of practical nature. Application branches were inspired to create own types of regulation. Concepts that could be regulated were related to: As can be seen here, these types of regulation interests differ quite a lot. One way to sort these could be to differ between those that contain form and those who address content. Even if the border between form and content at the time not was sharp (and would become even less sharp as time passed), at the time it could be possible to separate between formal parts and parts that concern content. These were updated in 1989, where a new concern for "Moral" was added, specifically referring to pornography [START_REF] Ohlin | Etiska koder i videotex[END_REF]. Soon after this, in April 1990, it was decided in Sweden to especially observe the international situation concerning network ethics.

Sanctions

Crimes against existing law would naturally be treated according to the relevant laws. But how would this be done? What type of punishment -if any -would be relevant? In several countries, legal investigations appeared during the 1980s. For branch-wise created rules and codes of conduct, an uneasy feeling often appeared about threatening with sanctions. But how would these principles otherwise be enforced? And who would be concerned? Ought responsibility be shared or not, between the user and the service provider? When would sanctions be voluntary, and when mandatory?

The communications medium in itself introduced new forms. Blacklisting of service providers who did not behave according to accepted principles, was a form that could be used. Demand for payment of sharply directed form was another. Both of these could be handled online. Questions that were asked included: Who would be responsible for enforcement of the rules for conduct? Would a specific organization be created, nationally or internationally? How would this organization cooperate with existing Fair Trading organizations?

These possibilities concerning sanctions -when they were applied -were to be implemented in different forms in different countries at the late 1980s and the beginning of the 1990s. Increasingly, cooperation between countries was asked for here, and this was amplified with the appearance of the Internet.

International Contact

The legal concerns generally contained observation on personal integrity (where laws at the time in many countries were quite new), and intellectual property (where laws were established but hardly adapted to computer networks). Early ethical principles naturally pointed at the demand from society to have users observe and follow existing legal rules, evident as this may seem. But in electronic form, the application of existing legal principles was often not simple and evident (ref 7).. Numerous public legal committees came to be engaged in the adaption of existing legal rules to new environments.

In the US, discussions about form and content regulation increased during the later parts of the 1980s. The North American Videotex Industry Association later formulated a proposal for a "Videotex Code of Rights and Conduct for North America" at a conference in June 1990 [START_REF] Ohlin | Videotex ethics and codes of conduct in an IVIA perspective[END_REF].This was to contain observations concerning:

-Privacy -Copyright -Exclusion -Users -Enforcement -Rating system These proposals were to be applied on industrial applications concerning entertainment, health, media, personal and professional services.

In the International Videotex Industry Association, representatives of 14 countries in April 1990 declared their wish to support compatibility between national videotex systems. This would include common ethical concerns. Soon thereafter, and under the chairmanship of this author, IVIA specifically initiated collection of national codes of conduct, with the aim to translate them and look for common interests.

Conclusion

Seen in perspective, this ethical regulation analysis was fairly early in time. Often concern for ethics and systems moral appears in a fairly late phase of development of technology. However, the type of ethical concern that has been discussed above in this case inspired the direct creation of the more general ethical principles, once the main technical standard on the market was coordinated to TCP/IP. Then a common "language" turned out to be fairly easily in reach, and the Internet expansion could be given a flying start. It is possible to note that, in this perspective, regulation focus then changed from form to content, although the border between these over time became less sharp.

At the international IVIA meeting in 1991, a number of ethical interests of common concern were made more precise. It was mentioned that focus in the near future would include concern for children online, sharper classification of services, concern for whistle blowers, and steps towards network ethics for all citizens.

This came to form an important ground for the increased ethical influence concerning services on the Internet, a network that at the time was expanding very fast.


Lone Dybkjaer
email: lone@lonedybkjaer.dk

Reasons behind the Privatization of Datacentralen

In 1959 Datacentralen was created by the State and local governments to provide IT services to the government and to regional authorities. Similar centralized IT service centers were created in other parts of society, where Danish Agriculture created LEC, Landbrugets Edb-Central. The municipal governments created one big IT center, Kommunedata, by merging many small local IT centers. For several years Datacentralen was the only supplier of IT to central government and administration. But through the 1980s the development of minicomputers and powerful PCs led to new kinds of decentralized IT systems and IT services. Economic conditions also forced the government to reconsider the role of Datacentralen and of the whole use of IT in Denmark. Gradually this led to the privatization of Datacentralen and other IT services. Quite similar developments took place in other Nordic countries.

The Computer Environment in the 1950s

2.1

The Background for creating Datacentralen

The use of computers in Denmark started in the late 1950s with Regnecentralen (RC), who built DASK, the first Danish computer, and started research and service center activity. In 1959 Datacentralen I/S was created by the State and local governments (municipalities) with the purpose of providing IT services to the government and to regional authorities. In the early 1960s several similar IT service centers were created in other parts of society, where, e.g., Danish Agriculture created LEC, Landbrugets Edb-Central, and the municipal governments created one big IT center, Kommunedata, by merging many small local IT centers.

In other words there was a good environment for the use of computers in Denmark in that period. And furthermore we had a Danish company RC which developed and built computers that were quite outstanding, and RC had a milieu with a solid knowledge about computer technology and applications. The Ministry of Finances wanted a technical report on the future use of computers in the public sector. So I agree with Anders Vind Ebbesen [1] who writes that it is noteworthy that the task of writing this report fell on the desk of an IBM consultant, who furthermore was paid by IBM. The report considers 'commercial EDP' as requiring another type of computers than 'scientific EDP'.

My personal opinion at that time was -and still is -that RC wasn´t given a fair chance, and that we missed some opportunities by not using the experience gathered at RC. May be I am biased, knowing some of the excellent people working at that time on Regnecentralen, and biased by my connection to ATV1 , whose report led to the start of Regnecentralen.

But knowing that period -and with my later knowledge and experience with the public sector -I believe there is a need for a study of the public administration and its relation to the environment outside the administration. It is not less important to day than earlier.

Establishment of D/C I/S in 1959

Anyhow, the result of the report was the establishment of Datacentralen I/S in 1959 with the author as director and IBM equipment -which also was -as explained by Per Gjerløv -introduced by a gift from IBM to The Tecnical University later on.

Whether it was with equipment from IBM or another supplier, establishing a computer center with the purpose of handling the various task from different public sectors was a wise decision, and is part of the danish succes in relation to effectiveness in public service.

3

The first 30 Years

During the first 30 years, approx. 1959-91, Datacentralen (DC) was jointly owned by the State and the local governments and grew rapidly into a big service center running applications for many branches of public administration. A few milestones in this development are mentioned.

In 1962 the first computers were delivered to DC and the first task done for the Ministry of Transportation.

In 1965 DC had 34 employees.

In 1967 the government decided to introduce the value added tax system (VAT)which means handling an amount of data not seen before. DC got the task to create an IT system capable of doing that. Fortunately DC and the custom authorities already had started working together on building such a system.

Anders Ebbesen [1] has described the situation up to 1970 with the establishment of CPR and pay-as-you-earn tax reform (a reliable CPR is a prerequisite for the tax reform). It is interesting that there was -as far as I remember -no substantial public debate about the registration of every citizen by a number. I don´t think it could have been introduced today without a major debate.

The big issue was the tax reform, which was -among other things -advocated with the advantage of getting a taxfree year. This was a truth with modifications but it was 'sold' well without the use of spindoctors.

This are just a few examples on how close the cooperation between various parts of the public administration and DC was.

A result of the development was that the number of employees at DC grew with the culminating 1400 employees in 1984, and DC was responsible for very many public service systems. DC had a de facto monopoly on these services, and with strong trade unions the employees had the power to bring the society to a stand-still. And that was used at some occasions.

4

Change in Ownership

The first Change in 1991

In 1991 it was decided to change Datacentralen I/S (owned by partners) to Datacentralen A/S (a limited company) and at the same time a decision was made to sell 25 % of the capital. That type af political decisions is normally done through a bill/document from the minister in charge to the Committe of Finance (CF) and de-cided/voted upon there. In this case the responsible ministry was the Ministry of Finance.

The overall reason for this was the changing circumstances on the electronic data market. To this was added -The wish to reduce the exceptional position of DC and create competition in the field of IT systems for public administration -EEC demands on liberalisation of the state purchases -A wish to given DC a more business oriented profile -To get rid of the municipalities, which did not use DC and had created there own center, Kommunedata -The wish from DC to expand its export activities What was not mentioned in the bill was the deficit in the State budget. But by selling a part of the capital you could take money out of the company. Other impulses were to limit the power of strong trade unions and to follow a generel tendency to privatize public administration.

The bill was passed with a marginal majority behind -but for people interested in politics it is worth noting that the Social Democratic Party voted against it because 170 mio. DKr. were taken out of the company to cover part of the financial deficit. Less than two years later the party was in government with another point of view!! I was appointed chair of the board by the Minister of Finance.

It turned out to be impossible to sell 25 % of the shares. No company wanted to buy without getting real influence on DC. The board of DC A/S therefore had to look for other solutions and succeeded in doing so.

Creation of DCM in 1993

The solution we found was to separate the operational activities from DC and create a new company 50-50 owned company together with Maersk Data. Several good business arguments were behind that. The construction was quite genious -which I can say as it was not my idea -because it solved the task laid on the board, namely to sell 25% of the shares. Besides, the separation of operational activities from the rest of DC had several business advantages.

The creation of the new company DCM required a new bill to be accepted in CF. It was sent confidentially to CF and approved in December 1992. It may be interesting to note that in the same month a broad political agreement was made on privatizing other state owned companies.

4.3

From 25% to 75% sold in 1996

The creation of DCM solved "the 25% problem" but it was obvious that the solution did not solve the deeper problems of DC. A strategic partner was a necessity for the survival of DC unless the state wanted to be an active partner in the company. We have no tradition for companies run by the State in Denmark. This was outlined in a report 1993 written by me with strong help from others.

The work to find a new strong strategic partner started in 1995. It ended with a very close race between CSC2 and IBM after months of intensive work negotiating and comparing. Due to the strong cooporation with IBM in DCM there was interest in a IBM take-over for two reasons:

-we knew IBM which was operating in Denmark while CSC was new to us -with IBM, Maersk and DC we would create a big strong IT company in Denmark.

There are two stories to be told about the final result. One is the official one stated in the bill to CF. The biddings from IBM and CSC were very equal in many respects, and the evaluation led to CSC as being the best future partner for DC. The other inofficial story is that the remark about pollution on the DC ground was decisive. It said that if the buildings one day should be expanded, the pollution should be fully removed if IBM should join. This was not possible due to Danish law.

The result was that CSC was chosen as the partner -as we all know today. In the bill -which was confidential until 1999 -is stated that Ministry of Research and Ministry of Finances weighted that:

1. DC should be strengthened 2. The competion on the market should grow 3. The price should be attractive for the State The bill also explained how CSC should perform in Denmark after the buy. Lastbut not least -it states various conditions about eventual expansion of the capital, possibility for the State to sell -and for CSC to buy -the rest of the shares, etc.

Final Sale to CSC in 1999

In 1999 CSC requested to buy the rest of the shares, which was accepted by the government.

Worth noting is a quite comprehensive paper from the Danish data protection agency, dealing with the security situation in relation to authority registers of various art. It is concluded that the ruling for private companies is the same as for the State, municipalities etc. This question was also raised with the first privatization of DC with the same conclusion, but as far as I remenber no report was issued.

But having experienced several leaks of civil registration numbers -the last one in the summer of 2014 -we can conclude that we have a general safety problem that also comprises the data kept by the State and municipalities. Remember, e.g., the case in 2013, wherethe police admitted that the driving license register was hacked.

In the bill about selling the last shares in DC is also mentioned a compensation for the pollution of the ground -mentioned earlier -and three law-suit´s still unsolved. The most important of these is about a system to Thailand. The negotiation on this sale was started before the establishment of A/S in 1991 and the final contract was signed just arond the time the A/S was established.

I am mentioning in particular the Thailand case because it started as a very good system export case -supply of software -and ended in a disaster. It cost the company a lot of money, took up lots of working hours -including in the board -and ended with compensation to Thailand payed by CSC and the State. The software was ok but nobody had checked the tax system behind, which was non-existing. It underlines that system export is not always an easy go.

Conclusion on the Privatization

The privatization of Datacentralen was done by a step by step method. From the beginning we did not know the final result. My conclusion is:

• The state got money out of the privatization.

• All in all it was a good idea and succesful for the State • It is more difficult to judge whether it was succesful for CSC. That I will leave to others to conclude upon.

The women in Denmark got their voting rights in 1915 in the new constitution. In the first election thereafter, in 1918, four women were elected (but the small number was a disappointment). One of them belonged to my political party The Social-Liberal Party. She can be considered as my pre-pre-predecessor.In her second speech in parliament in 1918 -on the law of finance -she asked the minister if he would consider passing a law, which made it possible for those municipalities -who so wished -to establish a population register. She mentioned many reasons for that, but no doubt one of them was closer to her heart than others, namely the possibility to get hold of the alimentants, the men/fathers who should pay to their children born out of wedlock, the so-called illegitimate children, but who ran away from their payment. A register system could be helpful in solving that problem.Such a population register system was very effective in Germany, she said, so effective, that it was easier to find a fleeing Danish father in Germany than in Denmark. In 1924 Denmark got the first law on establishing a population register, and that was the beginning of the later CPR.Do not say the election of women makes no difference to man or mankind!

ATV is the Danish Academy of Technical Sciences.

CSC (Computer Sciences Corporation) is a big US-based company selling IT services and solutions world-wide.


lecturer, MA Søren Duus Østergaard
email: soren@duus.com

The Danish Tax System and the 'No Touch Strategy'

In 2004 the Danish Tax Administration won the Danish e-Business price for the successful implementation of the 'No Touch' IT solution TASTSELV, which provides the Danish Tax payers with a unique, fast and accurate solution handling for pre-assessment of income and tax declarations. This paper describes the milestones towards this result that is based on several decades of development of the basic IT support for the IT solution that developed into a World Class taxation system.

1

The Early Days -Birth of Datacentralen

In the late 1950s the social democratic Government had a strong focus on creating a true welfare state. One of the major challenges was the increasing pressure on the costs from the large number of children from the 'Baby Boom' of the late 40s and the combined fact that the influx of women on the labour market also led to an increased need for public childcare as well as health care costs. Because of the increased need for public financing, the efficiency and accuracy of the taxation system had to be improved.

The major political and administrative challenge was to create a fair taxation system, which at the same time should be capable of handling even a moderate inflation, which called for a better alignment between wages paid and tax collected. The taxation system at the time was based on a personal self-declaration based on last year's income with deduction schemes for interest rates and other costs. In 1956 one of the most important welfare legislations was passed dealing with General Pensions for everybody from the age of 69 with a guaranteed minimum payment independent of the personal income. The legislation came into effect in 1957, adding to the pressure on how to finance the welfare state.

The administrative experiences with 'EDP' at that time were based on large-scale Punch Card solutions for salaries, statistics and financial systems. Up to this point, these applications had been successful, but due to the foreseen complexity of the new Taxation system, it was obvious that a modernisation had to include the use of newer technology.

In 1958 Viggo Kampmann, the Minister of Finance, sent a confidential letter to IBM Denmark and invited a consultant to assist the Ministry in analyzing and defining necessary foundations, pre-conditions and barriers for introducing a 'pay-asyou-earn-taxation system -PAYE. The letter to IBM stated that the information had to be treated confidentially, as the Parliament at that time had not been informed yet. IBM Denmark appointed the Government Lead Sales Specialist, Willy Olsen, as a member of the investigating team and as a lead consultant for the 'secret committee'.

The committee stated, that in order for an effective 'Pay as You Earn' system to work it would be necessary to have a unique identification of each taxpayer, a unique identification of each employer, a compulsory notification of salaries -and because of the need to collect taxes as part of the salary, also a close cooperation with the Financial sector was necessary.

One of the main recommendations from the Committee was to ensure a close cooperation between state Government and municipalities -partly because the Tax assessment was a municipal task, the quality of which the central Government wanted to improve, and partly because of the major costs involved in launching a 'real' EDPsolution.

This led to the creation of I/S Datacentralen on December 17, 1959 as a joint Central/Local government venture with the task to acquire 'computers' and develop and operate the new tax system and related supporting systems. The first managing director of I/S Datacentralen became Mr. Willy Olsen. The Board of Datacentralen was left with the difficult task also to coordinate and approve use of 'computers' acquired by the local Government organisations. Regional Punched Card centres were at that time already established around the country and soon developed into regional EDP-centres.

Supporting Systems and Launch of the PAYE

As it was a clear prerequisite for an effective IT solution that each tax payer could be easily and uniquely identified, the first important step was the launch of the Central Personal Registration System, CPR. Parliament approved the act of CPR in June 1968, but in fact the work had already started in 1965 under 'The Secretariat for Personal Registration' based on the recommendations from 1963, 'Betaenkning om Personregistrering'. As a prerequisite the municipalities were forced to convert information contained in traditional index files to punched cards before September 1967. In October 1968 Personal Identification documents were distributed to all Danish citizens. The key information was the citizen's identification number, based on birthday, a serial number where an odd end number signified a male citizen and an even end number a female. A modulus 11 check ensured a way to assist automatic control of validity of the CPR number. But another prerequisite for a PAYE tax system was of course the identification of the employers, as it would be based on their accounting systems to withhold tax based on the current income.

Already in 1964 this hurdle was at least partly overcome, when the Law of income related additional pension, ATP, was passed. The purpose was to decrease the burden of the public sector to pay out pensions to everybody, and the ATP system ensured that employees would co-finance their own pension. The employers had to withhold a fixed amount of the salary paid to each employee. Because of this, a register of Companies and Employers was established (CIR -Det centrale Indeholdelsesregister). This later (in 1999) developed to CVR, the Central Company Register containing detailed descriptions of companies, owners, directors etc.

The PAYE system was launched -not in 1969 as originally planned, but in 1970.

This coincided with the start of the first major administrative reform, where the number of municipalities was reduced from 1300 to 277. As it was still the responsibility of the municipalities to assess declarations for citizens covering other items than direct salary, the IT architecture had to be re-designed concurrently with the mergers, so in effect the PAYE tax system was split between local authorities and the Central Tax authorities. Datacentralen established a PAYE department in Birkerød, where the tax department of the Ministry of Finance was also placed.

In parallel with the municipality reform the regional and local Government EDPcentres were merged into one organization named KOMMUNEDATA (later KMD). The city of Copenhagen and the City of Aarhus kept their regional DP centres. In spite of the original guiding principles from Datacentralen, stating that all major EDP investments in local Government had to be approved by Datacentralen, the increase in local government administrative tasks made this expansion necessary. One of the major new municipal tasks was the new law on social security/illness insurance for everybody, and this became Kommunedata's largest project so far.

Improvement of the PAYE -Attempts to centralize Control

In 1972 a report was published from the committee responsible for analyzing the PAYE system and suggesting improvements. (betaenkning 638, April 1972). One of the key persons in this commission was Hans Westerberg, who later became director of the PAYE system. The report contained a number of recommendations on how to improve efficiency and how to create a system that as far as possible made additional payments unnecessary and at the same time eased the burden of control. Hans Westerberg and his IT manager started a long period of step-by-step improvements and automatic collection of data from a large number of sources, most important from other government registers and banks. His work was the real foundation for the development of the 'no touch' tax idea.

In the late 1970s the discussions between the central taxation authorities and the municipalities accelerated. Kommunedata had launched a terminal based intranet system for the municipalities (SIP -Skatter, Indkomst, Person oplysninger) for combined access to tax, income and citizen data based on the decentralized registers operated by the regional centres, while Datacentralen supported a centralized system to ensure up-to-date information and avoid duplication. A new committee on coregulation of the area was set to work, and as the central government representatives had a majority, the recommendations were to back the Datacentralen approach. However, this did not convince the local government organisations, that regarded the recommendation as a threat for local authonomy.

The central government representatives wanted a completely centralized solution where all development, operations and location of the tax/income registers were placed at Datacentralen. The local government representatives wanted a decentralized solution where information from the central income/tax databases could be combined and compared with accounting information residing at the municipalities' files. The conflict between Datacentralen and Kommunedata was in reality a conflict between centralization and decentralization. (EDB Samordningsudvalget -om styrelsen af statslige og faelleskommunale registersystemer maj 1977 and Mogens Brabrand Jensen, 1984).

In 1981 the Central Government/Ministry of Finance agreed with The Association of Municipalities and the city of Copenhagen to establish a committee with the purpose of defining common guidelines (Read: 'Enterprise Architecture Standards') for the IT decisions made by Kommunedata, Datacentralen, and the city of Copenhagen. An attempt to create a common organization failed, and a number of tax related tasks still remained at municipal level.

In 1983 the central Government expenditure for IT was estimated to 760 Mio Dkr. of which the Tax system accounted for a total of 161 Mio kr. We have the figures for the municipalities' and counties' use of IT in 1985, totalling some 673 mio Dkr., of which personal taxation system accounted for 11% or 93,6 mio Dkr. The number of applications in local regional Government was much higher than for central Government, explaining the interest from the local govt. politicians to maintain the power over their regional IT centres and the application development.

So for many years the conflict between local and central tax authorities continued, while the Tax department at the ministry of Finance, later Ministry of Tax kept improving automatic updating of income-relevant information and gradually reduced the need for local information and databases concerning income, tax and tax related debt. All these step-by-step solutions cleverly administered by the Central Tax Authorities helped create the foundation for the 'no touch' tax system and avoided to repeat the conflict between the political owners of Datacentralen and Kommunedata.

Dawn of the Internet -the 'No Touch' Strategy

In 1993 the reorganized department, the Central Customs & Tax Authority (CCTA) launched the first voice response system offering citizens the ability to check and change their pre-assessment of tax using the telephone. Security was provided via a pin code printed on the pre-assessment form. Until now CCTA received all reports from citizens on paper, and payments -incoming as well as outgoing -were made using the Giro System. The citizens had no direct access to their own data when they wanted to check these or to send in a report. They had to wait for the annual settlement before they could see the basis for the taxation. As this obviously also represented a heavy administrative burden on the CCTA, the digital self-service strategy was launched 1995, and the mission statement was to ensure public revenue in a simple, efficient and correct way. The principles behind this effort were to ensure 1) a simple and automated process and only disturb customers (!!) when unavoidable, 2) efficient, best and low priced service within the financial framework offered to CCTA, 3) governed by the rule of the law to ensure customers are treated promptly, correctly and uniformly and protected according to the law. Further, 4) individualized service, reflecting that customers have different abilities, and 5) service oriented in the sense that CCTA wanted to meet the customers according to their needs -personally, by phone or by 24 hours digital selfadministration.

The gradual development of the 'No Touch' TASTSELV system was based on the voice response option as well as the browser option via the Internet (since 1995). The browser option became the foundation for a long range of subsequent services, initially focusing on submitting tax returns and changes of pre-tax assessment based on access to an individual, digital tax folder. The back end of the system was not visible for the citizen, which provided the somewhat complicated technical split of processing between KMD (which changed it's name from Kommunedata) and DC (Datacentralen also changed it's name).

This was made operational by introducing a component-based architecture that defined the interfaces and data standards ensuring interoperability between the back end systems.

Encryption was introduced from the outset (for the browser option) based on a 128 bit SSL via proxy server. This was at the time considered a high level of security.

This solution soon proved to be a huge success: already in 1996 more than 600.000 tax payers took benefit of the TastSelv solution. In 2004 the CCTA solution won the e-Government Prize for the best public solution of the year. Some of the reasons for this award (2004) stated:

The total census of the year was 4.635.012 taxable persons, of whom 4.585.331 are natural/real? persons. Of those an amazing 4.007.796 received a pre-filled tax form, corresponding to about 86%. Of these, 2.5 million of the forwarded, pre-filled tax forms were accompanied by an annual settlement. These citizens do not have to do anything regarding their tax return. Some 430.000 persons made corrections to their pre-filled tax return.

In 2008 Tax (Danish SKAT as it is now called instead of CCTA) made a customer satisfaction survey to check their image in the Danish population. The overall response showed that 4 out of 5 Danes consider the Danish Tax system to be fair and just, while 1 out of 6 believe the opposite.

60% of the Danes agree that the tax system is working well/efficiently, 25% neither/nor.

Conclusion

The tax system for individual citizens has become gradually more and more automated to ensure the original intention behind the 'No Touch' strategy, originally defined by Hans Westerberg and Somani, but also for private companies. A lot of tax related information is automatically collected. The success of the 'No Touch' strategy seen from the citizens' point of view can hardly be debated, and it is interesting to combine the general acceptance of the tax system being fair and just with the list of income related information, which today is being handled directly between the tax authority, the employers, financial institutions and pension companies. This list of automatically collected data will in some countries lead to a strong protest, but obviously not in Denmark.

The following data (and more) are automatically transferred to the citizens individual digital tax folders: Declared taxes, paid taxes, mileage allowance, deductions, contributions, trade union and unemployment fund fees, VAT, controlling shareholder info, interest received and paid, bank deposits, reported info on assets, shares and funds, interest on financial assets abroad, portfolio of shares, unit trusts, financial contracts, interest paid and outstanding debts, equity, self pensioning schemes, occupational pension schemes, taxable benefits, tax deductible benefits, property value and taxation, tax exempted benefits, car ownership info, salaries, pensions, travel allowance, student grants and loans ...

In 2004, the year the Tax system won the e-Government award, the second major structural reform of Denmark took place, reducing the number of municipalities from 277 to 98 and reducing the number of counties from 14 to 5 regions. At the same time, the municipal tax departments were moved to regional centres directly controlled by the Ministry of Taxation. Since then, the payment system including collection of debts and any return payment to citizens has also been centralized, still leaving some administrative tasks (like property taxation) with the municipalities, but centralizing all tax-related IT development and operations.

Fig. 1 .

 1 Fig. 1. Do you consider the Danish Tax System to be fair and just? Light blue: Fair and Just Blue: Not Fair and Just Dark Blue: Don't know

Fig. 2 .

 2 Fig. 2. Do you agree that the Declaration is easy to manage? Dark Green: Yes, agree Brown: Neither agree nor disagree Light Green: disagree Light Blue: Don't know